課題；素因数分解

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

No.8 ベストアンサー 回答者： a-kuma 回答日時： 2001/06/12 18:08

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

なんてぇ補足　(^^;
要するに、再帰を使え、とのことかな？

#include <iostream.h>

void sum(int x, int xx[], int n)
{
　　int i, s;
　　for (i = 0, s = 0 ; i < n ; ++i)
　　　　s += xx[i];
　　if (s == x) {
　　　　for (i = 0 ; i < n ; ++i)
　　　　　　cout << " " << xx[i];
　　　　cout << endl;
　　　　return;
　　}
　　for (i = 1 ; i <= x - s ; ++i) {
　　　　xx[n] = i;
　　　　sum(x, xx, n + 1);
　　}
}

int main()
{
　　int x;
　　cout << "sum:";
　　cin >> x;

　　int xx[10];
　　sum(x, xx, 0);

　　return 0;
}

たいして分かり易くなったわけではありませんね。

■以下、余談

honiyon> 学校の課題ですよね？これ
honiyon> 他力本願な姿勢であると誤解されてしまいますよ

最初から、質問のタイトルに「課題」と入っているのだし、
質問サイトの本質は、他社の知恵におすがりしよう、というのだから
自分で何をしていようがかまわんとは思います。ただ、

> スマソ。

2ch なんか見ている暇があったら、テキストや参考書を開きましょう　:-)
とは言うものの、あのソースを参考に、っていうのも辛いものが
ありますね。

念の為、最後に書いておきますけど、私が提示しているソースは
全部 c++ なので、多分、そのまま課題には使えないと思いますよ。

No.7 回答者： akino4 回答日時： 2001/06/12 17:12

どうでもいいけど・・・

問題読み間違えました(^^;ご指摘ど～も

No.6 回答者： honiyon 回答日時： 2001/06/12 16:32

　自分で考えてますか？　学校の課題ですよね？これ。

　質問内容や、補足内容には「こういう問題が出されました」「こう指示されました」とだけ書かれており、ご自分でなされた努力や考えなどが一切出されていません。

　これでは、ただ出された問題を他人に解いてもらおうとしてる、他力本願な姿勢であると誤解されてしまいますよ。

この回答への補足

スマソ。
ひたすら考えてるんですがまったくわからないのです。。。
誰に聞いても教えていただけないので。

補足日時：2001/06/12 16:39

No.5 回答者： a-kuma 回答日時： 2001/06/12 13:27

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

あって、却って簡単にならないのね。

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

#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

補足日時：2001/06/12 15:55

No.4 回答者： a-kuma 回答日時： 2001/06/12 12:15

> １は・・・・そりゃあ～た４から１、２、３、って順番にひいいていけば

> いいでしょ？

「ぷっ」

１、２、１ や １、１、１、１ も「和が一定（ここでは４）となる自然数の列」
なのよ。君もちゃんと授業に集中しなさいね　:-)

どうせ、力ずくで求める解（ループが四重になっている奴）を書いてくるのが
いるだろうと思ってたのだけどなあ。

No.3 回答者： akino4 回答日時： 2001/06/12 11:59

あんたもしかしてとーこーだいせい？

今日のドイツ語の授業中にそんな話してるやつらがいて・・・・・
横でそいつらの話聞いててぷっってわらってしまった・・・・

１は・・・・そりゃあ～た４から１、２、３、って順番にひいいていけば
いいでしょ？
#define kokodeha 4 //（笑)
for (int i=0;i<kokodeha;i++){
cout << i<<","<<kokodea-i<<endl;
}
２はwebで検索かけても、図書館に行ってもあるので省略（下にもあるし）

3）
再帰を用いるとスタックを食う（レポートに書くときは何に比例してって
書かないと点数がこないかも）
んで計算量はそんなには変わらないよね

No.2 回答者： a-kuma 回答日時： 2001/06/11 17:51

１）は、つまらないのでパス。

２）は、こんな感じ（効率は、あまり良くないけど）。

#include <iostream.h>

int main()
{
　　int i = 2, x;
　　cout << "input n:";
　　cin >> x;
　　while (i <= x) {
　　　　if ((x % i) == 0) {
　　　　　　cout << " " << i;
　　　　　　x /= i;
　　　　} else {
　　　　　　++i;
　　　　}
　　}
　　cout << endl;

　　return 0;
}

３）の前に、再帰版のプログラムはこんな感じ。

include <iostream.h>

void pri(int x, int i)
{
　　if (x <= 1) return;
　　if ((x % i) == 0) {
　　　　cout << " " << i;
　　　　pri(x / i, i);
　　} else {
　　　　pri(x, i+1);
　　}
　　return;
}

int main()
{
　　int x;
　　cout << "input n:";
　　cin >> x;
　　pri(x, 2);
　　cout << endl;

　　return 0;
}

はっきり言って、（この程度のプログラムでは）たいした違いはない、よね。

再帰を使ったからといって、ロジックの見通しが良くなっているわけでも
無いし、却ってメモリ（スタック）を無駄に食うだけ。

あくまでもソフト屋さんの視点での比較なので、学校のレポートで点数を
もらえる保証は無いよ　;-)

＃ と言う意味では、「自信あり」とするわけにはいかないか…

No.1 回答者： honiyon 回答日時： 2001/06/11 17:18

こんにちは、honiyonです。

　
　どの辺が分からないのですか？
　プログラミングなのか、コーディングなのか。　ナドナド。
　また、3番に関しては他人に検討を依頼するならば、まずは自分の意見を記述し、「皆さんはどう思いますか？」を問いかけるのが筋だと思います。