【剑指offer】和为定值的连续正数序列
转载请注明出处:http://blog.csdn.net/ns_code/article/details/27823291
- 题目描写叙述:
-
小明非常喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他立即就写出了正确答案是100。可是他并不满足于此,他在想到底有多少种连续的正数序列的和为100(至少包含两个数)。没多久,他就得到还有一组连续正数和为100的序列:18,19,20,21,22。如今把问题交给你,你能不能也非常快的找出全部和为S的连续正数序列? Good Luck!
- 输入:
-
输入有多组数据。
每组数据仅包含1个整数S(S<=1,000,000)。假设S为负数时,则结束输入。
- 输出:
-
相应每组数据,若不存在和为S的连续正数序列,则输出“Pity!”;否则,依照開始数字从小到大的顺序,输出全部和为S的连续正数序列。每组数据末尾以“#”号结束。
- 例子输入:
-
4
5
100
-1
- 例子输出:
-
Pity!
#
2 3
#
9 10 11 12 13 14 15 16
18 19 20 21 22
#
这道题刚開始用的剑指offer上的思路写的代码,我也是相同将打印正数序列部分的代码独立开来写成了一个函数,可是在九度OJ上測试,最后一个測试用例超时了,看论坛非常多人採取此策略也都AC了,知识最后一个測试用例的时间可能要400ms左右,我就认为应该是调用打印函数耗费了太多时间,尤其连续序列有非常多的时候,要非常多次地调用,开销还是蛮大的。就把打印部分的代码和寻找连续序列的代码写在了一起,这次AC了,最后一个測试用例的时间是340ms。
AC代码例如以下:
#include<stdio.h>
#include<stdbool.h>
bool can; /*
void PrintSequence(int start ,int end)
{
int i;
for(i=start;i<=end;i++)
{
printf("%d",i);
if(i == end)
printf("\n");
else
printf(" ");
}
}
*/ /*
找到和为s的连续正数序列
*/
void FindSumSequence(int s)
{
int start = 1;
int end = 2;
int mid = (1+s)>>1;
int cursum = start + end; while(start < mid)
{
if(cursum == s)
{ can = true;
// PrintSequence(start,end);
int i;
for(i=start;i<=end;i++)
{
printf("%d",i);
if(i == end)
printf("\n");
else
printf(" ");
}
end++;
cursum += end;
}
else if(cursum < s)
{
end++;
cursum += end;
}
else
{
cursum -= start;
start++;
}
}
} int main()
{
int s;
while(scanf("%d",&s) != EOF && s>=0)
{
can = false;
FindSumSequence(s);
if(!can)
printf("Pity!\n");
printf("#\n");
}
return 0;
}
/**************************************************************
Problem: 1354
User: mmc_maodun
Language: C
Result: Accepted
Time:380 ms
Memory:912 kb
****************************************************************/
另外,九度在这个问题的讨论里面,有个内科大的哥们给了个不错的解法(我咋就想不出尼,哎!差距啊!!),大致思路例如以下(慢慢琢磨吧,不难理解,直接从论坛Copy过来的):
S = ( a0 + aN)N/2 ---- 等差数列求和公式
= ( 2a0-1 + N )N /2
==> 2a0 = 2S/N - N + 1
==> 2S % N == 0 && N < sqrt(2S)
for N = [ 2 , sqrt(2S) )
if 2S % N == 0 && 2a0 % 2 == 0
show( a0 , N )
我也用这样的思路写了代码,相同AC了,只是比剑指offer上的思路写的代码要快非常多,最后一个測试用例仅仅用了80ms。
AC代码例如以下;
#include<stdio.h>
#include<math.h>
#include<stdbool.h>
bool can; /*
打印从Start開始的连续n个正数序列
*/
void PrintSequence(int start ,int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d",start+i);
if(i == n-1)
printf("\n");
else
printf(" ");
}
} /*
找到和为s的连续正数序列
*/
void FindSumSequence(int s)
{
int i;
//这里的i为要求的连续正数的个数,至少为2
for(i=(int)sqrt(2*s);i>=2;i--)
{
if((2*s)%i == 0)
{
int DoubleStart = 2*s/i-i+1;
if((DoubleStart&1) == 0) //假设为偶数
{
can = true;
PrintSequence(DoubleStart/2,i);
}
}
}
} int main()
{
int s;
while(scanf("%d",&s) != EOF && s>=0)
{
can = false;
FindSumSequence(s);
if(!can)
printf("Pity!\n");
printf("#\n");
}
return 0;
}
/**************************************************************
Problem: 1354
User: mmc_maodun
Language: C
Result: Accepted
Time:110 ms
Memory:928 kb
****************************************************************/
最新文章
- Reverse Core 第二部分 - 16&;17章 - 基址重定位表&;.reloc节区
- Base64正反编码
- 为什么是梯度下降?SGD
- 让python整型计算结果为浮点型
- <;九>;面向对象分析之UML核心元素之设计类,类,属性,方法,可见性
- 常用sql命令
- php smarty foreach循环注意
- Warning: Function created with compilation errors!
- 配置Linux Kernel时make menuconfig执行流程分析
- Unity文档总结(2)-Understanding Automatic Memory Management
- Jetson TX1使用usb camera采集图像 (2)
- 虚拟机安装macos 分辨率不正常修改不了,不能全屏如何解决
- 批量删除MSSQL 中主外键约束
- JAVA字符串
- git push origin master 上传失败
- 【Java基础】char
- Redis入门指南之三(入门)
- JS基础-数组的常用方法-冒泡排序
- vue单页应用中 返回列表记住上次滚动位置、keep-alive缓存之后更新列表数据 那点事
- 使用explain来分析SQL语句实现优化SQL语句
热门文章
- Delphi 用ToolButton和MonthCalendar实现DateTimePicker的功能
- 对C#泛型实例化对像--转
- codevs 1139 观光公交
- 用批处理来重启IIS的应用程序池
- C#制作ActiveX控件及部署升级(摘自网络)
- grails框架中读取txt文件内容将内容转换为json格式,出现异常Exception in thread ";main"; org.json.JSONException: A JSONObject text must begin with &#39;{&#39; at character 1 of [...]
- jQuery中$.get()、$.post()和$.ajax()
- Js屏蔽键盘事件
- C语言笔记(数组地址一些细节)
- UVA - 1614 Hell on the Market(贪心)