/*任给 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+3 5  = 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种可能。 程序可这样安排 //给出程序的大体结构。如何写就随便了。。。。/////////////////////////////////////////////// 辅助函数或结构定义。。。可有可无。..................///实现long getsumcount(long data[], long count){}///主函数。void main(){  // 输入数据。  .........  .........  xx = getsumcount(data, count);  // 输出有多少种  .........}////////////////////////////////////////////// */ #include <iostream>#include <time.h>#define libsize (1<<16)#define hashsize (1<<16)#define hashmask (0xffff)using namespace std; const long MAX = 20; typedef struct node1{    long key;    int si;}NODE1;NODE1 *hashtab1; typedef struct node2{    long data;    struct node2 *next;}NODE2;NODE2 hashtab2[hashsize]; void Swap(int & a, int & b);void Solve1(const int data[], bool lib[], int a[], long len, int pos, int max, int num);long Sum(const int a[], int len);long getsumcount1(const int data[], int count);long getsumcount2(const int data[], int count);long getsumcount3(const int data[], int count); int main(void){      time_t startTime; time_t endTime; time(&startTime);      int data[MAX]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};       //产生100个100以内不重复随机数的代码      int a[100];      for(int i=0; i<=99; ++i)            a[i] = i+1;      for(int i=99; i>=1; --i)            Swap(a[i], a[rand()%i]);       //for (int i=0; i<MAX; i++) //给数组赋值为1-100的随机数//            data[i] = a[i];       for (int i=0; i<MAX; i++)            cout << data[i] << ' ';      cout << endl;       long sum = 0;      for (int i=1; i<=MAX; i++)      {            long s1 = getsumcount1(data, i);            long s2 = getsumcount2(data, i);            long s3 = getsumcount3(data, i);             cout << i << ": s1=" << s1 << "  s2=" << s2 << "  s3=" << s3 << endl;            if (s1 == s2 && s1 == s3)                  sum++;      }      cout << sum << endl;       time(&endTime); cout << "time:" << difftime(endTime, startTime) << endl;  getchar(); return 0;}///////////////////////////////////////////////////////////////////////////*  Author: goal00001111*/void Swap(int & a, int & b){      int temp = a;      a = b;      b = temp;} long getsumcount1(const int data[], int count){      bool lib[libsize];      for (long i=0; i<libsize; i++)            lib[i] = false;      int *a = new int[count];       for (int k=0; k<count; k++)            Solve1(data, lib, a, count, 0, k, 0);       delete []a;      long sum = 0;      for (long i=0; i<libsize; i++)      {            if (lib[i])            {                  sum++;                // cout << i << ' ';            }      }      return sum;} void Solve1(const int data[], bool lib[], int a[], long len, int pos, int max, int 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];   Solve1(data, lib, a, len, i+1, max, num+1); //分析下一个数            }      }} long Sum(const int a[], int len){      long sum = 0;      for (int i=0; i<=len; i++)            sum += a[i];      return sum;}////////////////////////////////////////////////////////////////////////*  Author: goal00001111*/ int HashInsert2(NODE1 hashtab[], long max, long data){      long d = data % max;      if (hashtab[d].key == 0)      {            hashtab[d].key = data;            hashtab[d].si = 1;      }      else      {            int sum = 1;            while (hashtab[d].key != data && hashtab[d].key != 0)            {                  d = (d + 1) % max;                  sum++;            }             if (hashtab[d].key == data)                  return 0;             hashtab[d].key = data;            hashtab[d].si = sum;      }      return 1;} void Solve2(const int data[], NODE1 hashtab[], int a[], long len, int pos, int max, int num, long sumAll, long & sum){      if (num == max)      {            for (int i=pos; i<len; i++)            {                  a[num] = data[i];                  sum += HashInsert2(hashtab, sumAll, Sum(a, num));            }      }      else  //如果不是最后一个数字      {            for (int i=pos; i<len; i++)            {                  a[num] = data[i];   Solve2(data, hashtab, a, len, i+1, max, num+1, sumAll, sum); //分析下一个数            }      }} long getsumcount2(const int data[], int count){      long sumAll = (1<<count)%10000;    cout << "toatl: " << sumAll << endl;       hashtab1 = new NODE1[sumAll];      for (long i=0; i<sumAll; i++)      {            hashtab1[i].key = 0;            hashtab1[i].si = 0;      }       int *a = new int[count];      long sum = 0;      for (int k=0; k<count; k++)            Solve2(data, hashtab1, a, count, 0, k, 0, sumAll, sum);       double ave = 0;      for (long i=0; i<sumAll; i++)            ave += hashtab1[i].si;      cout << "ave= " << ave/sum << endl;       delete []a;      delete []hashtab1;       return sum;}/////////////////////////////////////////////////////////////////////////////////*  Author: eastcowboy*/ /*寻找并插入，找到而未插入返回0，未找到而插入返回1*/static int hashinsert(long sum){    NODE2 *p,*q;    p = hashtab2+ (sum & hashmask);    while( p && (p->data!=sum) )    {   q = p;        p = p->next;    }    if( p )        return 0;    q->next = p = (NODE2*)malloc(sizeof(NODE2));    p ->next = NULL;    p ->data = sum;    return 1;}/*删除hash表的第index条目*/static void hashdelete(long index){      NODE2 *p,*q;      p = hashtab2[index].next;      while(p)      {            q = p;            p = p->next;            free(q);      }}/*这才是正主^^*/long getsumcount3(const int data[], int count){    long i;    int state[MAX] = {0};    long sum = 0,sp = 0;    long ret = 0; /*由于0已经先放入表中，所以首先就有一个*/     /*hash表初始化*/    for(i=0;i<hashsize;++i)    {   hashtab2[i].data = 0;        hashtab2[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;}

评论