用C和Java解决数字难题

Question

我在另一个论坛上将这个问题翻译成英文,我发现它很有趣,然后编写一个Java解决方案.并且在处理像10000000这样的大量数据时发现存在一些堆大小问题.而且我想寻找一些与我自己相比的非常聪明的解决方案.

原帖是中文的.我根据我的理解对其进行了一些修改,以使其更清晰. http://zhidao.baidu.com/question/1637660984282265740.html?sort=6&old=1#here

以下是谜题:

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.然后到这一点的重复次数将是3,因为6已经在第1行并且在第2行中出现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;

我提出了一个Java解决方案,但由于10000000太大且内存不足,我有堆大小问题.所以我只使用10000而不是10000000,10而不是10000.下面是我用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中完成它,因为我记得在C中没有Set类.(导入第三方库不是首选)？

谢谢.

Answer 1

这是您的代码的简化版本。因为它不使用\xe2\x80\x99t HashSet，所以用它创建一个C 版本应该不再有问题了。

\n\n

int max = 10000;\nint row = 10;\nboolean[] seen=new boolean[max+1];\nfor(int i=2;i<=max;i+=2) seen[i]=true;\nint w = 0;\nfor(int i=2;i<=(row);i++) {\n    int self_count = 0;\n    for(int j=(2*i-1);j<=max;j+=(2*i-1)) {\n        self_count++;\n        if(seen[j]) w++; else seen[j]=true;\n    }\n    w += self_count/2;\n    System.out.println("w"+(i-1)+": "+w);\n}\n

\n