/*任给 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种可能。
程序可这样安排
//给出程序的大体结构。如何写就随便了。。。。
/////////////////////////////////////////////
// 辅助函数或结构定义。。。可有可无。
......
......
......
///实现
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;
}
评论