回文数

[takeru]

32ビット整数で処理し、100~199までの値で回文数にならない値とその結果を表示しなさい。という問題があるのですが、ちょっと行き詰まってしまって…教えていただけませんか？

コード:

#include<stdio.h>
int shori(int n)
{
	int m=0;
	if (n>0){
	    while(n>0){
		m=m*10+n%10;
		n/=10;
	    }
	}
	return(m);
}
int main(void)
{
	int n,m,k,i;
	for(n=100;n<=199;n++){
		k=0;
		printf("%d\n",n);
		m=shori(n);
		while(n!=m){
			n=n+m;
			k++;
			printf("%d\n",n);
			if(k==50)break;
			m=shori(n);
		}
		if(n==m){
			printf("\n");
		}
		else{
			printf("不一致%d\n",n);
		}
	}
	return(0);
}

上の関数は数値を反転するプログラムで下の関数は実際に反転する前の数値と反転した数値を足すという作業を回文数になるまで繰り返すというプログラムになっているのですが、
回文数にならないという定義が決められている問題ではないので何をもって回文数にならない数値と判断していいかわからないのですが、とりあえず次のような説をもとにプログラムを作りました。

「まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.
更に, 10000未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.
1.50回未満の操作で回文数になる
2.まだ誰も回文数まで到達していない」

結果の表示の仕方的には、
例
196
887
1675
7436
13783
52514
94039
187088
1067869
10755470
18211171
35322452
60744805
111589511
227574622
454050344
897100798
1794102596
156182975
735464626
1361929163
686253498
1580606184
2101699739
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
-1403241137
不一致　196

というかんじにしたいのですがどなたかご教授ください。

[non]

カウンタで使っている変数nをそのループの中で変更してはいけません。
別の変数を用意しましょう。

[box]

まずは、「回文数」の定義を示すのが筋ではないか、と思います。

[takeru]

nonさん：どこのことかよく分からないんですが…？

boxさん：回文数事態まだ未解決のことですので決まった定義はないのですが上にも記したように50回やって回文数にならなければ海運数にならないと判断するようにしてます。　ただintでやってしまうと21億程度までしかいかないので50回やる前に範囲を超えてしまっているので何とも言えません。

[box]

nonさん：どこのことかよく分からないんですが…？

おそらく21行目のことだと思います。ところで、

32ビット整数で処理し、100~199までの値で回文数にならない値とその結果を表示しなさい。

決まった定義がない（らしい）回文数という概念を前提として、
100～199までの値が、その決まった定義がない（らしい）回文数になるかどうかを
どうやって判定するのでしょうか。

質問者さんのコードでは、何を根拠にして判定しているのでしょうか。
まあ、コードをきちんと読めば私でもわかるとは思いますが、質問者さんのことばで説明してほしいです。

[takeru]

21行目はべつに問題ないと思うんですが？！

ですから元の数に反転した数を足すという行為を50回やっても回文数にならなければその元の数値は回文数にならないと判断するプログラムなんです。k=0からはじまって足すという行為を1回やるごとに１ずつ足していってそれまでの間に回文数にならなければループを抜けるようにしてます。

[non]

nonさん：どこのことかよく分からないんですが…？

おそらく21行目のことだと思います。

その通り、
１６行のnを２１行で変えてはいけません。

[box]

ですから元の数に反転した数を足すという行為を50回やっても回文数にならなければその元の数値は回文数にならないと判断するプログラムなんです。

回文数そのものの定義を行なわずに、回文数という用語を使われているので、
まわりの人（私だけかも）にはよく理解できないのです。

質問者さんが理解されている（はずの）回文数の定義について、
日本語で説明してほしいなぁ、と思います。
ちょうど、国語辞典で回文数を引いたときに何と書いてあるか、のように。

[beatle]

21行目はべつに問題ないと思うんですが？！

本当に問題ありませんか？
16行目のfor文では，ループカウンタに変数nが使われていますね．nの初期値は100です．
for文はnが199以下の間，繰り返すようになっています．

