josephus … ヨセフス数、nの輪からkごとに消す時s番目の数 - Imoのアルゴリズムライブラリ

ヨセフス数

説明

n人の輪からk人ごとに殺していったとき、s番目に殺される人の番号(1〜n)を求める

計算量

O(?)

使い方

josephus(n,k,s)でn人の輪からk人ごとに殺していったとき、s番目に殺される人の番号(1〜n)を返す。ただしn,k,sは1以上、s<=nを満たさなければならない。

ソースコード

int josephus(int n, int k, int s) {
  int x = k * s;
  while (x > n) x = ((x - n) * k - 1) / (k - 1);
  return x;
}

確認

なし