出个题目，大家求解 - 编程论坛

#2

csmenglei9512007-11-03 19:56

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int a,b;
for( a=1000;a<10000;a++)
{
for( b=1000;b<10000;b++)
{
if(a+b==sqrt(a*10000+b))
cout<<a*10000+b<<endl;
}
}
return 0;
}
这个程序算法效率很低，惭愧．．抛砖引玉

#3

a217zxg2007-11-03 20:33

哈哈不错，我就知道这个有人会写的，循环次数多了，自然慢了一点，C++代码效率本来就不高的。

#4

zhoulikelvjj2007-11-03 20:34

这只是8位的。
#include<iostream>
#include<conio.h>

using namespace std;

int main()
{
int i,j,n;
long m;
for(i = 1001;i <= 9999;i++)
for(j = 1001;j <= 9999;j++){
n = i + j;
m = i * 10000 + j;
if( m == n*n)cout << m << endl;
}
cin.get();
return 0;
}

#5

zhoulikelvjj2007-11-03 20:38

我的要比2楼的快不少...不过只是算8位的.搂主应该说明数的范围,否则算法应该不一样了

#6

aipb20072007-11-03 20:48

以下是引用zhoulikelvjj在2007-11-3 20:38:21的发言：
我的要比2楼的快不少...不过只是算8位的.搂主应该说明数的范围,否则算法应该不一样了

没看出来你比2楼快在哪里！

#7

zhoulikelvjj2007-11-03 21:18

斑竹把程序运行下就能看出来了

#8

孤魂居士2007-11-03 23:22

都是差不错感觉不到

#9

leeco2007-11-03 23:57

/*
分析：
x+y=z
z*z=10000x+y
去掉参数z得 (x+y)^2=10000x+y
二元二次不定方程,其中1000<=x<10000,0<=y<10000,x,y属于Z
其解即是要求的

做如下变形
z=x+y
z^2=z+9999x
z^2-z=9999x
所以，有必要条件(z^2-z)(mod 9999)=0
即(z(z-1))(mod 9999)=0

算法设计，不妨枚举9999的倍数，再测试z(z-1)=x*9999是否有解，最后核查x,y的合法范围。
*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main()
{
int x,y,z;
for(x=1000;x<10000;x++){
z=(int)ceil(sqrt(9999.0*x));
if(z*(z-1)!=9999*x)continue;
y=z-x;
if(y>=10000 || y<0)continue;
printf("%.4d%.4d\n",x,y);
}
//system("pause");
}

#10

csmenglei9512007-11-04 14:02

9楼的算法的确很好．．.
ceil是返回一个大于或等于其参数的正整数．．你怎么就确定Z就是你要找的那个值了？

#11

nuciewth2007-11-04 16:04

z=a+b;
z^2==a*10000+b;
(z-1)*z==a*9999//a一定要是偶数
z^2-z-a*9999==0;
z=[1+sqrt(1+4*a*9999)]/2
直接遍历a解方程组做判断.

#12

leeco2007-11-04 16:20

以下是引用csmenglei951在2007-11-4 14:02:27的发言：
9楼的算法的确很好．．.
ceil是返回一个大于或等于其参数的正整数．．你怎么就确定Z就是你要找的那个值了？

如果z*(z-1)=C,那么
必然存在一个w，z-1<w<z,使得w^2=C
因此z=ceil(w)=ceil(sqrt(C))

反之，如果z=ceil(sqrt(C))
是否一定有z*(z-1)=C不确定
所以我用if(z*(z-1)!=9999*x)continue;做了验证

#13

yanyananlin2007-11-04 19:44

回复:9楼

请问这是什么意思啊？
(z^2-z)(mod 9999)=0
即(z(z-1))(mod 9999)=0

#14

a198705022007-11-05 10:53

不好意思,新手~~
(z^2-z)(mod 9999)=0
mod是什么来的~~~我试过去找的啦~~~不过找不到.麻烦了.

#15

duccdd2007-11-05 11:07

int a, b, n;

//在8位的平方数中找答案
for( int i = 3163; i <= 9999; i++ )
{
n = i * i;
a = n / 10000;
b = n % 10000;
if( a + b == i ) cout << n << endl;
}

#16

jonc2007-11-10 09:04

的确9楼的算法不错！
学习了！
顶一下！