私はProject Eulerの問題31を見ています。これは、1p、2p、5p、10p、20p、50p、£1（100p）、£の任意の数のコインを使用して£2を作成する方法はいくつあるかを尋ねます。 2（200p）。
Scalaにあるような再帰的な解決策があります（Pavel Fatinの功績）
def f(ms: List[Int], n: Int): Int = ms match {
case h :: t =>
if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
case _ => 0
}
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
また、十分に高速で実行されますが、比較的効率が悪く、f関数を約560万回呼び出します。
動的にプログラムされたJavaで他の誰かの解決策を見ました（ポルトガルのwizemanへのクレジット）
final static int TOTAL = 200;
public static void main(String[] args) {
int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
int[] ways = new int[TOTAL + 1];
ways[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= TOTAL; j++) {
ways[j] += ways[j - coin];
}
}
System.out.println("Result: " + ways[TOTAL]);
}
これははるかに効率的であり、内部ループを1220回しか通過しません。
Arrayオブジェクトを使用してこれを多かれ少なかれ逐語的にScalaに変換することはできますが、不変のデータ構造を使用してこれを行う慣用的な機能的な方法はありますか？
私は、Listおそらく間違った方法でそれに近づいていると判断する前に、再帰的に更新しようと試みて行き詰まりました。
データのリストの一部が前の要素に基づいて計算されるときはいつでも、私はStream再帰を考えます。残念ながら、そのような再帰はメソッド定義や関数の内部では発生しないため、関数をクラスに変換して機能させる必要がありました。
class IterationForCoin(stream: Stream[Int], coin: Int) {
val (lower, higher) = stream splitAt coin
val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b })
}
val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>
new IterationForCoin(stream, coin).next
} last
定義lowerとhigher必要はありません-私は簡単に置き換えることができstream take coinそしてstream drop coinこのように、私はそれが少し明確に（そしてより効率的）だと思います。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加