Fig: A 4x4 Grid Fig: A 4x4x4 Cube 這是一道數(shù)學(xué)題吧。想清楚之后就發(fā)現(xiàn)就是求累加和。
問題是給定一個正方形(體,超體)，求其中的所有的正方形(體,超體),長方形(體,超體)。 比如，4 * 4的正方形中，有14個正方形，
22個長方形，4 * 4 * 4的立方體中有36個正方體，180個長方體。依次類推，超正方體指的是四維空間。
觀察一下一個4*4正方形中，仔細(xì)驗(yàn)證一下就會發(fā)現(xiàn)，正方形的個數(shù)是 Σ(4 - i + 1) * (4 - i + 1)(其中i從1到4)，長方形的個數(shù)是
Σ(4 - i + 1) (其中j從1到4) * Σ(4 - j + 1)(其中j從1到4)。如果變成3維的就多一層k，k也從1變化到4。如果變成4維的就再多一層l，
l也從1變化到4。
然后變換一下，就可以得到s2(n) = 1^1 + 2^2 + ... + n^n，s3(n)則是對立方的累加和，s4(n)則是對四次方的累加和。
再計算r2(n)。可以先把正方形包括在內(nèi)計算出所有的和。那么r2(n) = Σ(n - i + 1) * Σ(n - j + 1) - s2(n)。如果直接進(jìn)行這個式子
的求和話很復(fù)雜。再觀察一下這個式子，因?yàn)閚 - i + 1的變化范圍就是1到n，那么上面的式子可以變化為 r2(n) = ΣΣi * j - s2(n)。
意思是求i*j的和，i和j都是從1變化到n。很簡單就可以得到r2(n) = pow(n * (n + 1) / 2, 2) - s2(n)。同樣的求和可以得到，
r3(n) = pow(n * (n + 1) / 2, 3) - s3(n)。r4(n) = pow(n * (n + 1) / 2, 4) - s4(n)。
另外如果不知道平方和，立方和，四次方和的公式，也可以迭代計算，復(fù)雜度也是O(100)。這樣的話，根本不需要使用這些難記憶的公式了。
代碼如下：
#include <stdio.h>
#include <math.h>
unsigned long long s2[101];
unsigned long long r2[101];
unsigned long long s3[101];
unsigned long long r3[101];
unsigned long long s4[101];
unsigned long long r4[101];
int main()
{
unsigned long long i = 0;
while (i <= 100)
{
s2[i] = i * (i + 1) * (2 * i + 1) / 6;//平方和
s3[i] = i * i * (i + 1) * (i + 1) / 4;//立方和
s4[i] = i * (i + 1) * (6 * i * i * i + 9 * i * i + i - 1) / 30;//四次方和
r2[i] = pow(i * (i + 1) / 2, 2) - s2[i];
r3[i] = pow(i * (i + 1) / 2, 3) - s3[i];
r4[i] = pow(i * (i + 1) / 2, 4) - s4[i];
++i;
}
int nN;
while (scanf("%d", &nN) != EOF)
{
//printf("%I64u %I64u %I64u %I64u %I64u %I64u\n", s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
printf("%llu %llu %llu %llu %llu %llu\n", s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
}
return 0;
}