蛮力法求解“狱吏问题”

浅浅的花香味﹌ 2022-05-28 06:59 215阅读 0赞

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

--------------------

源代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int n = 0;
        int i = 0;
        int j = 0;
        int* p = NULL;
    
        scanf("%d", &n);
        //开辟存储空间
        p = (int *)calloc(n + 1, sizeof(int));     
        for (i = 1; i <= n; i++)
        {
        //将锁的状态初始化为关闭，1表示锁上，0表示打开
            p[i] = 1;
        }
        //i表示通过牢房的次数,j表示要转动的锁的编号
        for (i = 1; i <= n; i++)
        {
            for (j = i; j <= n; j += i)
            {
                //切换锁的状态
                p[j] = 1 - p[j];
            }
        }
    
        for (i = 1; i <= n; i++)
        {
            if (p[i] == 0)
            {
                printf("%d is free \n", i);
            }
        }
    
        free(p);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关算法设计与分析：蛮力法

算法分析与设计实验报告第四次实验姓名裴朵朵学号 5001170016 班级计科一班时间 2019.10.31 地点实验名称暴力法的使用实

朴灿烈づ我的快乐病毒、/ 2023年06月12日 09:46/ 0 赞/ 12 阅读

相关蛮力法之最近对问题（C实现）

include <stdio.h> include <math.h> / 我们可以避免求平方根，窍门是忽略平方根函数，而只比较(x

Dear 丶/ 2022年08月10日 00:58/ 0 赞/ 165 阅读

相关蛮力法之冒泡排序（C实现）

include <stdio.h> void DataSwap(int data1, int data2) {

短命女/ 2022年08月10日 00:55/ 0 赞/ 187 阅读

相关用蛮力法解决冒泡排序

冒泡排序是蛮力法的另一个经典体现。算法思想：比较列表中相邻的元素，如果是逆序的话，就交换他们的位置。重复多次之后，最大的元素就排到了最后一个位置。第二遍操作将第二个元素排到

秒速五厘米/ 2022年06月04日 05:44/ 0 赞/ 189 阅读

相关蛮力法求解“狱吏问题”

> 问题描述：狱吏问题；某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次按所定规则转动n间牢房中的某些门锁，每转动一次原来锁着的被打开，原来打

浅浅的花香味﹌/ 2022年05月28日 06:59/ 0 赞/ 216 阅读

相关使用蛮力法求解数字迷问题（类似ABCAB*A = DDDDDD）

蛮力法概述 > 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述>和所涉及的概念定义。是基于计算机运算速度快这一特性，在解决问题时采用的一种“懒惰”的策略。把

朱雀/ 2022年05月28日 04:59/ 1 赞/ 633 阅读

相关 0/1背包问题（蛮力法）

问题描述：给定n个重量为\{w1,w2,w3,....,wn\}、价值为\{v1,v2,v3,...,vn\}的物品和一个容量为C的背包，0/1背包问题是求解这些物品中

朴灿烈づ我的快乐病毒、/ 2022年04月16日 05:05/ 0 赞/ 314 阅读

相关排序问题（蛮力法，分治法）

蛮力法：选择排序法：算法思想：在剩余序列中选出最小（或最大）的关键字，和剩余序列的第一个关键字交换位置，依次选择下去（每次扫描结束找出最小的一个元素依次放在前面的位

布满荆棘的人生/ 2022年04月16日 04:59/ 0 赞/ 236 阅读

相关蛮力法（Java）

> 暴力算法理论上十分容易理解，就是将问题可能出现的所有答案都列举出来，然后与条件对比，符合条件的解即为正解。下面我们列举几道例题。 > 1-1 数谜问题 > ABC

末蓝、/ 2022年03月11日 09:56/ 0 赞/ 215 阅读

相关 python动态演示蛮力法解决凸包问题

最近开了算法课，但是我的算法着实不咋地，一直搞web和逆向，就没怎么编程。记录一下0.0 算法倒是不难实现，但是这个动态演示很烦，从纯粹的可视化小白，强行写完了，写完发现非常

爱被打了一巴掌/ 2021年10月01日 06:58/ 0 赞/ 268 阅读