笔试题2-约瑟夫问题：n个数字形成的圆圈中循环删除第m个数字

2020年2月24日找工作过程中的笔试题之一

题目描述

n个数字（1, 2, … , n）形成一个圆圈。从数字1开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。

思路

• 思路1 个人笔试时候的做法，把问题复杂化了感觉
  (1) 用循环队列，初始化队列元素的值为n个连续的数
  (2) 循环报数，用累加器来辅助找到每次需要被删除的元素
  (3) 每次有人被淘汰，先把这个数删除掉，队列的长度减1
  (4) 当循环队列长度为1的时候，输出仅存的这个数
  (5) 用数组模拟循环队列 or 用链表模拟

思路2 后来网上查阅到的容易理解的做法
先构建递推公式，再使用循环或者递归都能轻松求解。
这个问题的其实就是约瑟夫问题的小变形，数据范围由约瑟夫问题的0到N-1，变为了 1 到 N
由于我们要求解的是n个元素，第m个数字，要找到最后留下的一个数字，那么我在这里假设得到的结果是f(n,m),
根据“左加右减”的数学原理和环形的特征，得到递推公式：
{ 0 ，n = 1
f(n,m)= {
{ (f(n-1,m) + m)%n ，n > 1

根据这个来调整代码，就可以得到数据范围是1 到 N ， 目标值是M的答案

代码

思路1代码

public class Joseph {
	public int getResult(int n, int m) {
		if (m == 1) {	// m 是 1，直接返回n 就行了，不需要多跑程序
			return n;
		}
		ListNode head = new ListNode(1);
		ListNode p = head;
		int counts = 1; // 创建用的计数器
		while (counts < n) {
			// 尾插法创建单链表
			ListNode q = new ListNode(counts + 1);
			q.next = p.next;
			p.next = q;
			p = p.next;
			counts ++;
		}
		// 使单链表变为循环链表
		p.next = head;

		int count = 0; // 删除用的计数器
		ListNode del = head;
		while (del.next != del) { // 使其一直遍历、计数、删除
			count++;
			System.out.println(del.val + " " + count);
			if (count == m) {
				// 删除这个结点
				del.val = del.next.val;
				del.next = del.next.next;
				count = 1; // 计数器清零
			}
			del = del.next;
		}
		return del.val;
    }
}

思路2代码

public class Jpseph2 {
	public int getResult(int n, int m) {
        int fn = 1;
        for (int i = 2; i <= n; i++) {
        	fn = (fn + m - 1) % i;
        }
		return fn;
    }
}

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/491299a6.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。