資源簡介

(共17張PPT)
鏈表的應用（第四課時）
n個人排成一圈，從某個人開始，按順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，…，m，1，2，3，…”報數，報到m（m＞1）的人退出圈子。按原始編號輸出最后一個出圈的編號。
1
2
3
4
5
……
n
6
7
8
約瑟夫游戲
1
2
3
4
5
……
n
6
7
8
約瑟夫游戲
任務一：當n=8,m=3時，請每位同學按游戲規則模擬一下，并按順序輸出出圈人員的編號。
約瑟夫游戲
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
8
出圈順序為：3 6 1 5 2 8 4 7
7
約瑟夫游戲
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
8
任務二：如何用鏈表存儲這n個人的數據？
7
約瑟夫游戲
1 1
數據區域
指針區域
數組下標
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
每個人設置數據區域和指針區域，當n=8,m=3時，數據如下圖所示：
約瑟夫游戲
1 1
數據區域
指針區域
數組下標
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
任務三：請模擬游戲過程中的指針區域的變化過程。
約瑟夫問題
1 1
數據區域
指針區域
數組下標
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
編號為3的人出圈
1 1
數據區域
指針區域
數組下標
2 3
3 3
4 4
5 6
6 6
7 7
8 0
0
1
2
3
4
5
6
7
編號為6的人出圈
1 1
數據區域
指針區域
數組下標
2 3
3 3
4 4
5 6
6 6
7 7
8 0
0
1
2
3
4
5
6
7
編號為1的人出圈
約瑟夫游戲
1 1
數據區域
指針區域
數組下標
2 3
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
編號為3的人出圈
算法設計：
任務四：請為約瑟夫游戲設計算法？
約瑟夫游戲
1 1
數據域
指針域
數組下標
2 3
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
編號為3的人出圈
算法設計：
1.用二維數組a記錄約瑟夫環，a[i][0]表示第i+1個人的編號，a[i][1]表示第i+1個人的指針區域。計數器cnt，初始值為0；總人數n,減少1人時，n的值減1；head表示鏈表頭初始值為0；k表示當前位置，初始值為head，prev為k的前一個數的位置，初始值為n-1。
2.計數器cnt每次加1，分兩種情況。
①cnt=m時，當前位置k上的數需要出環，則需要修改prev上的指針域，a[prev][1]=a[k][1]，指向位置k上的指針域指向的數；同時，當前位置發生改變了，k=a[k][1]。并把cnt=0，n=n-1。如果當前的位置k恰好是鏈表頭，則需要修改head的值為a[k][1]。
②cnt!=m時，只需一起移動prev和k。
3.輸出a[head][0]。
約瑟夫游戲
1 1
數據區域
指針區域
數組下標
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
問題一：如何新建單向環狀鏈表？
n,m=map(int,input().split())
a=[]
for i in range(n-1):
a.append([i+1,i+1])
a.append([n,0])
for i in range(n):
print(a[i])
約瑟夫問題
n,m=map(int,input().split())
a=[]
for i in range(n-1):
a.append([i+1,i+1])
a.append([n,0])
head=0
prev=n-1
k=head
cnt=0
while n>1:
cnt+=1
if cnt==m:
if k==head:
head=a[k][1]
a[prev][1]=a[k][1]
k=a[k][1]
cnt=0
n-=1
else:
prev=k
k=a[k][1]
print(a[head][0])
1 1
數據區域
指針區域
數組下標
2 2
3 3
4 4
5 5
6 6
7 7
8 0
0
1
2
3
4
5
6
7
約瑟夫游戲
思考：用數組存儲數據，并設計算法，用程序實現約瑟夫游戲？
約瑟夫游戲
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
算法：用一維數組a存儲每個人的編號，用一維數組flag標記是否出列；順時針記數，
記錄在列的人數，到達m時，則輸出該編號，并把flag數組對應的值標記為False。
約瑟夫游戲
n,m=map(int,input().split())
flag=[True]*(n+1)
a=[0]*n
for i in range(n):
a[i]=i+1
k=0;cnt=0;num=0
while numif k==n:
k=1
else:
k+=1
if flag[k]:
cnt+=1
if cnt==m:
print(k,end=" ")
flag[k]=False
cnt=0
1
2
3
4
5
6
7
8
總結
當實例中的數據之間存在相鄰關系，又有很多數據需要刪除、或者插入時，就可以用鏈表結構來處理。
同學們，再見

展開更多......

收起↑