0

友人がオンラインのScalaコースをやっていて、これを共有しています。

# Write a recursive function that counts how many different ways you can make
# change for an amount, given a list of coin denominations. For example, there
# are 3 ways to give change for 4 if you have coins with denomiation 1 and 2:
# 1+1+1+1, 1+1+2, 2+2.

あなたが出席していてまだ解決策に取り組んでいるなら、これを読まないでください！

（免責事項：私のPythonソリューションが間違っている場合でも、コースに参加している場合は、何らかの方法であなたの思考に影響を与えたくありません！学習をもたらすのは思考だけではないでしょう。 「解決」...）

それはさておき...

Scalaチョップがないので、Pythonで試してみようと思いました（私自身はコースに参加していません。PythonとJavaの学習に興味があり、練習するための「ドリル」を歓迎します）。

これが私の解決策です。可能な限りコンパクトな表記法を使用してJavaに移植したいと思います。

def show_change(money, coins, total, combo):
  if total == money:
    print combo, '=', money
    return 1
  if total > money or len(coins) == 0:
    return 0
  c = coins[0]
  return (show_change(money, coins, total + c, combo + [c]) +
    show_change(money, coins[1:], total, combo))

def make_change(money, coins):
  if money == 0 or len(coins) == 0:
    return 0
  return show_change(money, list(set(coins)), 0, [])

def main():
  print make_change(4, [2, 1])

if __name__ == '__main__':
  main()

質問

  • 上記をJavaでどれだけコンパクトにして、JDKの外部のライブラリを使用できるようにすることができますか？

自分で移植してみましたが、非常に冗長になり、いつもの「もっと良い方法があるはず」と思いました！

ここに私の試み：

import java.util.ArrayList;
import java.util.List;
import com.google.common.collect.Lists;
import com.google.common.primitives.Ints;
public class MakeChange {
  static int makeChange(int money, int[] coins) {
    if (money == 0 || coins.length == 0) {
      return 0;
    }
    return showChange(money, Ints.asList(coins), 0, new ArrayList<Integer>());
  }
  static int showChange(int money, List<Integer> coins, int total,
      List<Integer> combo) {
    if (total == money) {
      System.out.printf("%s = %d%n", combo, total);
      return 1;
    }
    if (total > money || coins.isEmpty()) {
      return 0;
    }
    int c = coins.get(0);
    List<Integer> comboWithC = Lists.newArrayList(combo);
    comboWithC.add(c);
    return (showChange(money, coins, total + c, comboWithC) + showChange(money,
        coins.subList(1, coins.size()), total, combo));
  }
  public static void main(String[] args) {
    System.out.println(makeChange(4, new int[] { 1, 2 }));
  }
}

具体的には、私が非常に嫌いなのは、要素が追加されたリストのコピーを渡すためだけに、以下のことを実行する必要があることです。

    List<Integer> comboWithC = Lists.newArrayList(combo);
    comboWithC.add(c);

Javaがいかにコンパクトで読みやすいかを教えてください。私はまだ両方の言語の初心者です...

4

1 に答える 1

1

実際、ここで行っているほとんどすべてのことは、余分な冗長性なしに、Javaに直接変換できます。

例えば：

def make_change(money, coins):
  if money == 0 or len(coins) == 0: return 0
  return calculate_change(money, list(set(coins)), 0)

明らかなJavaの同等物は次のとおりです。

public static int make_change(int money, int coins[]) {
  if (money == 0 || coins.length == 0) return 0;
  return calculate_change(money, coins, 0);
}

あちこちにいくつかの余分な単語、閉じ中括弧のための余分な行、そしてもちろん明示的なタイプ…しかしそれを超えて、大きな変化はありません。

もちろん、より多くのPythonおよびJavariffic（同等の単語は何ですか？）バージョンは次のようになります。

def make_change(money, coins):
  if money == 0 or len(coins) == 0: 
    return 0
  return calculate_change(money, list(set(coins)), 0)

明らかなJavaの同等物は次のとおりです。

public static int make_change(int money, int coins[]) {
  if (money == 0 || coins.length == 0) {
    return 0;
  }
  return calculate_change(money, coins, 0);
}

したがって、Javaは1つの余分な閉じ中括弧と数文字の空白を取得します。まだ大したことではありません。

すべてをクラス内にmain配置し、メソッドに変換すると、さらに約3行が追加されます。[2, 1]リテラルとして使用する代わりに明示的な配列変数を初期化するのはもう1つです。またSystem.out.println、は数文字長くprint、lengthは3文字長くlen、各コメントは1文字//ではなく2文字になり#ます。しかし、私はそれのどれもあなたが心配していることではないかと思います。

最終的に、トリッキーな行は全部で1つあります。

return (calculate_change(money, coins, total + c, combo + [c]) +
    calculate_change(money, coins[1:], total, combo))

Javaint coins[]には、「現在の配列の末尾を持つ新しい配列を教えてください」と言う方法がありません。start最も簡単な解決策は、追加のパラメーターを渡すことです。

public static int calculate_change(int money, int coins[], int start, int total) {
    if (total == money) {
        return 1;
    }
    if (total > money || coins.length == start) {
        return 0;
    }
    return calculate_change(money, coins, 0, total + coins[start]) +
        calculate_change(money, coins, start + 1 total);
}

実際、ほとんどすべてが簡単にCに変換できます。JavaやPythonのように実行時に計算することはできないため、配列の長さについてさらに別のパラメーターを渡す必要があります。

あなたが不満を言っている一行は、もう少し考えてみる価値のある興味深い点です。Pythonでは、次のようになります（事実上）：

comboWithC = combo + [c]

Javaのリストでは、これは次のとおりです。

List<Integer> comboWithC = Lists.newArrayList(combo);
comboWithC.add(c);

これはより冗長です。しかし、それは意図的なものです。JavaList<>はこのように使用されることを意図していません。小さなリストの場合、すべてをコピーすることは大したことではありませんが、大きなリストの場合、パフォーマンスが大幅に低下する可能性があります。Pythonlistは、ほとんどの場合、小さなリストを処理していて、それらをコピーすることはまったく問題ないという前提に基づいて設計されているため、作成するのは簡単です。JavaListは、巨大なリストを扱っていることがあり、それらをコピーすることは非常に悪い考えであるという前提に基づいて設計されているため、コードで本当にそうしたいことを明確にする必要があります。

理想的な解決策は、リストをコピーする必要のないアルゴリズムを使用するか、その方法でコピーするように設計されたデータ構造を見つけることです。たとえば、LispまたはHaskellでは、デフォルトのリストタイプがこの種のアルゴリズムに最適であり、オンラインで見つけることができるはずの「JavaのLispスタイルリスト」または「Java短所」のレシピが約69105あります。（もちろん、Pythonのような「addToCopy」メソッドを追加したリストの周りに簡単なラッパーを書くこともできますが__add__、それはおそらく正しい答えではありません。慣用的なJavaを書きたい、または他の多くのJavaの代わりにJavaを使用する理由JVM言語？）

于 2012-09-27T23:00:02.467 に答える