![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
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で質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Flash Lite1.1 計算の誤差
-
趣味で「乗換案内」みたいなソ...
-
60進数の四則計算
-
絶対ち
-
継承元と継承先での変数
-
C言語で電卓を作成する。修正お...
-
変化させるセルが変化しない
-
Scilabでのプログラミング
-
剰余の計算方法
-
65536は2の何乗なのでしょうか?
-
最適円順列を求めるアルゴリズ...
-
C言語で N行*M列 の逆行列を求...
-
引き放し法による除算アルゴリ...
-
VB6.0でのバイナリデータの扱い...
-
EXCELなどで「返す」という表現
-
Javaでのある数の小数点乗に...
-
階乗のマクロ
-
VB6で 1-0.1*10 の計算結果が...
-
逆行列求めたい
-
VBAの再計算が反映されない件に...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
パソコン
-
VBAで関数をつくる
-
階乗のマクロ
-
EXCELなどで「返す」という表現
-
排他的論理和 BCC(水平パリテ...
-
バッチファイルでウインドウを...
-
変化させるセルが変化しない
-
VBAの再計算が反映されない件に...
-
引き放し法による除算アルゴリ...
-
モジュラス103の計算とは何でし...
-
Visual C++でdebugとreleaseで...
-
エクセルで特定のセルのみを任...
-
数値計算の高速化 (cos, sin, exp)
-
傾いた四角形内の範囲の条件式
-
VBでReplace
-
骨折リスク評価のFRAXについて...
-
アドオン利率を実質年率に変換
-
入射角反射角
-
C言語についてです。 再帰を使...
おすすめ情報