Assignment-2021-08-02

MyCowQuestion.java

package ca.bytetube._11_recursion;

public class MyCowQuestion {
    public static int myCowQuestion1(int n){
        if (n  <= 1) return n;
        int[] arr = new int[n + 1];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;
        arr[4] = 4;
        for (int i = 5; i <= n ; i++) {
            arr[i] = arr[i - 1] + arr[i - 3];
        }

        return arr[n];
    }

    public static int myCowQuestion2(int n){
        //f(n) = f(n-1) + f(n-3)
        if (n <= 4) return n;

        int threeAgo = 2;
        int twoAgo = 3;
        int oneAgo = 4;
        //start from 5th
        for (int i = 4; i < n; i++) {
            int sum = oneAgo + threeAgo;
            threeAgo = twoAgo;
            twoAgo = oneAgo;
            oneAgo = sum;
        }
        return oneAgo;
    }


    public static void main(String[] args) {
        System.out.println(myCowQuestion1(10));
        System.out.println(myCowQuestion2(10));
    }

}

MyHanoi.java

package ca.bytetube._11_recursion;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class MyHanoi {
    public static void main(String[] args) {
        Set<MyMoveInfo> myMoveInfos = myHanoi(3, "A", "C", "B");
        System.out.println(myMoveInfos);
    }

    public static Set<MyMoveInfo> myHanoi(int n,String from,String to,String help){
        LinkedHashSet<MyMoveInfo> myMoveInfos = new LinkedHashSet<>();
        myHanoi(n, from, to, help, myMoveInfos);
        return myMoveInfos;

    }

    private static class MyMoveInfo {
        int index;
        String from;
        String to;

        @Override
        public String toString() {
            return "Index: " + index + ", Move From " + from + " To " + to + "\n";
        }

        public MyMoveInfo(int index, String from, String to) {
            this.index = index;
            this.from = from;
            this.to = to;
        }
    }

    private static void myHanoi(int n, String from, String to, String help, Set<MyMoveInfo> moveInfoSet) {
        if (n == 1) {
            moveInfoSet.add(new MyMoveInfo(n, from, to));
        }else {
            myHanoi(n - 1, from, help, to, moveInfoSet);//将前n-1 plates 从 A --- B
            moveInfoSet.add(new MyMoveInfo(n, from, to));
            myHanoi(n - 1, help, to, from, moveInfoSet);//将前n-1 plates 从 B --- C
//            moveInfoSet.add(new MyMoveInfo(n, help, to));
        }
    }

}