| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3838 人关注过本帖
标题:石头归并问题
只看楼主 加入收藏
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
实在不好意思,我也错了!
将int型改为 long int型也就可以计算15堆,改为unsign long int才可以计算31堆啊!我知道错在那里了.
请问有什么方法可以保存更大的整数呢???
"32楼算20堆 81毫秒,不过算更多也不行"请问怎样计算时间的?????

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

最省脑子的方法,把所有可能的堆法列一下,直接数。
#include "math.h"

int main(int argc, char* argv[])
{
long lTryTimes, lCount, lCurrentCount;
int intStoneNumber, intStoneWeight[20], intTotalWeight=0, intTmp, intCurrentWeight, intMinDiff;

scanf("%d", &intStoneNumber);
for (intTmp = 0; intTmp < intStoneNumber; intTmp++)
{
scanf("%d", &intStoneWeight[intTmp]);
intTotalWeight += intStoneWeight[intTmp];
}

lTryTimes = (int)pow(2, intStoneNumber);

intMinDiff = intTotalWeight;
for (lCount = 0; lCount < lTryTimes; lCount++)
{
lCurrentCount = lCount, intCurrentWeight = 0;
for (intTmp = 0; intTmp < intStoneNumber; intTmp++)
{
if (lCurrentCount % 2)
intCurrentWeight += intStoneWeight[intTmp];
lCurrentCount /= 2;
}
if (intMinDiff > abs(intTotalWeight - intCurrentWeight * 2))
intMinDiff = abs(intTotalWeight - intCurrentWeight * 2);
}

printf("min diff is %d\n", intMinDiff);
return 0;
}


http://myajax95./
2006-05-14 14:24
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 
以下是引用songweiwen在2006-5-14 14:16:00的发言:
实在不好意思,我也错了!
将int型改为 long int型也就可以计算15堆,改为unsign long int才可以计算31堆啊!我知道错在那里了.
请问有什么方法可以保存更大的整数呢???
"32楼算20堆 81毫秒,不过算更多也不行"请问怎样计算时间的?????

long start ,end;

----
----
start=clock();

----
---
end=clock();

end-start 就是运行时间(单位:毫秒)


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-14 14:30
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

如果是穷举,我想我的算法虽然很烂,但却是最清楚的了,呵呵
程序应该有更好的算法才是……
版主老大,您用的也是穷举吗?


对不礼貌的女生收钱......
2006-05-14 14:35
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
以下是引用feng1256在2006-5-14 14:30:00的发言:

long start ,end;

----
----
start=clock();

----
---
end=clock();

end-start 就是运行时间(单位:毫秒)

谢谢!!
你说用32楼的方法计算20堆用了81毫秒,大于20堆又不行了,干嘛不行了??


Finding!!!
2006-05-14 21:15
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
power(int n)
{int i;long p=2;
for(i=1;i<n;i++)
p=2*p;
return(p);
}
void count(int n,int *sum,int *a)
{long i,j,l,k,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 m,temp,j=0,num=1;long i,l,k,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;long start,end;
start=clock();
printf("Input the number of array n(1<n<8):");
scanf("%d",&n);
sum=(int *)malloc( sizeof(int)*power(n));
if(sum==NULL)
{
printf("No enough memory!Press any key to exit.");
getch();
exit(0);
}
printf("\nInput the array:\n");
for(i=0;i<n;i++)
scanf("%d",(a+i));
printf("\n");
count(n,sum,a);
output(n,sum);
free(sum);end=clock();printf("\ntime is:%d",end-start);
getch();
}
用以上程序计算12个以下数据:789 456 123 120 130 452 852 654 369 258 147 256.所用时间平均是600毫秒,但用32楼的程序平均要用700毫秒(我试了三次:624 780 769),可以看出的程序在计算大数时还是具有优势的,更何况可以输出具体的分组方法呢!!!
但有一个问题我实在解决不了,那就是我这个程序不能解决14个数以上的问题,我搞了一晚就是两个字"郁闷".各位版主有时间帮我想想,帮把忙好吗???

Finding!!!
2006-05-14 21:46
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

用以上程序计算12个以下数据:789 456 123 120 130 452 852 654 369 258 147 256.所用时间平均是600毫秒,但用32楼的程序平均要用700毫秒(我试了三次:624 780 769),可以看出的程序在计算大数时还是具有优势的,更何况可以输出具体的分组方法呢!!!
但有一个问题我实在解决不了,那就是我这个程序不能解决14个数以上的问题,我搞了一晚就是两个字"郁闷".各位版主有时间帮我想想,帮把忙好吗???


这组数据我测试了,用时0豪秒~ 我怀疑你用的是286
这题用时和数字多少是呈几何级数的,和数字大小可以说没关系

32楼的我的意思是算20堆以后的越来越慢,数字越大越吃力
例如石头有30堆,用了91秒才算出来,累

你的不能算14以上的,可能是算的时间太长,马上出不了结果,所以你以为算不了?


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-14 22:59
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
以下是引用feng1256在2006-5-14 22:59:00的发言:


这组数据我测试了,用时0豪秒~ 我怀疑你用的是286
这题用时和数字多少是呈几何级数的,和数字大小可以说没关系

32楼的我的意思是算20堆以后的越来越慢,数字越大越吃力
例如石头有30堆,用了91秒才算出来,累

你的不能算14以上的,可能是算的时间太长,马上出不了结果,所以你以为算不了?


看一下,这就是用你的程序在我的电脑上运行的情况:time is:696 910 768.
我是没骗你的!也许你电脑是快,但在我的电脑 上出问题起码可以说明程序的通用性!!你也不要小看人,我这台电脑据说是奔4的.
还有你看到了没有,我在最后输入12个千位数字,计算他们用了1022毫秒!!!更惨是输出的结果是-24492.是负值!!!

[此贴子已经被作者于2006-5-15 8:10:36编辑过]


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

怎么图片看不了的????


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

哎!算了,都是我这个人太马虎!!我算出来的时间包含了我输入数字的时间!!!
现在我改了,发现程序运行确实用还不到1毫秒,我是用%d输出时间的,所以输出0.
但有一点没错,就是你程序的运行结果还是-24492,错的!!!
正确的答案是5868.
你可以用下面的方法检验一下:0 1 0 0 0 0 0 0 0 0 0 0
就是用23456减去其他.
我的测试数据是:1234 23456 1245 1263 1475 1596 1236 2365 2321 2145 1256 1452


Finding!!!
2006-05-15 08:27
快速回复:石头归并问题
数据加载中...
 
   



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

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