線性表是數(shù)據(jù)結(jié)構(gòu)的中很常見的結(jié)構(gòu)，其中一種就是順序表椎椰，python已經(jīng)內(nèi)置了順序表厦幅。list就是循序表的的實現(xiàn)。
下面就用順序表解決一些有趣的問題慨飘！
josephus 問題開始鏈表上的經(jīng)典問題,問題如下:假設(shè)有n個人圍坐一圈,現(xiàn)在要求從第k個人開始報數(shù),報到第m個數(shù)的人退出,然后從下一人開始繼續(xù)報數(shù)重復(fù)上述規(guī)則,直到所有人退出确憨。要求按順序輸出各出列人的編號。
#coding:utf-8
import time
def josephus(n,k,m):
people = list(range(1,n + 1)) # 將開始的i置為指定的k 減1是由于數(shù)組下標的緣故
i = k - 1
for num in range(n,0,-1): #每循環(huán)一次總數(shù)減1
i = (i + m - 1) % num
print people.pop(i)
return
# 下面這個實現(xiàn)方法不會將退出的人彈出或刪除,只是將它置0
def josephus_no_pop(n,k,m):
people = list(range(1,n + 1))
i = k - 1
for num in range(n):
count = 0 # 一定是小于m,由于在循環(huán)里面有加一,如果加上等于就會在第一次等于后無限循環(huán)!
while count < m:
if people[i] > 0:
count += 1
if count == m:
print people[i]
people[i] = 0
i = (i + 1) % n
if __name__ == '__main__':
start = time.clock()
josephus(10, 1, 7)
print '花費時間:%f' % (time.clock() - start)
start = time.clock()
josephus_no_pop(10, 1, 7)
print '花費時間:%f' % (time.clock() - start)
```