JSは欲張りアルゴリズムを使って、お釣り問題を解決する例を示します。
2089 ワード
本論文の実例はJSが欲張りアルゴリズムを使ってお釣り問題を解決することを述べている。皆さんに参考にしてあげます。具体的には以下の通りです。
前にJS貪欲アルゴリズムはリュックサックの問題を解決します。を紹介しましたが、ここでお釣り問題の解決方法を見てみます。
実際の生活では、頻繁にお釣りの問題が発生していますが、数に限りがない額面が20,10,5,1のコインがあると仮定しています。端数を求めて、お釣りの方案を求めて、要求を与えます。一番少ない数の硬貨を使います。
このような問題に対して、欲張りアルゴリズムはお釣りをする時に、いつもお釣りができるコインの最大値を選びます。例えば、お釣りが必要な場合は、お釣りは20+5で、10+10+5ではありません。
貪欲アルゴリズムはよくあるアルゴリズムの一つです。それは簡単で実行しやすいので、貪欲な策略を作るのは難しくないです。
残念なことに、それは証明が必要で、本当にテーマの計算方法に使えるようになります。
例えば、お釣りを提供する場合は11、5、1、15をお釣りします。
欲張りアルゴリズムを使ってお釣りをする方式は11+1+1+1で、5+5+5と5枚のコインを5枚必要とします。コインは3枚だけ必要です。
もっと多くのJavaScriptに関する内容に興味がある読者は、当駅のテーマを見ることができます。「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript数学演算の使い方のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。
前にJS貪欲アルゴリズムはリュックサックの問題を解決します。を紹介しましたが、ここでお釣り問題の解決方法を見てみます。
実際の生活では、頻繁にお釣りの問題が発生していますが、数に限りがない額面が20,10,5,1のコインがあると仮定しています。端数を求めて、お釣りの方案を求めて、要求を与えます。一番少ない数の硬貨を使います。
このような問題に対して、欲張りアルゴリズムはお釣りをする時に、いつもお釣りができるコインの最大値を選びます。例えば、お釣りが必要な場合は、お釣りは20+5で、10+10+5ではありません。
貪欲アルゴリズムはよくあるアルゴリズムの一つです。それは簡単で実行しやすいので、貪欲な策略を作るのは難しくないです。
残念なことに、それは証明が必要で、本当にテーマの計算方法に使えるようになります。
<script>
var money= [20,10,5,1];
/*
* m[]: ,
* n:
*/
function greedyMoney(m,n){
for(var i=0;i<m.length;i++){
while(n>=m[i] && n>0){
document.write(m[i]+" ");
n = n-m[i];
}
}
document.write("<br>");
}
greedyMoney(money,73);
greedyMoney([25,10,1],63);
</script>
結果は:
20 20 20 10 1 1 1
25 25 10 1 1 1
説明が必要なのは、いくつかの場合、お釣りの問題は貪欲なアルゴリズムを使って全体の最適解を得ることができません。その結果は最良解のよく似ているだけかもしれません。例えば、お釣りを提供する場合は11、5、1、15をお釣りします。
欲張りアルゴリズムを使ってお釣りをする方式は11+1+1+1で、5+5+5と5枚のコインを5枚必要とします。コインは3枚だけ必要です。
もっと多くのJavaScriptに関する内容に興味がある読者は、当駅のテーマを見ることができます。「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript数学演算の使い方のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。