Posted on 2006-03-05 14:52
Tauruser 閱讀(1745)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法與數(shù)據(jù)結(jié)構(gòu)
摘一下題目：
試用遞歸和非遞歸的方法編寫(xiě)程序解決Josephus問(wèn)題：設(shè)有n個(gè)人圍坐一個(gè)圓桌周?chē)F(xiàn)從第S人開(kāi)始報(bào)數(shù)，數(shù)到第m的人出列，然后從出列的下一個(gè)重新開(kāi)始報(bào)數(shù)，數(shù)列的第m個(gè)人又出列……如此重復(fù)，直到所有的人全部出列為止。對(duì)任意給定的n、s、m，求按出列次序得到的n個(gè)人員的順序表。
使用兩種方法：
方法１：用整數(shù)i來(lái)代替pi，將初始序列看成一個(gè)整數(shù)序列存儲(chǔ)在向量p中，pi出列，將p[i+1]，……，p[n]前移一個(gè)元素，將pi放入p[n]中，最后出列放在p[1]中，再作逆序。
方法２：每出列一個(gè)元素存入另一個(gè)向量中，不移位，設(shè)置標(biāo)志，全部出列后，打印出出列順序表。
詳細(xì)解決辦法請(qǐng)點(diǎn)下面的鏈接。
Josephus問(wèn)題非遞歸方法１解決辦法 Josephus問(wèn)題遞歸方法１解決辦法 Josephus問(wèn)題非遞歸方法２解決辦法
Josephus問(wèn)題遞歸方法２解決辦法