蛮力法的使用：-1083: False coin（1）
蛮力法的使用：-1083: False coin（1）<div class="postbody"><div id="cnblogs_post_body">题目：http://acm.hzic.edu.cn/JudgeOnline/problem.php?id=1083
思路很简单 ：把所有的金币都试一遍。
Step 1： 依次假设I号金币是假的；
Step 2： 对称量的记录进行检测；如果假设与所有的记录都不矛盾，则有可能是假的 ；
Step 3： 如果有可能是假的金币只有一个，则输出他的编号；否则输出为0；
HINT
[*]不需要特殊的数据结构；
[*]算法采用暴力搜索；
<div class="cnblogs_code" >http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gifhttp://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gifView Code <div id="cnblogs_code_open_ae7c64f4-1929-41bc-a53a-9ebf1a97c5df" class="cnblogs_code_hide"> 1 #include<iostream> 2 using namespace std; 3 int jd(int,int *,char); 4 int main() 5 { 6 int num[100][1001]; 7 char s[1000];//输入内容 8 int n,i,j,t,k,no; 9 cin>>n>>k;10 for(i=0;i<k;i++)11 {12 cin>>num[0];13 for(j=1;j<=2*num[0];j++)14 {15 cin>>num;16 } 17 cin>>s; 18 }//以上为输入参数 19 for(i=1,t=0;i<=n;i++)//暴力搜索所有的情况 20 {21 for(j=0;j<k&&jd(i,num,s);j++);22 //对所有情况的称量记录进行检测 23 if(j<k) continue;24 t++;//t保存嫌疑对象的个数 25 if(t>1)26 break;27 no=i; 28 } 29 if(t-1)30 cout<<0<<endl;31 else cout<<no<<endl;32 return 0;33 }34 35 int jd(int j,int *s,char c)36 {37 //函数判断假设j号金币是假的与称量结果是否矛盾38 //s是称量记录，其第一个元素是砝码个数39 //c是称量结果 40 int m,i,f;//f是判断测量是否含含有j号金币 41 m=s[0]<<1;//m是砝码个数乘以2，是指天平左右的总数 42 for(i=f=1;i<=m&&f;)43 if(s==j)44 f=0;45 else 46 ++i;47 //判断本次称量有没有j号金币。 48 if(!f&&c=='=' || f&&c!='=')49 return 0;//与假设矛盾 50 return 1;51 }
页:
[1]