Hello~这是我的新专辑！这个专辑中是竞赛真题，所有真题的解将会用Python、C++、C、Java、JS和Go几种语言给大家实现！现在，开始我们的第一个竞赛题目：约瑟夫环
目录
题目内容：
题目分析：
题目思路：
Python代码：
C++代码：
C代码：
Java代码：
JS代码：
Go代码：
题目内容：
n个人站成一个环，分别有编号1~n。从编号为1的人开始报数，每报道m的人将会淘汰。每淘汰一个人后面的一个人再从1报起。求最后一个人的编号是多少？
题目分析：
结合生活实际，这n个人站成一个环，我们也可以把这n个人排成一个队伍。每报道m的人就出队，没报道m的人就再次回到队尾，直到队伍中只有一个人为止。大家都发现了，这不就是队列吗？这样的话不就简单了吗？
题目思路：
（下面假设所有人的编号都在一个数组A中）我们可以利用while循环来帮我们解决问题。如果我们只想获取最后一个人的编号的话，那判断条件就是数组的长度不为1（反过来说就是直到数组长度为1为止），然后再定义一个变量cnt，用来记录现在报道的数字。在循环中判断cnt变量是否等于m，如果等于，则将A[cnt-1]删除，并且重置cnt为1。如果不等于，则cnt自增1。
Python代码：
AC代码
from collections import deque
n, m = map(int, input().split())
q = deque(range(1, n + 1))
cnt = 1
while len(q) > 1:
x = q.popleft()
if cnt != m:
q.append(x)
cnt += 1
else:
cnt = 1
print(q[0])
C++代码：
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<int> q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
q.push(i);
}
int cnt = 1;
while(q.size()>1)
{
int x = q.front();
q.pop();
if(cnt!=m){
q.push(x);
cnt++;
}
else
{
cnt = 1;
}
}
cout<<q.front();
}
C代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
} Node;
typedef struct Queue {
Node* head;
Node* tail;
int size;
} Queue;
void init(Queue* q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
void enqueue(Queue* q, int value) {
Node* new_node = (Node*) malloc(sizeof(Node));
new_node->value = value;
new_node->next = NULL;
if (q->tail == NULL) {
q->head = new_node;
} else {
q->tail->next = new_node;
}
q->tail = new_node;
q->size++;
}
int dequeue(Queue* q) {
if (q->size == 0) {
printf("Error: queue is empty!\n");
exit(1);
}
int value = q->head->value;
Node* temp = q->head;
q->head = q->head->next;
free(temp);
q->size--;
if (q->size == 0) {
q->tail = NULL;
}
return value;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
Queue q;
init(&q);
for (int i = 1; i <= n; i++) {
enqueue(&q, i);
}
int cnt = 1;
while (q.size > 1) {
int x = dequeue(&q);
if (cnt != m) {
enqueue(&q, x);
cnt++;
} else {
cnt = 1;
}
}
printf("%d", q.head->value);
return 0;
}
Java代码：
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
queue.offer(i);
}
int cnt = 1;
while (queue.size() > 1) {
int x = queue.poll();
if (cnt != m) {
queue.offer(x);
cnt++;
} else {
cnt = 1;
}
}
System.out.println(queue.poll());
}
}
JS代码：
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n, m;
let queue = [];
let cnt = 1;
rl.on('line', (line) => {
if (!n) {
[n, m] = line.trim().split(' ').map(Number);
queue = Array.from({length: n}, (_, i) => i + 1);
} else {
const x = queue.shift();
if (cnt !== m) {
queue.push(x);
cnt++;
} else {
cnt = 1;
}
if (queue.length === 1) {
console.log(queue[0]);
rl.close();
}
}
});
Go代码：
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
reader := bufio.NewReader(os.Stdin)
line, _ := reader.ReadString('\n')
line = strings.TrimRight(line, "\n")
params := strings.Split(line, " ")
n, _ := strconv.Atoi(params[0])
m, _ := strconv.Atoi(params[1])
queue := make([]int, n)
for i := 0; i < n; i++ {
queue[i] = i + 1
}
cnt := 1
for len(queue) > 1 {
x := queue[0]
queue = queue[1:]
if cnt != m {
queue = append(queue, x)
cnt++
} else {
cnt = 1
}
}
fmt.Println(queue[0])
}
上面就是我带给大家的代码，谢谢大家！
