程序设计与算法二郭炜枚举001特殊密码锁
2021/7/27 20:08:08
本文主要是介绍程序设计与算法二郭炜枚举001特殊密码锁,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
有一种特殊的二进制密码锁,由n个相连的按钮组成(n<30),按钮有凹/凸两种状态,用手按按钮会改变其状态。
然而让人头疼的是,当你按一个按钮时,跟它相邻的两个按钮状态也会反转。当然,如果你按的是最左或者最右边的按钮,该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知,需要解决的问题是,你至少需要按多少次按钮,才能将密码锁转变为所期望的目标状态。
输入
两行,给出两个由0、1组成的等长字符串,表示当前/目标密码锁状态,其中0代表凹,1代表凸。
输出
至少需要进行的按按钮操作次数,如果无法实现转变,则输出impossible。
样例输入
011
000
样例输出
1
解题方法
使用两个int型的变量保存初始值和最终值,通过位运算改变每个bit的状态。枚举第一个bit也就是第一个按钮的两种情况,按下第一个按钮,第一个bit反转后可能的按键次数,这是第一种情况;不按下第一个按钮,第一个bit不发生反转后续可能的案件次数,这是第二种情况。
代码实现
# include <iostream> # include <cstring> # include <string> # include <memory> using namespace std; int Getbit(int a, int i) { return (a>>i)&1; } int Setbit(int &a, int i, int b) { if(b) a |= (1<<i); else a &= ~(1<<i); } int Filtbit(int &a, int i) { a ^= (1<<i); } int OutputResult(int result) { if(result>=0) cout<<result; else cout<<"impossible"; } int main() { int init=0,mid=0,end=0,cnt=0,result1=0,result2=0; char line[30]; //输入数据 cin>>line; cnt = strlen(line); for(int i=0;i<cnt;i++) Setbit(init,i,line[i]-'0'); cin>>line; for(int i=0;i<cnt;i++) Setbit(end,i,line[i]-'0'); //不按下第一个按钮的情况 mid = init; for(int i=0;i<cnt-1;i++){ if(Getbit(mid,i)!=Getbit(end,i)){ Filtbit(mid,i); Filtbit(mid,i+1); if(i<cnt-2&&i!=0) Filtbit(mid,i+2); result1++; } if(mid==end){ OutputResult(result1); break; } } //按下第一个按钮的情况 if(mid!=end) { mid = init; //按下第一个按钮 Filtbit(mid,0); Filtbit(mid,1); result2++; for(int i=0;i<cnt-1;i++){ if(Getbit(mid,i)!=Getbit(end,i)){ Filtbit(mid,i); Filtbit(mid,i+1); if(i<cnt-2) Filtbit(mid,i+2); result2++; } if(mid==end){ OutputResult(result2); break; } } } if(cnt==1){ result1 = 1; OutputResult(result1); } else if(mid!=end){ result1 = -1; OutputResult(result1); } return 0; }
这篇关于程序设计与算法二郭炜枚举001特殊密码锁的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么修改Kafka的JVM参数?-icode9专业技术文章分享
- 2024-12-23线下车企门店如何实现线上线下融合?
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转,哪款办公软件可助力风险评估?
- 2024-12-23优化库存,提升效率:医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担!轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘,为何是团队成长的核心环节?
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动:电商复盘从基础到进阶!
- 2024-12-23从数据到客户:跨境电商如何通过销售跟踪工具提升营销精准度?