Python으로 구현된 "원숭이가 왕을 선택합니다" 알고리즘

오늘은 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)

참고: 여기서는 목록이 아닌 사전이 사용됩니다. 주로 사전의 색인을 활용할 수 있기 때문입니다