PTA约瑟夫环之位标记

PTA约瑟夫环问题是一个经典的数学问题，由于它的应用广泛，因此在面试中也经常被提到。其问题描述为：已知n个人（用编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出圈；他的下一个人又从1开始报数，数到m的那个人又出圈；依此规律重复下去，直到圆桌周围的人全部出圈。

PTA约瑟夫环之位标记，指的是一个数组标记，用来记录每个人是否出圈。在具体实现上，我们可以用一个布尔类型的数组，将所有元素初始化为false表示未出圈，当某个人出圈时将其对应位置设为true。这样就可以避免重复报数和统计剩余人数时的错误。

相关问题

pta约瑟夫问题

PTA约瑟夫问题是一个经典的数学问题，假设有n个人围成一圈，从第1个人开始报数，报到m的人出圈，下一个人重新从1开始报数，直到所有人出圈为止。问最后剩下的人在原来的编号中是第几个。

具体的解题思路可以使用环形链表模拟这个过程，每次找到要出圈的人并将其从链表中移除，然后重新从下一个人开始继续报数。最后留下的那个人就是最终的答案。

以下是一个使用Python实现的示例代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


def josephus(n, m):
    head = Node(1)
    last = head
    for i in range(2, n+1):
        new_node = Node(i)
        last.next = new_node
        last = new_node
    last.next = head

    p = last
    for i in range(n):
        for j in range(m-1):
            p = p.next
        print("出圈：", p.next.data)
        p.next = p.next.next
    print("最后留下的人：", p.data)


n = 5
m = 3
josephus(n, m)

输出结果为：

出圈： 3
出圈： 1
出圈： 5
出圈： 2
最后留下的人： 4

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);