POJ 1844 Sum

Bright Star — Mon, 18 May 2009 16:22:00 GMT

一、题目描述

为从1到N的N个自然数每个分配一个符号（+或者-），并计算这个表达式的和sum。问题是对于给定的数S，计算最少需要多少个自然数，使得可以通过分配符号给这1到N个数来得到S。（0）比如，12 = -1+2+3+4+5+6-7，则对于给定的数S=12，最少需要7个数来得到12。

二、解题思路

假设T(S)表示输入为S时的输出结果，如T(12)=7。给定一个数S=10的话，我们就会从1开始计算累加和1+2+3+4=10，需要4个数，每个数分配的符号都是正号，这4个数之和刚好为10。4必定是最小的，因为没有分配负号,所以T(10)=4。其它的数如6=1+2+3，3=1+2都是这种情况。但是并不是所有数是这种情况，比如11，则不行。这时我们找到一个最小数N，使得1+2+...+N>=S，这时N=5。1+2+3+4+5=15。这里d=15-11=4，d/2=2，如果把其中2的符号变为负号的话，就能得到1-2+3+4+5=11；结果就是T(11)=5。如果上面的d是个奇数的话，则d=1+2+…+N+N+1-S一定是个偶数，得到的结果便是T(S)=N+1。例如7=1+2+3-4+5，因为d=1+2+3+4-7=3是奇数，我们再加上一个5的话，d=1+2+3+4+5-7=8是偶数，d/2=4只需要把4变成负号就能满足7=1+2+3-4+5。把这个规律可以拓展到一般情况。

三、源代码

1#include <iostream>
2#include<math.h>
3using namespace std;
4/*
5描述：求连续自然数之和
6参数：i是开始的元素，j是最一个元素
7返回：返回i+(i+1)++j的值
8*/
9int SumFromTo(int i,int j)
10{
11    return (i+j)*(j-i+1)/2;
12}
13/*
14描述：获取一个最小的数N，使得1+2++N>=Sn
15参数：N保存返回的结果
16返回：如果1+2+..+N==Sn,返回true,否则返回false
17*/
18bool GetN(int Sn, int & N)
19{
20    double n=sqrt(2*Sn+0.25)-0.5;
21    N=n;
22    if(n==N)
23        return true;
24    else
25        return false;
26
27}
28int main()
29{
30    int S;
31    cin>>S;
32    int n;
33    bool b=GetN(S,n);
34    if(b)
35    {
36        cout<<n<<endl;
37    }
38    else
39    {
40        do
41        {
42            n++;
43        } while((SumFromTo(1,n)-S)%2!=0);
44        cout<<n<<endl;
45    }
46    return 1;
47}
48

四、复杂度分析
上面那个while()最多执行两次，故复杂度为O(1)。

Bright Star 2009-05-19 00:22 发表评论

C++博客-BrightStar's Blog

POJ 1844 Sum