算法题

Question

对于给定的一个数字正整数Ｎ，是否存在有几个连续数字相加等于Ｎ．
如：
１＋２＝３
４＋５＝９
２＋３＋４＝９１.给定一个数字，求出所有满足以上条件的表达式．
２.什么样的数字一定不存在以上的的情况？
３．Ｎ最多可以是几个连续数字相加的和？（这是＜编程之美＞上的一道题）
以下是我写的，不知道是否正确，大家看一下吧．
１.
public class ComputeH
    {
        public static void Compute(int x)
        {
            int cnt = (int)System.Math.Ceiling(((System.Math.Sqrt(8 * x + 1) - 1) / 2));            for (int i = 2; i <= cnt; i++)
            {
                if (i == 2 && x % 2 != 0)
                {
                    Console.WriteLine((x / 2) + "+" + ((int)System.Math.Ceiling((double)x / 2)) + "=" + x);
                }
                else if (i % 2 != 0 && x % i == 0)
                {
                    print1(x, i);
                }
                else if (i % 2 == 0 && x % i == i / 2)
                {
                    print2(x, i);
                }
            }
        }        private static void print1(int x,int i)
        {
            int[] tmp = new int[i];            for (int j = 0; j < i; j++)
            {
                tmp[j] = x / i;
            }            for (int j = 0; j < (i / 2); j++)
            {
                tmp[j]-=(i/2-j);
                tmp[i-j-1] += (i/2 - j);
            }            printArray(tmp, x);
        }        private static void print2(int x, int i)
        {
            int[] tmp = new int[i];            for (int j = 0; j < i; j++)
            {
                tmp[j] = x / i;
            }
            tmp[i - 1] += x % i;            for (int j = i-2; j >= 1; j--)
            {
                int t = tmp[j];
                tmp[j] += (tmp[j + 1] - 1 - t);
                tmp[j - 1] -= (tmp[j + 1] - 1 - t);
            }            printArray(tmp, x);
        }        private static void printArray(int[] array,int x)
        {
            for (int j = 0; j < array.Length  - 1; j++)
            {
                Console.Write(array[j] + "+");
            }            Console.WriteLine(array[array.Length - 1] + "=" + x);
        }
    }
２.当Ｎ＝2^x的时候，一定有满足的表达式．至于原因我说不太清楚．我想的是
Ｎ＝2^x=2*2^(x-1)
因为２本身就没有能满足以上条件的表达式，所以2*2^(x-1)也不会满足．３.第三个问题可以用∑来求．也就是１到x的和等于Ｎ．,推理公式为：
x*(x+1)/2=N
x=(sqrt(8*N+1)-1)/2
也就是Ｎ最多可以由x项结成．

Answer 1

对于第二个问题，有两种连续数字
1. m-n, ... m-1, m, m+1, ... ,m+n 奇数个连续数 2n+1个
2. m-n+1, ... m, m+1, ... ,m+n 偶数个连续数 2n个对于1. 其和为 (m-n + m+n)*(2n+1)/2=m*(2n+1)
对于2. 其和为 (m-n+1 + m+n)*2n/2 = (2m+1)*n综合1，2，可以看到，连续若干个数相加得到的结果一定包含一个奇数因子。因此，一定不能被分解成若干个连续数相加的数就是2^x。因为2^x不包含奇数因子

Answer 2

如果一个数k能够写成若干个连续数的和，比如i+...+j，那么可以列一个求和公式，(1+2+....j) - (1+2+...i-1) = k，根据求和公式，j*(j+1) / 2 - (i-1)*i /2 = k => j^2 + j - i^2 + i = 2k 变化一下，(j^2 - i^2) + j + i = 2k => (j + i)(j - i) + (j + i) = 2k => (j+i)(j-i+1) = 2k因此只要对2k做因式分解，就可以求出j和i

Answer 3

用穷举算法貌似可以，解方程。X+Y=N。这样貌似可以吧？

Answer 4

恩，是个好方法呀．
通过求出j的范围，然后带入方程求i.那j的最大值应该是什么呢．n/2吗？

Answer 5

连续数相加
N+(N+1)+....+(N+k)=(k-1)*N*(1+k)*k/2
大概意思如此
直接循环解方程可以得出解

Answer 6

我觉的还是的规律的．如果N分为X(X为奇数)个连接的数相加，满足N%X=0,则N必可分为X个连续的数相加．如果N分为X(X为偶数)个连接的数相加．满足N%X=X/2的话，则N必可分为X个连续的数相加.且Ｘ个连续个数中最大的一项为N/X+N%X

Answer 7

直接对待求的数k*2的约数，比如k = 9,2*k = 1818 = 1 * 18
18 = 2 * 9
18 = 3 * 6那么每一种不同的分解，都有可能对应一组解（去掉解不是整数的情况）(j+i)(j-i+1) = 18
设 j + i = 18, j - i + 1 = 1 => j = 9, i = 9(只有1个数，舍去）
设 j + i = 9, j - i + 1 = 2 => j = 5, i = 4(解 4+5 = 9)
设 j + i = 6, j - i + 1 = 3 => j = 4, i = 2(解 2+3+4 = 9)