面試100 26求和為給定值的連續序列

    26 和為給定值的連續序列

 一 問題描述
      和為n的正數序列，比如求合為15的正數連續序列，則有以下序列滿足
    12345 == 456 == 78
    解題思路：
     設置一個small =1 ,big=2
     求 sum = [small , big]
   
    若sum 大于15 ，則small左移，相當于去掉最小值。
    若sum 小于15 ，則big  右移， 相當于增加最大值。  

   擴展如下：
     若在一個已經排序的序列中，求兩個元素之和為定值的元素。
    可以使用left ,right分別表示，序列中的首尾元素，若left+right 大于給定和，則right--，若小于則left++。 與此題的思路相似。

#include <iostream>
  using namespace std ;
  int H = 15 ;
  
  int sum(int l , int h)
  {
     int i , sum = 0;
     for(i = l ; i <= h ;i++) 
       sum += i ;
       
       return sum ;
  }
  
  void findsequence(int n)
  {
       int small = 1 ;
       int big = 2 ;
       
       while(small < (n + 1) / 2)
       {
          int sums = sum(small , big);          
         if( sums < H)
           big++ ;
         else
         if(sums == H)         
         {
           cout<<small<<"--->"<<big<<endl ;                             
           small++ ;
         }
        else
          small++ ;  
                     
       }
       
  }
  
  int main()
  {
   findsequence(H) ;
   system("pause") ;
   return 0 ;    
  }

posted on 2011-05-19 13:46 kahn 閱讀(246) 評論(0)  編輯 收藏 引用