7

シーケンスは、自然数のシーケンスから作成されます。

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

2番目のステップで2番目ごとの数字を削除します：

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

（前のシーケンスから） 3番目のステップで3番目ごとの番号を削除します。

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へのリンクは、高速計算のためのいくつかの方法を提供します（FORMULAなど）

2番目のものの実装：

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の場合に15を与えるべきではないと思います。はい、正しくないことがあります:(

編集 ：

複雑さの大まかなアイデアを得るために、countersへのアクセス数を測定しました。n = 10000

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

あなたのアルゴリズムは間O(n^2)にO(n^2*(logn))あるので、あなたは物事を正しくやっています.... :)

于 2012-04-06T17:50:31.020 に答える
1

うわー、それは本当に興味深い問題です。
どうもありがとうございました。

私はこれで私の人生の1時間を失いました。問題はNP困難になると思います。そして、j番目のステップでi番目の項を計算するための方程式を生成するのに途方に暮れています。

「ブルートフォース」ソリューションは、1つのステップで最終的なソリューションを生成するための巧妙な数学のトリックがない限り、問題ないように見えます。しかし、私はそうは思わない。

プログラミングの観点からは、最初の配列をリンクリストにして、削除する用語のリンクを解除してみてください。すべてのステップでリストを再構築する必要がないため、時間を節約できます。

于 2012-04-06T17:27:44.617 に答える
1

1つのアプローチは、ふるいにかけられる数ではなく、ふるいにかけるために使用している数の配列を保持することです。基本的に、シーケンス内でN番目の値を検索する場合は、N個のカウンターの配列を作成してから、自然数を反復処理します。数値ごとに、カウンターをループし、「最大」値に達するまでカウンターをインクリメントします。その時点で、そのカウンターをゼロに設定し、残りのカウンターのインクリメントを停止します。（これは、そのカウンターのステップで現在の番号を削除することを表します。）現在の番号を削除せずにすべてのカウンターを通過した場合、これは残っている番号の1つです。

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 に答える