首页 > 代码库 > 喝醉的狱卒
喝醉的狱卒
在一所监狱里有一条长长的走廊,沿着走廊排列着n个牢房,编号为1到n。每个牢房有一个囚犯,而且牢房的门都是锁着的。
一天晚上,狱卒很无聊,于是他就玩起了一个人的游戏。第一轮,他喝了一口威士忌,然后沿着走廊,将所有牢房的门打开。第二轮,他又喝了一口威士忌,然后又沿着走廊,将所有编号为2的倍数的牢房锁上。第三轮,他再喝一口威士忌,再沿着走廊,视察所有编号为3的倍数的牢房,如果牢房是锁着的,他就把它打开;如果牢房是开着的,他就把它锁上。他如此玩了n轮后,喝下最后一口威士忌,醉倒了。
当他醉倒后,一些犯人发现他们的牢房开着而且狱卒已经无能为力,他们立刻逃跑了。
给出牢房的数目n,请你确认最多有可能有多少犯人逃出了监狱?
Input 仅一行,为一个正整数n,n<=10000。
Output 仅一行,一个整数,为最多逃跑的犯人数
解法一:
#include<iostream> using namespace std; int main() { //1 代表打开 ;0代表关闭 int a[10000],i,j,n,m=0; cin>>n; for(i=0;i<n;i++) a[i]=0; //开始牢房的们是关闭的 for(j=1;j<=n;j++)//表示第几轮 { for(i=j-1;i<n;i=i+j)//第几轮加几 所以这儿加j 相当于倍数 a[i]=a[i]+1; } for(i=0;i<n;i++) if(a[i]%2!=0) //如果经过N轮之后 a[i]为奇数则此时是打开的(因为开始是关闭的) m=m+1; //如果是偶数,说明牢门经过开关 正好是偶数次,此时为关闭。 cout<<m<<endl; }
解法二:
#include<iostream> using namespace std; int main() { //1 代表打开 ;0代表关闭 int value[10000]; int n; cin>>n; for(int i=0;i<n;i++) value[i]=0; int k; for(int i=1;i<=n;i++)//轮次 从1开始 { for(int j=1;j<=n;j++) //牢房编号 if(j%i==0)//如果牢房编号正好整除轮次,开始操作 锁着的话打开,开着的话锁着 { if(value[j]==1) value[j]=0; else value[j]=1; } } int m=0; for(int j=0;j<n;j++) { if(value[j]==1)//然后统计元素为1的个数 m++; } cout<<m<<endl; return 0; }
喝醉的狱卒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。