算法题:求四个数的和为定值的组合
算法题：有数组【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;};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;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);}}void sort(int * p){int tmp;for (int i = 0; i < LEN-1; i++){for (int j = 1; j < LEN-i; j++){if (p>p){tmp = p;p = p;p = 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);}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){printErr(debug);return;}else{for (int j = tail; j >start; j--){if(p<=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+p==value){e.str = p;e.str = p;printArray(e.str,N);i++;j--;}else if(p+p<value){i++;}else{j--;}}}else{for (int i = start; i < tail; i++){e.str = p;ELEM tmp = {i+1,tail,num-1,value-p};copyArray(e.str,tmp.str);find(p,tmp);}}}void copyArray(int in[],int *p){for (int i = 0; i<LEN1; i++){p = in;}}void printErr(ERR level){switch (level){case debug://fprintf(stderr,"ERROR type 1");break;case run:fprintf(stderr,"ERROR type 2");break;default:break;}}
页:
[1]