(c++)枚举--假币问题(详细讲解)
本实验取材于郭炜老师《程序设计与算法》.假币问题课上也讲了,学徒我听得也不是很明白,仔细消化理解之后,发了这篇文章。#include<iostream>#include<cstring>using namespace std;char Left[3][7];char Right[3][7];char result[3][7];bool IsFake(char...
·
本实验取材于郭炜老师《程序设计与算法》.
假币问题课上也讲了,学徒我听得也不是很明白,仔细消化理解之后,发了这篇文章。
#include<iostream>
#include<cstring>
using namespace std;
char Left[3][7];
char Right[3][7];
char result[3][7];
bool IsFake(char c,bool light);
int main()
{
int t;
cin >> t;
while(t--){
for(int i=0;i<3;++i)
cin >> Left[i] >> Right[i] >> result[i];
for(char c='A';c<='L';c++){
if(IsFake(c,true)){
cout << c << " is the counterfeit coin and it is light.\n";
break;
}else if(IsFake(c,false)){
cout << c << " is the counterfeit coin and it is heavy.\n";
break;
}
}
}
return 0;
}
bool IsFake(char c,bool light){
//light 为真表示假设假币为轻,否则表示假设假币为重
for(int i=0;i<3;i++){
char *pLeft,*pRight;
if(light){
pLeft = Left[i];
pRight = Right[i];
}else{//如果假设假币是重的,则把称量结果左右对换
pLeft = Right[i];
pRight = Left[i];
}
switch(result[i][0]){
case 'u':
if(strchr(pRight,c)==NULL)
return false;
break;
case 'e':
if(strchr(pLeft,c) || strchr(pRight,c))
return false;
break;
case 'd':
if(strchr(pLeft,c) == NULL)
return false;
break;
}
}
return true;
}
本实验一共两个函数。一个是主函数,一个是判断真假函数。数据的存储利用left和right,最后这个result就是判断到底是天平上升、下降、相平的。
代码先输入,输入完,三种状态,从A到L开始枚举也就是2^12种状态,判断是该字符是否是重的还是轻,假设为轻的,然后调用isfake函数。三次循环开始
亮点亮点!重和轻始终是相对而言,因此他就两者交换,堪称妙笔。
然后开始遍历 ,如果都是真币按照情况你应该平等,一次判断只出现一种情况也就是上升、下降、相平的一种不会出现三种情况都出现的情况这也是认知前提。
- 天平上升的右端没有发现有这个字母,所以它不可能了
- 天平相等那就必然是左边没这个字母,右边也没这个字母才算这个质量有问题,因此他也算一个case语句。
- 天平下降也就是left有没有这个字母。
如果都没有说明不是请了,而是重了,然后在分析重的情况!
总结:
- 枚举算法考虑枚举范围
- 枚举算法考虑枚举状态
- 枚举算法考虑枚举顺序
枚举算法也被称为暴力破解!
更多推荐
所有评论(0)