二、任給 1<=n<=20 個(gè)不同的非零正整數(shù)，每個(gè)正整數(shù)最多使用1次，請(qǐng)問(wèn)這n個(gè)正整數(shù)能夠加和的結(jié)果共有多少種(不考慮和超出long的最大值的可以),
程序中請(qǐng)實(shí)現(xiàn)如下函數(shù)。用于計(jì)算數(shù)組data,中ncount的加和的數(shù)量。
long getsumcount(long data[], long count);
程序中可以出現(xiàn)別的輔助函數(shù)。或輔助結(jié)構(gòu)等。
例如，
data[] = {1,2,3,4};
ncount = 4;
函數(shù)返回 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
如上。所以結(jié)果是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++) //給數(shù)組賦值為1-100的隨機(jī)數(shù)
????? {
??????????? 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? //如果不是最后一個(gè)數(shù)字
????? {
??????????? for (int i=pos; i<len; i++)
??????????? {
????????????????? a[num] = data[i];
???solve(data, lib, a, len, i+1, max, num+1);?//分析下一個(gè)數(shù)
??????????? }
????? }
}
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已經(jīng)先放入表中，所以首先就有一個(gè)*/
??? /*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表銷(xiāo)毀*/
??? for(i=0;i<hashsize;++i)
??? {?? hashdelete(i);
??? }
??? return ret;
}