フェリータスク

Toasterには、プログラマーとしての考え方を学ぶ方法に関する質問が時々あります。 1年前、娯楽のために、私は誰もがよく知っている問題を解決するプログラム、つまりオオカミ、ヤギ、キャベツに関するパズルを書くことにしました。 川を渡るパズルとして知られる英語の情報源。



この投稿では、タスクからアルゴリズムによる解決までの思考プロセスの例を紹介します。



オブジェクト指向のパラダイムが脳に長期的に影響するため、私に最初に起こったのは、すべてのエンティティ、タスクの参加者がクラスを書くことでした。 問題指向プログラミングとそのすべて。 しかし、私はPascalの古い教科書を思い出し、機能と手順の概念で操作していました。



タスクをマシンが理解できるプレーンに変換するには、そのソリューションに関係のないタスクのコンテキストの部分を取り除く必要があります。



数字で表現できないものはすべて重要ではありません。 このキャベツまたはボールは重要ではありません。参加者が4人いることが重要です。 それらの前の川または山-それは重要ではありません、このタスクの参加者ができる2つの場所があります。 ボートで、彼らは交差するか飛行機で-それは重要ではありません、彼らは1つのポイントから別のポイントへ、またはその逆に移動できます。



完全に抽象化すると、条件は次のようになります。

• 3つの要素と1つの特別な要素のセットがあります。
• 要素の禁止された組み合わせがあります（特別な要素がない場合）
• 特別な要素との組み合わせでは、すべての組み合わせが許可されます。
• 禁止された要素の組み合わせが形成されないように、すべての要素をある場所から別の場所に転送する必要があります。
• この場合、一度に1つの要素のみを転送できます。 すなわち 一方向に2回転送することはできません。 -Dr_Dashに注目してくれてありがとう。

要素とその組み合わせを区別するには、それらに識別子を与える必要があります。 機械は数字で最もよく機能します-数字で表します。 要素を組み合わせたい。 数値を結合するとは、それらに対して算術演算を行うことを意味します。



次に、数値の合計が一意に組み合わせを示すように、個々の値をエンコードします。



0- 誰も

1- P農民

2- Gヤギ（ヤギ）

4- Cキャベツ（キャベツ）

8- Wウルフ



ここの文字はニーモニック専用であり、負荷がかかりません



農民が番号1で示されているという事実は重要です。 このため、農民との「海岸構成コード」は常に奇妙です。 したがって、どちら側にあるかを理解することが可能になります。



両方の銀行で可能な組み合わせを表の形式で書き留め、Xの銀行に沿った参加者の分布の許容可能なオプションに注意してください。







沿岸の構成の可能な組み合わせは常に合計で15になりますが、すべてが有効であるわけではありません。



テーブル形式の視覚的表示から、許容可能な状態にのみ移行して、テーブルのあるコーナーから別のコーナーに移動する必要があることが明らかになります。



左岸と右岸はタスクにとって重要ではありません。 つまり、例11の構成コードを指定すると、同じ銀行には小作人、ヤギ、オオカミがいると言います。 反対側のそのキャベツは特に示される必要はありません。 両方の銀行の合計が15を与えるので、他の銀行では4-キャベツです。



私たちの状態は水中の石であり、石から石にジャンプするとき、私たちは一方の端からもう一方の端まで移動しなければならないことを想像してください。 チューリングマシンのテープを思い出しますよね？

$$

$$\ begin {array} {| l | l | l | l | l | l | l | l | l | l | l | l | l | l | l | l | l |} \ hline \ blacktriangledown_ {0}＆\ times_ {1}＆\ bullet＆\ bullet＆\ bullet＆\ times_ {5}＆\ times_ {6}＆\ bullet＆\ bullet＆\ times_ {9}＆\ times_ {10}＆\ bullet＆\ bullet＆ \ bullet＆\ times_ {14}＆\ blacktriangle_ {15} \\ \ hline \ end {array}$$

