pythonジョセフループ問題の解決

3860 ワード

タイトル:
有名なユダヤ人歴史学者Josephusには、ローマ人がジョタパットを占領した後、39人のユダヤ人とJosephusと彼の友达が穴の中に隠れ、39人のユダヤ人が死んでも敵に捕まえられないことを決め、41人が輪になって1人目から数え始め、3人目になるたびに自殺しなければならないと決め、次から数え直すという話があるそうです.全員が自殺するまで.しかしJosephusと彼の友达は従いたくない.まず一人から、k-2人を越え(最初の人は越えられたので)、k人を殺します.次に、k-1人を越え、k人目を殺す.この過程は円に沿ってずっと行われ、最終的には一人しか残っていないまで、この人は生き続けることができます.
Josephusは友人と自分を16番目と31番目の位置に配置し、この死のゲームを逃れた.
猿が王を選ぶとか...
シミュレーションの方法で、時間の複雑さはO(MK)...pythonを使うと葛藤しません(水)
H=[1]*41 #1    ,0    
M=3#  M    
K=len(H)
p=0
for i in range(K//M*M):#        ,       
    i=0
    while i<M:#  p  ,         
        if H[p%K]==1:#    ,          。                
            i+=1
            p+=1
        else:
            p+=1#     ,      
    H[p%K-1]=0
    print(p%K,'   ')
print()
for j in range(K):
    if H[j]==1:
        print(j+1,'      ')