題目:輸入一個遞增排序的數組和一個數字s,在數組中查找兩個數,使得它們的和正好是s。如果有多對數字的和等於s,輸出任意一對即可。
思路:最初我們找到數組的第一個數字和最後一個數字。首先定義兩個指針,第一個指針指向數組的第一個(也就是最小的)數字,第二個指針指向數組的最後一個(也就是最大的)數字。當兩個數字的和大於輸入的數字時,把較大的數字往前移動;當兩個數字的和小於數字時,把較小的數字往後移動;當相等時,打完收工。這樣掃描的順序是從數組的兩端向數組的中間掃描。
#include "stdafx.h" #include<iostream> bool FindNumbersWithSum(int data[], int length, int sum, int* num1, int* num2) { bool found = false; if(length < 1 || num1 == NULL || num2 == NULL) return found; int ahead = length -1; int behind = 0; while(ahead > behind) { long long curSum = data[ahead] + data[behind]; if(curSum == sum) { *num1 = data[behind]; *num2 = data[ahead]; found = true; break; } else if(curSum > sum) ahead --; else behind ++; } return found; } int main() { int data[] = {1,2,4,7,11,15}; int length = sizeof(data)/sizeof(int); int sum = 15; int num1, num2; int result = FindNumbersWithSum(data, length, sum, &num1, &num2); if(result) { if(num1 + num2 == sum) printf("%d %d\n", num1, num2); else printf("Failed.\n"); } else printf("Failed.\n"); return 0; }
題目:輸入一個正數S,打印出所有和為S的連續正數序列(至少有兩個數)。例如輸入15,由於1+2+3+4+5=4+5+6=7+8=15,所以結果打印出3個連續序列1~5,4~6和7~8.
思路:
兩個數small和big分別表示序列的最小值和最大值。首先把small初始化為1,big初始化為2.如果從small到big的序列的和大於S,可以從序列中去掉較小的值,也就是增大small的值。如果從small到big的序列的和小於S,可以增大big,讓這個序列包含更多的數字。因為這個序列至少要有兩個數字,我們一直增加small到(1+S)/2為止。
1 #include "stdafx.h" 2 3 void PrintContinuousSequence(int small, int big); 4 5 void FindContinuousSequence(int sum) 6 { 7 if(sum < 3) 8 return; 9 10 int small = 1; 11 int big = 2; 12 int middle = (1 + sum) / 2; 13 int curSum = small + big; 14 15 while(small < middle) 16 { 17 if(curSum == sum) 18 PrintContinuousSequence(small, big); 19 20 while(curSum > sum && small < middle) 21 { 22 curSum -= small; 23 small ++; 24 25 if(curSum == sum) 26 PrintContinuousSequence(small, big); 27 } 28 29 big ++; 30 curSum += big; 31 } 32 } 33 34 void PrintContinuousSequence(int small, int big) 35 { 36 for(int i = small; i <= big ; i ++) 37 printf("%d ", i); 38 39 printf("\n"); 40 } 41 42 int main(int argc, char const *argv[]) 43 { 44 int sum = 9; 45 printf("test for %d:\n", sum); 46 FindContinuousSequence(sum); 47 48 sum = 15; 49 printf("test for %d:\n", sum); 50 FindContinuousSequence(sum); 51 52 sum = 100; 53 printf("test for %d:\n", sum); 54 FindContinuousSequence(sum); 55 56 return 0; 57 }