課題；素因数分解

質問

１）和が一定（ここでは４）となる自然数の列を全て列挙するプログラムを教え
てください。
２）再帰を用いずに素因数分解を行うプログラムを教えてくさい。
３）再帰を用いたプログラムと、再帰を用いないプログラムの比較・検討を行っ
てください。

回答No.5

a-kuma

試しに力ずくで求めるプログラムを書いてみたら、重大な欠点（後述）が
あって、却って簡単にならないのね。

というわけで、１）もやってみました。

#include <iostream.h>

int main()
{
　　int x, n;

　　cout << "sum:";
　　cin >> x;
　　n = 1 << (x-1);
　　for (int i = 0 ; i < n ; ++i) {
　　　　for (int j = 0, a = 1 ; j < x ; ++j) {
　　　　　　if ((1 << j) & i) {
　　　　　　　　++a;
　　　　　　} else {
　　　　　　　　cout << " " << a;
　　　　　　　　a = 1;
　　　　　　}
　　　　}
　　　　cout << endl;
　　}

　　return 0;
}

「和」を指定できるように作ってみた（31までだけど）。４を指定した
ときの出力は

% wa
sum:4
1 1 1 1
2 1 1
1 2 1
3 1
1 1 2
2 2
1 3
4

って感じ。ソースだけ読んでも理屈が分からないと思うので、ちょっと
解説を。

例えば、和が４のときの自然数の列は、全て、１を基準に考えられる。
図示してみると、
１　２　１　→　１　１＋１　１
３　１　　　→　１＋１＋１　１
という感じ。

つまり、4つ並んだ1のそれぞれの隙間を＋で表現して、ひとつの数値と
見るか、空白で区切って別の数値としてみるか。

先に提示したプログラムでは、その隙間をビット表現として１ならば
＋、０ならば空白だと思って、隙間の組み合わせ（４なら２の３乗）だけ
繰り返してみています。

＃ 下手な説明だなあ　(^^;

ちなみに、「力ずくで書けるから」と思っていたプログラムは、

#include <iostream.h>

int main()
{
　　int i,j,k,l;
　　for (i = 0 ; i <= 4 ; ++i)
　　　　for (j = 0 ; j <= 4 ; ++j)
　　　　　　for (k = 0 ; k <= 4 ; ++k)
　　　　　　　　for (l = 0 ; l <= 4 ; ++l)
　　　　　　　　　　if (i + j + k + l == 4) {
　　　　　　　　　　　　if (i != 0) cout << " " << i;
　　　　　　　　　　　　if (j != 0) cout << " " << j;
　　　　　　　　　　　　if (k != 0) cout << " " << k;
　　　　　　　　　　　　if (l != 0) cout << " " << l;
　　　　　　　　　　　　cout << endl;
　　　　　　　　　　}
　　return 0;
}

という感じのプログラム。動かしてみると分かるのだけれど、
組合わせのダブりが出てくるのだよね。例えば、１・１・２だけ
でも４回も出てくる。

ダブりをはじくように考えると、却って面倒なので、考え方から
見直してみたのが、最初に出したプログラムなの。

補足

ここで、今日ヒントが出たのですが、次のプログラムを参考にして(1)をやってく
ださいとのことでした。

例）和がw以下となる長さnの数列をすべて表示するためのプログラム

#include<stdio.h>

void abs_sum( int n, int w);
int main()
{
int w =2,n =3;
abs_sum( n, w);
return 0;
}
void abs_sum( int n, int w)
{
void in_abs_sum( int total_length, int n, int w);
in_abs_sum( n,0,w);
}
void in_abs_sum( int total_length, int pos, int w)
{
int i, j, called =0;
if ( pos >= total_length ){
putchar( '\n');
return;
}
for ( i =0;i <= w;++i){
if ( called++ ){
for ( j =0;j < pos;++j){
printf(" ");
}
}
printf("%2d",i);

in_abs_sum( total_length, pos +1,w-i);
}
}

出力したらこうなりました。
0 0 0
1
2
1 0
1
2 0
1 0 0
1
1 0
2 0 0
Press any key to continue