- ベストアンサー
正数分割の個数
benderの回答
- bender
- ベストアンサー率45% (108/236)
partition(n,k) の読み替えとしては、おおよそ、「正の数 n を分割してできる分割の個数、ただし各部分の数は k 以下とする」だと思います。 直感的なアルゴリズムの理解としてはおおよそ、分割の個数を数え上げる際に、数え上げる種類に重複が無いように、与えられた数を、部分の数が徐々に小さくなる（か同じになる）ように分割して、それらを数えあげる、ということかと思います。 例、8を{1,2,5}に分割する場合、5+2+1の並びだけを数えることで、1+5+2、2+5+1、他、との数え上げの重複を避ける。 プログラムの終了条件で、(A) n==0 のときはそれ以上分割できないので 個数1を返すのですが、(B) n==1 のときも、次回の再帰呼び出しの結果がすでに決まっているので、同様に1を返して終了するのだと思います。 また、(C) k==1 の場合については、「各部分の数が1以下」である場合なので、そのような分割の仕方は、1+1+1+…+1しかないので、再帰呼び出しをするまでもなく個数1を返してよいことがわかります。 例、partition(5,5)=7 の場合： partition(5,5) partition(4,1) … 1+1+1+1+1 (C) partition(3,2) … 2+ partition(2,1) … 2+1+1+1 (C) partition(1,2) … 2+2+1 (B) partition(2,3) … 3+ partition(1,1) … 3+1+1 (B)/(C) partition(0,2) … 3+2 (A) partition(-1,3) partition(1,4) … 4+1 (B) partition(0,5) … 5 (A)
関連する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#
お礼
回答ありがとうございました。 おっしゃることは、だいたい判るのですが、 もう一つ、よく納得ができません。 物わかりの悪い頭ですみません。