求助编程高手帮忙设计最优算法

来源：百度知道 编辑：UC知道 时间：2024/06/19 12:25:35
我们很熟悉勾股定理：a^2+b^2=c^2; 现在的等式有了些许的变化a^2+b^2=c^2-c（1<=a<=b<=c);
如果给你一个整数，请你算出小于等于这个数且符合等式的数对的个数。
最多输入三百个数，最后一个数为0，不做处理
每个数都小于10000；
注：time limit：5s；memory limit：65536K
最好使用C/C++.
如：
输入：6
输出：2
输入：9
输出：3
输入：0
退出程序。
请写出完整程序代码，并分析算法。
如输入6
则有
1*1+1*1==2*2-2
2*2+4*4==5*5-5
共两种情况
输出2

我的算法比楼下你们时间少，但还不能满足要求。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int loop=1,n,x,i;
double a;
int b,c;
cin>>n;
while((n!=0)&&(loop<301))
{
i=0;
if(n==1)
cout<<0<<endl;
else
{
for(c=2;c<=n;c++)
{
x=sqrt((c*c-c)/2);
for(b=x;b<c;b++)
{
a=sqrt(c*c-c-b*b);
if(a==int(a))//判断a是否为整数，是则满足等式
i++;
}
}
cout<<i<<endl;
}
ci

开一个10000大小的数组，先做一个初始化工作，把n=1~10000的所有解找出来，然后再循环输入n，输出s[n]即可

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int loop=1,n,x,i=0;
int s[10000];
double a;
int b,c;

for(c=2;c<=10000;c++)
{
x=sqrt((c*c-c)/2);
for(b=x;b<c;b++)
{
a=sqrt(c*c-c-b*b);
if(a==int(a))
i++;
}
s[c-1]=i;
}
s[0]=0;

cin>>n;
while((n!=0)&&(loop<301))
{
cout<<s[n-1]<<endl;
cin>>n;
loop++;
}
return(0);
}

用楼主的办法，加上以空间换时间，可行的：
#include<iostream>
#include<cmath>
using namespace std;
#define N 10000
int main()
{ // a^2 + b^2 = c^2 - c
cout<<"开始"<<endl;
int numret[N] = { 0 }; // 每个数对应的数对量

int x ;
double a;
int b