| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3838 人关注过本帖
标题:石头归并问题
只看楼主 加入收藏
ninanwine
Rank: 1
等 级:新手上路
帖 子:47
专家分:0
注 册:2006-5-1
收藏
得分:0 
第一次有人表扬我,我可是遇到编程科目就挂红灯的主啊!

用0-1统治世界!
2006-05-03 21:41
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

声明:题目要求重量可以到100000,本程序限定在int内(测试者可以改动)
只提供一组测试数据测试,需要多组,测试者加个循环修改
本程序提供测试之用,不一定正确
[CODE]
#include "stdio.h"
#include "math.h"
#include "malloc.h"

int d_value;
int *array,size,sum=0;

void Subset(int i,int total)
{
int s_total=0;

for(;i<size;i++)
{
s_total=total+array[i];
if( d_value > (int) fabs(sum-2*s_total) )
d_value = (int) fabs(sum-2*s_total);
if(i<size-1)
Subset(i+1,s_total);
s_total=0;
}
}

int main()
{
int i,total=0;

printf("please input the num of test data:\n");
scanf("%d",&size);
array=(int *) malloc ( sizeof(int)*size );
printf("pleade input test data:\n");
for(i=0;i<size;i++)
{
scanf("%d",array+i);
sum+=array[i];
}
d_value=sum;
for(i=0;i<size;i++)
{
Subset(i,total);
total=0;
}
printf("%d\n",d_value);
free(array);

return 0;
}

[/CODE]


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-04 01:35
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-04 01:40
Sukiyou
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2006-5-6
收藏
得分:0 
先排一下序会 简单的多

2006-05-07 18:30
bennyhe
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2005-11-28
收藏
得分:0 
还是看不懂!!
???
2006-05-07 22:43
djx20040701
Rank: 1
等 级:新手上路
帖 子:44
专家分:0
注 册:2006-4-20
收藏
得分:0 
我感觉不用像楼上的,
你可以将前N项和N-1项比较呀
2006-05-07 23:38
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

版主老大您的程序,俺检验到现在,还没发现毛病呢!
我也编了个这道题的程序,专门用来检测版主您的程序,感动吧
呵呵,不过,我算法很烂,当时只是想用来检测而已,没仔细想算法.
现在也把它贴上去,提供小数字的检验,大数字这程序检验不了,算法太过垃圾!
/*
程序辅助生成一个长为n的0-1串,开始为111111;灼次减1至000000;每次生成两个和sum1(1相加),sum2(0相加);比较最小即可得到,当然,这个算法较烂,实现时间要很长,检验大数的时候,不可忍受!
*/
#include <stdio.h>
int main()
{
int num,i,j,k,tag=0,sum1=0,sum2=0,flag=0,temp,minous;
short *memo=NULL;
int *stone_weight=NULL;
printf("Please input the number of the stones:\n");
scanf("%d",&num);
memo=(short *)malloc(sizeof(short)*num);
for(i=0;i<num;i++)
memo[i]=1;
stone_weight=(int *)malloc(sizeof(int)*num);
printf("Now please enter the weight of the stones:\n");
for(i=0;i<num;i++)
scanf("%d",&stone_weight[i]);
while(1)
{
for(j=i-1;i>-1;j--)
{
if(memo[j]==1)
{
memo[j]=0;
for(k=j+1;k<num;k++)
memo[k]=1-memo[k];
break;
}
}
for(i=0;i<num;i++)
if(memo[i]==1)
break;
else tag++;
if(tag==num)
break;
tag=0;
for(i=0;i<num;i++)
{
if(memo[i]==1)
sum1+=stone_weight[i];
else
sum2+=stone_weight[i];
}
if(flag==0)
{
minous=sum2-sum1>0?sum2-sum1:sum1-sum2;
flag=1;
}
else
{
temp=sum2-sum1>0?sum2-sum1:sum1-sum2;
minous=minous>temp?temp:minous;
}
sum1=sum2=0;
}
printf("%d\n",minous);
free(memo);
free(stone_weight);
getch();
return 0;

}



对不礼貌的女生收钱......
2006-05-12 16:43
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 
soft_wind 实在是辛苦啦 ,记特等功一次


----------
胡锦涛

叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-12 21:02
songweiwen
Rank: 1
等 级:新手上路
帖 子:112
专家分:0
注 册:2006-2-19
收藏
得分:0 
大家看一下我的想法:
假设sum=(-1)^x1a1+(-1)^x2a2+...+(-1)^xnan
其中xn是-1的指数,an是第n堆石头的重量,且xn的取值是1或2.
那问题就是求sum的最小值,具体看一下每个xn的取值.

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

这本来是条数学问题,但我就不会用数学的方法解决了.
考虑到计算机的速度,我们完全可以用穷举法,将所有的sum求出来,再找到最小值.


Finding!!!
2006-05-14 12:38
快速回复:石头归并问题
数据加载中...
 
   



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

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