ページ 1 / 1
再帰についてです
Posted: 2008年10月11日(土) 21:28
by 初心者
何枚かの切手があるときに, 切手の金額の合計がちょうど与えられた金額になる組合せを求めるプログラムを作成する. このプログラムはまず目標の金額を入力した後, 切手1の金額と最大枚数, 切手2の金額と最大枚数, ... , 切手nの金額と最大枚数を入力する. 切手の金額として0 を入力すると終了とする. その後, 入力した切手の金額と最大枚数の範囲内で目標金額と等しくなる組合せを1つ出力する
この問題なんですけど再帰でのやり方が思いつきません。どなたかヒントをくれないでしょうか?
Re:再帰についてです
Posted: 2008年10月11日(土) 21:40
by box
本題にいく前に、前提条件を整理しておきます。
切手は何種類ありますか?
切手の金額と最大枚数の積和が、そもそも希望金額に達しない場合、どうしますか?
切手の金額と最大枚数の積和は希望金額以上であるが、ちょうど希望金額になる組み合わせがない場合、
どうしますか?
Re:再帰についてです
Posted: 2008年10月11日(土) 21:52
by 初心者
1、切手の種類は自分で決められます。
2、達しない場合解なしとします。
3、その場合は解なしとします。
ちょうど希望金額の同じになった時だけその組み合わせを出力したいのです。
私的にはn重ループを再帰で書き換えると思うのですがわかりません。
Re:再帰についてです
Posted: 2008年10月11日(土) 21:55
by box
> n重ループを再帰で書き換える
では、手始めにn重ループで実装してみてはいかがでしょうか。
実装したコードをながめているうちに、ループから再帰へ
どう変化させればよいかが見えてくるかもしれません。
Re:再帰についてです
Posted: 2008年10月11日(土) 22:04
by 初心者
すいません
ずっと考えているのですが、どうにもアルゴリズムがおもいつきません(泣
Re:再帰についてです
Posted: 2008年10月11日(土) 22:31
by lbfuvab
全て1枚は買うなどの条件はありますか?
それとも0枚でもいいのですか?
Re:再帰についてです
Posted: 2008年10月11日(土) 22:36
by 初心者
0枚でもよいです。
Re:再帰についてです
Posted: 2008年10月11日(土) 23:12
by box
具体的な例題から一般化するとよいかもしれません。例えば、
1円切手9枚、10円切手8枚、100円切手7枚があるとします。
合計が543円になる組み合わせは、何でしょうか。また、
その組み合わせを手で求める際、どういう手順を踏んだでしょうか。
Re:再帰についてです
Posted: 2008年10月11日(土) 23:31
by 初心者
1円切手3枚、10円切手4枚、100円切手5枚ですね
大きいほうから決めていきました。
Re:再帰についてです
Posted: 2008年10月11日(土) 23:42
by box
その手順を、プログラムにしてみてください。
Re:再帰についてです
Posted: 2008年10月11日(土) 23:59
by 初心者
for
金額を超えないまでたす。
if(まだ足せそうだったらn-1で再帰)
else if(あったら出力)
else if(超えてしまったら最初からやり直し)
こんな感じだと思うのですが分かりません
Re:再帰についてです
Posted: 2008年10月12日(日) 00:01
by lbfuvab
再帰についてですが
int saiki(int depth,int NowMoney);//depthは呼び出しの深さ(0から始まりn-1が最終) NowMoneyは呼び出された時点での合計額
でいけると思いますよ。
関数内での処理は
(SUCCESS,FAILUREは定数でNumStanpは枚数を保存する配列)
① depthがnを超えたら失敗(return FAILURE;)
② 枚数を1枚ずつ増やしていき・・・
③a 合計額が目標金額を超えたら失敗。(return FAILURE;)
③b 合計額が目標金額と同じなら成功。その時の枚数をNumStanp[depth]に登録
③c 合計額が目標金額より少ないならもう一度saikiを呼び、SUCCESSが帰ってきたら枚数をNumStanp[depth]に保存。
でいけると思います。
Re:再帰についてです
Posted: 2008年10月12日(日) 00:14
by 初心者
一度考えてきます。
またわからなくなったらよろしくお願いします。
Re:再帰についてです
Posted: 2008年10月12日(日) 08:24
by 初心者
これって深さ優先探索ですよね?
おおまかにプログラムを書いてくれませんか?
Re:再帰についてです
Posted: 2008年10月12日(日) 08:26
by 初心者
これですべての組み合わせを考えることが出来るのでしょうか?
Re:再帰についてです
Posted: 2008年10月12日(日) 10:17
by 初心者
#include<stdio.h>
void kitte(int , int,int );
int sum, s[100]={0}, k[100]={0};
int main(void)
{
int i=0,gk=0;
fprintf(stderr,"合計金額>>>");
scanf("%d", &sum);
while(1)
{
fprintf(stderr,"切手の金額と最大枚数を入力せよ>>>");
scanf("%d %d",&s,&k);
if(k==0)
{
break;
}
i++;
}
kitte(i+1,0,gk);
return 0;
}
void kitte(int c,int d ,int gk)
{
int i,j;
int h[100]={0};
if(c<=d)
{
printf("NO\n");
}
else {
for(i=0;i<=k[d];i++)
{
gk+=i*s[d];
if(sum-gk<0)
{
gk-=i*s[d];
}
else if(sum-gk==0)
{
h[d]=i;
for(j=0;j<c;j++)
{
printf("%d切手%d枚\n",s[j],h[j]);
}
}
else
{
kitte(c,d+1,gk);
h[d]=i;
gk-=i*s[d];
}
}
}
}
ここから分かりません
Re:再帰についてです
Posted: 2008年10月12日(日) 17:15
by 初心者
出来ました