- ベストアンサー
課題;素因数分解
- みんなの回答 (8)
- 専門家の回答
質問者が選んだベストアンサー
> ここで、今日ヒントが出たのですが、次のプログラムを参考にして(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++ なので、多分、そのまま課題には使えないと思いますよ。
その他の回答 (7)
- akino4
- ベストアンサー率18% (35/185)
どうでもいいけど・・・ 問題読み間違えました(^^;ご指摘ど~も
- honiyon
- ベストアンサー率37% (331/872)
自分で考えてますか? 学校の課題ですよね?これ。 質問内容や、補足内容には「こういう問題が出されました」「こう指示されました」とだけ書かれており、ご自分でなされた努力や考えなどが一切出されていません。 これでは、ただ出された問題を他人に解いてもらおうとしてる、他力本願な姿勢であると誤解されてしまいますよ。
- a-kuma
- ベストアンサー率50% (1122/2211)
試しに力ずくで求めるプログラムを書いてみたら、重大な欠点(後述)が あって、却って簡単にならないのね。 というわけで、1)もやってみました。 #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までだけど)。4を指定した ときの出力は % 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を基準に考えられる。 図示してみると、 1 2 1 → 1 1+1 1 3 1 → 1+1+1 1 という感じ。 つまり、4つ並んだ1のそれぞれの隙間を+で表現して、ひとつの数値と 見るか、空白で区切って別の数値としてみるか。 先に提示したプログラムでは、その隙間をビット表現として1ならば +、0ならば空白だと思って、隙間の組み合わせ(4なら2の3乗)だけ 繰り返してみています。 # 下手な説明だなあ (^^; ちなみに、「力ずくで書けるから」と思っていたプログラムは、 #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・1・2だけ でも4回も出てくる。 ダブりをはじくように考えると、却って面倒なので、考え方から 見直してみたのが、最初に出したプログラムなの。
補足
ここで、今日ヒントが出たのですが、次のプログラムを参考にして(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
- a-kuma
- ベストアンサー率50% (1122/2211)
> 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば > いいでしょ? 「ぷっ」 1、2、1 や 1、1、1、1 も「和が一定(ここでは4)となる自然数の列」 なのよ。君もちゃんと授業に集中しなさいね :-) どうせ、力ずくで求める解(ループが四重になっている奴)を書いてくるのが いるだろうと思ってたのだけどなあ。
- akino4
- ベストアンサー率18% (35/185)
あんたもしかしてとーこーだいせい? 今日のドイツ語の授業中にそんな話してるやつらがいて・・・・・ 横でそいつらの話聞いててぷっってわらってしまった・・・・ 1は・・・・そりゃあ~た4から1、2、3、って順番にひいいていけば いいでしょ? #define kokodeha 4 //(笑) for (int i=0;i<kokodeha;i++){ cout << i<<","<<kokodea-i<<endl; } 2はwebで検索かけても、図書館に行ってもあるので省略(下にもあるし) 3) 再帰を用いるとスタックを食う(レポートに書くときは何に比例してって 書かないと点数がこないかも) んで計算量はそんなには変わらないよね
- a-kuma
- ベストアンサー率50% (1122/2211)
1)は、つまらないのでパス。 2)は、こんな感じ(効率は、あまり良くないけど)。 #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; } 3)の前に、再帰版のプログラムはこんな感じ。 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; } はっきり言って、(この程度のプログラムでは)たいした違いはない、よね。 再帰を使ったからといって、ロジックの見通しが良くなっているわけでも 無いし、却ってメモリ(スタック)を無駄に食うだけ。 あくまでもソフト屋さんの視点での比較なので、学校のレポートで点数を もらえる保証は無いよ ;-) # と言う意味では、「自信あり」とするわけにはいかないか…
- honiyon
- ベストアンサー率37% (331/872)
こんにちは、honiyonです。 どの辺が分からないのですか? プログラミングなのか、コーディングなのか。 ナドナド。 また、3番に関しては他人に検討を依頼するならば、まずは自分の意見を記述し、「皆さんはどう思いますか?」を問いかけるのが筋だと思います。
関連するQ&A
- 素因数分解する問題?
√1980B の根号がとれる最も小さい自然数Bを求めよ。 上の問題で たぶん素因数分解をすると思うのですが、 素因数分解してそのあとがよくわかりません こんな私にもわかるように説明してほしいです; よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素因数分解の一意性?????
m,n,p,qをすべて互いに素な自然数とした時に、 2^n・p^m=q^mにおいて、 素因数分解の一意性より、qは2の倍数である。 素因数分解の一意性ってどういうことなのでしょうか?
- ベストアンサー
- 数学・算数
- 素因数分解ができない?
123、205の最大公約数はいくつでしょう? 素因数分解をして求めたいのですが、 123は3で割って41 3* 205は5で割って41 5* となるのでしょうか? その後の素因数分解が続きません。 すいませんが、教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
スマソ。 ひたすら考えてるんですがまったくわからないのです。。。 誰に聞いても教えていただけないので。