【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，
从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。
请返回游戏结束时最后一位成员的编号。
示例 1：
输入：num = 7, target = 4
输出：1
示例 2：
输入：num = 12, target = 5
输出：0
提示：
1 <= num <= 10^5
1 <= target <= 10^6

public int lastRemaining(int num, int target) {
    List<Integer> members = new ArrayList<>();
    for (int i = 0; i < num; i++) {
        members.add(i);
    }
    int index = 0;
    while (num > 1) {
        index = (index + target - 1) % num; // 减1因为从0开始计数，取余是因为是圆桌
        members.remove(index);
        num--;
    }
    return members.get(0);
}

#include <stdio.h>
#include <stdlib.h>
int lastRemaining(int num, int target) {
    // 创建一个动态数组来模拟成员围坐一圈的情况
    int *members = (int *)malloc(num * sizeof(int));
    
    // 初始化成员编号
    for (int i = 0; i < num; i++) {
        members[i] = i;
    }
    int current = 0; // 当前计数开始的位置
    int remaining = num; // 剩余成员数
    while (remaining > 1) {
        // 计算要移除成员的索引位置
        int removeIndex = (current + target - 1) % remaining;
        
        // 从数组中移除成员
        for (int j = removeIndex; j < remaining - 1; j++) {
            members[j] = members[j + 1];
        }
        // 更新当前计数开始的位置
        current = removeIndex % (remaining - 1);
        
        // 更新剩余成员数
        remaining--;
    }
    // 记录最后剩下的成员编号
    int lastMember = members[0];
    
    // 释放动态数组所占用的内存
    free(members);
    
    return lastMember;
}
// 测试程序
int main() {
    int num = 7, target = 4;
    printf("The last remaining member is: %d\n", lastRemaining(num, target));
    return 0;
}

def last_remaining(num, target):
    members = list(range(num))
    index = 0
    while num > 1:
        index = (index + target - 1) % num # 减1因为从0开始计数，取余是因为是圆桌
        members.pop(index)
        num -= 1
    return members[0]

public int lastRemaining(int num, int target) {
    int res = 0; // num=1时最后剩下的成员编号
    for (int i = 2; i <= num; i++) {
        res = (res + target) % i;
    }
    return res;
}

#include <stdio.h>
int lastRemaining(int num, int target) {
    int res = 0; // 最开始，编号为0的成员肯定会留下
    // 从第二位成员开始迭代，直到num位成员
    for(int i = 2; i <= num; i++) {
        res = (res + target) % i;
    }
    return res;
}
int main() {
    int num = 7, target = 4;
    printf("The last remaining member is: %d\n", lastRemaining(num, target));
    return 0;
}

def last_remaining(num, target):
    res = 0  # num=1时最后剩下的成员编号
    for i in range(2, num + 1):
        res = (res + target) % i
    return res

public int lastRemaining(int num, int target) {
    return lastRemainingRec(num, target);
}
private int lastRemainingRec(int num, int target) {
    if (num == 1) {
        // 只有一个成员时，他肯定是胜利者
        return 0;
    } else {
        // 递归计算 num-1 个成员时的胜利者的索引，并应用递归关系
        return (lastRemainingRec(num - 1, target) + target) % num;
    }
}

#include <stdio.h>
int lastRemainingRec(int num, int target) {
    if (num == 1) {
        // 只有一个成员时，他肯定是胜利者
        return 0;
    } else {
        // 递归计算 num-1 个成员时的胜利者的索引，并应用递归关系
        return (lastRemainingRec(num - 1, target) + target) % num;
    }
}
int lastRemaining(int num, int target) {
    return lastRemainingRec(num, target);
}
int main() {
    int num = 7, target = 4;
    printf("The last remaining member is: %d\n", lastRemaining(num, target));
    return 0;
}

def last_remaining_rec(num, target):
    if num == 1:
        # 只有一个成员时，他肯定是胜利者
        return 0
    else:
        # 递归计算 num-1 个成员时的胜利者的索引，并应用递归关系
        return (last_remaining_rec(num - 1, target) + target) % num
def last_remaining(num, target):
    return last_remaining_rec(num, target)
# 示例
print(last_remaining(7, 4))  # 输出: 1
print(last_remaining(12, 5)) # 输出: 0