バックトラックプログラミング

[☆]

お久しぶりです。
また、ご指導をもらいに来ました。
よろしくお願いします。

今、『正整数ｎの分割を全て求めるプログラム』を作っています。
このような実行結果を期待しているんです。

n: 5
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
5
total number = 7

[Hermit]

ちょっと違うけど、
http://www.play21.jp/board/formz.cgi?ac ... =8331#8255
あたりは参考になりませんか？

[☆]

今途中なのですが、私が作ったのは以下のプログラムです。。

# include <studio.h>

int part(int total,int min){
/*total をmin以上の数を使って分割する方法の数*/

int sub; /*分割の候補*/
int cnt=0;　 /*分割法の数*/

/*1つの解発見*/
if(total==0) cnt=1;
else{
/*total=sub+...と分割する方法の和*/

for(sub=min;sub<=total;sub++){
cnt+=part(total-sub,sub);
}
}
return cnt;
}

int main(void){

int n;
printf("n: ");
scanf("%d",&n);

printf("total number=%d\n",part(n,1));

return 0;
}

これでコンパイルも結果もきちんとできるんですけど・・・
まだ分割方法を全て表示できてないんですよねぇ。。。。

[☆]

考え方的には・・・・

int part(int total, int min, int divNum)として、、、、
total を min 以上の数を使って分割する方法の数を返す。
divNum 回目の分割で，解を発見した時、ans[0] ～ ans[divNum-1]
までを出力する。解が見つかっていない時は，ans[divNum] に分割した数(sub) を代入する。

というイメージをしているんですけど・・・
こういう考え方でいいんでしょうか？？

[しっぽ]

> これでコンパイルも結果もきちんとできるんですけど・・・
> まだ分割方法を全て表示できてないんですよねぇ。。。。

どんな数値を入力したら、どんな分割の場合が不足しているのでしょうか？


本質には関係ないけど、インデントしてください。
あと scanf は戻り値のチェックが不足してます。

[☆]

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
5

↑の部分が出るプログラムになってなぃんです。

Hermitサン、ありがとうございます★
ちょっと違ったんですが、参考にしてみました。

[しっぽ]

> ↑の部分が出るプログラムになってなぃんです。

インデントがなく読みにくくて、見落としてましたが、
答えを入れておくバッファーさえもないとは！


http://www.play21.jp/board/formz.cgi?ac ... =8331#8255
の 2007/06/05(火) 21:40 の記事のコードをちょっと変更すればできますので、
☆さんのものと比較してみてください。

//#define MAXVALUE 39
#define MAXVALUE 20

//	static char str[(MAXVALUE + 1) * 2] = {0};
	static char str[MAXVALUE * 4] = {0};


//		sprintf(str + pos, "%d ", j);
		if(pos > 0)
			sprintf(str + pos, " + %d", j);
		else
			sprintf(str, "%d", j);

[☆]

おそくなりました。

すみません。。。見にくいですよねぇ。。。
申し訳ありません↓↓

はい、今から参考にさせてもらいます。
ありがとうございます。