猴子选大王(顺序表)

逃离我推掉我的手 2023-01-13 04:15 111阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70][]

\[程序代码\]

#include<stdio.h>
    #include<stdlib.h>
    
    /* 函数原型 */
    void Init(struct monkey *p, unsigned long n);
    unsigned long Game(struct monkey *p, unsigned long k, unsigned long n);
    void show(struct monkey *p, unsigned long num);
    
    /* 记录每只猴子的信息 */
    struct monkey
    {
        /* 猴子的编号 */
        unsigned long number;
        /* judge == 1: 猴子还在圈中 */
        /* judge == 0: 猴子已经出圈 */
        char judge;
    };
    
    int main()
    {
        /* 猴子数量 */
        long num;
        /* 数到k的猴子出圈 */
        long k;
        /* 增加输入容错机制 */
        while(scanf("%ld%ld", &num, &k) != 2 || num < 1 || k < 1)
        {
            while(getchar() != '\n') ;
        }
        /* 开辟猴子数组空间 */
        struct monkey *p = (struct monkey* )malloc(num * sizeof(struct monkey));
        /* 注意开辟连续存储空间必须在主函数中进行 */
        /* 如果在主函数中只是声明指针变量p, 而在Init函数中开辟连续存储空间, 程序将无法正常执行 */
        /* 初始化猴子数组 */
        Init(p, num);
        /* 输出猴子的信息 */
        /* show(p, num); */
        /* 开始猴子出圈游戏 */
        printf("%lu\n", Game(p, k, num));
        /* */
        return 0;
    }
    
    /* 初始化猴子数组, n为猴子的数量 */
    void Init(struct monkey *p, unsigned long n)
    {
        unsigned long i = 0;
        while(i < n)
        {
            (p + i) -> number = i + 1;
            (p + i) -> judge = 1;
            i ++;
        }
        /* printf("初始化成功.\n"); */
    }
    
    /* 输出所有猴子的信息, num为猴子的数量 */
    void show(struct monkey *p, unsigned long num)
    {
        unsigned long i = 0;
        printf("猴子编号  是否在圈内\n");
        while(i < num)
        {
            printf("%5lu           %d\n", (p + i) -> number, (p + i) -> judge);
            i ++;
        }
    }
    
    /* 数到k的猴子出圈, 确定圈中所剩的最后一只猴子的编号 */
    /* n为游戏开始前圈内猴子的数量 */
    unsigned long Game(struct monkey *p, unsigned long k, unsigned long n)
    {
        unsigned long i = 1;
        unsigned long m = n;
        struct monkey *q = p;
        while(n > 1)
        {
            //printf("1 ");
            /* 只要圈中还有2只猴子及以上, 游戏就继续下去 */
            if(q -> judge == 0)
            {
                /* 当前q指针所指猴子已经出圈 */
                 /* 猴子指针后移 */
                if(q - p == m - 1)
                {
                    /* 当前猴子已是最后一只, 下次应从表头开始 */
                    q = p;
                }
                else
                {
                    /* 当前猴子不是最后一只, q指针后移即可 */
                    q ++;
                }
                continue;
            }
            /* */
            if(i == k)
            {
                /* 当前q指针所指猴子出圈 */
                q -> judge = 0;
                /* 猴子数量-1 */
                n --;
                /* 报数值重新置1, 为下只猴子报数做准备 */
                i = 1;
            }
            else
            {
                /* 报数值+1, 为下只猴子报数做准备 */
                i ++;
            }
            /* 猴子指针后移 */
            if(q - p == m - 1)
            {
                /* 当前猴子已是最后一只, 下次应从表头开始 */
                q = p;
            }
            else
            {
                /* 当前猴子不是最后一只, q指针后移即可 */
                q ++;
            }
        }
        /* 寻找圈内所剩的最后一只猴子 */
        q = p;
        while(1)
        {
            if(q -> judge == 1)
            {
                return q -> number;
            }
            q ++;
        }
    }

\[运行结果\]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70]: /images/20221022/d46ec9f6af1e43d08778a722c1a21efa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1]: /images/20221022/ba7d0bf147354335970d6b6bd9c91139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 2]: /images/20221022/5cadac5c5b4f4fbfad9e2d78a1220e6f.png