|
|
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
|