VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 3241|回复: 19

无奖竞猜 因为咱也囊中羞涩

[复制链接]
25_avatar_middle
在线会员 发表于 2009-11-15 23:26:32 | 显示全部楼层 |阅读模式
求连续整数的固定和
  要求:  编写一个程序 读入一个正整数,把所有连续的和为给定正数的正整数找出来
  例如 输入 27 于是发现 2~7, 8~10, 13~14 的和是 27  注意:不一定会有
  答案  例如 4,16 就无解  排除只有一个数的情况   
   (尽量 时间上 和 空间上 更优)
  大家开始热烈的讨论吧!  本贴旨在相互学习

评分

参与人数 1驿站币 +8 收起 理由
56_avatar_small zhaoshengbo + 8

查看全部评分





上一篇:欢迎大家来出题
下一篇:【竞猜】非程序(放松下...)
81_avatar_middle
online_moderator 发表于 2009-11-16 10:46:47 | 显示全部楼层
可能是我愚笨,楼主能否再说的详细点?没十分的明白题意?
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 11:26:05 | 显示全部楼层
就是说 随便输入一个正整数数  例如 27
就要求出所有连续正整数的和是 27  
其中符合要求的 有 2+3+4+5+6+7+8 =27
                                 8+9+10=27
                                   13+14=27
但是不能是  27 =27
  4, 和16  就找不到这样的连续正整数
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 11:31:17 | 显示全部楼层
2+3+4+5+6+7=27
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 12:17:59 | 显示全部楼层

RE: 无奖竞猜 因为咱也囊中羞涩

C:\Documents and Settings\Administrator\桌面\未命名.jpg
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 12:43:46 | 显示全部楼层

RE: 无奖竞猜 因为咱也囊中羞涩


  1. #include "iostream.h"
  2. #include "stdlib.h"

  3. void consecutive(long given)   //求出所有方案 比将其输出
  4. {
  5.    //大家填充这个函数
  6. }
  7. int main()
  8. {
  9.         long given;
  10.         char line[100];

  11.         do
  12.         {
  13.                 cout<<" \n 求连续正整数的固定和  =============="<<endl;
  14.                         cout<<"==============================="<<endl;
  15.                 cout<<"请你输入一个正整数     ================"<<endl;
  16.                 cout<<"输入小于<=0 的数结束=================="<<endl;
  17.                 cin>>line;
  18.                 given=atol(line);

  19.                 consecutive(given);

  20.         }while(given>0);
  21.         return 1;
  22. }
复制代码
92_avatar_middle
在线会员 发表于 2009-11-16 16:13:27 | 显示全部楼层
数据范围是多少?
92_avatar_middle
在线会员 发表于 2009-11-16 16:36:43 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;

  3. const int MAX = 1000000;        //给定数的最大范围
  4. int sum[MAX+1];

  5. void init()
  6. {
  7.         sum[0] = 0;
  8.         for(int i=1; i<=MAX; i++)
  9.         {
  10.                 sum[i] = sum[i-1] + i;
  11.         }
  12. }

  13. int main()
  14. {
  15.         int number;
  16.         init();

  17.         while(cin >> number)
  18.         {
  19.                 bool isFound = false;
  20.                 for(int i = 1; i <= ((number+1) >> 1); i++)
  21.                 {
  22.                         for(int j=0; j < i; j++)
  23.                         {
  24.                                 int tmp = sum[i] - sum[j];
  25.                                 if(tmp < number)
  26.                                         break;
  27.                                 else if(tmp == number)
  28.                                 {        //输出
  29.                                         for(int k = j+1; k <= i; k++)
  30.                                                 cout << k << " ";
  31.                                         cout << endl;
  32.                                         isFound = true;
  33.                                 }
  34.                         }
  35.                 }
  36.                 if(!isFound)
  37.                 {
  38.                         cout << "不存在!\n";
  39.                 }
  40.         }

  41.         return 0;
  42. }
复制代码
暴力的,时间复杂度O(N^2), 空间复杂度O(N)
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 17:42:41 | 显示全部楼层
你这个也暴力了吧!
那你最大也只能求1000000之内的数啊!
  我定义的 long 型  可以求 10 的38 次方的数哦  这就是38 的整数
   那定义一个10 的38 次方维度的数组不好吧
92_avatar_middle
在线会员 发表于 2009-11-16 17:53:09 | 显示全部楼层
long型只有4字节 32位   10的10次方级别
unsigned long long int 也只有10的20次方级别
如果你的数字很大的话数组的确开不出,数组一般只能开到10的8次
47_avatar_middle
在线会员 发表于 2009-11-16 19:41:31 | 显示全部楼层
可惜,我不能给你评分!
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 21:15:38 | 显示全部楼层
回复 11# yangyucun
这么挺我,我受宠若惊了!
   我准备在讨论之余 在稍稍开展一下
