序列算法题，包括和序列求解等
首先，说明一下，很长时间没来写博客了，是的，前段时间忙考研，耽误了半年多，现在，考研初试成绩出来了，现在正准备复试，由于不冲突，我就在准备c/c++的复试，顺便写写自己的技术blog。我一直这样认为，写blog可以加深自己对知识的理解。言罢，今天写了来两个小算法，算是熟悉一下语言的应用。
?
?
关于和序列问题，即形如（数据不重复）
10=1+2+3+4
10=1+2+7
10=1+3+6
10=1+4+5
10=1+9
10=2+3+5
10=2+8
10=3+7
10=4+6
?
const int N = 10;/* test number *//* print the numbers */void print(int *list, int num){int i;cout<<N<<"="<<list[0];for(i = 1; i < num; i ++)cout<<"+"<<list[i];cout<<endl;}/* key function here */void getNumList(int sum, int begin,int *list ,int i){int next;list[i] = begin;i++;sum -= begin;if(sum == 0) print(list,i);// be foundelse{//continue searching the next numberfor(next = begin+1; next <= sum; next++)getNumList(sum,next,list,i);}}int main(void){int sum = N, begin;int list[N/2];/* test all beginings */for(begin = 1; begin <= sum/2; begin ++)getNumList(sum,begin,list,0);return 0;}?
?很容易理解，不错解释。
?
还有一道很老的腾讯面试题，类似题型：
?
const int N = 10;const int s[N] = {0,1,2,3,4,5,6,7,8,9};/* repair the result list */void repair(int *array){int sum = 0;for(int i = 1; i < N; i++)sum += array[i];array[0] = N - sum;}/* test the result list */int isRight(int *r){int i,j,sum; for(i = 0; i < N; i++){sum = 0;//test the i numberfor(j = 0; j < N; j++)if(r[j] == s[i]) sum ++;if(sum != r[i])//not matchreturn 0;}return 1;}/* print the right result list */void print(int *array){int i = 0;for(; i < N; i++) cout<<array[i]<<" ";cout<<endl;}/* * key function * serach from N to 0 * constrict 1 */void getSerial(int sum, int *result, int num){int i;/* case 1*/if(num == 0 && sum != 0) return;// not match here/* case 2*/if(sum == 0)// out of use{for(i = num; i > 0; i--) result[i] = 0;// important point for result[0]:constrict 2repair(result);if(isRight(result)) //constrict 3{print(result);return;}else return;}/* case 3*/for(i = 0;i*s[num] <= sum; i++){result[num] = i;getSerial(sum-i*s[num],result,num-1);}}?
?可以注意到 该序列有三个限制条件（程序中也用constrict表示出来）
constrict 1： 就是两数组对乘的结果是N
? ??由于该条件限制较强，好理解，所以用作循环条件，以便减少遍历次数
constrict 2：repair（）修正0的个数（比较特殊）待改善
constrict 3：就是检验是s【】中个数是否和人r【】中的对应（最强限制，但最难利用理解）