- - PR -
お手本になるようなソースコード
投稿者 | 投稿内容 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2007-05-14 10:43
あぁ!おっしゃる通りですね・・・orz 単純ループだと、このパターンのように小さい数字の方でまとめた方が最小枚数になる場合の対応は難しいですね。Ver.3 は僕の足りない頭脳では無理だなぁ ギブアップです。ごめんなさい。 しかし、わちゃさんのソースは速いですねぇ ビックリしました。どんな技術手法を採用されているのか時間がある時に勉強したいと思います。とても勉強になります。ありがとうございます。
例えば、0.5 秒 と 1.5 秒 ではその差が 3 倍 ですが体感的にはそれ程の差を感じないかなぁ、と思いましたので。 また、Ver.2 であればそこまでの差は発生しないのでは、とも思いました。 確かに、おっしゃる通り、実行速度最優先なら問題ないと思いますし、前レスでも書いていますが、自分のアプローチ方法では限界があるため、Anonymous Coward さんのアプローチも十分現実的な方法だと思います。 | ||||||||||||||||
|
投稿日時: 2007-05-14 10:46
訂正。40000円は「すべての金種の最小公倍数」ですね。 金種のパターンによっては、その最小公倍数が大きすぎて内部で表現できなくなってしまったり(インフレ ?)、 最小公倍数未満の探索ですらメモリ不足で実行できなくなったりしてしまうことが容易に想像できますが、 こうなってくると、外部メモリ(いっそDB)を利用してしまうほうが現実的かもしれません。何度も繰り返し使えますし | ||||||||||||||||
|
投稿日時: 2007-05-14 20:01
ぬぅ、たしかに、よくないですね。 unibon さんのコードでは、ちゃんと大小関係までチェックされていて、 あぁ、こうするのがいいんだなぁと、ちょっと関心しておりました。 こういうので、チェックしないから、43 がダブってても、気づかないん ですね、、、orz 自分のコードは、1円硬貨がある前提でした。 一応、条件分岐で、1行足すと、先ほどの 135 円のも大丈夫にはしましたが、 こういうあたりは、自分のエラーチェックに対する認識に少なさを 感じてしまいますね。
たしかに、unibon さんのような最小公倍数などを使う場合は影響しそうですね。 私のアルゴリズムだと、単純に総当たりなので、あまり関係はないような気がします。 とりあえず、コメントを入れてはいたのですが、分かりにくかった部分もあるようですので、 簡単にアルゴリズムの紹介をしたいと思います。 基本は、再帰呼び出しによる総当たりがベースです。 ループが、金種の数だけあると思うと分かりやすいかもしれません。 そのなかで、最大の金種から、1枚ずつ変更しながら、残った金額を それ以下の金種で、何枚でできるかを探索していきます。 その中で、主な最適化のうち、二つを紹介したいと思います。 一つ目の最適化は、
の部分です。 例えば、実際の硬貨で、401 円を支払うのに、まずは、100円玉を 4 枚使った場合を 探索します。すると、100 x 4 + 1 で、5 枚でできる事が分かります。 次に、100円玉を減らして 3 枚にした場合を考えると、残額は 101 円になり、 次の金種である 50 円玉が少なくとも 2 枚は必要になります。 これでは、100 円玉を減らす意味がありません。 つまり、その次に大きい金種以降を、どう組み合わせてもすでに知っている枚数よりも 多い枚数が必要になってしまいます。 そうであれば、それ以上、100円玉を減らす理由がありません。 その場合は、ループを抜けてしまいます。 ただ、この方法の場合、404 円などの場合に、ほとんど最適化がききません。 つまり、100円玉を 4 枚使った場合、100 x 4 + 1 x 4 の8枚が必要ですが、 100円玉を減らして 3 枚にした場合を考えると、残額は 104 円になり、 50 円玉以降の金種で、運がよければ 3 枚でできるかもしれませんので、 (実際、27円硬貨があれば、104円を3枚でできます) 100円玉を1枚ずつ減らして、全パターンを探索してしまいます。 二つ目の最適化は、
の部分です。 再帰定義される関数は、末端において、まったく同じパターンによる呼び出しが多い事がしばしばあります。 特に、Ver.2 で、63999円などを計算する場合、2000円札以上の組み合わせには探索の価値がありますが、 1000円札を使った後の 999円以下の組み合わせについては、すでに計算済みであるのに、何度も 呼び出されてしまいます。 そのようなパターンを少なくするために、すでに計算済みのパターンであれば、キャッシュで記憶して おくようにしました。 びしばしさんの外部 DB に入れておくのに似たイメージかもしれません。 ただ、このキャッシュは、要素数が、最大で(金額 × 金種数)に膨れ上がる可能性がありますので、 なんらかの限度を設けるようにした方がいいのかもしれません。 unibon さんの最大枚数を使ったアルゴリズムも興味があるのですが、なかなか 自分のコードにうまく適用できませんでした。 ちなみに、そこそこ速くはなったのですが、 {100, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 1} という金種で、404 円を計算しようとすると、 再帰呼び出しが、2500回ぐらいにまで増えてしまったので、ちょっとへこんでます。 誰か、つぎのお題ありませんか? | ||||||||||||||||
|
投稿日時: 2007-05-14 22:24
次のお題というより、つづきなんですけど。
私の場合、通貨だと、どうしても 「1円は絶対あるだろ」 とか、クレカのポイントにしても、 「現実的に大きい素数を使うことなんかありえねー」 とかの意識が頭から離れないので、 お題Ver.4を考えてみました。 ────────────────────────────────────────── お題Ver.4 あなたはあるゲームに参加することになりました。 このゲームのルールは以下の通りです。
例)最初の所持金が30000円でA〜Dの買い方が以下の通りだった場合 A:29999 B:25000+4000+500+500 C:25000+3000+2000 D:25000+2500+2500 順位はCDBA 最初の所持金とお店で扱っている全商品の価格(重複するものはあらかじめマージ)を 入力とし、確実に1位になれるような買い方を求めるプログラムを作ってください。 ────────────────────────────────────────── Ver.3すら自分で解けてないのに難易度を上げてしまった… 自分で自分の首を締めてどーする>俺w | ||||||||||||||||
|
投稿日時: 2007-05-15 09:56
クソ長いプログラムを貼っても怒られないスレッドはここですか
Ver.3、Ver.4対応です。 前回のRuby版の拡張ですが、こんどはJavaで。
実行例
目標金額が高々100万円程度なら、どんな金種(商品)の組でもほぼ一瞬で解けます。現実的な金種なら、かなり大きな目標金額でもOK。ダメなときはjava.lang.OutOfMemoryErrorかjava.lang.NegativeArraySizeExceptionになります。(ダメなときも一瞬) 元々作ってあったやつで、Ver.4対応で変えたところは、途中の"<"を"<="に変えて(高い商品を優先)、と「お釣り」でなく「不足」を求めるように変更ぐらいです。 コメントとかは端折り気味ですがご勘弁を。(さらに長くなるので…) 修正:枚数(商品数)の差がすごく大きいときに、金額をぴったりにすることより、枚数を減らすことを優先してしまうバグを修正。(Scoreクラスの導入) そしたら、ちょっと処理性能が悪くなった…。 再修正:処理速度の劣化がひどいので、やっぱりScoreクラスは廃止。枚数の差が65536を超えると間違えますが…。 [ メッセージ編集済み 編集者: sawat 編集日時 2007-05-15 11:58 ] [ メッセージ編集済み 編集者: sawat 編集日時 2007-05-15 12:01 ] [ メッセージ編集済み 編集者: sawat 編集日時 2007-05-15 12:42 ] | ||||||||||||||||
|
投稿日時: 2007-05-17 08:18
お題Ver.4の解が、ようやく形になってきますた
自分でバージョンアップさせたお題を解けないのが悔しくて、 仕事の合間にちょこちょこ弄くってたのですが、 なんとか速度的にもツカイモノになるレベルになってきました。 数字の組み合わせによっては、sawatさんのプログラムの方が明らかに速い場合もあるのですが、 逆に別の数字の組み合わせだと、sawatさんのプログラムがOutOfMemoryErrorを投げるのに対し、 こっちはちゃんと動いてくれたりと、一長一短です。 とはいえ、私のは一番肝心なところはほぼわちゃさんのコードがベースで、 自分でやったのは、結果をクラス化してコードの見通しを良くしたくらいです。 あと、商品(金種)の個数の上限値をあらかじめ決めておくアイデアは、 unibonさんのコードからヒントを得て追加しました。 最小公倍数以上を分離させるのは、動かして試してみたらそれ程効果がなかったので削りました。 まだ細かいバグとかあるかもしれませんので、その点はご承知おきを。 言語はC#です。
ちょっとだけ脱線しますが、mainを一番下に書くのって、C/C++出身者に多かったりするんでしょうか? このスレの中でも、一番上に書いてる方と一番下に書いてる方に別れますよね。 | ||||||||||||||||
|
投稿日時: 2007-05-17 11:37
大昔のCって定義を上に書いておかないといけなかった筈なんで 慣習として各サブルーチンを先に宣言するスタイルが残っているのかも。 | ||||||||||||||||
|
投稿日時: 2007-05-17 12:59
本題ネタじゃなくて申し訳ないですが、ここだけ。 C は、呼び出し時点より前に宣言(または定義)がある場合(前方参照)は、その宣言のとおりに、そうではない場合は、int func( ... )と仮定して呼び出します。(現行の Pure C でも通ります。がワーニングでると思いますw)。 C++は、このあいまいな定義を認めていないので、呼び出し時点より前に宣言も定義もなければ、エラーとして扱います。 JavaやC#などでは宣言(はそもそもない)や定義がどこにあってもよい事になっています。 ちなみに、宣言は int func( int ); という関数の形を宣言したもの 定義は int func( int a ) { return a; } のように中身もあるものを指します。 #多分、C系言語の用語だと思うので余計ですが一応補足 _________________ // とっちゃん(高萩 俊行)@わんくま同盟 // とっちゃん’Blog // MS-MVP for Developer Tools - Visual C++ // WindowsInstallerの話題はhttp://www.freeml.com/msiまで |