二、任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。long getsumcount(long data[], long count); 程序中可以出现别的辅助函数。或辅助结构等。例如，data[] = {1,2,3,4};ncount = 4;函数返回 10分解如下。（0不算）1 = 12 = 23 = 3 = 1+24 = 4 = 1+35 = 2+3 = 1+46 = 2+4 = 1+2+37 = 3+4 = 1+2+48 = 1+3+49 = 2+3+410 = 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;}
评论