#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; }
这是一个数学题，比较有意思。题意大致是：有2条平行的直线，第一条上面有m个点，第二条上面有n个点。那么连接这写点能产生mn条直线(不包括和原来的执行平行的直线)。问这mn直线最多有多少个内交点(意思是不属于原来m,n个点的交点)… 想来想去，推理了1个多小时才出来正式结果。感觉比较有意思，写篇博文记录下。我先是从反面排除，想了试了好久到最后还是发现无法排除干净。。。最后只能从正面开始求证了。我这样定义一条执行(i，j)，其中i代表在第一条直线中的端点，j代表在第二条直线中的端点。显然1 现在的话只要求出和直线(i，j)相加的直线有多少条，然后对i，j进行累加求和。再对和除以2就能得到答案了。 那么有多少条直线能和直线(i，j）相交了。很显然，和(i,j)相交的直线的端点必须在其两侧。意思是在第一条直线中的端点范围为[1, i - 1],在第二条直线中的端点范围为[j + 1, n]，总结(i - 1) (n - j) 条直线。但是还有第二种情况,在第一条直线中的端点范围为[i + 1, m], 在第二条直线中的端点范围为[1, j - 1]，总计(m - i) (j - 1) 条直线。总计sum = i n + i - m -n + j (m - 2 i + 1) 条直线。 再求Σsum（j从1到n)得到和式(mnn - mn - nn + n) / 2，再对这个式子进行i从1到m的累加。因为没有i了，其效果就是乘以m。然后最终的和除以2，所以最后的表达式是(mmnn - mmn - mnn + mn) / 4。这个式子显然是关于m,n对称的。这一点也可以验证这个式子的正确性。
程序写起来就很简单了，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#include <iostream> using namespace std;
int main() { long long m, n; int nCases = 0;
while (cin >> m >> n, m + n != 0) { long long a = m * m; long long b = n * n; cout << ";Case "; << ++nCases << ";: "; << (a * b - a * n - b * m + m * n) / 4 << endl; }
#define MAX (10) int main() { Init(); int i; for (i = 0; i < MAX; ++i) { Insert(i); } for (i = 0; i < MAX; ++i) { printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure"); } printf("\n");
Delete(4); Delete(9); Delete(1); for (i = 0; i < MAX * 2; ++i) { printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure"); }
#include <stdio.h> #include <string.h> #include <string> #include <map> #include <vector> #include <algorithm> #define MAX (100) using std::map; using std::string; using std::vector; using std::sort;
void pop() { if (nTime % 2) { while (!one.empty()) { T t = one.front(); one.pop(); if (!one.empty()) { two.push(t); } } } else { while (!two.empty()) { T t = two.front(); two.pop(); if (!two.empty()) { one.push(t); } } }
nTime = (nTime + 1) % 2; --nSize; }
T& top() { if (nTime % 2) { while (!one.empty()) { T t = one.front(); one.pop(); if (!one.empty()) { two.push(t); } else { two.push(t); nTime = (nTime + 1) % 2; return two.back(); } } } else { while (!two.empty()) { T t = two.front(); two.pop(); if (!two.empty()) { one.push(t); } else { one.push(t); nTime = (nTime + 1) % 2; return one.back(); } } } }
bool empty() { return nSize == 0; }
private: queue<T> one; queue<T> two; int nSize; int nTime; };
#define MAX 20
int main() { CStack<int> stack;
for (int i = 0; i < MAX; ++i) { stack.push(i); }
while (!stack.empty()) { printf("top: %d\n", stack.top()); stack.pop(); }
