为什么80%的码农都做不了架构师？>>> 
一个有趣的问题：
A triplet of positive integers (a,b,c) is called a Cardano Triplet if it satisfies the condition:
For example, (2,1,5) is a Cardano Triplet.
There exist 149 Cardano Triplets for which a+b+c 
1000.
Find how many Cardano Triplets exist such that a+b+c 110,000,000.
首先可以把问题的表达式可以化成：
8a^3 + 15a^2 + 6a - 1 = 27b^2*c
然后使用穷举法遍历a，b，c可以取的所有值，判断是否满足上述表达式：
int CardanoTriplets1(int Max)
{
long a, b, c;
long count = 0;
for(a = 1; a < Max; a++)
{
for(b = 1; b < Max - a; b++)
{
for(c = 1; c <= Max - a - b; c++)
{
if((8*a*a*a + 15*a*a + 6*a - 1) == 27*b*b*c)
{
count++;
}
}
}
}
return count;
}
可以根据问题的性质对算法稍作改进：
第一，可以证明a满足a = 2 (mod 3)或者2a = 1 (mod 3)，证明略
第二，给定a的值以后，有：
b^2*c = S
b + c = K
S和K都是a的表达式，从上面两式可以求出b的一个下界和上界：
4 * S / K^2 <= b <= S^0.5
由此可以给出程序：
int CardanoTriplets2(int Max)
{
long a, b, c;
long count = 0;
double S, K, b_min, b_max;
double t;
for(a = 1; a < Max; a++)
{
if(a % 3 == 2)
{
K = Max - a;
t = 1.0 - 2.0 * a;
S = a * a - t*t*t/27.0;
b_min = 4.0 * S / K / K - 1;
b_max = sqrt(S) + 1;
if(b_min < 1) b_min = 1;
if(b_max > K) b_max = K;
for(b = (long)b_min; b <= (long)b_max; b++)
{
c = (long)S / b / b;
if(c >= 1 && (b * b * c) == S && (b + c) <= K)
{
//cout<<"("<<<","<<<","< <<")"<
count++;
}
}
}
}
return count;
}
随机文章：
收藏到： Del.icio.us
