首页 > 代码库 > 约瑟夫问题

约瑟夫问题

2024-07-18 02:32:04   221人阅读

原题

N个人围成一个圆圈，首先第一个人从1开始一个人一个人顺时针报数，报道第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…如此下去，直到圈中只剩下一个人为止。此人即为优胜者。写一个函数求N个人中的胜者。

我的思路

可以使用一数组，来存放标记为1,2,3,…,N的N个人，每当有人出列，对应数组元素置为0，下次报数遇到置0的数组元素直接跳过。

实现代码

/*************************************************************************    > File Name: testmain.c    > Author: KrisChou    > Mail:zhoujx0219@163.com     > Created Time: Sun 17 Aug 2014 10:50:53 PM CST ************************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>int find(int *arr,int m, int n);int main(int argc, char *argv[]){    int M,N;    int *arr;    int index;    printf("please input M and N: ");    fflush(stdout);    scanf("%d%d",&M,&N);    /* 动态分配数组，存放N个人 */    arr = (int*)calloc(N,sizeof(int));    for(index = 0; index < N; index++)    {        arr[index] = index + 1;    }    /* 返回胜者 */    printf("winner : %d\n",find(arr,M,N));        free(arr);    arr = NULL;        return 0;}int find(int *arr,int m, int n){    int len = n;    int index;   //数组下标    int step;    //报数索引    index = step = 0;    while(len > 1)    {        if(arr[index] != 0)        {            ++step;            if(step == m)            {                arr[index] = 0;                step = 0;                len--;            }        }        index = (index + 1) % n;    }    /* 寻找出已经存在的winner，并返回 */    for(index = 0;index < n; index++)    {        if(arr[index] != 0)        {            return arr[index];        }    }}


联系
我们