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