4

自然数系列では、1 回目のパスで 2 つおきの要素を削除する必要があります。次に、残りの要素で、2 番目のパスで 3 つおきの要素を削除します。次に、K 番目のパスで、残りの要素から (k+1) 番目の要素をすべて削除します。

シリーズはこうなる

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ...

1回目のパスの後（2つおきの要素を削除した後）、

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...

2 回目のパスの後 (3 番目の要素をすべて削除した後)、

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...

3 回目のパスの後 (4 つごとの要素を削除した後)、

1, 3, 13, 15, 19, 25, 27, ...

したがって、無限パスの後、次のようになります

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, ...

このシリーズはFlavius-Josephus sieveとも呼ばれます。

これに対する解決策は、シリーズの 6 番目の要素を見つけることです。

  • 6^2 = 36 を行います
  • 35 を与える 5 の倍数に下がる
  • それから 4 の倍数 = 32 まで
  • それから 3 の倍数 = 30 まで
  • 次に 2 の倍数 = 28 まで
  • 次に、1 = 27 の倍数まで
  • したがって、6 番目のラッキー ナンバーは 27 です。

それは機能しますが、ソリューションがどのように機能するのか理解できませんか?

このためのACプログラムは、

int calc(int n)
{
   if (n == 1) return 1;
   return calc_rec(n*n, n-1);
}

int calc_rec(int nu, int level)
{
   int tmp;
   if (level == 1) return (nu-1);
   tmp = nu % level;
   return calc_rec(nu - (tmp ? tmp : level), level-1);
}

これを説明するリンクhttp://oeis.org/A000960

4

1 に答える 1

2

これはあなたの質問には答えませんが、ストリームの任意の要素を高速に計算するためのより直感的なアルゴリズムの導出を次に示します。

すべての整数を含む最初のシリーズを S[0] と呼び、次に S[1] を最初のパスの後のシリーズ、S[2] を 2 番目のパスの後のシリーズなどと呼びましょう。

シリーズ S[0] では、N 番目の整数 (ゼロから始まるインデックス) は N + 1 です。

1 2 3 4 5 6 7 8 9 10 ...

シリーズ S[1] では、N 番目の整数は、S[0] から (2N) 番目の要素にアクセスすることによって取得されます。2N = N+(N div 1) に注意してください。'div' は整数除算、つまり剰余を捨てる除算です。

1 3 5 7 9 11 13 15 17 ...

シリーズ S[2] では、N 番目の整数は、S[1] から N+(N div 2) 番目の要素にアクセスすることによって取得されます。

1 3 7 9 13 15 19 21 ...

シリーズ S[3] では、N 番目の整数は、S[2] から N+(N div 3) 番目の要素にアクセスすることによって取得されます。

1 3 7 13 15 19 ...

したがって、次の再帰プロシージャが得られます。

get_number(int series, int N):
   if (series == 0):
      return N + 1
   else:
      return get_number(series - 1, N + floor(N / series))

ただし、series > N の場合、floor(N / series) はまったくゼロであるため、常に get_number(N, N) として呼び出すことができることに注意してください。

例えば、

get_number(5, 5) = get_number(4, 6) = get_number(3, 7) =
  get_number(2, 9) = get_number(1, 13) = get_number(0, 26) = 27.

これは、ストリームから 6 番目 (5 であるがゼロベースのインデックス) として '27' を取得する方法を示しています。

于 2012-05-11T13:58:04.377 に答える