7

序列是从自然数序列创建的：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

在第二步中删除每个第二个数字：

1 3 5 7 9 11 13 15 17 19 21 23

删除第三步中的每个第三个数字（来自上一个序列）：

1 3 7 9 13 15 19 21

在第4 步中删除每个第 4 个数字（从上一个序列中）：

1 3 7 13 19

等等......现在，我们可以说，序列的第 4 个数字将是 13。

定义和正确的解决方案在这里： http: //oeis.org/A000960

我的任务是找到序列的第 1000 个成员。我为此编写了一个算法，但我认为它很慢（当我用第 10.000 个成员尝试它时，大约需要 13 秒）。它的作用是：

  • 我number的每一步都增加 2，因为我们知道没有偶数。

  • 在counters数组中，我存储每个步骤的索引。如果第 x 步中的数字是第 x，我必须将其删除，例如第 3 步中的数字 5。我为下一步启动了一个计数器。

    ArrayList<Long> list = new ArrayList<Long>(10000);
long[] counters = new long[1002];
long number = -1;
int active_counter = 3;
boolean removed;
counters[active_counter] = 1;
int total_numbers = 1;

while (total_numbers <= 1000) {
    number += 2;
    removed = false;
    for (int i = 3; i <= active_counter; i++) {
        if ((counters[i] % i) == 0) {
            removed = true;
            if (i == active_counter) {
                active_counter++;
                counters[active_counter] = i;
            }
            counters[i]++;
            break;
        }
        counters[i]++;
    }
    if (!removed) {
        list.add(number);
        total_numbers++;
    }
}
4

4 回答 4

4

您与 OEIS 的链接为我们提供了一些快速计算的方法（公式等）

第二个的实现：

function Flavius(n: Integer): Integer;
var
  m, i: Integer;
begin
  m := n * n;
  for i := n - 1 downto 1 do
    m := (m - 1) - (m - 1) mod i;
  Result := m;
end;

PS 算法是线性的 (O(n))，n=10000 的结果是 78537769

于 2012-04-06T18:04:52.520 回答
2

不，这个问题不是NP难...

我有直觉O(n^2)，链接证明了这一点：

Let F(n) = number of terms <= n. Andersson, improving results of Brun,
shows that F(n) = 2 sqrt(n/Pi) + O(n^(1/6)). Hence a(n) grows like Pi n^2 / 4.

它认为O(n^2)不应该给 n = 10000 15s。是的，有些东西不正确:(

编辑 ：

我测量了访问counters(for n = 10000) 的次数以大致了解复杂性，我有

 F = 1305646150
 F/n^2 = 13.05...

你的算法介于两者之间O(n^2)，O(n^2*(logn))所以你做对了...... :)

于 2012-04-06T17:50:31.020 回答
1

一种方法可能是保留用于筛选的数字数组，而不是被筛选的数字。基本上，如果您正在寻找序列中的第 N 个值，您可以创建一个包含 N 个计数器的数组，然后遍历自然数。对于每个数字，您循环遍历您的计数器，递增它们直到一个达到其“最大值”值，此时您将该计数器设置为零并停止递增剩余的计数器。（这表示在该计数器的步骤中删除当前数字。）如果您通过所有计数器而不删除当前数字，那么这是剩下的数字之一。

一些似乎与 OEIS 给出的序列相匹配的示例 (Java) 代码：

public class Test {
  public static void main(String[] args) {
    int N=10000;
    int n=0;
    long c=0;

    int[] counters = new int[N];

    outer: while(n<N) {
      c++;
      for(int i=0;i<N;i++){
        counters[i]++;
        if(counters[i]==i+2){
          counters[i]=0;
          continue outer;
        }
      }

      // c is the n'th leftover
      System.out.println(n + " " + c);
      n++;
    }
  }
}

我相信这在 O(N^3) 中运行。

于 2012-04-06T17:47:42.177 回答
1

哇，这真是一个有趣的问题。
对此感激不尽。

我刚刚为此失去了一个小时的生命。我认为这个问题将变成 NP 难题。而且我无法生成一个方程来计算第j步中的第i项。

除非有一些聪明的数学技巧可以一步生成最终解决方案，否则您的“蛮力”解决方案似乎很好。但我不认为有。

从编程的角度来看，您可以尝试将初始数组设为链表，然后取消链接您想要删除的术语。这将为您节省一些时间，因为您不会每一步都重建您的列表。

于 2012-04-06T17:27:44.617 回答