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

求和的一半SUM,然后数组前N项相加当和大于SUM时将此N项赋予新数组B,余下的给数组C,求B的和SUMB,T=SUM-SUMB;B中元素和C中元素求差值为N当T>N>0时交换两个元素,如B中元素<T,将此元素赋予C,B中变成0;循环!


用0-1统治世界!
2006-05-03 03:10
诸神的黄昏
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2006-4-27
收藏
得分:0 

// 6.cpp : Defines the entry point for the console application.
//
//哇 哈哈~做了2个多小时 终于搞定了~
//本题本人的思路是把输的堆(石头的重量)总数编为组,如 第一行的5 就是第一组~第7行的2就是第2组~
//由于是晚上12点过做的 瞌睡太浓~可能存在些问题(比如输入字母的情况等等),希大家帮我多看看,共
//同改进。
//本来想只写方法的 但是我想写了方法后还是会有人懂~干脆狠心做出来了
//哈哈 我英语差,所以变量名有字母.有英语,有拼音~大家表被名字麻痹了哈

#include "stdafx.h" //vc++6.0必须包含的头文件,其他编译器里可以不用写这一行
int a[100],b,last[10],j=0; // 定义全局变量.a[100]用来装每组所输入的堆数,每组最多100堆。 last[10]
char num; //用来装组数,最多可以输入10组。
int main(void)
{

int chaju(int i1);
char ch;
int i;
printf("请输入第1组总堆数(输入后按回车继续):\n");//文字都是自己加上去的,方便
scanf("%c",&num); //理解,也可删除。
num=int(num-48);
do //先do 输入~再判断是否继续输
{


for(i=0;i<num;i++)
{
printf("请输入第%d组第%d堆(输入后按回车继续):\n",j+1,i+1);
scanf("%d",&a[i]);
scanf("%c",&ch); //用ch 吃掉每次输入数据后输入的回车。

}
for(i=0;i<num;i++)
last[j]+=a[i];
for(i=0;i<num*num;i++) //其实好象是i<2的num次方就行了的.嘿嘿 不想再写函数了
last[j]=chaju(i); //调用函数(chaju)


printf("请输入第%d组总堆数(输入后按回车继续):\n",j+2);
scanf("%c",&num);
if(num==10) //判断输完一组数据后否输入的是回车,若是 跳出
break; //这里想了很久啊,所以我是把输入的每组大小定义为CHAR类型的。好满足
num=int(num-48); //作者的要求。具体的大家自是己想,有更好的方法请提出来大家一起参考。
j++;
}
while(1);
for(i=0;i<=j;i++)
{
printf("第%d组相差得最小的数为:%d \n",i+1,last[i]);//输出最后结果.
}
return 0;
}
int chaju(int i1)//每次传递参数,每次判断.
{
int b,c,d[100],all=0;
for(int i=0;i<num;i++)
d[i]=a[i];
c=i1;
do
{

b=c%num; //这里比较核心哦,想了半个多小时~嘿嘿 我没学过数据结构,不知道是否学了它
d[b]=-1*d[b];//之后在处理这种问题会简单些
c=c/num;
}
while(c!=0);

for(i=0;i<num;i++)
all+=d[i];
all=all>0?all:-all; //取绝对值
return(last[j]=last[j]>all?all:last[j]);

}

以下是引用–★–在2006-5-3 7:52:00的发言:
虽然您很辛苦,但还是有点简单事情复杂化。因为本题的关键在于算法探讨,而并不在乎怎样扩大“战果”从一组扩张到N组。

晕,本来作者要求的就是输入N组后,再输出每组的结果啊...要是输入一组 输出一组.那方便多了~
你还以为我多事,自找麻烦啊...
还有我用的算法根本不是11楼的算法,我承认他的算法很经典,但是处理的过程中会有很多难点我的算法更简单
我们的算法根本不一样,我之前也没看过他的算法,我没有一遇到题就先看别人的算法的好习惯 不知道大家到底看明白我写的没~
请大家不要想当然,有了算法离结果就差不多了;
程序是靠写出来的 不是想出来的....
正如伟大的毛主席的一句话--------理论和实践是有差别的...
我的思路是:若是+代表防在左边 -代表放在右边
刚开始把所有的数据都相加~然后用一个数来控制有几个数,第几个数反号.比如一组数中有5个数装入a[5]中.把a[5]拷贝到函数中的形参b[5]中当i=0时,
因为i%5=0,所以形式参b[0]变为-b[0]也就是把他放在右边.然后把B的每个元素想加判断.,继续循环 比如i=21时~21%5=1所以b[1]变为-b[1] 然后4%5=4所以 b[4]变为-b[4];

