pta约瑟夫问题c语言

在C语言中，约瑟夫环（Josephus Problem）是一个经典的算法问题，源于古罗马时期的游戏。游戏规则是这样的：一群人按照顺序站立，从第一个人开始报数，每次跳过k个人，直到剩下最后一个人为止。问题是确定最后一个存活的人的编号。

在C语言中解决这个问题通常采用循环和条件判断的方式。你可以创建一个数组表示人员，并通过计数器逐个淘汰。下面是一个简单的实现步骤：

1. 定义数组大小和初始步长k。
2. 初始化数组、计数器和生存者变量。
3. 使用while循环，当数组只剩下一个元素时跳出循环。
4. 更新计数器并删除指定位置的元素，除非它是生存者，那么计数器加到下一个元素的位置。
5. 循环结束后，生存者的索引即为答案。

#include <stdio.h>

int josephus(int n, int k) {
    int arr[n], current = 0, survivor;
    
    // 将数组初始化为从1开始的序列
    for (int i = 1; i <= n; ++i) {
        arr[i] = i;
    }

    while (n > 1) {
        current += k; // 移动指针
        if (current > n) { // 越界处理
            current %= n;
        }
        n -= 1; // 减少人数
        survivor = arr[current]; // 记录当前生存者
        arr[current] = arr[n]; // 删除当前人，将下一个移动到当前位置
    }
    
    return survivor;
}

int main() {
    int n, k;
    printf("请输入人数和跳过的人数：");
    scanf("%d %d", &n, &k);
    int lastMan = josephus(n, k);
    printf("最后幸存的是第%d位\n", lastMan);