tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

两数之和解题报告


1、题目概括:假设有n(2<n<10)个数,给你n个数中每两个数的和(那么共有n(n-1)/2)个和,要你求n个非负整数。无解则输出Impossible。

2、题目分析:看这组数据
4(n)
500 210 100 120 400 300(n(n-1)/2)个和)
先把这n(n-1)/2数排序。100 120 210 300 400 500
其中最小的和就应该是最小和第二小两个数之和。(这里枚举找最小和第二小两个数) 假设找到了 5 95(5+95=100)
再向下找,第二小的和就应该是最小和第三小数之和。 然后就可以找出三个和了。 继续找 115 那么就求出了三个和 100 120 210
接着找,依次的和就应该是最小和第i小数之和。 ....
最后如果找到n个数并且所有的和都用完就可以输出了。 ....

3、程序实现:关键有两点:1、找最小和第二小两个数。
2、判断枚举到的是否走过。
对于1 我用了while来找
对于2 我用了一个b数组,来判断本个数走过的次数(c数组记录初始走过的次数)
核心代码:
while(ans[1]+1<a[1]/2+1)//ans记录找到的结果
{
int s=0;//判断是否找到了一个不符合条件的数
ans[1]++;//第一个数
ans[2]=a[1]-ans[1];//第二个数应该是最小的和-第一个数(这里n(n-1)/2个和是a,已排好序)
m=2;//找到的结果的个数
for(int i=1;i<=n*(n-1)/2;i++) b[a[i]]=c[a[i]];//初始化b数组
for(int i=2;i<=n*(n-1)/2;i++)
if(b[a[i]]!=c[a[i]])//如果第i小的和没被用过
{
b[a[i]]--;//第i小的和用过一次
ans[++m]=a[i]-ans[1];//找到新一个结果,计数器加1
for(int j=2;j<m;j++)//枚举以前找到的数和刚刚找到的数做和
{
if(b[ans[m]+ans[j]]>0) b[ans[m]+ans[j]]--;//如果这个数还可以用,就把次数--
else {s=1;break;}//如果这个数不能用了,就记录不能用了,跳出循环
}
if(s==1) break;
if(m==n) shuchu();//如果找到n个数,就判断然后进行输出
}
}
4、总结归类 联想:这道题的n非常小,因为给出的和都小于100001,所以找到的数最大就是49999,所以我认为搜索也可以做到。(搜索就是找每个数)
但如果n非常大,就只可以用这个方法了。


推荐相关:

参数估计和假设检验习题解答

2.某纺织厂在正常的运转条件下, 平均每台布机每小时经纱断头数为 O.973 根,...A 和? B 分别是 A、B 两化验员测量数据总体的方差,且总体 2 2 服从正态...


楚香凝2015河北行测数量真题解析

并且 17 和 19 互质,所以买了 A4 纸 17 包、B5 纸 19 包,总费用 17*19*2,尾数 6,选 A (19)五个互不相同的自然数两两相加,只得到 8 个不同的...


组合数学习题解答

集合,于是 B 的 10-组合数就是 S 中不具有性质 p1,p2,p3 的 元素个数。...问掷骰子后,点数之 和为 r ,两颗骰子的点数有多少种搭配方式? 解:每个骰子...


楚香凝2014河南公务员数算真题解析

楚香凝2014河南公务员数算真题解析_公务员考试_资格考试/认证_教育专区。楚香凝数学...乙两部分,其面积之 比是 15∶7.问上底 AB 与下底 CD 的长度之比是( A...


楚香凝2015新疆行测数量真题解析

道题由答对转化为答不对就少 20 分,所以没答对的题数=80/20=4 道,选 D (6)A、 B 两个仓库分别存放有 8 台和 12 台挖掘机,现需要往 C 工地和 D ...


楚香凝2015江苏行测A类数量真题解析

相乘的两部分之和固定=(1+a+1+b),想当于把(1+a+1+b)拆分成两个数,使得乘积 最大,则令拆出的两个数相等即可,选 B (8)黑白两个盒子中共有棋子 193...


2016年山东省青岛市中考数学试卷参考答案与试题解析

2016年山东省青岛市中考数学试卷参考答案与试题解析_中考_初中教育_教育专区。...由两函 数图象只有一个交点可得知该方程有两个相同的实数根,结合根的判别式...


2015年天津公务员考试数量关系真题解析

在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档


楚香凝2015联考行测数量真题解析

(6) 掷两个骰子, 掷出的点数之和为奇数的概率为 P1, 掷出的点数之和为...P1>P2 C. P1<P2 D.无法判断 楚香凝解析:总情况数=6*6=36,点数和为奇数...


《解决问题(两数之和的奇偶性)》教学设计

《解决问题(两数之和的奇偶性)》教学设计一、教学目标 (一)知识与技能 能正确判断两数之和的奇偶性, 并利用两数之和的奇偶性解决简单的实际问题; 初步感 知...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com