用C和Java解决数字拼图
这个问题被我从另一个论坛翻译成英文，我发现它很有趣，然后只是写一个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次，并且3在第2行中出现2次;
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);
}
我的问题是
谢谢。
这里是你的代码的简化版本。 由于它不使用HashSet ，所以从它创建一个C版应该不再有问题了。
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);
}
不是一个答案，而是一个提示：尝试使用最小公倍数。
例如，LCM（5,3）= 15，并且15是第2行和第3行中的第一个元素.LCM（2,15）= 30，并且30是前3行中的每一行中的第一个元素。
您最终会进入行r，其中第r行的第一个元素的LCM超过10,000,000，此时没有数字显示每个行。
链接地址: http://www.djcxy.com/p/17245.html