当前位置:首页 >> 学科竞赛 >>

两数之和解题报告


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

相关文章:
2016年山东省烟台市中考数学试卷参考答案与试题解析
然后从他们的成绩平均数 (环)及方差两个因素进行分析, 甲、乙、 丙的成绩分析如表所示, 丁的成绩如图所示. 甲乙丙 7.9 7.9 8.0 平均数 3.29 0.49 1.8...
NOIP2015普及组复赛试题解题报告word版第一二题满分程序
NOIP2015普及组复赛试题解题报告word版第一二题满分程序_学科竞赛_初中教育_教育...输入文件第一行是用一个空格隔开的两个整数 n 和 m, 分别表示雷区的行数和...
参数估计和假设检验习题解答
2.某纺织厂在正常的运转条件下, 平均每台布机每小时经纱断头数为 O.973 根,...A 和? B 分别是 A、B 两化验员测量数据总体的方差,且总体 2 2 服从正态...
数字设计基础与应用(第2版)第1章习题解答
将下列十六进制数转换为二进制数和十进制数 (1) ...如图 1-17(a)(b)所示,从两个函数独立化简结果...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告...
数​字​电​路​2​题​解
试用两个 3 线-8 线译码器和适当的门电路设计一个组合逻辑电路,使其实现下列...解: 预置数? 15 ? N0 (模) ? 1 ? 4 ? (0100 )2 计数输出 1 时钟...
概率论第1章作业题解
1 ? ? 16 8 16 16 1.12 掷一颗匀称的骰子两次, 求前后两次出现的点数之和...解:用 Ai (i ? 0,1,2) 表示事件“在第一箱中取出两件产品的次品数 i ...
2015-2016学年度第一学期九年级数学测试(2) 参考答案与...
(2)方程 x +y =5 含有两个未知数,错误; (3) (4)x + 2 2 =5 是...分解法以及直接开平方和公式法解方程,熟练记忆求根公式是解题关 键. 7. (3 ...
spss软件应用与题解2
您本次 存款的 国家机关 商业服务业 个案数 百分比 个案数 百分比 24 100.0...下面两图常住地为分别为沿海和中心繁华城市和偏远地区, 不难发现在沿海和中心...
数理统计方法题解4-1
这说明参数的区间估计与参数的假设检验有着一一对应的关系,可以用参 数的区间...(显著水平 ? ? 0.05 )解中 2 设甲、乙两台机床生产的滚珠直径分别为 ? ...
楚香凝2014河南公务员数算真题解析
楚香凝2014河南公务员数算真题解析_公务员考试_资格考试/认证_教育专区。楚香凝数学...乙两部分,其面积之 比是 15∶7.问上底 AB 与下底 CD 的长度之比是( A...
更多相关标签: