【C++编程题】小希的数表

【问题描述】

Gardon 昨天给小希布置了一道作业，即根据一张由不超过 5000 的 N(3<=N<=100)个正整数组成的数表两两相加得到 N*(N-1)/2 个和，然后再将它们排序。例如，如果数表里含有四个数 1，3，4，9，那么正确答案是 4，5，7，10，12，13。小希做完作业以后出去玩了一阵，可是下午回家时发现原来的那张数表不见了，好在她做出的答案还在，你能帮助她根据她的答案计算出原来的数表么？

【输入形式】

包含多组数据，每组数据以一个 N 开头，接下来的一行有按照大小顺序排列的 N*(N-1)/2 个数，是小希完成的答案。文件最后以一个 0 结束。
假设输入保证解的存在性和唯一性。

【输出形式】

对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。

【样例输入】

4
4 5 7 10 12 13
4
5 6 7 8 9 10
0

【样例输出】

1 3 4 9
2 3 4 6

【解题思路/叨叨念】

这道题想了很久很久，没思路，照着别人代码写还折腾了很久...

上面就是所有的sum。（1，2）和（1，3）肯定是最小和次小的，可以确定。

问题是，怎么找到（2，3）？

如果找到（2，3），就可以求出a3，而且可以把（1，2），（1，3），（2，3）都标记，像下面：

那么这时候只要在剩下没有标记的sum中找到最小值，那个最小值就是（1，4），这样又可以求出a4,这样再标记（2，4），（3，4），又可以求出（1，5）...直到求出所有a值。

问题是怎么确定哪个sum是（2，3）？那当然是计算机拿手好戏~

------>【暴力遍历】所有sum来 “当作” （2，3）,得到所有a，如果此时能把sum全部标记，那么得到的所有a值就是唯一答案！

有时候我们会觉得难以解决的问题, 可能不是思维上的问题(没有方法), 可能只是数据很大, 我们思维定势觉得我们无法解决这样的问题, 然而其实可以通过计算机, 利用这种计算思维, 将求解过程模拟出来. @姬小野

【AC代码】

  #include#include#include#includeusing namespace std;/*这道题想了挺久  主要是知道a1+a2,a1+a3  但是怎么找到a2+a3呢？计算机-->【遍历】来寻找验证，答案唯一，找到就是正确的 本身数据量是不大的：N < 100 */int sum[10200]; //和 数组 
int vis[10200]; //访问和的数组 
int num[110];   // 原数字 int main(){int n;while(cin>>n&&n){int size=(n*(n-1))/2;for(int i=1;i<=size;i++){  //下标从1开始 cin>>sum[i];}	for(int i=3;i<=size;i++) {     //循环很多次，暴力穷举！ 假设sum【i】是a2+a3，//如果，sum全被访问了，说明sum【i】就是a2+a3，否则继续遍历 //num[1]+num[2]=sum[1];//num[1]+num[3]=sum[2];//num[2]+num[3]=sum[i];   这里假设sum[i]是a2+a3,推出a4，a5，an……能全部推出来，就是答案 num[1]=(sum[1]+sum[2]-sum[i])/2;num[2]=sum[1]-num[1];num[3]=sum[2]-num[1]; if (( sum[1]+ sum[2] - sum[i]) % 2 || (sum[1] + sum[2] - sum[i] <= 0)) continue; // 2*a1肯定不是奇数   a1一定是正整数....不然得出来一组非整数解 memset(vis,0,sizeof(vis));//每次都要把mark数组清0，检验当前的sum[i]是不是a2+a3vis[1]=vis[2]=vis[i]=1;  //标记 和1，2，i都已经被访问过//这个时候，没有被访问的和中，最小的就是a1+a4,然后求出a4,标记a1+a4,a2+a4,a3+a4;这个时候最小的就是a1+a5…… int know=3; //目前已经知道的数int flag=1;while(know!=n){int mini=-1;//在没被访问的数字里找到最小值，由于有序，没被访问的第一个就是最小值 for(int j=1;j<=size;j++){if(vis[j]==0){mini=sum[j];vis[j]=1;//标记访问，这里最小值实际上就是a1+a4,a1+a5...等 break; }}num[know+1]=mini-num[1];know++; //这里是2~(know-1)  因为a1+aj已经被标记过了for(int k=2;k<=know-1;k++) { //找到了新的数字，把之前找到的数字和新数字相加，从sum中去去除 int temp=num[k]+num[know];flag=0;for(int p=1;p<=size;p++){if(vis[p]==0 && sum[p]==temp){flag=1;vis[p]=1;break;}}if(flag==0) break;  //如果相加出来的值找不到，那说明一开始a2+a3找错了 }if(flag==0) break;} 	//while循环正常或者不正常结束了...if(know!=n) continue;   //这个sum[i]不对，继续for循环找下一个for(int h=1;h<=n;h++){  //找到了 cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！