No.3ベストアンサー
- 回答日時:
>#2
いえ、それはまずいです。818円だと
800円(32円25枚)+18円(10円+1円8枚)合計34枚よりも、
768円(32円24枚)+50円(25円2枚)合計26枚のほうが少なくなります。
なので愚直に32円硬貨が0枚のとき、1枚のとき・・・、おのおのについて25円硬貨が0枚のとき、1枚のとき・・・、と計算するしかないのでは。
が、1,234,567円を支払うとき、32円硬貨が0枚~38580枚を調べるのは遅すぎます。
さて、32円硬貨83枚と1円硬貨24枚で、107枚2680円になりますが、25円硬貨107枚では2675円しかありません。よって、32円硬貨は38580枚から、83枚を引いた38497枚まで調べれば十分です。
また、25円硬貨6枚と1円硬貨9枚で15枚159円ですが、10円硬貨15枚では150円しかありません。よって25円硬貨は(最大枚数)~(最大枚数-6枚)を調べれば十分です。
#32円硬貨の枚数はもっと狭い範囲で十分のはずなのですが、証明できない。
No.4
- 回答日時:
あ~, 本当だ....>#3. ご指摘ありがとうございます.
一応「ある程度以上は 32円硬貨を使い, 余った分を残りも混ぜる」ということになるんだけど, どこに境界があるんだろう.
この問題のセオリーは DP なんだけど, Java だと DP がやりにくいんだよね~. まあ, こんな問題で再帰使ったらどう考えても「高速」にはなりえないんだけど.
No.2
- 回答日時:
1つのアイデアとして:
800円単位では自明だから, 0円~799円までは手計算で答えを求めておく. で, 「800円単位」とそれ以下にわけてそれぞれの必要枚数を調べ和を返す.
「最速」とはいわんが,「高速に動作するプログラム」であることは保証する.
No.1
- 回答日時:
この回答へのお礼
お礼日時:2010/04/11 17:27
ありがとうございます。この問題の場合、金種表とは少し違うんです(たとえば51円のとき 25円2枚と1円1枚のほうが32円を使うよりも少ないんです) でも参考になりました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- ゴミ出し・リサイクル 外国のコインを換金したい 5 2023/05/05 14:15
- 数学 【 数A 場合の数 】 問題 10円硬貨2枚,50円硬貨3枚, 100円硬貨3枚の硬貨のうち一部また 2 2022/07/05 19:57
- その他(悩み相談・人生相談) マッチングアプリで好きになった元彼、初対面である事をされて凄く好きになったんですが、注目する所おかし 1 2022/11/15 18:17
- 数学 【 数Ⅰ 仮説検定 】 3 2023/02/27 22:21
- コレクション パチスロのコイン1000枚って 何キロあるのですか? パチスロの台集めてたのですが、 かなり倉庫に7 1 2022/06/12 17:08
- 数学 数学の参考書に コインを2枚投げる 「ただ裏表の出方は何通りか」の場合は コインを区別せず「3通り」 5 2023/01/20 17:46
- 数学 相変わらずヘッタクソ!! A君とB君はコインを1枚ずつ投げ、2枚とも表あるいは2枚とも裏が出れば投げ 5 2023/02/06 13:35
- 数学 場合の数、確率 47 (教科書章末問題) 再掲載 2 2023/08/22 11:50
- 数学 【大至急】確率の問題のやり方と解答を教えてください ①5枚のコインを同時に投げた時、表が出たのが3枚 4 2022/06/17 08:40
- パチンコ・スロット パチンコスロット スマスロにゃんこ大戦争が6月に出ますが、皆さんはどう見てますか? AT スマスロ 1 2023/04/23 14:43
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
数値計算の高速化 (cos, sin, exp)
-
排他的論理和 BCC(水平パリテ...
-
変化させるセルが変化しない
-
モジュラス103の計算とは何でし...
-
クォータニオンの計算?
-
バッチファイルでウインドウを...
-
科学技術計算の仕事について
-
EXCELなどで「返す」という表現
-
60進数の四則計算
-
入射角反射角
-
傾いた四角形内の範囲の条件式
-
VBAで関数をつくる
-
0x61の10進数は97との事ですが...
-
VBAの再計算が反映されない件に...
-
【fortran77】データ行数のカウ...
-
算術記号(+,-,/,*)を文字とし...
-
エクセル以外で麻雀の成績を管...
-
Excel VBAの残業時間の合計計算...
-
趣味で「乗換案内」みたいなソ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
mod でうまく
-
めちゃきれい
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
バッチファイルでウインドウを...
-
モジュラス103の計算とは何でし...
-
EXCELなどで「返す」という表現
-
変化させるセルが変化しない
-
60進数の四則計算
-
プログラムの質問
-
VBでReplace
-
数値計算の高速化 (cos, sin, exp)
-
C言語についてです。 再帰を使...
-
Javaを使った行列計算
-
C言語のプログラミングの問題で...
-
エクセルで特定のセルのみを任...
-
matlab計算での進捗状況を知りたい
-
CとFORTRANの計算速度はどちら...
-
matlabで計算終了
おすすめ情報