狐狸找兔子(java 版)

圍繞着山頂有10個洞，一隻狐狸和一隻兔子住在各自的洞裡。狐狸想吃掉兔子。

一天，兔子對狐狸說：“你想吃我有一個條件，先把洞從1－10編上号，你從10号洞出發，

先到1号洞找我；第二次隔1個洞找我，第三次隔2個洞找我，以後依次類推，次數不限，若能找到我，

你就可以飽餐一頓。不過在沒有找到我以前不能停下來。” 狐狸滿口答應，就開始找了。它從早到晚進了1000次洞，

累得昏了過去，也沒找到兔子，請問，兔子躲在幾号洞裡？

1、僞代碼

// 數組實作

算法 FindRabbit(num, holeNum)

// 輸入 num 為 fox 找的次數， holeNum為洞的個數

// 輸出 沒被通路hole

for i ← 1 to holeNumdo

hole[i]= 1

for i ← 1 and j = 0 to num do

j← j + i

ifj > 10

j← j %10

printj

hole[j]  = 1 // 把通路過的洞置為一

for i ← 1 to holeNumdo

ifhole[i] = 0

printi

// 遞歸實作

算法 FindRabbit(num)

// 輸出 fox 已經找過的洞

// 輸入 fox 找的次數

if num = 1return 1 //  fox 第一次找的是第一個洞

else

first ← find(num - 1) + num;

        if first > 10

            print first%10

    return first;

2、效率分析

// 數組實作效率分析

該算法有三個for 循環，基本操作為指派

C(n, m)=2   +   = 2m + n  O(m + n)

// 遞歸實作效率分析

通過分析 可以發現 遞歸式F(n) =F(n-1) + n  基本操作為指派

而次數函數 為 C(n) = C(n-1) +1   C(1) = 1

可知 C(n) = n  O(n)

3、源代碼

public class Josephus {

    public static void main(String[] args) {

        int num = 1000;

        int holeNum = 11;

        // 數組 實作

        findRabbit(num, holeNum);

        // 遞歸實作

        find(num);

    }

    public static void findRabbit(int num, int holeNum) {

        int hole[] = new int[holeNum];

        // 表示沒被通路過

        for (int i = 1; i < holeNum; i++) {

            hole[i] = 0;

        }

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

            j = j + i;

            if (j > 10) {

                j = j % 10;

            }

             System.out.println("第 " + i + " 次 , 找到 洞 " + j);

            hole[j] = 1;

        }

        // 表示沒被通路過

        for (int i = 1; i < holeNum; i++) {

            if (hole[i] == 0) {

                System.out.println(i);

            }

        }

    }

    public static int find(int num){

        if(num == 1){

            System.out.println("第  1  次 , 找到 洞 1");

            return 1;

        }else {

            int first = find(num - 1) + num;

            int hole = first;

            if (hole > 10) {

                hole = hole % 10;

            }

            System.out.println("第 " + num + " 次 , 找到 洞 " + hole);

            return first;

        }

    }

}