约瑟夫问题二

题目描述:

n 个人排成一圈，从某个人开始，按顺时针方向从 1 开始依次编号。从编号为1的人开始顺时针“ 1，2，3，…，m，1，2，3，… ”报数，报到 m( m>1 )的人退出圈子。这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的(n个)，因此最终会只剩下一个人。试问最后剩下的人的初始编号是多少?

输入格式:

两个整数，n和m。

输出格式:

一个整数，表示最后剩下的人的初始编号。

数据范围:

m, n <= 1000。

样例输入:

10 3

样例输出:

4

提示:

下面程序用链表实现，请完善该程序。

n, m = map( int, input().split() )
lst = []
for i in range( n ):
    lst.append( _____________ )  #填空1
_______________________   #填空2
head = 0
cnt, tot = 0, 0
q = p = head
while tot < n-1:
    cnt += 1
    if cnt == m:
        tot += 1   
        _____________________   #填空3
        ___________________   #填空4
        cnt = 0 
    else:
        q = p
        _____________    #填空5
print( ______________  )    #填空6

时间限制: 1000ms
空间限制: 256MB

---

来源: 选修1教材-P49