|
|
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的值。”
代码如下：
  /** *//**
 * 求毕达哥拉斯三元数组{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
 */
private static int getNumber(int target)  {
int a = 0;
int b = 0;
int c = 0;
  for (int i = 3; i < target; i++) {
for (int j = i; j < target; j++) {
if (target * target == 2 * target * i + 2 * target * j - 2 * i
* 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所整除的最小的数？”
代码如下：
/** *//**
* 数字i从m到n，遍历，如果i不能被result整除，我们就将i除以i与result的最大公约数，并与当前result想乘
*
*/
private static int getNumber(int m, int n) {
int result = n;
for (int i = n - 1; i >= m; i--) {
if (result % i != 0) {
result *= i/gcd(result,i);
}
}
return result;
}
/** *//**
* 最大公约数：欧几里德算法 定理：gcd(a,b) = gcd(b,a mod b)
*
* @param a
* @param b
* @return
*/
private static int gcd(int a, int b) {
if (b != 0)
return gcd(b, a % b);
else
return a;
}
调用getNumber(1,20)即可得到答案232792560。
由于在此用到最大公约数，所以在下面给出了一些实现。
/** *//**
* 最大公约数：欧几里德算法
* @param a
* @param b
* @return
*/
private static int gcd1(int a, int b) {
if (a > b) {
gcd1(b, a);
}
int temp = 0;
for (; b != 0;) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
/** *//**
* 最大公约数：Stein算法 gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，
* 特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除
*
* @param a
* @param b
* @return
*/
private static int gcdByStein(int a, int b) {
if (a > b) {
gcdByStein(b, a);
}
if (b == 0) {
return a;
}
if (a % 2 == 0 && b % 2 == 0) {
return 2 * gcdByStein(a / 2, b / 2);//a,b都是偶数
}
if (a % 2 == 0) {
return gcdByStein(a / 2, b);//仅a为偶数
}
if (b % 2 == 0) {
return gcdByStein(a, b / 2);//仅b为偶数
}
return gcdByStein((a + b) / 2, (a - b) / 2);//a,b都是奇数
}
如果有其他的方法，也请贴出大家一起讨论。^_^
请不吝赐教。
@anthor ClumsyBird
|