初めての店舗開業を成功させよう>>

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

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

このQ&Aに関連する最新のQ&A

1セント」に関するQ&A: 1セント硬貨

Java 練習」に関するQ&A: Javaの問題練習など

A 回答 (6件)

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


汎用的に動くかどうかもテストしてませんけど…
(質問文には、5セントがないけど、#1の補足にはあるから5セントを入れるんですよね?)
1$は、そのままなので、省いています。
/*
50,25,10,5,1セントを使って1$を作る
2枚から始めて、初めて作成できなくなる枚数は?
*/
class CoinCollect {
private static int oneDollar = 100; //一ドル=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){ //枚数が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);
}
}
    • good
    • 0
この回答へのお礼

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

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

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


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

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

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

    • good
    • 0

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


ごめんなさい。
ハズイ!
    • good
    • 0

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


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

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

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

あえてプログラム例は載せませんが、がんばってください。
    • good
    • 0
この回答へのお礼

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

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

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

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



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

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

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


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

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

この回答への補足

わかりづらくてすいません。。
質問の続きを書くと、
3枚の時は50セントが一枚と25セントが2枚。
4枚の時は25セントが4枚
5枚の時は50セントが1枚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
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング