狱卒问题

一、问题描述

  某王国对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次按所定规则转动门锁，每转动一次，原来锁着的被打开，原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的?

二、问题解析

从第k间开始转动，每隔k-1 间转动一次

  采用暴力枚举法，每种情况都进行遍历一遍。即第K次遍历，将第K间房锁/开一次，依次对+K间房进行锁/开**操作，一旦超过N则进行下一波遍历。

三、代码示例

//暴力枚举法
    void JailerProlem(int n) {
        int *prisoner = new int[n+1] {0};//0代表锁上 1代表开锁(从1开始计数)
        for (int i = 1; i <= n; i++) {//n次转动
            for (int k = i; k <= n; k=k+i) {//逐门转动
                prisoner[k] = prisoner[k] == 0 ? 1 : 0;
            }
        }
        //输出最后结果
        for (int j = 1; j <= n; j++) {//n次转动
            if (prisoner[j] == 1) {
                cout << "第" << j << "号囚犯获得自由" << endl;
            }
        }

结果：（默认输入16）