テープでは、開始は右側の黒い三角形で示され、終了は左側の逆三角形で示されます。 可能な中間状態は黒い点で示されています。 無効な状態には、×印が付いています。



受け入れ可能な状態にのみ移行できます。 また、問題の状況から、農民は常に運動に参加しており、ボートは最大2人まで収容できることがわかっています。 したがって、数字1（農民）、3（農民とヤギ）、5（農民とキャベツ）、9（農民とオオカミ）で操作できます。



状態15から開始すると、一方の銀行のすべてが唯一の可能な次の状態である場合、12になります。状態12から、農民をもう一方の銀行に戻す以外に選択肢はありません。 状態13に進みます。ここから、-5（輸送キャベツ）または-9（輸送オオカミ）を作成できます。 -9を実行すると、状態4になりますが、その後に農民を返還する必要があります。 単独で戻すことはできません。そうでない場合は状態5になりますが、ヤギで戻すことができます。 +3、状態7（ヤギキャベツと農民）になります。 ここから、-3（ヤギを避難させる）または-5（キャベツを保存する）を作成できます。 -3は前のアクションのロールバックになるため、-5は残ります。 状態2に進みます。ここからは、+ 1と+9のみを実行できます（+5は前のアクションのロールバックになるため、+ 3は受け入れられない状態です）。



ここで、+ 3は「ヤギが向こう側にいる」（これは人が理解できる説明である）ためではなく、容認できない状態への移行であるため（「説明」は機械にとって理解できる）ため、不可能です。 +1を行います。 状態3に進みます。-3を実行します。 できた



しかし、これが唯一の可能な解決策ではありません。 人がすべての動きを追跡するのは難しいことに注意してください。 マシンには、有効な状態と無効な状態のセット、およびルールのセットがあります。



車に問題のすべての可能な解決策を見つけさせましょう。 解決につながる可能性のあるすべての状態チェーンを見つけます。 言語として再帰とpythonを使用します。



遷移チェーンを保存するには、配列を使用します。 最初の状態は配列15にあります。ファンキーな再帰に渡します。 再帰が終了する条件を定義します。 これは、チェーンの終わりが0のときです。

def f(states): s = states[-1] #   ,   . if s==0: #   print(str(states)) print("END") else: #      ... print(f([15]))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

状態が偶数（反対側の農民）の場合、正符号（+ 1、+ 3、+ 5、または+9）を使用して可能な操作の1つを実行します。



可能な操作ごとに、次の条件を満たしている必要があります。

-それは容認できない状態には至りません、

-テープの最大の正の境界線を超えない

-彼女は私たちがすでにいた状態には至りません。



そのような操作が存在する場合、それを完了し、状態チェーンに新しい状態を追加します。

新しい状態チェーンを再帰機能に渡します。

  if s%2 == 0: for i in [9,5,3,1]: if (s+i not in [1,5,6,9,10,14]) and (s+i<=15) and (s+i not in states): f(states+[s+i])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

条件が奇数の場合、マイナス記号を使用して同じ考慮事項に従います。

  else: for i in [9,5,3,1]: if (si not in [1,5,6,9,10,14]) and (si>=0) and (si not in states): f(states+[si])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

出力では



[15, 12, 13, 4, 7, 2, 3, 0]

END

[15, 12, 13, 8, 11, 2, 3, 0]

END

None







ソリューションでは偶数と奇数が交互になっていることに注意してください。 これは、ある海岸から別の海岸への農民の移動です。 無駄ではありませんが、ユニットとして指定しました。

また、ソフトウェアソリューションの問題の初期条件は、人間が理解できるように、数値とそれらの操作に変わったという事実にも注意を向けます。



誰かがこの記事を参考にするといいのですが。



PS：

誰かがオブジェクト指向のソリューションを持っている場合、パラダイムを比較できるようにコメントで共有してください。