[白俊]1866ジョセフス問題0 python

4162 ワード
パイ アルゴリズム#アルゴリズム# boj python インプリメンテーション 白駿 テキストリンク

ジョセフス問題0


質問する


ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

入力


第1行NとKは、スペースを隔てて順次与えられる.(1 ≤ K ≤ N ≤ 1,000)

しゅつりょく


例に示すように、ジョセフスシーケンスを出力します.

解決策

  • K人を引き続きリストから外し、結果に追加した.
  • ただし、削除を続行すると、idxがリスト長を超える場合、idxをリスト長の残りの部分で割ってidxとして使用します.
    • n,k = map(int,input().split())
lst = [i+1 for i in range(n)]
result = []

#리스트 생성
idx = 0
#마지막 숫자가 남을때까지
for i in range(n-1) :
	#0베이스 고려 idx에 k-1을 추가한다.
	idx += k-1
	#리스트의 길이보다 idx가 크면 idx를 lst로 나눈 나머지를 idx로 사용한다. 
	if idx >=len(lst) :
		idx %= len(lst)
	#결과 리스트에 해당 index의 값을 넣고 제거한다.
	result.append(lst.pop(idx))

result += lst


result = f'<{result}>'
result = result.replace('[','')
print(result.replace(']',''))
    Baek Junアルゴリズム第8ステップ(エラトネスの体)
    Django API