21行目では，nにmを足しています．mは正の整数になるはずですから，nは必ず増えていきますね．
nにmを足すという処理は20行目のwhile文によって沢山繰り返されますから，多分nはとても大きな数になるでしょう．
そうすると，次に16行目のfor文に到達したときには，既にnは199を超えています．

ということで，21行目でnを変化させているせいで，16行目のfor文は1回しか実行されないことになります．
これはあなたの望んだ処理でしょうか？

[box]

21行目の件で、非常にザックリした言い方をすると、
nに何か正の数を足し込むことで、例えば101とか102とかが回文数であるかどうかの
チェックをすっ飛ばしてはいませんか？ということです。

これは、100～199のすべてについて回文数であるかどうかを求めたい、という
質問者さんの希望とマッチしているのでしょうか。

[takeru]

コード:

#include<stdio.h>
int shori(int i)
{
	int m=0;
	if (i>0){
	    while(i>0){
		m=m*10+i%10;
		i/=10;
	    }
	}
	return(m);
}
int main(void)
{
	int n,m,k,i;
	for(n=100;n<=199;n++){
		i=n;
		k=0;
		printf("%d\n",n);
		m=shori(i);
		while(i!=m){
			i=i+m;
			k++;
			if(k==50)break;
			m=shori(i);
		}
		if(i==m){
			printf("\n");
		}
		else{
			printf("不一致%d\n",i);
		}
	}
	return(0);
}

以上のように直しました。
回文数の定義は以下の通りです。
任意の整数 n>0 は、b進数（ただし、b≧2）においてk+1桁の数字として以下の式で表すことができる。

（∀ai ＜ b かつ ak ≠ 0 ）

nが回文数になるのは、任意の i に対して ai=ak-i が成り立つときである。また、0は何進法においても回文数である。

別の方法としては、以下の方法によって再帰的に定義される。

1桁の数は回文数である。
2桁の数は、その数を構成する2つの数が同じ場合回文数である。
3桁以上の場合、最初と最後の数字が等しく、その2つの数字を取り去った数が回文数である場合回文数である。

[beatle]

回文数の定義は以下の通りです。
任意の整数 n>0 は、b進数（ただし、b≧2）においてk+1桁の数字として以下の式で表すことができる。

（∀ai ＜ b かつ ak ≠ 0 ）

nがまったく表されていないのですが．．．

[box]

Wikipediaでの記述どおりのようですが、そうだとすると、
100～199の範囲にある回文数は
101,111,121,131,141,151,161,171,181,191
の10個です。回文数にならないのはこれら以外です。
この結果が求まるコードを完成させたいと思っている、ということでいいでしょうか。
とすると、何かを50回繰り返す、という、もともとのコードにあった処理は全くいらないように思うのですが…。

[takeru]

50回の行為の間に回文数になるものを回文数にしたいのですが。
つまり177,187,196の3つ以外は回文数ということで処理したいです。

[non]

「まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

この文章からすると、求めるのは、Lychrel数ということなのでしょうね。回文数ではなくて。
その辺の、説明が不十分なんですよね。

[takeru]

説明不足ですいませんでした。

[かずま]

196 は、その反転数 691 を足すという処理で、887 になります。

1: 196 + 691 = 887
2: 887 + 788 = 1675
3: 1675 + 5761 = 7436
4: 7436 + 6347 = 13783
5: 13783 + 38731 = 52514
6: 52514 + 41525 = 94039
7: 94039 + 93049 = 187088
8: 187088 + 880781 = 1067869
9: 1067869 + 9687601 = 10755470
10: 10755470 + 7455701 = 18211171
11: 18211171 + 17111281 = 35322452
12: 35322452 + 25422353 = 60744805
13: 60744805 + 50844706 = 111589511
14: 111589511 + 115985111 = 227574622
15: 227574622 + 226475722 = 454050344
16: 454050344 + 443050454 = 897100798
17: 897100798 + 897001798 = 1794102596
18: 1794102596 + 6952014971 = 8746117567
19: 8746117567 + 7657116478 = 16403234045
20: 16403234045 + 54043230461 = 70446464506

