|
2010年11月23日
由于javaeye现在可以访问,下面的内容将在javaeye中,博客地址 http://clumsybird.javaeye.com
摘要: 问题描述如下:
“一个20*20的数组如下所示
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
 ... 阅读全文
问题描述如下:
“ 毕达哥拉斯三元数组存在{a,b,c},a<b<c,使得a^2+b^2=c^2,如3^2+4^2=5^2=25,求a,b,c满足以上条件,并使a+b+c=1000,给出a*b*c的值。”
代码如下:
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 求毕达哥拉斯三元数组{a,b,c},使得a+b+c=target . 毕达哥拉斯三元数组存在{a,b,c},a<b<c,使得a^2+b^2=c^2
* a > 3,(target-(a+b))^2=c^2=a^2+b^2 --> target^2=2*target*(a+b)-2ab
*
* @return
*/
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) private static int getNumber(int target) {
int a = 0;
int b = 0;
int c = 0;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (int i = 3; i < target; i++) {
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (int j = i; j < target; j++) {
if (target * target == 2 * target * i + 2 * target * j - 2 * i
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) * j) {// target^2=2*target*(a+b)-2ab
a = i;
b = j;
break;
}
}
}
c = target - a - b;
return a * b * c;
}
具体的分析可以看代码注释。得出结果 31875000。
除了直接的办法,应该还有另外的方法来求,保持未完待续状态。
请不吝赐教。
@anthor ClumsyBird
问题叙述如下:
“2520是最小的数能够整除1到10,求能被1到20所整除的最小的数?”
代码如下:
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 数字i从m到n,遍历,如果i不能被result整除,我们就将i除以i与result的最大公约数,并与当前result想乘
*
*/
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) private static int getNumber(int m, int n) {
int result = n;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (int i = n - 1; i >= m; i--) {
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (result % i != 0) {
result *= i/gcd(result,i);
}
}
return result;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 最大公约数:欧几里德算法 定理:gcd(a,b) = gcd(b,a mod b)
*
* @param a
* @param b
* @return
*/
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) private static int gcd(int a, int b) {
if (b != 0)
return gcd(b, a % b);
else
return a;
}
调用getNumber(1,20)即可得到答案232792560。
由于在此用到最大公约数,所以在下面给出了一些实现。
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 最大公约数:欧几里德算法
* @param a
* @param b
* @return
*/
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) private static int gcd1(int a, int b) {
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (a > b) {
gcd1(b, a);
}
int temp = 0;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (; b != 0;) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 最大公约数:Stein算法 gcd(ka,kb) = k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换,
* 特殊的,当k=2时,说明两个偶数的最大公约数必然能被2整除
*
* @param a
* @param b
* @return
*/
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) private static int gcdByStein(int a, int b) {
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (a > b) {
gcdByStein(b, a);
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (b == 0) {
return a;
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (a % 2 == 0 && b % 2 == 0) {
return 2 * gcdByStein(a / 2, b / 2);//a,b都是偶数
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (a % 2 == 0) {
return gcdByStein(a / 2, b);//仅a为偶数
}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (b % 2 == 0) {
return gcdByStein(a, b / 2);//仅b为偶数
}
return gcdByStein((a + b) / 2, (a - b) / 2);//a,b都是奇数
}
如果有其他的方法,也请贴出大家一起讨论。^_^
请不吝赐教。
@anthor ClumsyBird
|