7

この質問は、私が別のフォーラムから英語に翻訳したものです。興味深いので、Java ソリューションを作成します。そして、10000000 のような大きな数を扱う場合、いくつかのヒープ サイズの問題があることがわかりました。そして、私は自分自身と比較して、本当にスマートな解決策を探したいと思います。

元の投稿は中国語です。そして、より明確にするために、私の理解に基づいて少し修正しました。 http://zhidao.baidu.com/question/1637660984282265740.html?sort=6&old=1#こちら

以下はパズルです。

10000 rows of numbers;
1 row: 2,4,6,8...2K(2K<=10000000); (numbers no repeats for this row)
2 row: 3,3,6,6,9,9...3K(3K<=10000000); (starting from this row, each number repeats 2 times and a multiple which has something to do with row number (2XrowNumber-1) to be specificaly)
3 row: 5,5,10,10,15,15...5K(5K<=10000000);
and following 7K,9K,11K,13K....until
10000 row: 19999,19999,39998,39998....19999K,19999K (19999K<=10000000);

次の部分で使用する行はこれですべてです。そして、行 1 と行 2 から始まる数値の繰り返し回数を計算します。

整数 w1 は、行 1 と行 2 の数値の繰り返し回数です。たとえば、行 1 の数字が 2、4、6 で、行 2 の数字が 3、3、6、6 であるとします。6 はすでに行 1 にあり、行 2 に 2 回表示され、3 は行 2 に 2 回表示されるため、この時点までの繰り返し回数は 3 になります。

Integer w2 is the repeat times of numbers in row 1 and row 2 and row 3. 
Integer w3 is the repeat times of numbers in row 1 and row 2 and row 3 and row 4. 
......
Integer w9999 is the repeat times of numbers of row 1,row 2,row 3 .....row 10000.

そして、すべての整数 w1,w2....w9999; を出力します。

私は1つのJavaソリューションを思いつきましたが、10000000は大きすぎてメモリが十分でないため、ヒープサイズの問題があります。したがって、10000000 の代わりに 10000 を使用し、10000 の代わりに 10 を使用します。以下は Java で記述したものです。私はそれが正しいはずだと思います（そうでない場合は、指摘してください）：

    Set nums = new HashSet();
    int max = 10000;
    int row = 10;
    for (int i=2;i<=max;i+=2){
        nums.add(new Integer(i));
    }
    int nums_size = nums.size();
    int w = 0;
    for (int i=2;i<=(row);i++){
        int tmp_count = 0;
        int self_count = 0;
        for (int j=(2*i-1);j<=max;j+=(2*i-1)){
            nums.add(new Integer(j));
            self_count++;
            if (nums.size()==nums_size){
                tmp_count++;
            } else {
                nums_size = nums.size();
            }
        }           
        w += tmp_count;
        w += self_count;
        System.out.println("w"+(i-1)+": "+w);
    }

私の質問は

  1. Java でより良い解決策を得るには (もしあれば)?
  2. 私が覚えているように、Cには Set クラスがないので、Cでそれを行う方法。(サードパーティのライブラリをインポートすることはお勧めしません)?

ありがとう。

4

2 に答える 2

3

これは、コードの簡略化されたバージョンです。を使用しないので、それからHashSetC バージョンを作成することはもはや問題ではありません。

int max = 10000;
int row = 10;
boolean[] seen=new boolean[max+1];
for(int i=2;i<=max;i+=2) seen[i]=true;
int w = 0;
for(int i=2;i<=(row);i++) {
    int self_count = 0;
    for(int j=(2*i-1);j<=max;j+=(2*i-1)) {
        self_count++;
        if(seen[j]) w++; else seen[j]=true;
    }
    w += self_count/2;
    System.out.println("w"+(i-1)+": "+w);
}
于 2013-11-12T09:55:13.433 に答える
0

答えではありませんが、ヒント: 最小公倍数を使用してみてください。

たとえば、LCM(5,3)=15 で、15 は行 2 と 3 の両方の最初の要素です。LCM(2,15)=30 で、30 は最初の 3 行のそれぞれの最初の要素です。

最終的に、最初の r 行の最初の要素の LCM が 10,000,000 を超える行 r に到達します。この時点で、これらの各行には数字が表示されません。

于 2013-11-12T13:09:06.143 に答える