| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3838 人关注过本帖
标题:石头归并问题
只看楼主 加入收藏
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
至于sum的计算,观察以下等式:
sum0=a0+a1+...+a(n-1)
******
sum1=-a0+a1+a2+...+a(n-1)=sum0-2*a0
******
sum2=a0-a1+a2+...+a(n-1)=sum0-2*a1
sum3=-a0-a1+a2+...+a(n-1)=sum1-2*a1
******
sum4=a0+a1-a2+...+a(n-1)=sum0-2*a2
sum5=-a0+a1-a2+...+a(n-1)=sum1-2*a2
sum6=a0-a1-a2+...+a(n-1)=sum2-2*a2
sum7=-a0-a1-a2+...+a(n-1)=sum3-2*a2
******
........

Finding!!!
2006-05-14 12:47
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 

总共有2^n个sum,n是石头的堆数,所以这个n小于16才好!
另外可以具体输出分组的方法!


Finding!!!
2006-05-14 12:52
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
大家试一下以下程序:
power(int n)
{int i,p=2;
for(i=1;i<n;i++)
p=2*p;
return(p);
}
void count(int n,int *sum,int *a)
{int i,j,k,l,m=1;
l=power(n);
for(i=1,*(sum+0)=*(a+0);i<n;i++) /*计算各分组方法的差*/
*(sum+0)=*(sum+0)+(*(a+i));
for(i=1,j=0,k=0;i<l&&j<m;i++,j++)
{*(sum+i)=*(sum+j)-(*(a+k))*2;
if(j==m-1)
{j=-1;k++;m=power(k);}
}
for(i=1;i<l;i++)
if(*(sum+i)<0) *(sum+i)=-(*(sum+i));
}
void output(int n,int *sum)
{int i,k,l,m,temp,j=0,num=1,flag[100];
temp=*(sum+1);l=power(n);
for(i=2;i<l;i++) /*记录最小的差*/
{if(temp>(*(sum+i)))
{temp=(*(sum+i));num=1;j=0;flag[j]=i;}
else if(temp==*(sum+i))
{num++;j++;flag[j]=i;}
}
printf("\nThe least value is:%d",temp);
printf("\nThe method are:"); /*输出差的最小值*/
for(i=1,j=0;j<num;i++,j++)
{printf("\nmethod %d :",i); /*用二进制的方法输出分组方法*/
k=flag[j];
for(m=0;m<n;m++)
if(k>=1){printf(" %d ",k%2);k=k/2;}
else printf(" 0 ");
}
}
#include <malloc.h>
main()
{int i,n,a[16],*sum;
sum=(int *)malloc(power(n)*sizeof(int));
printf("Input the number of array n(1<n<16):");
scanf("%d",&n);
printf("\nInput the array:\n");
for(i=0;i<n;i++)
scanf("%d",(a+i));
printf("\n");
count(n,sum,a);
output(n,sum);
getch();printf("\n");
}
方法的表示:用n个数(0或1)表示石头堆,凡是标号为1的为一组,为0的又是另一组.
当然,你会看到在输出里有方法重复的情况.按道理应该可以解决的,留给大家想想吧!

Finding!!!
2006-05-14 13:04
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
程序是搞出来了,只是没怎样测试,不知道有没有问题,尤其是当n比较大的时候!!

Finding!!!
2006-05-14 13:07
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
经测试,发现了很多问题无法解决.
比如输入 8;12 25 13 45 1 5 6 8

Finding!!!
2006-05-14 13:28
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 

感觉所有的方法都是在穷举,就是说把所有的可能性都试一下,所有的可能性是多少呢?
任一块石头都可能在左边一组,也可能在右,也就是说N块石头就用2的N次方种可能。对于100000块石头,就是2的100000次方,这个复杂度是不能接受的。暂时还没有想出什么好方法,不过一定不能穷举,需要找到一个算法来减小复杂度,如果存在的话。


http://myajax95./
2006-05-14 13:48
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
对sum=(int *)malloc(power(n)*sizeof(int));做了点修改后(该为int s[1000];sum=s;),又可以得到答案了,不过方法实在太陋,只能用于检测.
也许是因为自己对malloc(size)这个函数不大理解所至!

Finding!!!
2006-05-14 13:50
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
以下是引用everajax在2006-5-14 13:48:00的发言:

感觉所有的方法都是在穷举,就是说把所有的可能性都试一下,所有的可能性是多少呢?
任一块石头都可能在左边一组,也可能在右,也就是说N块石头就用2的N次方种可能。对于100000块石头,就是2的100000次方,这个复杂度是不能接受的。暂时还没有想出什么好方法,不过一定不能穷举,需要找到一个算法来减小复杂度,如果存在的话。

对,所有都是穷举!
"该程序有多组测试数据,每组测试数据第一行为整数N(1<=N<=20)"这是问题里的话,石头堆数至多是20.不用想10000堆那么多!当然20堆对我来说也是够多的了,我只能实现15对,也许将int 型改为long int型可以增加至31堆.
不过你说的也对,穷举法也实在太陋了!!!


Finding!!!
2006-05-14 13:59
myajax95
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:30
帖 子:2978
专家分:0
注 册:2006-3-5
收藏
得分:0 
抱歉看错题了,如果最多只有20堆的话 2的20次方没多大就随便怎么写都行了。
很可能只能穷举解,多体问题能用演绎方法推理出来的太少了。

[此贴子已经被作者于2006-5-14 14:04:30编辑过]


http://myajax95./
2006-05-14 14:04
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

这个题感觉没什么好办法,就是群举了,最多20堆,还是可以算的
32楼算20堆 81毫秒,不过算更多也不行


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-14 14:07
快速回复:石头归并问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028191 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved