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

高洛峰
풀어 주다: 2016-10-18 10:33:15
원래의
4582명이 탐색했습니다.

오늘은 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)
로그인 후 복사

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

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!