编程之美2.21 只考加法的面试题

kon3155

我们知道： 1+2=3 4+5=9 2+3+4=9 等式左边都是两个以上连续的自然数相加，那么是不是所有的整数都可以写成这样的形式呢？稍微考虑一下，我们发现，4、8等数并不能写成这样的形式。 【问题1】写一个程序，对于一个64位正整数，输出它所有可能的连续自然数（两个以上）之和的算式。 【问题2】大家在测试上面程序的过程中，肯定会注意到一些数字不能表达为一系列连续的自然数之和，例如32好像就找不到。那么，这样的数字有什么规律呢？能否证明你的结论？ 【问题3】在64位正整数范围内，子序列数目最多的数是哪一个？这个问题要用程序蛮力搜索，恐怕要运行很长时间，能否用数学知识推导出来？

mathe

这个问题比较简单.我怎么记得这里问过的

winxos

$a(n+1)+(n(n+1))/2$

〇〇

记录学习

tprime

这题很简单的, POJ上有到类试题 int main( ) { int n,w; while(scanf("%d",&n) == 1) { while (n%2 == 0) n >>= 1; if(n == 1) { w = 1; continue; //无解条件： n &(n -1) == 0 } w = 2; int s = sqrt(n); for(int i = 3; i < s + 1; i += 2) if(n%i == 0) w += 2; if(s * s == n) w--; printf("%d\n",w); } return 0; }

tprime

上面只计算的分解的组数，简单改改 能满足题目的要求， 此题的复杂度是O(n^1/2) 最难的第3问，需要质因数快速分解算法，进行枚举

〇〇

任何奇数都可以 2n+1 =n+(n+1) 如果是偶数,必须是3的倍数，6n=2n-1+2n+2n+1

mathe

第三问显然要通过使用构造法.要让n有尽量多的奇数因子(不大于${sqrt(1+8n)+1}/2~=sqrt(2n)$),这个至少可以通过线性规划来做.

tprime

要使n的因子个数尽量多 不妨设 n的最大素因子maxfactor 为 (5,7,11,13,17) 中的一个 进行枚举 n = 3^p1 * 5^p2 * 7^p3 * ... maxfactor^pn 满足 n < 2^64, 然后算出p1,p2, ...pn的所有组合 再进行判断

kon3155

任何奇数都可以 2n+1 =n+(n+1) 如果是偶数,必须是3的倍数，6n=2n-1+2n+2n+1 〇〇 发表于 2009-10-13 21:18

10=1+2+3+4