프로그램 1.4.4 자기 회피 무작위 보행 (selfavoid.py)
import random import sys import stdarray import stdio n = int(sys.argv[1]) trials = int(sys.argv[2]) deadEnds = 0 for t in range(trials): a = stdarray.create2D(n, n, False) x = n // 2 y = n // 2 while (x > 0) and (x < n-1) and (y > 0) and (y < n-1): # 궁지에 몰렸는지 확인하고 나서 무작위로 다음 길을 선택한다. a[x][y] = True if a[x-1][y] and a[x+1][y] and a[x][y-1] and a[x][y+1]: deadEnds += 1 break r = random.randrange(1, 5) if (r == 1) and (not a[x+1][y]): x += 1 elif (r == 2) and (not a[x-1][y]): x -= 1 elif (r == 3) and (not a[x][y+1]): y += 1 elif (r == 4) and (not a[x][y-1]): y -= 1 stdio.writeln(str(100*deadEnds//trials) + '% 궁지에 몰림')
n trials deadEnds a[][] x, y r |
격자 크기 시도 횟수 궁지에 몰린 시도 횟수 교차로 현재 위치 [1, 5) 범위의 난수 |
이 프로그램은 명령 줄 인수로 정수 n
과 trials
를 입력받는다. n x n
격자에서 trials
횟수만큼 자기 회피 보행 실험을 반복한 후, 궁지에 몰릴 확률을 출력한다. 보행 실험을 한 번 할 때마다 교차로를 나타내는 불형 배열을 생성하고, 중앙에서 출발해 궁지에 빠지거나 경계선에 도달할 때까지 계속 다음 교차로를 선택하며 진행한다.
% python3 selfavoid.py 5 100 0% 궁지에 몰림 % python3 selfavoid.py 20 100 35% 궁지에 몰림 % python3 selfavoid.py 40 100 80% 궁지에 몰림 % python3 selfavoid.py 80 100 98% 궁지에 몰림
% python3 selfavoid.py 5 1000 0% 궁지에 몰림 % python3 selfavoid.py 20 1000 32% 궁지에 몰림 % python3 selfavoid.py 40 1000 76% 궁지에 몰림 % python3 selfavoid.py 80 1000 98% 궁지에 몰림