挑战58

rosynirvana · 发表于 2014-3-27 23:16:57

本帖最后由 rosynirvana 于 2014-3-27 23:19 编辑

很早之前就有人问我，本想直接拿原来的代码来凑数的，结果昨天因为某些原因又写了类似的代码，所以现在写出来吧……

直接穷举的复杂度非常高，我第一次做的时候，先写好直接穷举的代码，然后去查相关的数学知识，代码写完跑出结果后，直接穷举的代码还没跑出结果，所以在这么大的数字的时候，直接穷举就不必考虑了。

题目的关键是要知道相应的数学知识，直角三角形的三边长可以构造出来，具体可以参考
http://zh.wikipedia.org/wiki/%E5%8B%BE%E8%82%A1%E6%95%B0

#include <stdio.h>
int gcd(int, int);
/* 计算过程中需要判断两个数是否互质，所以一个计算最大公约数的函数是必要的 */
int count[1500000+1];
/* 大数组记得要放在静态区 */
int main()
{
int m, n;
/* 构造所需的两个变量 */
int num = 0;
int i;
for(m=2; m<=1225; ++m)
/* sqrt(1500000)上取整，计算到1225绝对够了 */
for(n=1; n<m; ++n)
if(gcd(m, n) == 1)
if(m % 2 == 0 || n % 2 == 0){
int a = m*m - n*n;
int b = 2*m*n;
int c = m*m + n*n;
int length = a+b+c;
int times = 1;
while(times * length <=1500000){
/* 所有勾股数都可以用勾股素数来构造 */
count[times*length] += 1;
times += 1;
}
}
for(i=0; i<=1500000; ++i)
if(count[i] == 1)
num += 1;
/* 计算出来后，扫描一遍表格，把只有一种可能的统计下来 */
printf("%d\n", num);
return 0;
}
/* 计算最大公约数用的函数，个人比较习惯的一种写法，效率应该还可以提高 */
int gcd(int a, int b)
{
while(a > 0 && b > 0)
if(a > b)
a %= b;
else
b %= a;
return a > b ? a : b;
}

复制代码

rosynirvana · 发表于 2014-7-29 19:55:06

MoreHail 发表于 2014-7-29 19:50
是啊，跑了5、6个小时，都没结果。代码里边，count[1500000+1]是数组么？静态区是什么？怎么放入静态区？

放在所有函数外面定义

调试ing · 发表于 2014-3-28 11:40:01

正需要，赞一个

rosynirvana · 发表于 2014-3-27 23:23:37

几个注意的要点：
1. 1500000的大数组要放在静态区，不然有可能把函数栈爆掉
（动态分配也可以，不过这么一小段代码放在静态区就可以了）

2. 计算勾股素数，然后再乘以整数倍，这样可以保证求得的三边长不会重复
如果直接用m, n构造，会出现重复情况的

3. 构造勾股素数的条件在此再写一遍：

a = m*m - n*n;
b = 2*m*n;
c = m*m + n*n;
三边长满足这样的约束关系

其中
m > n;
m % 2 == 0 || n % 2 == 0 (m, n至少有一个是偶数)
gcd(m, n) == 1(m和n互质)

4399APPLE · 发表于 2014-3-28 09:42:27

????????????

超神级 · 发表于 2014-3-28 20:57:34

{:soso__17261225861671879680_3:}竟然如此简单..............................

Gallen · 发表于 2014-7-17 17:35:14

{:soso_e183:}

MoreHail · 发表于 2014-7-29 18:55:59

对不起，我数学不好，不知道什么是勾股素数。。。

MoreHail · 发表于 2014-7-29 19:31:13

这个、我就是直接穷举的。。。{:soso__51be3e80bf36fd0f-84cb9798c2b54967-da186aed5a4735fc1066ec7649be2846.jpg_1:}[mw_shl_code=c,true]#include <stdio.h>
#include <stdlib.h>
int main()
{
int l=12,m,sum;
int tri(int a);
while (l<=1500000)
{
m=tri(l);
      sum=sum+m;
      if (m!=0) printf("%d ",sum);
l++;
}
system("pause");
return 0;
}
int tri(int a)
{
int i,j,k,x,y,z,p=0;
for (i=3;i<=a/3;i++)
{
for (j=i+1;j<=a/2;j++)
      {
k=a-j-i;
         x=i*i;
         y=j*j;
         z=k*k;
         if (z<y||z<x||z<y+x) break;
         if (z==x+y)
         {
p=p+1;
            break;
         }
      }
}
if (p==1)
return p;
else
return 0;
}
[/mw_shl_code]有崩溃的赶脚。。。

rosynirvana · 发表于 2014-7-29 19:42:24

MoreHail 发表于 2014-7-29 19:31
这个、我就是直接穷举的。。。{:soso__51be3e80bf36fd0f-84cb9798c2b54967-da186aed5a4735fc1066ec7649be28 ...

穷举没意义

MoreHail · 发表于 2014-7-29 19:50:23

rosynirvana 发表于 2014-7-29 19:42
穷举没意义

是啊，跑了5、6个小时，都没结果。代码里边，count[1500000+1]是数组么？静态区是什么？怎么放入静态区？

MoreHail · 发表于 2014-7-30 01:39:52

rosynirvana 发表于 2014-7-29 19:55
放在所有函数外面定义

哦，我造了，谢啦~~~

挑战58

点评