고전 알고리즘: 백문의 수수께끼 풀기
set을 사용했다.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번의 문 노선을 걸어야 한다.모든 문은 두 가지 가능한 상태가 있는데, 그것이 바로 '열기' 또는 '닫기' 이다.
NIL과 T으로 전환할 수 있습니다.우리가 그와 상호작용하는 모든 문에 대해 우리는 상태를 T에서 NIL으로 교환할 것이다. 반대로도 마찬가지다.우선, 'Doors' 라는 목록을 정의합니다. 100개의 요소가 있고, 각 요소는
NIL으로 초기화됩니다.함수 need을 사용하여 다음을 수행할 수 있습니다.: (setq Doors (need 100))
-> (NIL NIL NIL NIL NIL ...... NIL NIL NIL)
첫 번째 문으로 전환
우선 문 한 짝의 상태를 바꾸어 봅시다.
NIL과 T 사이를 전환하는 것은 간단한 부정이다. 우리는 not 함수로 실현할 수 있다.이렇게:(set Doors (not (car Doors)))
(car Doors)은 목록의 첫 번째 값으로 NIL 또는 T을 되돌려줍니다.not으로 반전시킨 후 Doors의 첫 번째 항목으로 다시 설정했습니다.첫 번째 요소를 가져오려면
(set (car Doors) ...)과 같은 코드를 작성하려고 시도할 수 있지만, 이것은 잘못된 것입니다. 왜냐하면 set이 첫 번째 프로젝트를 해결했기 때문입니다.만약 이것이 당신을 곤혹스럽게 한다면, post about the set function을 보십시오.세 개의 문마다 한 번씩 전환한다
이제 문을 어떻게 바꾸는지 봅시다.그러나 어떻게 모든 문, 예를 들어 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)
(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
symis saved, andsymis bound toany1. [...] While the conditionany2evaluates to non-NIL, the body is repeatedly executed and, ifprgis given,symis re-bound to the result of its evaluation.
복잡하게 들리니까 한 걸음 한 걸음 시도해 봅시다.
간단하게 말하자면, 우리는 문이 남지 않을 때까지 세 개의 문을 걸어서 우리의 일을 완성하고, 계속 걷고 싶다.매번 우리가 세 개의 문을 걸을 때마다 우리의
Doors - 명단은 짧아진다.그래서 우선'귀속
sym에서 any까지'를 문서에서 알려준 대로 하겠습니다.우리는 기호 D을 사용하여 그것을 Doors으로 귀속시켰다.앞의 두 개의 문은 우리에게 결코 흥미롭지 않기 때문에 우리는 세 번째 문부터 시작할 수 있다.: (for (D (nth Doors 3) ...
NIL조건(any2)이 있다.이를 위해 우리는 남은 문 목록 D을 사용할 수 있다.더 많은 문이 없으면 D은 NIL이고 순환도로가 멈춘다.: (for (D (nth Doors 3) D ...
D이 한 걸음 한 걸음 뒤에 어떻게 해야 하는지만 정의할 수 있다. 답은 간단하다. 우리는 세 개의 문을 갔기 때문에 현재의 D 목록에서 세 개의 문을 빼야 한다. 그렇지?이는 ( 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)
총명한 방법
우리는 확실히 해결 방안을 찾았지만 불행하게도 이것은 매우 현명한 해결 방안이 아니다.왜 안 해요?만약 우리가 앉아서 다시 생각해 본다면, 우리는 많은 보행 시간을 절약할 수 있기 때문이다.
우리 프로그램의 프린트를 보여 주세요.우리는 아래의 문이
T이고 기타 모든 문이 NIL:1번, 4번, 9번, 16번, 25번인 것을 보았다...100좋아요?오른쪽: 모든 열린 문은 정사각형입니다.
그래서 사실 우리가 해야 할 일은 정사각형의 문을 열고 이렇게 하는 것이다.나머지 부분은 열 필요가 없습니다.
이게 마법인가요?
그런데 왜 정사각형 문만 열려 있죠?우리 체계적으로 생각해 봅시다.
6=1*2*3)에서 6번째 문을 둘러본다.1차와 17차 중 17번째 문을 참관하다.제곱수의 제수만 고르지 않다.
이것은 그다지 뚜렷하지는 않지만 사실이다.어떤 숫자든
z은 x*y으로 표시할 수 있다.질수에 대해서는 1*z이다.소수문은 마침 두 번 방문했기 때문에 닫혔다.비소수는?이러한 상황에서
x*y의 해결 방안이 있는데 그 중 두 가지 숫자는 모두 z과 같지 않다.예: 21 = 21*1 = 3*7.1, 3, 7, 21라운드에서 21번 문을 참관하세요.그러나 만약에
z이 제곱수라면 우리는 두 개의 다른 x*y을 얻지 못하고 x*x만 얻을 수 있다.우리는 단지 한 번만 가면 된다.우리 스크립트의 스마트 버전
분명히 이 코드는 더 간단하다.우리는 1에서 10(100의 뿌리)으로 교체한 다음에 모든 제곱수를
T으로 설정하면 된다.(let Doors (need 100)
(for I (sqrt 100)
(set (nth Doors (* I I)) T) )
(println Doors) )
예쁘다
마지막으로 포맷에 더 많은 노력을 하겠습니다. 왜냐하면 우리의
NIL NIL NIL NIL - 출력은 정말 읽기 어렵기 때문입니다.우리는 반드시 목록을 반복해서 훑어보고, 문을 여는 번호만 출력해야 한다.교체에 있어서, 우리는
for 순환의 또 다른 편리한 변체를 사용할 것이다. 이번에는 두 개의 파라미터가 있는 변수를 사용할 것이다. 하나는 카운터가 목록 요소의 인덱스에 사용되고, 다른 하나는 목록 항목에 사용된다.파일에서 다음을 수행합니다.``(for sym2 . sym) 'lst ['any]) -> any
(...) If
sym2is 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 명단의 게시물은 새로운 명단에 넣어야 한다.이것은 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 prints1 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
이 문제에 관하여(고전 알고리즘: 백문의 수수께끼 풀기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/miatemma/classic-algorithms-solving-the-100-doors-riddle-2m9e
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
