S11G4 約瑟夫斯問題 Josephus Problem

       由 40 個人繞成一圈，每間隔兩人淘汰一人，問最後一位被淘汰的為哪一位，這就是有名的約瑟夫斯問題。這次將介紹用 GGB 的列表功能來動態呈現淘汰的過程，並且用數學來分析最後一個被淘汰的遞回關係式。

任務一 用list指令模擬減少的效果

說明：為了模擬每 g 個移除一個的效果，我們將前面 g-1 個往後移動，形成一個新串列，接著再選取最後 n- 個，就可得到移除第 g 個的效果。

操作：

n=Slider(3,40,1)

g=Slider(2,n-1,1)

k=Slider(1,n-1,1)

N0=Sequence(k,k,1,n)

N1a=join({N0,Take(N0,1,g-1)})      #  N1a=合并({N0, 提取(N0, 1, g - 1)})

N1b=Last(N1a,Length(N0)-1)       #  N1b=最后元素(N1a, 长度(N0) - 1)

N1=Last(join({N0,Take(N0,1,g-1)}),Length(N0)-1)

# N1=最后元素(合并({N0, 提取(N0, 1, g - 1)}), 长度(N0) - 1)

N2=Last(join({N1,Take(N1,1,g-1)}),Length(N1)-1)

N3=Last(join({N2,Take(N2,1,g-1)}),Length(N2)-1)

任务二 用Iteration指令模拟k次结果

說明：對上一小節的操作要反復地執行，因此可利用 iteration 來達到這個效果。但當串列的長度比 g 還小時，需要通過取 mod 才能得到這結果。最後可將第 k-1 次的串列再  remove k 次的串列就可得到最新移除的元素。

操作：

Nk=Iteration(Last(join({ns,Take(ns,1,g-1)}),Length(ns)-1),ns,{N0},k)

#迭代(最后元素(合并({ns, 提取(ns, 1, g - 1)}), 长度(ns) - 1), ns, {N0}, k)

迭代后删除N1、N2、N3

Nkp=Iteration(Last(Join({ns, Take(ns, 1, mod(g - 1, Length(ns)))}), Length(ns) - 1), ns, {N0}, k )

#迭代(最后元素(合并({ns, 提取(ns, 1, 余式(g - 1, 长度(ns)))}), 长度(ns) - 1), ns, {N0}, k )

Nkpp=Iteration(Last(Join({ns, Take(ns, 1, mod(g - 1, Length(ns)))}), Length(ns) - 1), ns, {N0}, k - 1)

Nkr=Remove(Nkpp, Nkp)       # #Remove  去除

任務三 將刪除的順序動態圖示化

說明：目前獲得執行k次的列表後，可通過 zip 來將這結果與圓周上的點作對應。並且利用 sequence 與 Text 來將每個點添加文字編號。

操作：

c=Circle((0,0),1)

Ps=Sequence((1; 2k π / n), k, 0, n - 1)

Nps=Zip(Ps(a), a, Nkp)

Ts=Sequence(Text(k, (0.8; 2π / n (k - 1)) - (0.05, 0.05)), k, 1, n)

Pkr=Ps(Nkr(1))

小結

從最後的數學分析可知想不被淘汰應該站在什麼位置？與二進位相關的應用還可參照

連接

【GGB】https://www.geogebra.org/classic/ah5prb6t
【Bili】https://www.bilibili.com/video/BV193411y7Nf/

【YouTube】https://www.youtube.com/playlist?list=PLXH05kw-i_5JWHo-T4rRKc4FBI4ea8QCj