Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題「すべての数は6174に通ず」
0 から 9 の数字からなる四桁の数 N に対して以下の操作を行う。
1.N の桁それぞれの数値を大きい順に並べた結果得た数を L とする
2.N の桁それぞれの数値を小さい順に並べた結果得た数を S とする
3.差 L-S を新しい N とする(1回分の操作終了)
4.新しい N に対して 1. から繰り返す
このとき、全桁が同じ数字(0000, 1111など)である場合を除き、あらゆる四桁の数はいつかは 6174になることが知られている。
例えば N = 2012の場合
1回目 (N = 2012): L = 2210, S = 0122, L-S = 2088
2回目 (N = 2088): L = 8820, S = 0288, L-S = 8532
3回目 (N = 8532): L = 8532, S = 2358, L-S = 6174
となり、3 回の操作で 6174 に到達する。
0 から 9 の数字からなる四桁の数が与えられたとき、何回の操作で 6174 に到達するか計算するプログラムを作成して下さい。
・入力される値
入力は複数のデータセットからなる。
入力の終わりは 0000 が1つの行で示される。
各データセットは以下の形式で与えられる。
N
データセットは1行であり、N (1 ≤ N ≤ 9999) は四桁の数を示す。
N < 1000 の場合は上の桁は 0 で埋められている。
データセットの数は 10000 を超えない。
・期待する出力
各データセットごとに何回の操作で 6174 に到達したかを1行に出力する。
ただし全桁が同じ数字である数が入力として与えられた場合は NA と出力する。
僕が作成、提出したコードは、以下のとおりです。
/* Volume2-0259 All Numbers Lead to 6174 http://judge.u-aizu.ac.jp/ 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<stdio.h> #include<string.h> #include<stdlib.h> int compare1(const void *x,const void *y){ const char *c1=(const char *)x; const char *c2=(const char *)y; return *c2-*c1; } int compare2(const void *x,const void *y){ const char *c1=(const char *)x; const char *c2=(const char *)y; return *c1-*c2; } int main(void){ int i,n,m1,m2,a[4]; char c1[5],c2[5]; while(1){ go: scanf("%d",&n); a[0]=n%10; a[1]=(n/10)%10; a[2]=(n/100)%10; a[3]=(n/1000)%10; if(a[0]==a[1] && a[0]==a[2] && a[0]==a[3]){ if(a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0){ return 0; }else{ printf("NA\n"); goto go; } } for(i=1; ;i++){ sprintf(c1,"%d%d%d%d",a[0],a[1],a[2],a[3]); strcpy(c2,c1); qsort(c1,4,sizeof(char),compare1); qsort(c2,4,sizeof(char),compare2); m1=atoi(c1); m2=atoi(c2); if(m1-m2==n){ break; } n=m1-m2; a[0]=n%10; a[1]=(n/10)%10; a[2]=(n/100)%10; a[3]=(n/1000)%10; } printf("%d\n",i-1); } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
Volume2-0259 All Numbers Lead to 6174