古典的アルゴリズム:100ドア謎を解く

9864 ワード

functional lisp picolisp テキストリンク

今日は我々について話します100 Doors ロゼッタコードプロジェクトのタスク.これは多くの制御フロー要素とset -機能を議論yesterday .
あなたがPicolispに新しいならば、記事を読むことは役に立つかもしれませんControl Flow functions
ファースト.

仕事

There are 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, visit every door and toggle the door (if the door is closed, open it; if it is open, close it). The second time, only visit every 2nd door (door #2, #4, #6, ...), and toggle it. The third time, visit every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.

Answer the question: What state are the doors in after the last pass? Which are open, which are closed?

簡単でスマートな実装があります.簡単なものから始めましょう.

ドアの定義
我々が簡単な方法でそれを実装するならば、我々は100回我々の「ドア」ルートをとる必要があります.それぞれのドアには2つの可能な状態があります.これを翻訳することができますNIL and T . 我々は相互作用する各ドアについては、我々はからのステータスを交換T to NIL と逆も同様です.
まず、100の要素を持つ「ドア」というリストを定義しましょうNIL . これは、関数を使用して行うことができますneed :

: (setq Doors (need 100))
-> (NIL NIL NIL NIL NIL ...... NIL NIL NIL)

第1ドアを切り替える
つのドアの状態を変更しようとしましょう.間を切り替えるNIL and T 単純な否定であり、私たちはnot 関数.このように:

(set Doors (not (car Doors)))

(car Doors) リスト内の最初の項目の値を返します.NIL or T . 反転後not , 我々は再び1の最初の項目に設定Doors .
あなたは、何かを書くように誘惑されるかもしれません(set (car Doors) ...) 最初の要素を得るにはset 既に最初の項目に対応します.これがあなたのために混乱するならば、チェックしてくださいpost about the set function .

3ドアごとに切り替える
現在、我々は現在1つのドアを変える方法です.しかし、どのようにすべてのドアを変更するには、例えば、分割3?
我々が「足の上で」それをするならば、我々のアルゴリズムは以下のようです

三軒歩く

我々の前にあるドアをトグルする

繰り返し

ドアをトグルした後、それらのドアだけがリストに残っているならば、我々はすでに「まだされていない」それはよいでしょう.それは、我々は最初からアイテムを削除することによってリストを短縮することを意味します.これはまさに機能とはnth を行う

: (setq L (1 2 3 4 5))
-> (1 2 3 4 5)
: (nth L 3)
-> (3 4 5)
: (cdr (nth L 3))
-> (4 5)

Picolispへの「足」アルゴリズムの翻訳

(nth Doors 3) --> 「三軒歩きます」

(set Doors (not (car Doors))) --> 「ドアの前でドアをトグル」

?? --> "繰り返し"

我々が全体を下ろすまで、我々はこのステップを繰り返したいですDoors リスト.しかし、どのように我々はそれをチェックできますか?我々は100に達したときに我々に指示するカウンタを置くことができました.しかし、我々が明日200のドアを歩く必要があるならば、どうですか?
幸いにも、より柔軟な選択肢がありますfor これらの種類のケースのために設計されたループ.読みましょうdocumentation :

(for (sym 'any1 'any2 [. prg])) -> any

In the third form, the value of sym is saved, and sym is bound to any1. [...] While the condition any2 evaluates to non-NIL, the body is repeatedly executed and, if prg is given, sym is re-bound to the result of its evaluation.

複雑に聞こえるので、一歩一歩試してみましょう.
簡単な言葉では、3ドアを歩いて、仕事をし、ドアがないまで歩き続けます.毎回3ドアを歩きますDoors -リストは短くなるはずです.
だから、まずsym to any ドキュメントのように、シンボルを使いますD にバインドし、Doors . 最初の2つのドアは私たちにとって興味がないので、我々はすでに3番目のドアで始めることができます:

:  (for (D (nth Doors 3)  ...

次のステップとして、我々は非-NIL コンディションany2 ). このため、残りのドアのリストを使うことができます.D . ドアがないならば.D is NIL そして、ループは止まります.

:  (for (D (nth Doors 3) D  ...

我々が必要とするすべては、方法を定めることですD 各ステップの後のように見えるし、答えは簡単です:我々は3つのドアを歩いたので、それは現在のはずですD リストマイナス3ドア、右?これは( cdr (nth D 3)) .
だから、これは我々のフルですfor トグルを含むループ

(for (D (nth Doors 3)  D  (cdr (nth D 3)))
   (set D (not (car D))) )

それは複雑に見えますが、それは基本的です.

ドアをすべて切り換える
残りは簡単です!明らかに我々はすべてのサードドアだけをトグルしたくない.実際には、1から100までのすべての数字を繰り返します.私たちはfor ループ再び、しかし、今度はより単純なもの.反復パラメータを呼び出しましょうI 最後のプログラムを入手します.

(let Doors (need 100)
   (for I 100
      (for (D (nth Doors I)  D  (cdr (nth D I)))
         (set D (not (car D))) ) )
   (println Doors) )

結果:

(T NIL NIL T NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL T)

それだ!最終的なスクリプトをダウンロードすることができますhere .

スマートウェイ
我々は解決策を見つけたが、残念ながら非常にスマートなものではなかった.なぜ?私たちが座って、もう一度それについて考えるならば、我々は多くのウォーキングを保存することができたので.
プログラムのプリントを見ましょう.次のドアはT 他のすべてはNIL : 第1 , 4 , 9 , 16 , 25 ,…100 .
よく?右:すべてのオープンドアは正方形の数字です.
したがって、実際に我々がする必要があるすべての正方形のドアを開いている、それはそれです.必要はありません閉じる閉じて開いて閉じるの残りの部分.

これは魔法ですか.
しかし、なぜ正方形のドアだけ開いている?それを体系的に考えましょう.

ドアが開いている場合は、何度も訪れています.

たとえば、一度だけ訪れたら、それは開かれて、二度と閉じられません.2回訪れたら一度開けて一度閉じます.など.

ドアが訪れる回数は、除数の数に等しい.

例えば、最初のドアは一度だけ(第1ラウンドで)訪問されます.第6のドアは、第1、第2、第3、第6ラウンドで訪問されます6=1*2*3 ). 第17のドアは、最初と17回目のラウンドで訪問されます.

角の数だけが除数の偶数を持ちます.
これは少しより明白であるが、まだ真実です.任意の数z を表すx*y . 素数については1*z . 正午のドアは正確に2回訪問されるので、それは閉じられます.
非素数についてはどうですか?この場合、解決策がありますx*y どちらの数字もz . 例えば21 = 21*1 = 3*7 . ドア21は、第1、第3、第7、第21番で訪問される.
ただし、z 正方形の数です、そして、我々は2つの異なるx*y , でも、x*x . 私たちは“一度だけ”そこに歩く必要があります.

スクリプトのスマートバージョン
明らかにこの1つのコードはより簡単です.我々は1から10まで(100のルートである)を繰り返すだけで、すべての正方形の数字を0に設定する必要があるだけですT .

(let Doors (need 100)
   (for I (sqrt 100)
      (set (nth Doors (* I I)) T) )
   (println Doors) )

それだ!

メイクイットプリティ
最後に、書式設定にもう少し努力しましょうNIL NIL NIL NIL -出力は本当に楽しい読むことです.リストの上で繰り返して、開いたドア番号だけを印刷しなければなりません.
反復のために、我々はもう一つの便利なバリエーションを使いますfor ループ-私たちは2つのパラメータを取る1つを使用します:リスト要素のインデックスの1つのカウンタとリスト項目の別の1つ.ドキュメントから:

``(for sym2 . sym) 'lst ['any]) -> any

(...) If sym2 is given, it is treated as a counter variable, first bound to 1 and then incremented for each execution of the body.

選びましょうN カウンタ変数D リストイテレータとして

`

      (for (N . D) Doors

`

各項目については、チェックD 非NIL . これは簡単にできますwhen . 非NIL リストpostionsは、新しいリストに入れられなければなりません.これはmake (...) link 関数.

`   

(make

   (for (N . D) Doors

      (when D (link N)) )  ) 

`

現在、これはリストを返します、しかし、我々はまた、変数L スクリプトから印刷可能にするには、次の手順に従います.
`



   (let L

      (make

         (for (N . D) Doors

            (when D (link N)) )  )

   (println L) )    )





which prints  1 4 9 16 25 36 49 64 81 100 `. 




Finished! 

The final script can be downloaded here.





  
  
  Sources



Cover pic: Photo by Dil on Unsplash


http://www.rosettacode.org/wiki/100_doors#PicoLisp


https://software-lab.de/doc/index.html



                                    
                                    
                                    
                                    
                                

                                

                                
                                    

                                        


                                            
                                            Reference
                                            

                                            この問題について(古典的アルゴリズム:100ドア謎を解く), 我々は、より多くの情報をここで見つけました
                                                
                                                https://dev.to/miatemma/classic-algorithms-solving-the-100-doors-riddle-2m9e
                                            
                                            
                                            
                                            
                                                テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
                                            


                                            
                                            
                                                
                                                    Collection and Share based on the CC Protocol



                            
                                    
                                        

                                        [伯俊]AをBに変えるjava
                                

                                    [伯俊]回文は回文じゃない!!java