750
京東網上商城
劍指Offer之和為S的連續正數序列
- 題目描述：
-
小明很喜歡數學,有一天他在做數學作業時,要求計算出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 #
【解析】
/*********************************
* 日期：2013-11-29
* 作者：SJF0115
* 題號: 題目1354：和為S的連續正數序列
* 來源：https://ac.jobdu.com/problem.php?pid=1354
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
int FindSequence(int n){
//初始化
int end = (n + 1) / 2;
int small = 1;
int big = 2;
int isFound = 0;
int curSum = small + big;
while(small < big && big <= end){
//當前值等於給定值，打印序列
if(curSum == n){
isFound = 1;
//打印
for(int i = small;i <= big;i++){
if(i == big){
printf("%d\n",i);
}
else{
printf("%d ",i);
}
}
curSum -= small;
small++;
}
//當前值大於給定值，需要棄掉一個小值
else if(curSum > n){
curSum -= small;
small ++;
}
//當前值小於給定值，需要加上一個大值
else{
big ++;
curSum += big;
}
}//while
return isFound;
}
int main() {
int i,n,m,num1,num2;
while(scanf("%d",&n) != EOF && n >= 0){
int result = FindSequence(n);
//輸出
if(result == 0){
printf("Pity!\n");
}
printf("#\n");
}//while
return 0;
}
最後更新：2017-04-03 14:54:36