约瑟夫问题I

[编程题]约瑟夫问题I

热度指数：10900 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知n个人坐成一圈，按顺时针由1开始给大家编号。然后由第一个人开始顺时针循环报数，数到m的人出局，循环此过程直到最后只剩一个人。给定两个int n和m，要求编写函数返回最后一个人的编号。保证n和m小于等于1000。

示例1

输入

5,3

输出

算法知识视频讲解

推荐

orgcheng

把n个人的编号改为0~n-1，然后对删除的过程进行分析。
第一个删除的数字是(m-1)%n，几位k，则剩余的编号为(0,1,...,k-1,k+1,...,n-1)，下次开始删除时，顺序为(k+1,...,n-1,0,1,...k-1)。
用f(n,m)表示从(0~n-1)开始删除后的最终结果。
用q(n-1,m)表示从(k+1,...,n-1,0,1,...k-1)开始删除后的最终结果。
则f(n,m)=q(n-1,m)。

下面把(k+1,...,n-1,0,1,...k-1)转换为(0~n-2)的形式，即
k+1对应0
k+2对于1
...
k-1对应n-2
转化函数设为p(x)=(x-k-1)%n, p(x)的你函数为p^(x)=(x+k+1)%n。
则f(n,m)=q(n-1,m)=p^(f(n-1,m))=(f(n-1,m)+k+1)%n，又因为k=(m-1)%n。
f(n,m)=(f(n-1,m)+m)%n;

最终的递推关系式为
f(1,m) = 0; (n=1)
f(n,m)=(f(n-1,m)+m)%n; （n>1）

代码如下

import java.util.*;

public class Joseph {
    /*
	 * 编号为(0~n-1)
	 */
    public int getResult(int n, int m) {
        if (n < 0 || m < 0) {
			return -1;
		}
		int last = 0;
		for(int i=2;i<=n;++i){
			last = (last+m)%i;
		}
		// 因为实际编号为(1~n)
		return (last+1);
    }
}

编辑于 2015-08-18 19:21:29 回复(11)

Java

钱三一

public int lastRemainingSolution(int n, int m) { boolean[] flagArray = new boolean[n];  if (n == 0 && m == 0) { return -1; } int index = 0;  for (int i = 0; i < n; i++) { int j = 0;  while (j < m) { if (index > n - 1) {
                index %= n;  } if (!flagArray[index]) { if (j == m - 1){
                    flagArray[index] = true; } if (i == n - 1){ return index;  }
             j++;  }
          index++;  }
    } return index; }

发表于 2019-06-18 18:38:05 回复(0)

Java

一神

/*
 * 使用链表真实模拟踢除过程即可
 */
import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 1; i <= n; i ++) {
            list.add(i);
        }
        
        int bt = 0;
        while (list.size() > 1) {
            int delPos = (bt + m - 1) % list.size();
            list.remove(delPos);
            bt = delPos % list.size();
        }
        
        return list.get(0);
    }
}

发表于 2017-04-01 10:22:26 回复(5)