오늘은 Joseph Ring 알고리즘을 구현하겠습니다. 다음은 Sina의 인터뷰 질문입니다.
m명의 원숭이가 시계 방향으로 1부터 m까지 번호가 매겨진 원 안에 앉아 있습니다. 그런 다음 1번 원숭이부터 시계 방향으로 숫자를 세기 시작합니다. n을 보고한 원숭이가 아웃되고, 방금 나온 원숭이의 다음 위치부터 다시 세어가며, 원숭이가 한 마리만 남을 때까지 반복합니다. 왕이다. 다음 기능을 구현하는 프로그램을 설계하고 작성하세요.
(1) 사용자는 처음에 원숭이의 수 m과 보고된 마지막 숫자 n을 입력해야 합니다.
(2) 당선된 원숭이 왕의 초기 번호를 알려주세요.
이 질문은 전형적인 조셉 링 문제, 즉 원숭이가 왕을 선택하는 문제입니다.
참고: 이 예는 python2.7에서 테스트를 통과했지만 python3에서는 테스트되지 않았습니다. 관심 있는 학생들은 그룹에서 대화할 수 있습니다.
코드 직접 받기:
#!/usr/bin/python # coding=utf-8 # 约瑟夫环算法 之 猴子选王 问题 def king(m,n): dd = {} #生成一个字典 p = 1 while(p<=m): dd[p] = p p = p+1 j = 1 while(len(dd) >1): for k,v in dd.items(): if(j == n): del dd[k] j = 1 else: j = j+1 return dd print king(6,2)
참고: 여기서는 목록이 아닌 사전이 사용됩니다. 주로 사전의 색인을 활용할 수 있기 때문입니다