投げるたびにボールを受け取る子供の番号を求めるC++プログラム

問題の概要

ある数 n が与えられ、n 人の子供が円形に立っているとします。子供たちには時計回りに 1 から n までの番号が付けられており、最初は 1 番の子供がボールを持っています。

まず 1 番の子供が、時計回りに隣にいる子供(2 番)へボールを投げます。次に 2 番の子供が、その隣の子供(4 番)へ投げ、続いて 4 番の子供が 7 番の子供へと投げます。このように、投げるたびにボールが進む距離が 1 つずつ増えていきます。ボールが投げられる際には、円の一周をまたいで先頭に戻ることもあります。

ゲームの途中でボールを受け取らない子供もいるため、各投擲の後にボールを受け取る子供の番号をすべて求める必要があります。

例えば、入力が n = 10 の場合、出力は [2, 4, 7, 1, 6, 2, 9, 7, 6] となります。

アルゴリズムの手順

この問題は、次の手順で解くことができます。

• 現在位置を表す変数 p を 1 で初期化します。
• i を 1 から n-1 まで順に処理し、各ステップで p に i を加算します。
• p を n で割った余りに更新します。余りが 0 になった場合は n に置き換えます(番号は 1 から始まるため)。
• 各ステップの p の値を出力します。

p := 1
for initialize i := 1, when i < n, update (increase i by 1), do:
   p := p + i
   p := p mod n
   if not p is non-zero, then:
      p := n
   print p

仕組みの解説

i 回目の投擲では、ボールは時計回りに i 人先の子供へと渡されます。つまり、k 回目の投擲が終わった時点でのボールの位置は、「1 から k までの累積和を n で割った余り」(ただし 0 の場合は n)として表せます。この性質を利用することで、シミュレーションを単純なループで実装でき、計算量 O(n) で各投擲後のボールの受け取り手を効率的に列挙できます。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
   int p = 1;
   for (int i = 1; i < n; i++){
      p += i;
      p %= n;
      if (!p)
         p = n;
      printf("%d, ", p);
   }
}
int main(){
   int n = 10;
   solve(n);
}

入力

10

出力

2, 4, 7, 1, 6, 2, 9, 7, 6,