92_avatar_middle
在线会员 发表于 2009-11-16 21:26:12 | 显示全部楼层
根据题目可以发现,每组符合条件的连续整数的最小最大值是不同的,我们不妨依次找每一组,因而能优化到时间复杂度为O(N),空间复杂度为O(1). 应该还有其他规律可以找,比如分解质因数什么的
  1. #include <iostream>
  2. using namespace std;

  3. int main()
  4. {
  5.         int number;

  6.         while(cin >> number)
  7.         {
  8.                 bool isFound = false;
  9.                 for(int sum=0, left=1, right=1; left < ((number+1) >> 1); right++)
  10.                 {
  11.                         sum += right;
  12.                         while(sum > number)
  13.                         {
  14.                                 sum -= left;
  15.                                 left++;
  16.                         }
  17.                         if(sum == number)
  18.                         {
  19.                                 //找到,输出
  20.                                 cout << left << '~' << right << endl;
  21.                                 isFound = true;
  22.                         }
  23.                 }

  24.                 if(!isFound)
  25.                 {
  26.                         cout << "无解!\n";
  27.                 }
  28.         }

  29.         return 0;
  30. }
复制代码
25_avatar_middle
ico_lz  楼主| 发表于 2009-11-16 21:53:06 | 显示全部楼层
回复 13# yaojiank
   这算法很不错啊!
52_avatar_middle
在线会员 发表于 2009-11-18 15:36:29 | 显示全部楼层
今天忙哈,没时间写代码了,但是可以给大家一个思路,我认为是效率上应该可以的:
比如:27 可以分为:
        27                                                          ------1 层 一个数当然连续
     13      14                                                   -------2层 27 /  2 = 13(INT) ,
   8      9     10                                                  ------3层 27 /  3 = 9   
    5   6   7     8                                                 -------4 层 27 / 4  = 6   这一层不满足
  3  4   5     6     7                                            -----5 层 27 / 5  = 5 这一层也不满足
2   3  4    5     6    7                                      -------6 层 27 / 6 = 4  这一层满足
.
.
.                                                                 -------------n 层 27 / n

我想了下,一个数m,分解的 层数 n <= (int)sqrt(m)  +  1 ;   并且 第n 层有 n 个数。
若 n 为偶数,  则 n 层数列为:
{ i - k, . . . . ,i - 2, i -1,    i,    i + 1,  i + 2, ......, i + k |  i =  m / n, k 是正整数 且  2k + 2  = n}
若 n 为奇数,则 n 层数列为:
{i - k, ......., i - 2, i -1 ,    i ,   i + 1, i + 2 ,......, i + k | i = m / n, k 是正整数 且 2k + 1 = n}

就这样,这算法很简单。(突然发现数学真的很有用!!)
52_avatar_middle
在线会员 发表于 2009-11-18 17:30:18 | 显示全部楼层
忘说了:然后验证 每行数列相加是否等于 m
35_avatar_middle
在线会员 发表于 2010-1-19 10:27:34 | 显示全部楼层
今天忙哈,没时间写代码了,但是可以给大家一个思路,我认为是效率上应该可以的:
比如:27 可以分为:
   ...
viking 发表于 2009-11-18 15:36 无奖竞猜 因为咱也囊中羞涩



    昨天刚刚发现这个论坛的,突然发现,这里的人,真的,很牛叉。
小蚂蚁向大家学习无奖竞猜 因为咱也囊中羞涩
34_avatar_middle
在线会员 发表于 2010-6-6 20:33:48 | 显示全部楼层
#include <stdio.h>
int main()
        {
                int i;
                printf("please input a number::");
                scanf("%d",&i);
                for(int j=1;j<=i/2;j++)
                {
                        int k=j,m=j,l=j;
                        while(l<=i)
                                {
                                if(l==i)
                                        {
                                                for(int s=k;s<=m;s++)
                                                printf("%d ",s);
                                                printf("\n");
                                                break;
                                        }
                                else
                                        {
                                                m++;
                                                l+=m;               
                         
                                        }
                                }
                }
        }
我刚看到你的帖子,写了上面这个程序,我测试过了没有问题,你看看是够满足要求
00_avatar_middle
在线会员 发表于 2010-6-20 12:41:24 | 显示全部楼层
回复 1# HeyJude


    RE: 无奖竞猜 因为咱也囊中羞涩
52_avatar_middle
在线会员 发表于 2010-6-21 23:30:14 | 显示全部楼层
这边的人的确很牛X,以后要经常来学习了!!
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-3-25 23:23

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表