- ベストアンサー
課題;素因数分解
a-kumaの回答
- 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回も出てくる。 ダブりをはじくように考えると、却って面倒なので、考え方から 見直してみたのが、最初に出したプログラムなの。
関連する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* となるのでしょうか? その後の素因数分解が続きません。 すいませんが、教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
ここで、今日ヒントが出たのですが、次のプログラムを参考にして(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