4

在自然数系列中，我们必须在第一遍中删除每个第二个元素。然后在剩余的元素中，删除第二遍中的每个第 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, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...

在第二遍之后，（在删除每个第三个元素之后），

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 筛。

解决方案是找到系列中的第 6 个元素：

  • 做 6^2 = 36
  • 下降到 5 的倍数，得到 35
  • 然后下降到 4 = 32 的倍数
  • 然后下降到 3 = 30 的倍数
  • 然后下降到 2 = 28 的倍数
  • 然后下降到 1 = 27 的倍数
  • 所以第六个幸运数字是27。

虽然它有效，但我不明白解决方案是如何工作的？

交流计划是，

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] 称为第二遍之后的序列，依此类推。

在系列 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.

这显示了如何从流中获得“27”作为第 6 个（5 个但从零开始的索引）。

于 2012-05-11T13:58:04.377 回答