寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #Volume2-0259 All Numbers Lead to 6174

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