N人围圈,报数删除问题(约瑟夫问题)

时间:2022-10-05 11:00:59

这个问题算是比较经典的了吧,至少我刚学编程的时候就经常看到。最近又经常看到这个问题,就写了一下,算是怀旧的我老题重温吧,其实问题还是比较简单的。

问题描述:n 个人围成一圈报数,报到 m 的人出列,要求计算删除顺序,并找到最后剩下的那个人。

分析:问题的关键有两点

                 一是围成了一个圈,那么报数的时候就要考虑到循环遍历

                 二是被删除的人的表示问题:①如果是数组实现的话,那么就应该是对删除的人做标记,表示其已经被删除,否则你就需要每删除一个人,就要将所有后面的人的位置都向前挪一位;②如果是链表实现的话,那么你删除的时候直接删除表示该人的节点就好。

解答:下面的代码使用数组实现,比较简单。但是思路应该比较清晰了。

/**
 *  n人成圈问题
 * 详细描述:
 *      n 个人围成一圈报数,报到 m 的人出列,找到最后剩下的那个人。
 * 思路:
 *  先将所有人进行编号,如果被删除就将其编号设置为0。
 *  循环直到队列中只剩1个人
 */
#include <stdio.h>

int main(void) {
    int n;//总人数
    int m;//用来去除人的那个数
    int remain;//剩余人数

    int a[100]; //用来保存人
    int i;//循环临时变量

    //输入人数,并初始化数组
    printf("input the number of people:  ");
    scanf("%d",&n);
    for(i=0; i<n; i++)
        a[i]=i+1;

    //输出所有人
    printf("the index of people:  /n");
    for(i=0; i<n; i++)
        printf("%5d",a[i]);
    printf("/n/n");

    //输入要删除的数字号码
    printf("input the number you want to delete:  ");
    scanf("%d", &m);
    printf("/n");

    //依次删除,并打印删除过程
    remain=n;
    int count=0;//依次计数
    printf("the sequence to delete people:  /n");
    while(remain>1) {
        for(i=0; i<n; i++) {
            if(a[i]!=0) {
                count++;
                if(count == m) {
                    printf("%5d",a[i]);//打印被删除的人
                    a[i]=0;
                    count=0;
                    remain--;
                }
            }
        }
    }
    printf("/n/n");
    
    //打印最后剩下的人
    for(i=0; i<n; i++) {
        if(a[i]!=0) {
            printf("the last people:   %d/n",a[i]);
        }
    }
    return 0;
}

本文链接:http://blog.csdn.net/daheiantian/archive/2011/02/27/6452530.aspx