首页 > 代码库 > 喝醉的狱卒

喝醉的狱卒

在一所监狱里有一条长长的走廊,沿着走廊排列着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;
 } 
View Code

解法二:

#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;
  } 

 

喝醉的狱卒