Java兩種方法實作循環報數

問題描述：

十個猴子圍成一圈選大王，依次1-3 循環報數，報到3 的猴子被淘汰，直到最後一隻猴子成為大王。問，哪隻猴子最後能成為大王？

方法一：java連結清單

public class testall {

static scanner scanner = new scanner(system.in);

static int num;

static string str;

static linkedlist<string> list = new linkedlist<string>();

static linkedlist<string> result = new linkedlist<string>();

public static void main(string[] arg) {

input();

output();

}

private static void output() {

pushnum();

iterator it = result.iterator();

while (it.hasnext()) {

system.out.print(it.next() + " ");

private static void pushnum() {

int i = 1;

while (list.size() > 0) {

// system.out.println(i+"!! ");

iterator it = list.iterator();

string node = (string) it.next();

if (i == num) {

result.add(node);

it.remove();

i = 0;

i++;

private static void input() {

str = scanner.nextline();

string[] tmp = str.split(" ");

num = integer.parseint(tmp[0]);

for (int i = 1; i < tmp.length; i++) {

list.add(tmp[i]);

方法二：數組

public class timetest {

public static void main(string[] args) {

int num = 10;

boolean[] array = new boolean[num];

for (int i = 0; i < num; i++) {

array[i] = true;

int index = 0;

int count = 0;

int n = num;

while (n > 1) {

if (array[index] == true) {

count++;

if (count == 3)

// 當count等于3時，就淘汰一個；

{

array[index] = false;

n--; // 當有一個被淘汰時，n--；

count = 0;

index++;

// 當從0循環到29時，重新置index為0；

if (index == num) {

index = 0;

if (array[i] == true)

system.out.println(i + 1);

 其中方法一的時間複雜度為o（n^2）

方法二的時間複雜度為o(n)