アルゴリズム作成の命令でブルートフォースをどのように解釈するのですか？

Question

私のハングアップは、以下の問題点は、ブルートフォードが意味するものを解釈していることであり、私は単にそれが何を求めているのか分かっていれば、この問題のコードを設計できると思います。 ：ここでは/

は命令です：

[15マーク]彼/彼女が は貪欲知らない場合、プログラマは、課題3で変更を行うの問題のために出てくるかもしれないソリューションのどのような種類アルゴリズムは全くですか？この 問題を解決する1つの方法は、徹底的な検索またはブルートフォースアプローチです。この アプローチでは、すべての可能な回答をテストし、 答えを見つけるために、与えられた問題に対して 正しい解決策を比較します。特に

は、変更をマーキングの問題のため、現金を与え 量をセントで、私たちはまず、 最大の番号を（必ずしもできるだけ少ないコインを使用していない）を正しく変更 を作るのいずれかの方法を見つけることができます私たちが使用できるtoonies、looniesなどの 6レベルのループを実行して、すべての可能性のある組合せのコインを のコインで繰り返します。これは、前に計算した最大数を上限として、ソリューション内の対応するコインについて です。より正確には、 最も外側のループでは、1 toonie、2 toonies、...、計算されたトーニーの最大数を使用するソリューションを反復します。 2番目の 最も外側のループでは、1 loonie、2 loonies、 ...を使用するソリューションを繰り返し、計算されたlooniesの最大数（ のtooniesの数は最も外側のループで決定されます）など。 内の最も内側のループでは、各ソリューションについて、指定された金額に対して 正しい解決策であるかどうかをチェックします。そうであれば、 よりも少ないコインを使用しているかどうかを確認します。 例えば

現金量が200である場合、我々は せいぜい1 toonie、2 loonies 8四半期、20のダイム、任意の溶液中に40枚の硬貨と 200ペニーを使用することができます。 （それぞれの解決策には、 のコインの番号である6つの数字が使用されています. ,0,0,0,0,0,0,1,0,0,0,0,0,1 ; 0,0,0,0,0,2; ...、0,0,0,0,0,200; 0,0,0、 ,0,1,0; 0、0、0、0,1,1; 0,0,0,0,0,1,2、...、0,0,0,0,1、 200; 0,0,0,0,2,0; 0、0、0、2、1; ....この特定の の例では、テストするソリューションは、1 toonie、2 loonies、8 quarter、20 dimes、40 nickel、200 penniesを使用する必要があります。

それは、このブルートforcenessによって何を意味するのか？私はそれがどのように各種類の硬貨について可能な最大数を見つけるのかを理解していますが、これはどのようにして人が得なければならない各種類の硬貨の数を解決するために使用されますか？

Answer 1

ブルートフォースソリューションとは、すべての解決策を試すことです。多くの問題では、すべてのソリューションを試すことは非常にコストがかかります。これは、ブルートフォースと呼ばれています。なぜなら、問題に対する特別な洞察を必要としないからです。

たとえば、ロックを選択していた場合は、あらゆるキーを可能にしてすべてを試すことができます。当然、これには長い時間がかかります。

brute force searchについては、このウィキペディアの記事を読むことができます。

割り当てからの元の問題の説明がなければ、ブルートフォースの解説を詳しく説明するのは難しいですが、試してみます。 200現金の場合、一般的な手順は、現金200個までのすべての可能な組合せを生成し、それらの正当性をチェックすることです。

問題が「はい/いいえ」の問題（解決策が成功するかどうか）に問題がある場合は、答えが1つだけ必要です。あなたが解決策を見つけたら、あなたは止めることができます。あなたの問題に何らかの種類のスコア（例えば、セールスマンの問題）が含まれていて、最良の答えが必要な場合は、すべてのソリューションを試す必要があります。

一般的に、問題の特定のインスタンスにはブルートフォースを適用します。問題の特定のインスタンスが「200現金」の場合、可能なすべての解決策を200現金のみに生成します。次回、あなたの問題が「10現金」の場合、10の現金問題に対するすべてのソリューションを生成してテストします。ブルートフォースはソリューションを生成する効率的な方法ではないことを覚えておいてください。しかし、問題の場合はブルートフォースが完了したら最良の答えを見つけたことを保証することができます。

ほとんどの問題には、より効率的な最適解を生成する方法があることに注意してください（例：ブランチ・アンド・バウンドはセールスマンのタイプの問題を解決するために力量よりも優れています）。

---

最後の段落では、現金の最大量を知っていれば、あなたはあなたに200以上の現金を与えるソリューションを生成するかテストしていないことを確認することができますと言っています。これを行う簡単な方法は、200個の現金があるローン数を計算し、それ以上の数を使用するソリューションを生成しないことです。

ソリューションのあなたの世代をバインドするより良い方法は、あなたが常に現金の適切な量まで追加することを確実にするために、徐々に小さくコイン用の番号を設定することです：

for(0 to (cash % valueof(toonies)) as t) { 
    set cash_after_toonies to be (cash - valueof(t * toonies)) 

    for(0 to (cash_after_toonies % valueof(loonies)) as l) { 
    set cash_after_loonies to be (cash_after_toonies - valueof(l * loonies)) 

    for(0 to (cash_after_loonies % valueof(quarters)) as q) { 
     set cash_after_quarters to be (cash_after_loonies - valueof(q * quarters) 

     for(0 to (cash_after_quarters % valueof(dimes)) as d) { 
     set cash_after_dimes to be (cash_after_quarters - valueof(d * dimes)) 

     for(0 to (cash_after_dimes % valueof(nickels)) as n) {   
      set cash_after_nickels to be (cash_after_dimes - valueof(n * nickels)) 

      set p = cash_after_nickels in pennies 
      check_for_correctness(l,t,q,d,n,p); 
     } 
     } 
    } 
    } 
} 

Answer 2

強引なアプローチは、すべての可能な試みどのソリューションが正しいかを確認するソリューションです。例えば、強引にパスワードを解読すると、AAAAAA、AAAAAB、...などが試されます。

あなたの例では、彼は正しい変更の解決策を得るために、可能なコインのすべての組み合わせを試すように求めています。唯一の難しい部分は、そのコインだけを使って変更した場合よりも、1つ以上のコインを持つべきではないということです。

たとえば、最大で1つのtoonieがあることがわかっているので、200centの請求書に変更を加える（2 toonies、.....）必要はありません。

コインの各組み合わせは、正しい変更量であるかどうかを確認することができます。コインの数を数えれば、どのコインの組み合わせを使用するかを見つけることができます。