本篇文章主要介绍了"IT公司100题-18-圆圈中最后剩下的数字"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：
问题描述：n个数字(下标为0, 1, …, n-1)形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字(当前数字从1开始计数)。当一个数字被删除后，从被...
问题描述：
n个数字(下标为0, 1, …, n-1)形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字(当前数字从1开始计数)。当一个数字被删除后，从被删除数字的下一个数字开始计数，继续删除第m个数字。求这个圆圈中剩下的最后一个数字。
分析：
这是有名的约瑟夫环问题。
最直接的方法：
使用链表来模拟整个删除过程。因为需要n个链表节点，所以空间复杂度为O(n)。每删除一个节点，都需要m次运算，所以时间复杂度为O(mn)。
实现代码如下所示：
package oschina.IT100;
import java.util.Scanner;
/**
* @project: oschina
* @filename: IT18.java
* @version: 0.10
* @author: JM Han
* @date: 21:59 2015/12/19
* @comment: josephus
* @result:
*/
public class IT18 {
private static class Node{
public int no;
public Node next;
public Node(int no){
this.no = no;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the whole number: ");
int total = sc.nextInt();
System.out.println("Enter the inter number: ");
int count = sc.nextInt();
Node header = new Node(1);
Node current = header;
for (int i = 2; i <= total; i++){
current.next = new Node(i);
current = current.next;
}
//cycle
current.next = header;
System.out.println("Below is the sequence of deletion: ");
while(current.next != current){
for (int i = 1; i < count; i++){
current = current.next;
}
System.out.println("delete node: " + current.next.no);
current.next = current.next.next;
}
System.out.println("The last node is: " + current.no);
}
}代码输出：
Enter the whole number:
10
Enter the inter number:
2
Below is the sequence of deletion:
delete node: 2
delete node: 4
delete node: 6
delete node: 8
delete node: 10
delete node: 3
delete node: 7
delete node: 1
delete node: 9
The last node is: 5
以上就介绍了IT公司100题-18-圆圈中最后剩下的数字，包括了方面的内容，希望对其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。
本文网址链接：http://www.codes51.com/article/detail_253148.html
