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

算法题：有数组【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 20
using 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 array
	printf("Please Enter a number:\n");
	scanf("%d",&sum);

	sort(arr); // sort arr
	printArray(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 tail
	if(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;
	}
}

评论

2 楼 shizheng0124 2012-11-22  

不错吧

1 楼 shizheng0124 2012-10-04  

hahhaahaha