n个猴子围成一圈，从编号为k的开始报数1-2-m-1-2-m-……报“m”的猴子就被淘汰，游戏一直进行到圈内只剩一只猴子它就是猴大王了。 想了很长时间不会,问了@Spider-gty，得知用两个一维数组模拟圈可以解决，下面是代码：
class MonkeyProblem { public static void main(String[] args) { int k=17; int[] last=new int[k+1]; int[] next=new int[k+1]; last[1]=k;next[1]=2; last[k]=k-1;next[k]=1; for(int i=2;i<=k-1;i++) { last[i]=i-1; next[i]=i+1; } int result=solve(last,next,1,10); System.out.println(result); } // Find the correct monkey; //模拟报数过程 static int count(int[] l,int[] n,int k,int m) //l是上一个，n是下一个，k是某位置开始，m是往下数多少位 { if(m==1) return k; k=n[k]; return count(l,n,k,m-1); } //模拟淘汰过程，opted指被选中报到m的猴子 static void eliminate(int[] l,int[] n,int opted) { n[l[opted]]=n[opted]; l[n[opted]]=l[opted]; } static int solve(int[] l,int[] n,int k ,int m) { if(n[k]==k) return k; int opted=count(l,n,k,m); eliminate(l,n,opted); int next=n[opted]; return solve(l,n,next,m); } }··························································································· 事实上，过多的使用递归会影响程序的性能；按照这个思路，程序可以简化。 C++版本:
#include <iostream> void initialize(int *last, int *next, int length); int solve(int *, int *, int &, int &); int main() { std::cout<<"输入猴子的数量:"<<std::endl; int monkey_mount; std::cin>>monkey_mount; int ls[monkey_mount]; int nt[monkey_mount]; initialize(ls, nt, monkey_mount); int startMonkey = 0; int epoch_length = 8; std::cout << solve(ls, nt, startMonkey, epoch_length) << std::endl; return 0; } void initialize(int *last, int *next, int length) { for (int i = 1; i < length - 1; ++i) { last[i] = i - 1; next[i] = i + 1; } last[0] = length - 1; next[0] = 1; last[length - 1] = length - 2; next[length - 1] = 0; } int solve(int *last, int *next, int &startMonkey, int &epoch_length) { int monkey = startMonkey; while (next[monkey] != monkey) { for (int i = 1; i < epoch_length; i++) monkey = next[monkey]; next[last[monkey]] = next[monkey]; last[next[monkey]] = last[monkey]; printf("本轮淘汰第%d个猴\n", monkey); monkey = next[monkey]; } return monkey; }node版本
const readline = require('readline').createInterface({ input: process.stdin, output: process.stdout }) readline.question("输入猴子的数量\n", answer => { let next = []; let last = []; initialize(last, next, answer) console.log(`最终的猴子王是${solve(last, next, 0, answer)}`) }) function initialize(last, next, length) { for (let i = 1; i < length - 1; i++) { last[i] = i - 1; next[i] = i + 1; } last[0] = length - 1; next[0] = 1; last[length - 1] = length - 2; next[length - 1] = 0; } function solve(last, next, startMonkey, epoch_length) { let monkey = startMonkey; while (next[monkey] !== monkey) { for (let i = 1; i < epoch_length; i++) monkey = next[monkey]; next[last[monkey]] = next[monkey]; last[next[monkey]] = last[monkey]; console.log(`本轮淘汰第${monkey}个猴子`) monkey = next[monkey]; } return monkey; }Go语言版:
package main import ( "bufio" "fmt" "os" "strconv" ) func main() { fmt.Printf("输入猴子的数量:\n") scanner := bufio.NewScanner(os.Stdin) scanner.Scan() monkeyMount, _ := strconv.Atoi(scanner.Text()) fmt.Printf("输入起始猴子的位置(从0开始):\n") scanner.Scan() startMonkey, _ := strconv.Atoi(scanner.Text()) fmt.Printf("输入猴子数数的步长:\n") scanner.Scan() epochStep, _ := strconv.Atoi(scanner.Text()) last := make([]int, monkeyMount, monkeyMount) next := make([]int, monkeyMount, monkeyMount) initialize(last, next, monkeyMount) fmt.Printf("最终的猴子王是%d", solve(last, next, startMonkey, epochStep)) } func initialize(last []int, next []int, length int) { for i := 1; i < length-1; i++ { last[i] = i - 1 next[i] = i + 1 } last[0] = length - 1 next[0] = 1 last[length-1] = length - 2 next[length-1] = 0 } func solve(last []int, next []int, startMonkey int, epochLength int) int { monkey := startMonkey for monkey != next[monkey] { for i := 1; i < epochLength; i++ { monkey = next[monkey] } next[last[monkey]] = next[monkey] last[next[monkey]] = last[monkey] fmt.Printf("本轮淘汰第%d个猴子\n", monkey) monkey = next[monkey] } return monkey }最简单是当然是kotlin
package com.wang.binarySearch import java.util.* fun main() { val scanner = Scanner(System.`in`) println("猴子的数量为:") val monkeyMount = scanner.nextInt() println("猴子开始数数位置为:") val startMonkey = scanner.nextInt() println("猴子数数的步长是:") val countStep = scanner.nextInt() val last = Array(monkeyMount) { i: Int -> if (i == 0) monkeyMount - 1 else i - 1 } val next = Array(monkeyMount) { i: Int -> if (i == monkeyMount - 1) 0 else i + 1 } println("猴子王是:${solve(last, next, startMonkey, countStep)}") } fun solve(last: Array<Int>, next: Array<Int>, startMonkey: Int, epochLength: Int): Int { var monkey = startMonkey while (monkey != next[monkey]) { repeat(epochLength - 1) { monkey = next[monkey] } last[next[monkey]] = last[monkey] next[last[monkey]] = next[monkey] println("本轮淘汰第 $monkey 个猴子") monkey = next[monkey] } return monkey }