- ベストアンサー
正数分割の個数
benderの回答
- bender
- ベストアンサー率45% (108/236)
すでに簡潔な回答や、詳しい説明が寄せられていたことに気づいたのですが、もう一度説明に挑戦してみたので、すでに寄せられた回答と同じようにも思うのですが、いずれにしても投稿してみます。 はじめに、うまくいかない方法を書いて、それを通して質問欄にある賢いアルゴリズムについて書きたいと思います。 5を分割するということは、5個の要素 OOOOO をいくつかのグループにわけることなので、そこで、要素を一列に並べて左端から何個かづつ順にとりわけて、5個全部分割し終わったものを数え上げるような場合を考えます。 例、 [O]OOOO（左から一個とりわける） [O][O]OOO （左からさらにもう一個とりわける） … [O][O][O][O][O] 分割方法1 (1+1+1+1+1) -------------------------------------- [O]OOOO [O][O]OOO … [O][O][O][OO] 分割方法2 (1+1+1+2) -------------------------------------- … …（分割方法3 ～ j-1） … -------------------------------------- [OO]OOO [OO][O]OO … [OO][O][O][O] 分割方法 j (2+1+1+1) etc. 以上で、分割方法2と分割方法 j は同じ分け方とみなされるので、このようにすべての分割方法を求めて結果を数え上げていくのでは、分割方法を全種類導出できるものの、数え上げに重複があってうまくありません。 そこで、質問欄にある賢い関数では、（左から）要素とりわける際に、次に取り分けるグループを、直前にとりわけたグループと同じ大きさか、あるいはだんだん小さくなるようなものだけを考えています。なぜならば、そうすることで、ひとつの分割の仕方につき、ひとつだけ表現が対応するからです。例えば、{1,1,1,2} については、分割方法 jの [OO][O][O][O]のみが対応して、分割方法2は導出されません。 そこで、このようなアルゴリズムを実現する再帰関数の引数としては、分割する要素の個数 n 、さらに、次にグループを取り分ける際に最大何個の要素のグループをつくってよいか（つまり、直前にとりわけたグループの大きさ）k を指定することが必要です。 具体的に5の分割を求めるときには、はじめに、partition(5,5) （5個の要素を、最大のグループが5以下からなるものに分割して、それらの分割方法を数え上げたものを返す関数）を呼び出します。 このとき、（左端からの）要素のとりわけの一回目の方法としては、明らかに以下の５通りで、また、明らかにこの５通りしかありません。 [O]OOOO (n-i=4, i=1) [OO]OOO (n-i=3, i=2) [OOO]OO (n-i=2, i=3) [OOOO]O (n-i=1, i=4) [OOOOO] (n-i=0, i=5) それぞれの場合、さらなる分割をするために関数を再帰的に呼びだすのですが、ここで重要なのは、先に書いた分割方法に従う限り、以上の５通りのいずれからも重複する分割結果が導出されない、かつ、すべての分割方法が導出されることです。例えば、 [O]OOOO のときには、残りの（右の）４個（n-i=4）をさらに分割する方法で、ただし、その各要素数が最大１個(i=1)であるようなものの個数、を求める関数を呼びます、すなわち、partition(4,1) 。この場合について言えば、残りの4要素を分割する際に作れるグループの数が1個以下と指定されているので、これは([O])[O][O][O][O] とするしかありません。そこで、この場合1を返してよいことが関数に指定されています(k==1)。 [OO]OOO のときには、残りの（右の）3個をさらに分割する方法を数で、ただし、その各要素数は最大で2個であるようなもの、を求める関数の呼び出します、すなわち、partition(3,2) 。これはさらなる再帰の結果、最終的には、([OO])[OO][O] と([OO])[O][O][O] の２通りに帰結することがわかります。 残りの３つの場合についても、それぞれ、 partition(2,3)（([OOO])[OO]と、([OOO])[O][O]の２通りに帰結） partition(1,4)（残りの要素が1個なので、分割するまでもなく[OOOO][O]） partition(0,5)（すでに分割が完了している [OOOOO]） 実際に導出されたように、このように求められた分割には重複がなく、かつ、数え漏らしがありません（これ以外に取り分ける方法がないので）。そこで、この5通りから帰結した分割の個数の和 7 = 1 + 2 + 2 + 1 + 1 が、5 を分割する方法の個数であるとわかります。
関連するQ&A
- C言語＜素数を求めるプログラム＞
#include<stdio.h> int j; int prime(int n) { int i; if(n < 2) return 0; if(n == 2) return 1; if(n%2 == 0) return 0; for(i = 3; i*i<= n; i += 2){ if(n%i == 0) return 0; } return 1; } int main(void) { int n; for(n=1; n <= 1000; n++) { if(prime(n)){ printf("%d\n",n); j++; } } printf("素数の個数は全部で %d 件見つかりました。\n",j); return 0; } このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。 int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか？
- ベストアンサー
- C・C++・C#
- C言語のプログラム添削お願いします
#include<stdio.h> int main(void) { int a[4]; int i=0; int n; int sum=0; printf("正数を入力してください\n"); while(i<=4) {scanf("%d",&n); if(n>=0) {a[i]=n; sum=sum+a[i]; i++; } else{printf("正数を入力してください");} } printf("正数の合計値は%dです",sum); printf("正数の平均値は%lfです",(double)(sum/5)); return(0); } 上記は正数のみ配列に保存し、その合計と平均を表示するプログラムを 製作しようとして書いたものですが次のような問題点があり正常に機能しません。 （１）a[i]=n;をn=a[i];と置き換えると不正な値が表示される （２）平均値の小数点以下の値がおかしい （例）８＋８＋８＋９＋８と入力し合計値41に対し、平均値が８．００００００ 解決法が分からず困っています。どなたかお力添えお願いします。
- ベストアンサー
- その他（インターネット・Webサービス）
- パスカルの三角形についてのCプログラムの解説をお願いします！
プログラミング初心者です。 先日『ｎが入力されたときに、ｎ段のパスカルの三角形を出力するプログラムを作成しなさい』という課題が出ました。 まだ理解しきれていないところが多いもので、手元にある資料をマネて、とりあえず動いてくれるように書いてみました。 今消化不良をおこしているのは以下の２点です。 １ 一部理解できない箇所がある →解説をいただきたい ２ 出力される三角形が、パスカルの三角形ではなくただの『ｄ』の三角形になってしまう →どこが間違っているのかご指摘いただきたい 以下が書いたプログラムです。 #include<stdio.h> int comb(int n, int r) { if (r==0 || r==n) return 1; elese return comb(n - 1, r - 1) + comb(n - 1, r); } main() { int n,i,j; printf("n?"); scanf("%d",&n); for (i=0; i<=n, i++) { for(j=0; j<=i, j++) { printf("d%",comb(i,j)); } printf("\n"); } } ちなみに理解できていない（自分自身で説明できない）箇所は main関数の前、 if (r==0 || r==n) return 1; elese return comb(n - 1, r - 1) + comb(n - 1, r); の二行です。お恥ずかしい話、記号の意味もよくわかってません； どなたかご指導お願いします！！（＞＜）
- 締切済み
- C・C++・C#
- C言語でわからない問題があります
下のプログラムのXXXの値なのですが、何を返すのかがわかりません プログラム(1)と(2)では、処理にどういう違いがあるのでしょうか、できれば教えてください プログラム(1) #include <stdio.h> #define N 5 //関数のプロトタイプ宣言 int min(int *p , int n); int main(void){ int data[N] = {15,34,28,12,33}; int index; //最小値の位置 index = min(data,N); printf("最小値はdata[%d]で%d\n" , index, data[index]); } int min(int *p , int n){ int *pmin; //最小値のアドレス int i; //カウンタ pmin = p; for(i = 1; i < n; i++){ if (*pmin > *(p+i)){ pmin = p+i; } } return XXX; } プログラム(2) #include <stdio.h> #define N 5 //関数のプロトタイプ宣言 int *min(int *p , int n); int main(void){ int data[N] = {15,34,28,12,33}; int *p; //最小値の位置 p = min(data,N); printf("最小値は%d\n" , *p); } int *min(int *p , int n){ int *pmin; //最小値のアドレス int i; //カウンタ pmin = p; for(i = 1; i < n; i++){ if (*pmin > *(p+i)){ pimn = p+i; } } return pmin; }
- 締切済み
- C・C++・C#
- 数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。 コンパイルエラーはありません。 表示の関数は省いてあります。 よろしくお願いします。 #include <stdio.h> #define M 3 //小さいブロックのサイズ #define N M*M //全体のサイズ #define MTX N*N //全体のマス数 int sudoku[N][N]={ {0,2,4,5,0,0,6,0,0}, {0,0,6,3,2,0,0,0,4}, {0,0,5,0,9,0,0,8,3}, {0,0,8,4,0,3,0,0,1}, {0,6,1,9,0,0,4,3,0}, {7,0,0,1,0,0,5,0,0}, {8,3,0,0,4,0,9,0,0}, {4,0,0,0,3,5,8,0,0}, {0,0,7,0,0,9,3,4,0} }; /* 候補がOKかどうかチェック */ int OKkouho(int x, int y, int k) { int i,j; int p,q; for(i=0; i < N; i++){ //その行に候補は入るか if(sudoku[y][i] == k) return 0; } for(j=0; j < N; j++){ //その列に候補は入るか if(sudoku[j][x] == k) return 0; } p = x/M*M; q = y/M*M; //そのブロックに候補は入るか for(j = q; j < q+M; j++){ for(i = p; i < p+M; i++){ if(sudoku[j][i] == k) return 0; } } return 1; } void Solve(int level) { int k; int x,y; if(level >= MTX){ printf("OK"); return; } x = level%N; y = level/N; if(sudoku[y][x]) Solve(level+1); else{ for(k = 1; k <= N; k++){ if(OKkouho(x,y,k)){ sudoku[y][x] = k; Solve(level+1); sudoku[y][x] = 0; } } } } int main(void) { Solve(0); return 0; }
- 締切済み
- C・C++・C#
- ポインタエラー？
コンパイルエラーで、つまづいてます 型が合ってないというのはわかるのですが どうしたらいいのかわかりません どこを改善すればいいでしょうか 問題とソースです↓ ソースは色々てを加えたので変なものが混じってます。 関数ichi()を作成し、プログラムを完成させよ。 main内部を変更してはならない。 (見つからない場合も考慮されている事に注意せよ。) #include <stdio.h> #define MAX 10 int *ichi(int *,int); int main() { int x[MAX], i, n, *p; for (i = 0; i < MAX; ++i) { scanf("%d", &x[i]); } scanf("%d", &n); p = ichi(x, n); if (p) { printf("%d ha %d ko me ni arimashita\n", n, p-x); } else { printf("%d ha arimasen desita\n", n); } return 0; } int *cnt; int * ichi(int *x,int n) { //int cnt; //cnt = 0; while(*x){ if(*x == n){ cnt = &n; //cnt = x; //return x; return cnt; } *x++; } return NULL; }
- ベストアンサー
- C・C++・C#
- 組み合わせ
n個の集合からp個を取る組み合わせの総数を出力するプログラムなんですが nCp=n!/p!(n-p)!という式を使い #include<stdio.h> int kaijo(int m); int comb(int n,int p); int main(void) { int i,j; printf("n="); scanf("%d",&i); printf("p="); scanf("%d",&j); printf("comb(%d,%d)=%d\n",i,j,comb(i,j)); } int kaijo(int m) { if(m>0) return(m*kaijo(m-1)); else return 1; } int comb(int n,int p) { if(n>0) return((n*kaijo(n-1))/(p*kaijo(p-1)*(n-p)*kaijo(n-p-1))); else return 1; } と書いてみたのですがこれではnが大きいとＣ言語のint型で扱える最大値を超えてしまい正しい結果が出力されません。 そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたいのですがどう改良したらよいのでしょうか？ おそらくnCp=n*(n-1)*・・・*(n-p+1)/p!という式を使うのですがよく分かりません。よろしくお願いします。
- 締切済み
- C・C++・C#
- 選択ソートアルゴリズム（selection sort）について 質問No.1226692のつづき
BLUEPIXYさん、keikanさんありがとうございました。せっかく教えていただいたのですが、セグメンテーションエラーが出てしまいます。 選択法で基準値(pivot)を使用し、K番目に小さい要素を見つけるプログラムを作成しようとしています。しかし、コンパイル時にセグメンテーションフォルトメッセージが出力されるのですが、どこが間違っているのかわからず、途方にくれています。どなたか教えていただきたく。よろしく御願いいたします。 #include<stdio.h> int s[100]={27,10,12,20,25,13,15,22}; int pivotpoint; int selection(int, int, int); //void partition(int, int, int); main(){ int num; num=selection(0,7,3); printf("The third smallest is %d?n ", num); } int selection(int low,int high,int k) { void partition(int, int, int); //int pivotpoint; if(low==high) return s[low]; else{ partition(low,high,pivotpoint); if(k==pivotpoint) return s[pivotpoint]; else if(k<pivotpoint) return selection(low,pivotpoint-1,k); else return selection(pivotpoint+1,high, k); } } void partition(int low,int high,int pivotpoint) { int i,j; int pivotitem; int tmp; pivotitem=s[low]; j=low; for(i=low+1;i<=high;i++){ if(s[i]<pivotitem){ j++; tmp=s[i]; s[i]=s[j]; s[j]=tmp; } } pivotpoint=j; tmp=s[low]; s[pivotpoint]=s[low]; s[low]=tmp; }
- ベストアンサー
- C・C++・C#
- ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。
ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。 ソースコードは以下の様になります。 -------------------------------------------------- bool incircle(point a, point b, point c, point p) { a -= p; b -= p; c -= p; return norm(a) * cross(b, c) + norm(b) * cross(c, a) + norm(c) * cross(a, b) >= 0; // < : inside, = cocircular, > outside } #define SET_TRIANGLE(i, j, r) \ E[i].insert(j); em[i][j] = r; \ E[j].insert(r); em[j][r] = i; \ E[r].insert(i); em[r][i] = j; \ S.push(pair<int,int>(i, j)); #define REMOVE_EDGE(i, j) \ E[i].erase(j); em[i][j] = -1; \ E[j].erase(i); em[j][i] = -1; #define DECOMPOSE_ON(i,j,k,r) { \ int m = em[j][i]; REMOVE_EDGE(j,i); \ SET_TRIANGLE(i,m,r); SET_TRIANGLE(m,j,r); \ SET_TRIANGLE(j,k,r); SET_TRIANGLE(k,i,r); } #define DECOMPOSE_IN(i,j,k,r) { \ SET_TRIANGLE(i,j,r); SET_TRIANGLE(j,k,r); \ SET_TRIANGLE(k,i,r); } #define FLIP_EDGE(i,j) { \ int k = em[j][i]; REMOVE_EDGE(i,j); \ SET_TRIANGLE(i,k,r); SET_TRIANGLE(k,j,r); } #define IS_LEGAL(i, j) \ (em[i][j] < 0 || em[j][i] < 0 || \ !incircle(P[i],P[j],P[em[i][j]],P[em[j][i]])) double Delaunay(vector<point> P) { const int n = P.size(); P.push_back( point(-inf,-inf) ); P.push_back( point(+inf,-inf) ); P.push_back( point( 0 ,+inf) ); int em[n+3][n+3]; memset(em, -1, sizeof(em)); set<int> E[n+3]; stack< pair<int,int> > S; SET_TRIANGLE(n+0, n+1, n+2); for (int r = 0; r < n; ++r) { int i = n, j = n+1, k; while (1) { k = em[i][j]; if (ccw(P[i], P[em[i][j]], P[r]) == +1) j = k; else if (ccw(P[j], P[em[i][j]], P[r]) == -1) i = k; else break; } if (ccw(P[i], P[j], P[r]) != +1) { DECOMPOSE_ON(i,j,k,r); } else if (ccw(P[j], P[k], P[r]) != +1) { DECOMPOSE_ON(j,k,i,r); } else if (ccw(P[k], P[i], P[r]) != +1) { DECOMPOSE_ON(k,i,j,r); } else { DECOMPOSE_IN(i,j,k,r); } while (!S.empty()) { int u = S.top().first, v = S.top().second; S.pop(); if (!IS_LEGAL(u, v)) FLIP_EDGE(u, v); } } double minarg = 1e5; for (int a = 0; a < n; ++a) { for (set<int>::iterator itr = E[a].begin(); itr != E[a].end(); ++itr) { int b = *itr, c = em[a][b]; if (b < n && c < n) { point p = P[a] - P[b], q = P[c] - P[b]; minarg = min(minarg, acos(dot(p,q)/abs(p)/abs(q))); } } } return minarg; } -------------------------------------------------- http://www.prefield.com/algorithm/geometry/delaunay.htmlのサイト様のものなんですが、私自身ｃ++プログラム初心者なので、わからず困っています。。概要でも結構ですのでどなたか回答してくださる方いらっしゃれば回答よろしくお願いします。
- 締切済み
- C・C++・C#
お礼
ありがとうございます。 ＃５で言われたことを非常に丁寧に説明されていて、 物わかりの悪い私にもよくわかりました。