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非常大,就只可以用这个方法了。

赞助商链接
推荐相关:

数学和差倍问题练习题解

(1+2×2+2+2)=108÷9=12(件) 二、和倍差数学题解 1、有两个自然数相除,商是 17,余数是 13,已知被除数、除数、商与余数之和等于 2113,则被除数是...


第1章作业题解

之和为 3 的概率为 1 。 18 1 1 , 。 12 9 同理可以求得前后两次出现...解:用 Ai (i ? 0,1,2) 表示事件“在第一箱中取出两件产品的次品数 i ...


二年级数学奥数题及解题详解

二年级数学奥数题及解题详解 - 第一类:简单推理 1、下列算式中,△和★各代表什么数? ★+★+★+△+△=22 △+△+★+★+★+★+★=30 ★=( )△=( ) ...


和差倍问题专项练习题解

参加跳绳和踢踺子比赛的各有多少人? 例 6、已知两个数相除的商为 4,相减的差是 39,者两个数分别为多少? 例 7、仓库里存放大米和面粉两种粮食,面粉比大米多...


西师版二下数学计算和问题解决习题_图文

小明的邮票 的张数比小云和小军的总数多 37 张。 小明有多少张邮票? 85、...70、有两群猴子,每群 9 只,现把它们平均分成 3 组,每 组有几只猴子? 71...


概率论第1章作业题解

1 ? ? 16 8 16 16 1.12 掷一颗匀称的骰子两次, 求前后两次出现的点数之和...解:用 Ai (i ? 0,1,2) 表示事件“在第一箱中取出两件产品的次品数 i ...


QZZN论坛资料_数量关系题解分析+思路解题

QZZN论坛资料_数量关系题解分析+思路解题_公务员考试_资格考试/认证_教育专区。一...3 题解析:此题为前两个数之和减 1 等于第三个数,22+35-1=56,35+56-1...


数电习题解(1,2章)

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


2004年数二试题解析

20页 1下载券 2011年数二考研真题及答... 6页 免费2​0​0​4​年...? 故λ = 2 对应的线性无关的特征向量有两个, 从而 A 可相似对角化. 若...


二年级数学奥数题及解题详解

二年级数学奥数题及解题详解_学科竞赛_小学教育_教育专区。第一类:简单推理 1、...解题思路:相邻两个数之间没有规律时,看相隔两个数之间的规律。先看单数 前面...

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