题记:本文为第一篇技术贴
题目:给定一个输入的正整数X,求出X的所有可以被表示为 n(n>=2) 个连续正整数之和的形式:
如:15=15=7+8=4+5+6=1+2+3+4+5
(该题目可以说是骨灰级的题目了,我做了简单的改变,便于分析)
程序的实现(改方法是我能想到的最简单的一种了,如有更快的,请各位赐教)
程序代码:
int main(){
int exist = 0;
int x = 0;
printf("Please input x:");
scanf("%d", &x);
for(int n = 1; n * n < x * 2; ++ n){
int a = (2 * x / n - n + 1) / 2;
if( n * a + n * (n - 1) / 2 == x){
for(int i = 0; i < n; ++i)
printf("%d ", a + i);
printf("\n");
have = 1;
}
}
if(!exist)
printf("none\n");
}
可是题目并没有在此结束,
如果计算n的所有表示方式的种类数(记为k(n)),有如下序列(n=1..20):
1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 4, 1, 2, 3, 2, 2
通过搜索,发现这个序列还有其他的含义:
1. Number of odd divisors of n;
2. Number of ways to write n as difference of two triangular numbers;
3. Number of ways to arrange n identical objects in a trapezoid;
4. Number of sums of sequences of consecutive positive integers including sequences of length 1;
5. Number of factors in the factorization of the Chebyshev polynomial of thee first kind T_n(x);
6. Number of ways to present n as sum of consecutive integers;
7. Number of factors in the factorization of the polynomial x^n+1 over the integers.
其中4就是程序所描述的方式。其描述很特别,尤其是第一个。很惊异其中的关系。
搞了很久也不知道其中的缘由,请各位赐教。