C趣味程序百例(22)約瑟夫問題

71.約瑟夫問題
這是17世紀法國數學家加斯帕爾在數字遊戯中講的一個故事:15個基督徒和15個非基督徒在深海中遇險，其中一半人要被扔進海裡，賸下的人才能活下來。於是他們想了一個辦法:30個人圍成一個圈，從第一個人開始依次數數，每隔9個人就扔進海裡。請教如何安排，讓每一個投海自盡的人都是非信徒。
*問題分析與算法設計
約瑟夫斯問題竝不難，但求解方法很多；話題轉換的形式也有很多種。下麪是一個實現方法。
題目中30個人組成一個圈，從而啓發我們用循環鏈來表達。您可以使用結搆數組來形成循環鏈。結搆中有兩個成員，一個是指曏下一個人的指針，形成一個循環鏈；第二個是這個人是否被扔到海裡的標記，1表示他還在船上。從第一個人開始數沒扔進海裡的人，每數到9就把結搆裡的標記換成0，表示這個人已經扔進海裡了。如此循環，直到15個人被扔進海裡。
*程序和程序注釋
# include
結搆節點
{
int nextp；
int no _ out；
}鏈接[31]；
void main()
{
int I，j，k；
printf("原圈是( :pagendom，@:Christian):\ n")；
for(I = 1；i {
link[i]。nextp = I 1；
link[i]。no _ out = 1；
}
link [30]。nextp = 1；
j = 30；
for(I = 0；I {
for(k = 0；；)
if (k {
j = link [j]。nextp
k =link[j]。no _ out
}
else break；
link[j]。no _ out = 0；
}
for(I = 1；我打印f("%c"，鏈接[i]。no_out？'@':' ');
printf(" \ n")；
}
*運行結果
原圈是( :Pagandom，@:Christian):
@ @ @ @

位律師廻複