約瑟夫環數組解法——C語言實作

約瑟夫環

​ 1、一群人圍在一起坐成環狀（如：N）

​ 2、從某個編号開始報數（如：K）

​ 3、數到某個數（如：M）的時候，此人出列，他的下一個人又從1開始報數，數到M的那個人又出列

​ 4、一直循環，直到所有人出列，約瑟夫環結束

​ 提示：N個人，其編号從1到N，存儲在數組元素a中。從a[0]開始報數，數到M的數組元素a[i],存儲到b[j++]中，然後把a[i]标記為0或-1,表示已經出列，下次要跳過。當走到數組末尾a[N-1]是，再從頭開始接着報數（模拟成一圈）。當所有元素都标記為0時，表示都出列了，列印數組b的值，即為結果。

#include <stdio.h>

#define ARRLEN 20


void josephRing(int n,int k, int m)
{
    int a[ARRLEN] = {0};
    int b[ARRLEN] = {0};
    int subscript = 0;
    int surviveNum = n;
    int count = 1;
    int i =0;
    //從M開始數到N
    for(i = (k-1); i <= n; i++)
    {
        (i==n)?(i=0):1;
        //判斷這個數是否出列
        if(a[i] == -1){
            continue;
        }
        else{
             //判斷是否數到m
            if (count == m)
            {
                printf("(%d,%d)出列\t", (i+1), count);
                surviveNum--;
                a[i] = -1;
                b[subscript++] = a[i];
                count = 1;
            }
            else{
                printf("(%d,%d)\t", (i+1), count++);
            }
            
        }

        if (surviveNum == 1)
        {
            break;
        }
            
    }
    putchar('\n');
    printf("最後的赢家是：%d\n",(i));
    

}
int main(int argc, char const *argv[])
{
    int n, k, m;
    printf("請輸入人數：");
    scanf("%d%*c",&n);
    putchar('\n');

    printf("請輸入從哪個編号開始：");
    scanf("%d%*c",&k);
    putchar('\n');   

    printf("請輸入數到哪個數出列：");
    scanf("%d%*c",&m);
    putchar('\n');   

    josephRing(n,k,m);
    return 0;
}


           

運作結果：

請輸入人數：10

請輸入從哪個編号開始：3

請輸入數到哪個數出列：5

(3,1)   (4,2)   (5,3)   (6,4)   (7,5)出列       (8,1)   (9,2)   (10,3)  (1,4)   (2,5)出列       (3,1)    (4,2)   (5,3)   (6,4)   (8,5)出列       (9,1)   (10,2)  (1,3)   (3,4)   (4,5)出列       (5,1)    (6,2)   (9,3)   (10,4)  (1,5)出列       (3,1)   (5,2)   (6,3)   (9,4)   (10,5)出列      (3,1)    (5,2)   (6,3)   (9,4)   (3,5)出列       (5,1)   (6,2)   (9,3)   (5,4)   (6,5)出列       (9,1)    (5,2)   (9,3)   (5,4)   (9,5)出列
最後的赢家是：8