[此贴子已经被作者于2006-5-3 11:16:34编辑过]

2006-05-03 03:58
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
以下是引用诸神的黄昏在2006-5-3 3:58:00的发言:

// 6.cpp : Defines the entry point for the console application.
//
//哇 哈哈~做了2个多小时 终于搞定了~
//本题本人的思路是把输的堆(石头的重量)总数编为组,如 第一行的5 就是第一组~第7行的2就是第2组~
int a[100],b,last[10],j=0; // 定义全局变量.a[100]用来装每组所输入的堆数,每组最多100堆。 last[10]
char num; //用来装组数,最多可以输入10组。

虽然您很辛苦,但还是有点简单事情复杂化。因为本题的关键在于算法探讨,而并不在乎怎样扩大“战果”从一组扩张到N组。

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-03 07:52
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
这道题不错哦!楼上的说得没错,本题的关键在于算法探讨,
有了算法,这道题实现起来是比较容易的。
我觉得11楼的方法相当不错.俺自己估计是想不出那样的算法的

对不礼貌的女生收钱......
2006-05-03 09:02
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
回复:(ninanwine)求和的一半SUM,然后数组前N项相加...
以下是引用ninanwine在2006-5-3 3:10:00的发言:

求和的一半SUM,然后数组前N项相加当和大于SUM时将此N项赋予新数组B,余下的给数组C,求B的和SUMB,T=SUM-SUMB;B中元素和C中元素求差值为N当T>N>0时交换两个元素,如B中元素<T,将此元素赋予C,B中变成0;循环!


应改为如B中元素<=T/2,因为一进一出,双倍关系哦。


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-03 09:25
诸神的黄昏
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2006-4-27
收藏
得分:0 
以下是引用–★–在2006-5-3 7:52:00的发言:
虽然您很辛苦,但还是有点简单事情复杂化。因为本题的关键在于算法探讨,而并不在乎怎样扩大“战果”从一组扩张到N组。

晕,本来作者要求的就是输入N组后,再输出每组的结果啊...要是输入一组 输出一组.那方便多了~
你还以为我多事,自找麻烦啊...
还有我用的算法根本不是11楼的算法,我承认他的算法很经典,但是处理的过程中会有很多难点我的算法更简单
我们的算法根本不一样,我之前也没看过他的算法,我没有一遇到题就先看别人的算法的好习惯 不知道大家到底看明白我写的没~
请大家不要想当然,有了算法离结果就差不多了;
程序是靠写出来的 不是想出来的....
正如伟大的毛主席的一句话--------理论和实践是有差别的...

[此贴子已经被作者于2006-5-3 11:02:05编辑过]

2006-05-03 10:40
youxiaxyz
Rank: 1
等 级:新手上路
帖 子:85
专家分:0
注 册:2006-4-5
收藏
得分:0 
以下是引用ninanwine在2006-5-3 3:10:00的发言:

求和的一半SUM,然后数组前N项相加当和大于SUM时将此N项赋予新数组B,余下的给数组C,求B的和SUMB,T=SUM-SUMB;B中元素和C中元素求差值为N当T>N>0时交换两个元素,如B中元素<T,将此元素赋予C,B中变成0;循环!

我觉的T = SUMB - SUM这样才大于0
11楼算法挺好,值得借鉴

2006-05-03 10:58
youxiaxyz
Rank: 1
等 级:新手上路
帖 子:85
专家分:0
注 册:2006-4-5
收藏
得分:0 
以下是引用ninanwine在2006-5-3 3:10:00的发言:

求和的一半SUM,然后数组前N项相加当和大于SUM时将此N项赋予新数组B,余下的给数组C,求B的和SUMB,T=SUM-SUMB;B中元素和C中元素求差值为N当T>N>0时交换两个元素,如B中元素<T,将此元素赋予C,B中变成0;循环!

我觉得T = SUMB - SUM
11楼算法比较好,值得借鉴

2006-05-03 11:01
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
回复:(诸神的黄昏)
请(诸神的黄昏)测试1组数据即可:
10
1
2
3
4
5
6
7
8
9
10

要请教的是,您的运行结果为何是17?
除非我的电脑不正常。
毛主席说过那句话?毛选几卷几页呀?

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-03 11:52
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

当提供了一组测试数据,你可以求出它的所有非空子集
每个子集当然相对于测试数据整体有个补集、

例如所有数据字之和为sum0
某子集所有数据之和为sum1
显然当|sum0-2*sum1| 在所有可能中最小时
也就是题目要的那种状态

差值为|(sum0-sum1)-sum1|=|sum0-2*sum1|

当然这样要找出它的所有子集(也很麻烦)


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



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

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