kon3155 发表于 2009-10-9 14:49:29

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

我们知道：
1+2=3
4+5=9
2+3+4=9
等式左边都是两个以上连续的自然数相加，那么是不是所有的整数都可以写成这样的形式呢？稍微考虑一下，我们发现，4、8等数并不能写成这样的形式。

【问题1】写一个程序，对于一个64位正整数，输出它所有可能的连续自然数（两个以上）之和的算式。

【问题2】大家在测试上面程序的过程中，肯定会注意到一些数字不能表达为一系列连续的自然数之和，例如32好像就找不到。那么，这样的数字有什么规律呢？能否证明你的结论？

【问题3】在64位正整数范围内，子序列数目最多的数是哪一个？这个问题要用程序蛮力搜索，恐怕要运行很长时间，能否用数学知识推导出来？

mathe 发表于 2009-10-9 17:59:23

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

winxos 发表于 2009-10-9 22:32:31

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

〇〇 发表于 2009-10-10 08:00:31

记录学习

tprime 发表于 2009-10-13 09:57:00

本帖最后由 tprime 于 2009-10-13 10:03 编辑

这题很简单的, 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 发表于 2009-10-13 10:01:52

上面只计算的分解的组数，简单改改
能满足题目的要求， 此题的复杂度是O(n^1/2)

最难的第3问，需要质因数快速分解算法，进行枚举

〇〇 发表于 2009-10-13 21:18:33

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

mathe 发表于 2009-10-13 22:27:55

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

tprime 发表于 2009-10-14 10:23:14

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

kon3155 发表于 2009-10-14 11:56:56

任何奇数都可以 2n+1 =n+(n+1)
如果是偶数,必须是3的倍数，6n=2n-1+2n+2n+1
〇〇 发表于 2009-10-13 21:18 http://bbs.emath.ac.cn/images/common/back.gif

10=1+2+3+4
页: [1] 2
查看完整版本: 编程之美2.21 只考加法的面试题