算法题:求四个数的和为定值的组合

shizheng0124

算法题：有数组【1,2,3，...10】,请找出四个数的和为16的这四个数。请给出算法。

/****a.cpp  - In order to solve the specified sum of several numbers in a array**       Copyright (c) 2012. All rights reserved.**Purpose:*****/#include <iostream>#include <stdarg.h>#define LEN 10#define N 4#define LEN1 20using namespace std;struct elem{int start;int tail;int num;int value;int str[LEN1];};typedef struct elem ELEM;enum err{debug,run};typedef enum err ERR;void sort(int * p);void find(const int * p, ELEM e);void printArray(int *p,...);void scanfArray(int *p);void printErr(ERR level);void copyArray(int in[],int *p);/************************************************************************//* 假设输入到数组中的值都是大于零的数                                   *//************************************************************************/void main(){int arr[LEN];int sum = 16;scanfArray(arr); // input arrayprintf("Please Enter a number:\n");scanf("%d",&sum);sort(arr); // sort arrprintArray(arr,0);printf("输出的组合：\n");int start = 0, tail = LEN, num = N;ELEM e = {start,tail,N,sum,{0}};find(arr,e);}void scanfArray(int *p){printf("Please Enter %d Numbers:\n",LEN);for (int i = 0; i < LEN; i++){scanf("%d",&p[i]);}}void sort(int * p){int tmp;for (int i = 0; i < LEN-1; i++){for (int j = 1; j < LEN-i; j++){if (p[j-1]>p[j]){tmp = p[j];p[j] = p[j-1];p[j-1] = tmp;}}}}void printArray(int *p,...){    va_list arg_ptr;    va_start(arg_ptr,p);int num = va_arg(arg_ptr,int);if (num == 0){num = LEN;} printf("[");for (int i = 0; i < num; i++){printf(" %d ,",p[i]);}printf("\b]\n");}void find(const int * p, ELEM e){int start = e.start;int tail = e.tail;int num = e.num;int value = e.value;// adjust the value of start and tailif(start+num<=tail){if (value<p[start]){printErr(debug);return;}else{for (int j = tail; j >start; j--){if(p[j]<=value){tail = j;break;}}}}else{printErr(debug);return;}if (num<2){printErr(debug);return;}else if(num==2){int i = start;int j = tail;while (i<j){if (p[i]+p[j]==value){e.str[N-num] = p[i];e.str[N-num+1] = p[j];printArray(e.str,N);i++;j--;}else if(p[i]+p[j]<value){i++;}else{j--;}}}else{for (int i = start; i < tail; i++){e.str[N-num] = p[i];ELEM tmp = {i+1,tail,num-1,value-p[i]};copyArray(e.str,tmp.str);find(p,tmp);}}}void copyArray(int in[],int *p){for (int i = 0; i<LEN1; i++){p[i] = in[i];}}void printErr(ERR level){switch (level){case debug://fprintf(stderr,"ERROR type 1");break;case run:fprintf(stderr,"ERROR type 2");break;default:break;}}