午後のひとときに、久々にプログラミング問題を作ってみました。
問題
自然数Nの各桁の階乗の和がNと等しいNをすべて求めよ。
シンキングタ～イム
まずは、数学的な考察から。
各桁の階乗ということなので、1桁の階乗を求めてみる。
0!＝1
1!＝1
2!＝2
3!＝6
4!＝24
5!＝120
6!＝720
7!＝5040
8!＝40320
9!＝362880
これらをいくつか足したものがNということ。
すべて求めよということは、上限があるんだろうということです。
9!＝362880
ということから、9が3個あれば、Nは7桁となり、
その7桁がすべて9であっても、Nは7桁止まりということで、
Nの可能性として最大の桁数は7桁であることが解る。
というわけで、7重ネストとか考えた人。
さて、私のプログラムはどうなったでしょうか。
digitsfactorial.c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int f[10],c[10],b[10],k,l,m,n;
f[0] = 1;
for (m=1; m<10; m++) {
f[m] = f[m-1]*m;
}
for (n=1; n<8; n++)
for (c[9]=0; c[9]<=n; c[9]++)
for (c[8]=0; c[9]+c[8]<=n; c[8]++)
for (c[7]=0; c[9]+c[8]+c[7]<=n; c[7]++)
for (c[6]=0; c[9]+c[8]+c[7]+c[6]<=n; c[6]++)
for (c[5]=0; c[9]+c[8]+c[7]+c[6]+c[5]<=n; c[5]++)
for (c[4]=0; c[9]+c[8]+c[7]+c[6]+c[5]+c[4]<=n; c[4]++)
for (c[3]=0; c[9]+c[8]+c[7]+c[6]+c[5]+c[4]+c[3]<=n; c[3]++)
for (c[2]=0; c[9]+c[8]+c[7]+c[6]+c[5]+c[4]+c[3]+c[2]<=n; c[2]++)
for (c[1]=0; c[9]+c[8]+c[7]+c[6]+c[5]+c[4]+c[3]+c[2]+c[1]<=n; c[1]++) {
c[0] = n;
for (m=1; m<10; m++) {
c[0] -= c[m];
}
k = 0;
for (m=0; m<10; m++) {
k += f[m]*c[m];
b[m] = c[m];
}
l = k;
m = 0;
while ( k > 0 ) {
b[k%10]--;
k /= 10;
m++;
}
if ( m != n ) continue;
for (m=0; m<10; m++) {
if ( b[m] != 0 ) {
break;
}
}
if ( m == 10 ) {
printf("%d\n",l);
}
}
return EXIT_SUCCESS;
}
プログラミングの授業で、こんな解答をすると先生によっては怒られるやつですので、よいこのみんなはマネをしないように。
一応解説しておくと、
nはNの桁数。
f[m]は、m!の値。
c[m]は、m!の個数。
b[m]は、c[m]のバックアップ。
kは各桁の階乗の合計。
lはkのバックアップ。
結果10重ネストになりました。
外側から、n桁、9!の個数、8!の個数、7!の個数、…、1!の個数、として、0!の個数はこれらから算出。
kを求めて、ついでにcをbにバックアップする。
kが求まったら、lにバックアップする。
kの各桁を%10で抜き出して、b[k%10]をデクリメント。
kの桁数とnが等しくなかったら、コンティニュー。
b[m]が0で無いならば、ブレイク。
すべてのb[m]が0ならば、表示。
という流れですかね。
では、出力結果を見てみましょう。
> digitsfactorial
1
2
145
40585
解は4つしかありませんでした。
私の10年前のボロパソコンでも瞬殺でした。
さて、一応検算してみましょう。
1＝1!＝1
2＝2!＝2
145＝1!＋4!＋5!＝1＋24＋120＝145
40585＝4!＋0!＋5!＋8!＋5!＝24＋1＋120＋40320＋120＝40585
これを手計算で求めることも出来なくはないですが、かなりの場合分けが必要になることは予想されますので、やっぱりこういう計算はプログラミングで解くのが精神衛生上よろしいかと思います。
例えば、1から9999999までの1重ネストで探すようにコーディングしたとする。
digitsfactorial2.c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int f[10],k,l,m,n;
f[0] = 1;
for (m=1; m<10; m++) {
f[m] = f[m-1]*m;
}
for (l=1; l<10000000; l++) {
k = l;
n = 0;
while ( k > 0 ) {
n += f[k%10];
k /= 10;
}
if ( l != n ) continue;
printf("%d\n",l);
}
return EXIT_SUCCESS;
}
テストで良い点を取りたいならば、こちらの解答だろうな。
こちらのプログラムでも、同じ結果を出力するも、私のボロパソコンでは瞬殺といかず、多少もたついた瞬殺、秒殺といったところでした。
プログラムは簡潔になった分、枝刈りはやっていないので、
例えば、101と110はどちらか一方を試せば、もう片方は試す必要がないですよね。
つまり、それだけ余計なところまで調べているということにはなる。
だがしかし、枝刈りの処理も、それ自体に時間が掛かるのであれば、トレードオフな関係なのです。
どっちが良い悪いは、何を目指すのかに依存するかと思います。
例えば、今回は10進数表記の話しでしたが、これが16進数表記だった場合、
15!＝1307674368000＝0ｘ13077775800
と16進数11桁となって、11桁すべてがFだとしても11桁と変わらず、16進数11桁まで調べる必要がある。
こうなってくると、上記2つのプログラミングの方針の差が如実に現れてくるかと思います。
因みに、16進数の場合の解は、
0x1
0x2
0x260F3B66BF9
の3つとなりました。
ではでは