二、任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。
例如，
data[] = {1,2,3,4};
ncount = 4;
函数返回 10
分解如下。（0不算）
1 = 1
2 = 2
3 = 3 = 1+2
4 = 4 = 1+3
5 = 2+3 = 1+4
6 = 2+4 = 1+2+3
7 = 3+4 = 1+2+4
8 = 1+3+4
9 = 2+3+4
10 = 1+2+3+4
如上。所以结果是10种可能。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#define hashsize (1<<16)
#define hashmask (0xffff)
using namespace std;
typedef struct node{
long data;
struct node *next;
}NODE;
NODE hashtab[hashsize];
const long MAX = 20;
bool IsNew(long array[], long len, long data);
void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num);
long _getsumcount(const long data[], long count);
long Sum(const long a[], int len);
long getsumcount(const long data[], long count);
int main(void)
{
time_t startTime;
time_t endTime;
time(&startTime);
long data[MAX]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
for (long i=0; i<MAX; i++) //给数组赋值为1-100的随机数
{
long temp = rand()%100 + 1;
if (IsNew(data, i, temp))
data[i] = temp;
}
for (long i=0; i<MAX; i++)
cout << data[i] << ' ';
cout << endl;
int sum = 0;
for (long i=1; i<=MAX; i++)
{
long s1 = getsumcount(data, i);
long s2 = _getsumcount(data, i);
cout << i << ": s1=" << s1 <<" s2=" << s2 << endl;
if (s1 == s2)
sum++;
}
cout << sum << endl;
time(&endTime);
cout << "time:" << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
//////////////////////////////////////////////////////////////////////////
/*
Author: goal00001111
*/
bool IsNew(long array[], long len, long data)
{
for(int i=0; i<=len; i++)
if (array[i] == data)
return false;
return true;
}
long _getsumcount(const long data[], long count)
{
bool lib[libsize];
for (long i=0; i<libsize; i++)
lib[i] = false;
long *a = new long[count];
for (int k=0; k<count; k++)
solve(data, lib, a, count, 0, k, 0);
delete []a;
long sum = 1;
for (long i=0; i<libsize; i++)
{
if (lib[i])
{
sum++;
// cout << i << ' ';
}
}
return sum;
}
void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num)
{
if (num == max)
{
for (int i=pos; i<len; i++)
{
a[num] = data[i];
lib[Sum(a, num)] = true;
}
}
else //如果不是最后一个数字
{
for (int i=pos; i<len; i++)
{
a[num] = data[i];
solve(data, lib, a, len, i+1, max, num+1); //分析下一个数
}
}
}
long Sum(const long a[], int len)
{
long sum = 0;
for (int i=0; i<=len; i++)
sum += a[i];
return sum;
}
///////////////////////////////////////////////////////////////////////
/*
Author: eastcowboy
*/
/*寻找并插入，找到而未插入返回0，未找到而插入返回1*/
static int hashinsert(long sum)
{
NODE *p,*q;
p = hashtab+ (sum & hashmask);
while( p && (p->data!=sum) )
{ q = p;
p = p->next;
}
if( p )
return 0;
q->next = p = (NODE*)malloc(sizeof(NODE));
p ->next = NULL;
p ->data = sum;
return 1;
}
/*删除hash表的第index条目*/
static void hashdelete(long index)
{ NODE *p,*q;
p = hashtab[index].next;
while(p)
{ q = p;
p = p->next;
free(q);
}
}
/*这才是正主^^*/
long getsumcount(const long data[],long count)
{
long i;
int state[MAX] = {0};
long sum = 0,sp = 0;
int ret = 1; /*由于0已经先放入表中，所以首先就有一个*/
/*hash表初始化*/
for(i=0;i<hashsize;++i)
{ hashtab[i].data = 0;
hashtab[i].next = NULL;
}
/*回溯求解*/
while(sp>=0)
{ if(sp==count)
{ ret += hashinsert(sum);
--sp;
}
switch( state[sp] )
{ case 0:
state[sp] = 1;
sum += data[sp];
++sp;
break;
case 1:
state[sp] = 2;
sum -= data[sp];
++sp;
break;
case 2:
state[sp] = 0;
--sp;
break;
}
}
/*hash表销毁*/
for(i=0;i<hashsize;++i)
{ hashdelete(i);
}
return ret;
}