17回の処理で 1794102596 になります。
ところが、32ビット符号付き整数は 2147483647 までの数しか表現できません。
18回目の処理でオーバフローを起こしてしまうのです。
32ビット符号無し整数でも 4294967295 までの数しか表現できないので
やはり、18回目の処理でオーバーフローします。
64ビット符号無し整数 (unsigned long long) を使っても
40回の処理でオーバーフローします。

[かずま]

50回の行為の間に回文数になるものを回文数にしたいのですが。
つまり177,187,196の3つ以外は回文数ということで処理したいです。

32ビット整数で表せる範囲は超えていますが、 177 は 15回の処理で、187 は 23回で回文数になります。

コード:

177
   1: 177 + 771 = 948
   2: 948 + 849 = 1797
   3: 1797 + 7971 = 9768
   4: 9768 + 8679 = 18447
   5: 18447 + 74481 = 92928
   6: 92928 + 82929 = 175857
   7: 175857 + 758571 = 934428
   8: 934428 + 824439 = 1758867
   9: 1758867 + 7688571 = 9447438
   10: 9447438 + 8347449 = 17794887
   11: 17794887 + 78849771 = 96644658
   12: 96644658 + 85644669 = 182289327
   13: 182289327 + 723982281 = 906271608
   14: 906271608 + 806172609 = 1712444217
   15: 1712444217 + 7124442171 = 8836886388

187
   1: 187 + 781 = 968
   2: 968 + 869 = 1837
   3: 1837 + 7381 = 9218
   4: 9218 + 8129 = 17347
   5: 17347 + 74371 = 91718
   6: 91718 + 81719 = 173437
   7: 173437 + 734371 = 907808
   8: 907808 + 808709 = 1716517
   9: 1716517 + 7156171 = 8872688
   10: 8872688 + 8862788 = 17735476
   11: 17735476 + 67453771 = 85189247
   12: 85189247 + 74298158 = 159487405
   13: 159487405 + 504784951 = 664272356
   14: 664272356 + 653272466 = 1317544822
   15: 1317544822 + 2284457131 = 3602001953
   16: 3602001953 + 3591002063 = 7193004016
   17: 7193004016 + 6104003917 = 13297007933
   18: 13297007933 + 33970079231 = 47267087164
   19: 47267087164 + 46178076274 = 93445163438
   20: 93445163438 + 83436154439 = 176881317877
   21: 176881317877 + 778713188671 = 955594506548
   22: 955594506548 + 845605495559 = 1801200002107
   23: 1801200002107 + 7012000021081 = 8813200023188

これは次のプログラムの実行結果の一部です。
このプログラムは、32ビット整数で処理していないので、課題の解答ではありません。

コード:

#include <stdio.h>
 
#define SIZE  30

void reverse(const char *x, char *y)
{
    int i, j;
    for (i = SIZE; --i > 0 && x[i] == 0; ) y[i] = 0;
    for (j = 0; i >= 0; i--, j++) y[j] = x[i];
}

void add(const char *x, const char *y, char *z)
{
    int i, carry = 0;;
    for (i = 0; i < SIZE; i++) {
        z[i] = x[i] + y[i] + carry;
        carry = (z[i] >= 10);
        if (carry) z[i] -= 10;
    }
}

void print(const char *x)
{
    int i = SIZE;
    while (--i > 0 && x[i] == 0) ;
    while (i >= 0) putchar(x[i--] + '0');
}

void set(int n, char *x)
{
    int i;
    for (i = 0; i < SIZE; i++) x[i] = n % 10, n /= 10;
}

void test(int n) 
{
    char x[SIZE], y[SIZE], z[SIZE];
    int k;
    printf("%d\n", n);
    set(n, x);
    for (k = 0; k < 50; k++) {
        reverse(x, y);
        if (memcmp(x, y, SIZE) == 0) {
            return;
        }
        add(x, y, z);
        printf("   %d: ", k + 1), print(x), printf(" + ");
        print(y), printf(" = "), print(z), printf("\n");
        memcpy(x, z, SIZE);
    }
    printf(" %d -- Lychrel number?\n", n);
}

int main(void)
{
    int i;
    for (i = 175; i <= 199; i++) test(i);
    return 0;
}

[みけCAT]

32ビット整数縛りということは、32ビット整数を使った多倍長計算を行うべきですね。おそらく。