ページ 1 / 1
回文数
Posted: 2012年1月15日(日) 17:49
by 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
というかんじにしたいのですがどなたかご教授ください。
Re: 回文数
Posted: 2012年1月15日(日) 18:16
by non
カウンタで使っている変数nをそのループの中で変更してはいけません。
別の変数を用意しましょう。
Re: 回文数
Posted: 2012年1月15日(日) 18:23
by box
まずは、「回文数」の定義を示すのが筋ではないか、と思います。
Re: 回文数
Posted: 2012年1月15日(日) 20:28
by takeru
nonさん:どこのことかよく分からないんですが…?
boxさん:回文数事態まだ未解決のことですので決まった定義はないのですが上にも記したように50回やって回文数にならなければ海運数にならないと判断するようにしてます。 ただintでやってしまうと21億程度までしかいかないので50回やる前に範囲を超えてしまっているので何とも言えません。
Re: 回文数
Posted: 2012年1月15日(日) 20:47
by box
takeru さんが書きました:nonさん:どこのことかよく分からないんですが…?
おそらく21行目のことだと思います。ところで、
takeru さんが書きました:32ビット整数で処理し、100~199までの値で回文数にならない値とその結果を表示しなさい。
決まった定義がない(らしい)回文数という概念を前提として、
100~199までの値が、その決まった定義がない(らしい)回文数になるかどうかを
どうやって判定するのでしょうか。
質問者さんのコードでは、何を根拠にして判定しているのでしょうか。
まあ、コードをきちんと読めば私でもわかるとは思いますが、質問者さんのことばで説明してほしいです。
Re: 回文数
Posted: 2012年1月15日(日) 20:57
by takeru
21行目はべつに問題ないと思うんですが?!
ですから元の数に反転した数を足すという行為を50回やっても回文数にならなければその元の数値は回文数にならないと判断するプログラムなんです。k=0からはじまって足すという行為を1回やるごとに1ずつ足していってそれまでの間に回文数にならなければループを抜けるようにしてます。
Re: 回文数
Posted: 2012年1月15日(日) 20:58
by non
box さんが書きました:takeru さんが書きました:nonさん:どこのことかよく分からないんですが…?
おそらく21行目のことだと思います。
その通り、
16行のnを21行で変えてはいけません。
Re: 回文数
Posted: 2012年1月15日(日) 21:07
by box
takeru さんが書きました:
ですから元の数に反転した数を足すという行為を50回やっても回文数にならなければその元の数値は回文数にならないと判断するプログラムなんです。
回文数そのものの定義を行なわずに、回文数という用語を使われているので、
まわりの人(私だけかも)にはよく理解できないのです。
質問者さんが理解されている(はずの)回文数の定義について、
日本語で説明してほしいなぁ、と思います。
ちょうど、国語辞典で回文数を引いたときに何と書いてあるか、のように。
Re: 回文数
Posted: 2012年1月15日(日) 21:09
by beatle
takeru さんが書きました: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回しか実行されないことになります.
これはあなたの望んだ処理でしょうか?
Re: 回文数
Posted: 2012年1月15日(日) 21:18
by box
21行目の件で、非常にザックリした言い方をすると、
nに何か正の数を足し込むことで、例えば101とか102とかが回文数であるかどうかの
チェックをすっ飛ばしてはいませんか?ということです。
これは、100~199のすべてについて回文数であるかどうかを求めたい、という
質問者さんの希望とマッチしているのでしょうか。
Re: 回文数
Posted: 2012年1月15日(日) 21:32
by 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つの数字を取り去った数が回文数である場合回文数である。
Re: 回文数
Posted: 2012年1月15日(日) 21:37
by beatle
takeru さんが書きました:
回文数の定義は以下の通りです。
任意の整数 n>0 は、b進数(ただし、b≧2)においてk+1桁の数字として以下の式で表すことができる。
(∀ai < b かつ ak ≠ 0 )
nがまったく表されていないのですが...
Re: 回文数
Posted: 2012年1月15日(日) 22:00
by box
Wikipediaでの記述どおりのようですが、そうだとすると、
100~199の範囲にある回文数は
101,111,121,131,141,151,161,171,181,191
の10個です。回文数にならないのはこれら以外です。
この結果が求まるコードを完成させたいと思っている、ということでいいでしょうか。
とすると、何かを50回繰り返す、という、もともとのコードにあった処理は全くいらないように思うのですが…。
Re: 回文数
Posted: 2012年1月15日(日) 22:14
by takeru
50回の行為の間に回文数になるものを回文数にしたいのですが。
つまり177,187,196の3つ以外は回文数ということで処理したいです。
Re: 回文数
Posted: 2012年1月15日(日) 22:54
by non
takeru さんが書きました:「まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.
この文章からすると、求めるのは、Lychrel数ということなのでしょうね。回文数ではなくて。
その辺の、説明が不十分なんですよね。
Re: 回文数
Posted: 2012年1月15日(日) 23:33
by takeru
説明不足ですいませんでした。
Re: 回文数
Posted: 2012年1月16日(月) 00:26
by かずま
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回の処理でオーバーフローします。
Re: 回文数
Posted: 2012年1月17日(火) 02:00
by かずま
takeru さんが書きました: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;
}
Re: 回文数
Posted: 2012年1月17日(火) 13:41
by みけCAT
32ビット整数縛りということは、32ビット整数を使った多倍長計算を行うべきですね。おそらく。