主题:第二界编程比赛试题
黄金风格
[专家分:4050] 发布于 2005-10-20 13:06:00
输入两个整数(要求100以内的自然数),若这两个整数之间存在自然数对,则将其中所有的自然数对输出,否则输出不存在的提示.所谓的自然数对是指两个自然数的和与差都是平方数.例如:17-8=9,17+8=25,那么17与8就是自然数对!
例如:输入:2 11
输出: 4 5
6 10
请大家按要求做题,一定要严密,贴上最优的代码!
由于本的能力有限,我想采取大家投票的方式取下届冠军.
请大家投自己最中意的程序编者!!
回复列表 (共72个回复)
31 楼
eastcowboy [专家分:25370] 发布于 2005-10-20 14:56:00
郑重宣布:我这个很可能是本楼目前为止所有程序中最快的。使用数学上的知识来化简。
首先假设我们已经找到两个数i,j,满足
i+j = x^2 , i-j = y^2 (这里假设i>j)
两式相乘,有i^2 - j^2 = (x*y)^2
移项得 j^2 + (x*y)^2 = i^2
所以j,x*y,i是一组勾股数。
古代埃及人已经发现,所有勾股数都满足下面这个式子:
j = 2*a*b
x*y = a^2 - b^2
i = a^2 + b^2
(假设a>b)
所以只要找到范围内的a,b就可以了。
由于i = a^2 + b^2 < max(这个max是用户输入的max),则a<sqrt(max)
又由于j = 2*a*b > min(这个min是用户输入的min),则a*b>(min/2)
又:a>b>=1,所以b>(min/2)
现在我们就可以编程了,虽然仍然有两个循环,但是计算量又以前的N*N/2下降到
sqrt(N) * sqrt(N) / 2,其中效率的差别不用我说了吧?如果不是1到100,而是1到100万的话,呵呵。我的方法所用的时间就是前面方法所用时间的算术平方根……
#include<stdio.h>
#include<math.h>
int main()
{ int i,j,a,b;
int min,max,lim;
int count = 0;
if(scanf("%d%d",&min,&max) == 0)
{ printf("输入有严重错误!退出程序……\n");
return 1;
}
while(min<1 || min>100 || max<1 || max>100 || min>max)
{ printf("数据有误,请重新输入:\n");
if(scanf("%d%d",&min,&max) == 0)
{ printf("输入有严重错误!退出程序……\n");
return 1;
}
}
lim = (int)sqrt(max)+1;
for(a=min/2;a<lim;++a)
for(b=a+1;b<lim;++b)
{ i = 2*a*b;
j = a*a + b*b;
if(i<min || j>max)
break;
printf("%8d%8d\n",i,j);
++count;
}
printf("共找到%d组解。\n",count);
return 0;
}
注意:此程序原来有点问题,现在已改正。想测试的朋友请重新测试。
32 楼
本人已死 [专家分:210] 发布于 2005-10-20 15:00:00
谁都可以参加么?
33 楼
eastcowboy [专家分:25370] 发布于 2005-10-20 15:00:00
各位可以把
while(min<1 || min>100 || max<1 || max>100 || min>max)
{ printf("数据有误,请重新输入:\n");
scanf("%d%d",&min,&max);
}
这段注释掉,(当然后面那个printf也注释掉)以后自己测试一下31楼的代码……
算1到100万也是瞬间的事。
34 楼
ppc [专家分:3090] 发布于 2005-10-20 15:20:00
#include <stdio.h>
#include <math.h>
void main()
{
int i,j,flag=0;
int m,n,t;
printf("Please input the two numbers:\n");
do
{
scanf("%d,%d", &m, &n);
if(m>=1 && m<=100 && n<=100 && n>=1)
break;
printf("input error, please input again. \n");
}while(1);
if(m < n)
{
t = m;
m = n;
n = t;
}
for(i = n; i <= m; i++)
for(j = n; j < i; j++)
{
if( pow((int)sqrt(i-j),2) == (i-j) && pow((int)sqrt(i+j),2) == (i+j))
{
flag = 1;
printf("%d %d\n",i,j);
}
}
if(flag == 0)
printf("There is no numbers\n");
}
35 楼
ppc [专家分:3090] 发布于 2005-10-20 15:27:00
回31,方法确实很妙,但是代码好像有问题,你的代码会在while时死循环
^_^
36 楼
garra [专家分:920] 发布于 2005-10-20 15:31:00
友情参加一下,不限于100以内的
#include <iostream.h>
#include <math.h>
void PrintPairNum(int i,int j,int small,int big)
{
int first,second;
first = (j*j - i*i)/2;
second = (j*j + i*i)/2;
if( first > small && second < big )
cout<<first<<" "<<second<<endl;
}
int main(int argc, char* argv[])
{
int small,big;
cin>>small>>big;
int sqt = sqrt(big*2);
for(int i = 1; i < sqt; i++)
{
for(int j = i+2; j <= sqt; j += 2)
{
PrintPairNum(i,j,small,big);
}
}
return 0;
}
37 楼
iAkiak [专家分:8460] 发布于 2005-10-20 15:39:00
garra这个好!
38 楼
lsylsy [专家分:400] 发布于 2005-10-20 15:51:00
这是我的,比较符合题意,也能大大减少冗余的计算。来看一下:
#include "math.h"
main()
{ int a,b,c,i,j,k;
float d;
scanf("%d",&a);
scanf("%d",&b);
if(a>b) i=a,j=b;
else i=b,j=a;
if(i<100&&j>0)
while(i>j)
{ for(k=i-1;k>=j;k--)
{ c=i-k;
if(c==1||c==4||c==9||c==16||c==25||c==36||c==49||c==64||c==81)
{ d=sqrt(i+k);
if(d-floor(d)==0) printf("%2d;%2d\t",k,i);
}
}
i--;
}
else printf("请输入0—100之间的整数");
}
39 楼
江大沙锅 [专家分:5660] 发布于 2005-10-20 15:52:00
刚下课,随便写了一下,不知错没错,试了几个结果还对
#include<stdio.h>
#include<math.h>
void main()
{
int n,m,i,j=1;
printf("请输入两个100之内的自然数\n");
scanf("%d%d",&n,&m);
for(i=n;i<=m;i++)
{
while((i+j*j)<=m)
{
if(sqrt(2*i+j*j)-(int)sqrt(2*i+j*j)==0)
printf("(%d %d) ",i,i+j*j);
//printf(" ");
j++;
}
j=1;
}
printf("\n");
}
40 楼
ppc [专家分:3090] 发布于 2005-10-20 15:53:00
这个方法应该和31楼的一样的。
却少了不少功能。
输入-1怎么办?
前面的比后面的大怎么办?
以上纯属抬杠^_^。
方法很好,是我想不到的,但是这是编程,不完全是比算法。
我来回复