约瑟夫环的3种java实现版本

星期三, 2011-12-07 | Author: Lee | JAVA-and-J2EE | 6,489 views

约瑟夫环即:
由m个人围成一个首尾相连的圈报数。从第一个人开始,从1开始报数,报到n的人出圈,剩下的人继续从1开始报数,直到所有的人都出圈为止。对于给定的m和n,求出所有人的出圈顺序.

实现代码如下,(3百万的寻找)对比的时间一目了然,性能依次走低,最后一种和前面两个差了1个数量级,时间还最长

getSeByNode 耗时 :1039
getSe 耗时 :3397
se 耗时 :38388

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package com.liyz.test.se;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Se {
	public static void main(String[] args) {
		long now = System.currentTimeMillis();
		getSeByNode(3000000, 3);
		long now1 = System.currentTimeMillis();
		System.out.println("getSeByNode 耗时 :" + (now1 - now));
 
		long now2 = System.currentTimeMillis();
		getSe(3000000, 3);
		long now3 = System.currentTimeMillis();
		System.out.println("getSe 耗时 :" + (now3 - now2));
 
		long now4 = System.currentTimeMillis();
		se(300000, 3);
		long now5 = System.currentTimeMillis();
		System.out.println("se 耗时 :" + (now5 - now4));
 
	}
 
	public static void getSeByNode(int totalNum, int cycleNum) {
		// Scanner scanner = new Scanner(System.in);
		// System.out.print("请输入总人数:");
		// int totalNum = scanner.nextInt();
		// System.out.print("请输入报数的大小:");
		// int cycleNum = scanner.nextInt();
		Node header = new Node(1);
		Node pointer = header;
		for (int i = 2; i <= totalNum; i++) {
			pointer.next = new Node(i);
			pointer = pointer.next;
		}
		pointer.next = header;
		// 初始化环形链表结束
		// System.out.println("以下是出列的顺序:");
		while (pointer != pointer.next) {
			for (int i = 1; i < cycleNum; i++) {
				pointer = pointer.next;
			}
			// System.out.print(pointer.next.no+"  ");
			pointer.next = pointer.next.next;
		}
		// System.out.print(pointer.next.no);
		// System.out.println();
	}
 
	public static void getSe(int m, int n) {
		// System.out.println("程序说明如下:");
		// System.out
		// .println("由m个人围成一个首尾相连的圈报数。从第一个人开始,从1开始报数,报到n的人出圈,剩下的人继续从1开始报数,直到所有的人都出圈为止。对于给定的m和n,求出所有人的出圈顺序.");
		//
		// // 提示输入总人数
		// System.out.println("请输入做这个游戏的总人数:");
		// Scanner sca = new Scanner(System.in);
		// int m = sca.nextInt();
		// // 提示输入要出圈的数值
		// System.out.println("请输入要出圈的数值:");
		// int n = sca.nextInt();
		// System.out.println("按出圈的次序输出序号:");
		// 创建有m个值的数组
		int[] a = new int[m];
		// 初始长度,以后出圈一个,长度就减一
		int len = m;
		// 给数组赋值
		for (int i = 0; i < a.length; i++)
			a[i] = i + 1;
		// i为元素下表,j代表当前要报的数
		int i = 0;
		int j = 1;
		int size = 0;
		// StringBuffer sb = new StringBuffer();
		while (len > 0) {
			if (a[i % m] > 0) {
				if (j % n == 0) {// 找到要出圈的人,并把圈中人数减一
					// System.out.print(a[i%m]+"  ");
					// sb.append(a[i % m] + " ");
					a[i % m] = -1;
					j = 1;
					i++;
					len--;
				} else {
					i++;
					j++;
				}
			} else {// 遇到空位了,就跳到下一位,但j不加一,也就是这个位置没有报数
				i++;
			}
			size++;
		}
		// System.out.println(sb.toString());
		// System.out.println(" total size:" + size);
	}
 
	public static String se(int maxNum, int cycNum) {
		List<Integer> people = new ArrayList<Integer>();
		for (int i = 1; i <= maxNum; i++) {
			people.add(i);
		}
 
		int say = 1; // 报数
		int on = 1;
		while (people.size() != 1) {
			// 报数大过现有人数跳转到第一个
			if (on - people.size() == 1) {
				on = 1;
			}
 
			// 当报数为3时删除
			if (say == cycNum) {
				people.remove(on - 1);
				say = 1;
			} else {
				say++;
				on++;
			}
		}
 
		return "THE:" + maxNum + " is:" + people.get(+0).toString();
	}
 
	private static class Node {
		public int no;// 编号
		public Node next;// 下一个节点
 
		public Node(int no) {
			this.no = no;
		}
	}
}

Tags: , ,

文章作者: Lee

本文地址: https://www.pomelolee.com/847.html

除非注明,Pomelo Lee文章均为原创,转载请以链接形式标明本文地址

No comments yet.

Leave a comment

Search

文章分类

Meta