コインのプログラムが作れずに困ってます

ＵＳ硬貨　1$コイン 50セントコイン 25セントコイン 10セントコイン　１セントコインを何枚でも使って、1$を作るとき、一番初めに作れなくなる枚数を求めるプログラムを作りたいのですが、どういったコードを書けばいいのか迷ってます。

質問がわかりづらいと申し訳ないので、補足として
例えば、一枚だったら　1$コインを使って作れます
二枚だったら　50セントコインを２枚使って作れます。枚数を増やしていって、ちなみに答えは77でした。手書きで一応解いてはみたんですが、不規則なパターンがあって、コインを細かくしていく方法ではなかなか難しくてコードができあがりませんでした。
他の金額でも使えるような汎用的なプログラムを作りたいと思っているんですが、どなたか解る方がいたらよろしくお願いします。

No.4 ベストアンサー 回答者： BLUEPIXY 回答日時： 2005/04/23 02:24

あんまり見本になるようなプログラムじゃないですが、とりあえず、（恥ずかしながら、練習を兼ねて）作ってみました。

汎用的に動くかどうかもテストしてませんけど…
（質問文には、５セントがないけど、＃１の補足にはあるから５セントを入れるんですよね？）
１＄は、そのままなので、省いています。
/*
50,25,10,5,1セントを使って１＄を作る
２枚から始めて、初めて作成できなくなる枚数は？
*/
class CoinCollect {
private static int oneDollar = 100; //一ドル＝１００セント
private static int kind[] = {50,25,10,5,1};//硬貨の種類
private static int size = kind.length;
private static int piece[] = new int[size];//種類に応じた枚数
private static int result[][] = new int[oneDollar/kind[size-1]+1][size];
public static void main(String args[]){
makeTable(oneDollar,0);//とりあえず作ってみる
for(int i=2; i<=oneDollar/kind[size-1] ; i++){
piece=result[i];
if(totalPiece()!=0){ //枚数が０枚でない時は成功！
piece=result[i];
System.out.print(i+":OK [ ");
for(int j=0;j<size;j++){
System.out.print(kind[j]+":"+piece[j] +" ");
}
System.out.println("]");
} else {
System.out.println(i+"枚の場合は存在しない。");
return ;
}
}
}
static void makeTable(int money, int level){
piece[level]=money/kind[level];
if(level==size-1){
if(money==piece[level]*kind[level]){
int work[] = new int[size];
for(int i=0;i<size;i++)
work[i]=piece[i];
result[totalPiece()]=work;
}
return;
}
while(piece[level]>=0){
makeTable(money - piece[level] * kind[level],level+1);
piece[level]--;
}
}
static int totalPiece(){
int sum=0;
for(int i=0;i<size;i++){
sum+=piece[i];
}
return(sum);
}
}

この回答へのお礼

このプログラムを試してみました！！！
完全に動いてます。そして、合計金額を増やしたり、硬貨の数を増やしたり（実際には紙幣もまぜるようにしたり）しても、完全に動いてました。
たとえば、＄２０までを、＄２０札までの紙幣と硬貨を使って求める場合を試してみたのですが、（＄２札をいれるのといれないので結果は変わってきます）
結果は、＄２札をいれた場合1977までのテーブルを作ってくれました！

まだ、ちょっとこのプログラムを理解してないのですが、後でじっくり読んで必ず理解します！
再帰を使った、メソッドを頭で考えるのはどうしたらいいのかよくわかりません。とても難しいですねぇ。。でも、これからいろいろな例をみたりして、勉強したいと思ってます！いつか、BLUEPIXYさんみたいにスグにコードが書けるようになりたいと思ってます。

本当にありがとうございました。


☆ちなみに、大学の課題だったのですが、自分で作ったコードは提出期限には間に合いませんでした（笑）
自分で作ったものはメソッドが汎用化されてなくて、合計が$20の時には完全に動きませんでした。

お礼日時：2005/04/24 02:52

No.6 回答者： BLUEPIXY 回答日時： 2005/04/23 02:34

やっぱあってるみたいです…

No.5 回答者： BLUEPIXY 回答日時： 2005/04/23 02:27

#4は、間違ってますね～

ごめんなさい。
ハズイ！

No.3 回答者： T0ngT0ng 回答日時： 2005/04/22 22:51

私が作るなら、1枚どこかのコインを決めて、残りの枚数で残りの

金額を実現できるか、というのを再帰的に繰り返していくような形
を考えます。
具体的には、3枚で実現する場合
1枚目を1ドルとすると残り2枚で0セントだからだめ
1枚目を50セントとすると残り2枚で50セントを実現できるか？
　　→　残りのうち100・50では残額を超えるので25セントを1枚として残額25セント
　　　　後25セント1枚で実現！
ってな感じでしょうか。

これをプログラム的に落とすと
金額と枚数を渡して実現可能かどうかを返すメソッドをひとつ用意し
この中で、1ドル(100セント)から1セントまで総当りで1枚使うことを仮定し
再度自分自身を呼び出す(引数の金額と枚数を減らすのを忘れないように)
残額0で枚数0ちょうどになったら終わり、って感じですか。

ちなみに馬鹿正直にこのままやると死ぬほど遅いはずなので、
1セント(最後の一種類)を判定するときは残り枚数*１セント=残額だったら終了
とか、前の判定で組み合わせ付加になってる額(今判定している金額より高額の
コインは判定しない)とかそういう判定も入れたほうがいいでしょうね。

あえてプログラム例は載せませんが、がんばってください。

この回答へのお礼

具体的なプログラムの構成教えていただいて、本当にありがとうございました！！
とても、参考になりました。
再帰のメソッドを作るのはまだちょっと僕には難しいですね。でも、もうちょっと練習や勉強をして、自分の頭の中でも考えられるようになりたいと思っています！

ありがとうございました！

お礼日時：2005/04/24 02:41

No.2 回答者： pcbeginner 回答日時： 2005/04/22 18:56

それは「解いた」んじゃなくて、単に書いていったら答えがわかっただけですよね？

「答えの求め方」
というのが数式や、アルゴリズムになるんですよ。
だから、まずは「答えの求め方」をちゃんと考えないとダメですね。

となると、javaのカテゴリじゃぁないかな。
でも、最終的にはプログラムを作りたいからここでもいいのか？

No.1 回答者： pcbeginner 回答日時： 2005/04/22 16:08

手書きで解けたのなら、その通りにプログラムを組めばいいだけでは？

不規則なパターンとはどういうパターンなのでしょう？

おそらく学校か何かの課題だと思いますが、もう少し具体的に質問をしないとダメですよ。

この回答への補足

わかりづらくてすいません。。
質問の続きを書くと、
３枚の時は50セントが一枚と25セントが２枚。
４枚の時は25セントが４枚
５枚の時は50セントが１枚25セントが一枚10セントが2枚5セントが1枚

このように、増えたり減ったりするコインがあったりするので、単純に増やしたり減らしたりするわけにもいかないのです。

表にすると

n $1 50 25 10 5 1

1 1 0 0 0 0 0
2 0 2 0 0 0 0
3 0 1 2 0 0 0
4 0 0 4 0 0 0
5 0 1 1 2 1 0
6 0 1 1 1 3 0
7 0 1 1 0 5 0
8 0 0 2 4 2 0

のように増えていきます。
後のほうになっていくとちょっとはパターン化してくるのですけども。。

補足日時：2005/04/22 18:23