COMP1110/6710 Final Exam(2020 S1)

发表于 分类于 ， 阅读数： 评论数： 本文字数： 13k 阅读时长 ≈ 21 分钟
Answers to the coding section of COMP1110-6710 Final Exam 2020 S1

Question 1

Q1.1 A

Print the Collatz sequence for the value n.If the input value is less than one, do nothing.Otherwise, print the input value n on a line by itself, and then:

  • if the input value is even, call tao again, passing in (n/2);
  • if the input value is odd and greater than one, call tao again, passing in (n*3+1);
  • if the input value is one, do nothing.

Special rule (not part of the Collatz sequence):If the input value is 13120, print the string “Tao!” on a line by itself and then exit (without printing anything further).

Solution

This is a very simple problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void tao(int n) {
    // FIXME complete this method
    if(n<1)	return;
    if(n==1) {
        System.out.println(n);
        return;
    }
    if (n == 13120) {
        System.out.println("Tao!");
        return;
    }
    System.out.println(n);
    if(n%2==0)	tao(n/2);
    if(n%2!=0)	tao(3*n+1); 	
}

Q1.1 B

This function takes a positive integer, n, and returns an array of ints containing all prime factors of that integer in ascending order.

For example:

  • factors(6) returns {2, 3}
  • factors{7} returns {7}
  • factors{24} returns {2, 2, 2, 3}

If n is less than 2, an empty array is returned.

Solution

To factorize n into prime factors, we should find the smallest prime number k firstly, and then follow these steps:

  1. If this prime number equals n, it means the process of factorization is complete, and we should print it.

  2. If n > k and n is divisible by k, we should print the value of k and use the quotient of n divided by k as the new positive integer n, then repeat step one.

  3. If n is not divisible by k, use k + 1 as the new k value, and repeat step one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] factors(int n) {
    if(n<2) {
        int ans[]= {};
        return ans;
    }
    ArrayList<Integer> ans= new ArrayList<Integer>();
    int i=2;
    while(i<=n) {
        if(n%i==0) {
            ans.add(i);
            n=n/i;
            i=2;
        }
        else 
            i++;
    }
    System.out.println(ans);
    int[] result = new int[ans.size()];
    for (int j = 0; j < ans.size(); j++) {
        result[j] = ans.get(j);
    }
    return result;
}

Q1.2 A

This function takes an array of integers and returns an integer that is the average of the ‘included’ integers in the array, or -1 if there are no ‘included’ integers in the array.

An array element is ‘included’ if:

  • it is greater than or equal to zero, and

  • it appears earlier in the array than the MAGIC number (999)

Because the return value is an integer, the average should be calculated using integer division.

Some examples:

[ 1, 3, 999] -> 2
[ 1, 6, 999, 4] -> 3
[ 1, -3, 5, 999] -> 3

Solution

We just need to calculate the sum of all the included integers and then divide it by the number of included integers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int avg(int[] in) {
    int sum = 0;
    int count = 0;
    for (int i : in) {
        if (i == 999) {
            break;
        }
        if (i >= 0) {
            sum += i;
            count++;
        }
    }
    return count == 0 ? -1 : sum / count;
}

Q1.2 B

This function accepts an Individual ancestor representing the root (common ancestor) of a family tree and the name of a target individual to find within that family tree, and returns a string representation of all the ancestors of that individual, each separated by the string " born of ".

If target name matches the name of ancestor, then only the target name is returned.

If the target name is not found within the family tree descended from ancestor, then null is returned.

For example, given an Individual homer representing a person named “Homer”, who has children named “Lisa” and “Bart”:

  • getAncestry(homer, “Lisa”) returns “Lisa born of Homer”;

  • getAncestry(homer, “Bart”) returns “Bart born of Homer”; and

  • getAncestry(homer, “Homer”) returns “Homer”; and

  • getAncestry(homer, “Barney”) returns null

Note: each individual has only one parent in the family tree.

Solution

Due to the necessity of inserting ‘born of’, we need to retrieve a ancestor string to fulfill the output. The retrieval of the ancestor string requires a depth-first search on a family tree. Here is a family tree of the Simpson family:

1
2
3
4
5
6
7
8
9
Stephanie__Ridge__Thomas__Douglas
    |      |_Steffy__Kelly
    |      |_Phoebe 
    |      |_R.J. 
    |_Kristen__Zende
    |_Angela
    |_Thorne__Alexandria
    |_Alexandria
    |_Felicia__Dominick

The search for R.J. unfolds as follows:

Stephanie’s children are Ridge, Kristen, Angela, Thorne, Alexandria, and Felicia. Therefore, we start by searching Ridge’s children. Ridge’s children are Thomas, Steffy, Phoebe, and R.J. So, we search Thomas’s children. Thomas’s children are Douglas. Douglas doesn’t have any children, so the search ends. We return to Thomas’s level. Since Thomas’s children have been searched, we return to Ridge’s level. Next, we search Ridge’s next child, Steffy. Steffy’s children include Kelly. We search Kelly’s level, but Kelly doesn’t have any children, so the search ends. We return to Steffy’s level. Since Steffy’s children have been searched, we return to Ridge’s level. Next, we search Ridge’s child Phoebe. Phoebe doesn’t have any children, so the search ends. We return to Ridge’s level and search for R.J., finding the target. We then return step by step based on the levels to obtain the result.

The code design based on this process is as follows:

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
static boolean recGetAncestry(ArrayList<String> ansList,Individual ancestor1, String ancestor) {
    ansList.add(ancestor1.name);
    if(ancestor1.name.equals(ancestor)) 
        return true;
    if(ancestor1.children==null) {
        ansList.remove(ancestor1.name);
        return false;
    }
    for(int i=0;i<ancestor1.children.length;i++) {
        if(recGetAncestry(ansList, ancestor1.children[i], ancestor))
            return true;
    }
    ansList.remove(ancestor1.name);
    return false;
}

public static String getAncestry(Individual ancestor1, String ancestor) {
    // FIXME complete this method
    ArrayList<String> ansList=new ArrayList<>();
    String ans="";
    recGetAncestry(ansList,ancestor1,ancestor);
    for(int i=ansList.size()-1;i>0;i--) 
        ans+=(ansList.get(i)+" born of ");
    if(ansList.size()!=0) {
        ans+=ansList.get(0);
        return ans;
    }
    return null;
}

Q1.3 A

Get all valid crop rotations that can be composed from the provided set of vegetable crops for the given number of seasons.
A crop rotation is a sequence of vegetable crops to plant.One crop is planted per season, and any crop may be planted at most once.Crops must be planted in order of their Group according to the following
rules:

  • a LEGUME may only be followed by a BRASSICA;
  • a BRASSICA may only be followed by an ALLIUM;
  • an ALLIUM may only be followed by a FRUITING crop; and
  • a FRUITING crop may only be followed by a LEGUME.
    For example, the call getAllRotations([Tomato (fruiting), Onion (allium)], 2) returns a set containing a single rotation:
  • [Onion (allium), Tomato (fruiting)]
    because an ALLIUM may only be followed by a fruiting crop.
    The call getAllRotations([Tomato (fruiting), Kale (brassica), Onion (allium), Pea (legume)], 4) returns a set containing four rotations:
  • [Kale (brassica), Onion (allium), Tomato (fruiting), Pea (legume)]
  • [Onion (allium), Tomato (fruiting), Pea (legume), Kale (brassica)]
  • [Pea (legume), Kale (brassica), Onion (allium), Tomato (fruiting)]
  • [Tomato (fruiting), Pea (legume), Kale (brassica), Onion (allium)]
    If no valid crop rotation can be found, an empty list is returned.
    For example, the call getAllRotations([Tomato (fruiting), Gai Lan (brassica)], 2) returns an empty set, because a FRUITING crop cannot be followed by a BRASSICA, and a BRASSICA cannot be followed by a FRUITING crop.

Solution

The problem is a typical backtracking problem. We can use a recursive method to generate all the possible rotations and then check if they are valid. If they are valid, we add them to the result set.

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
private static boolean isValidRotation(Vegetable v1, Vegetable v2) {
    switch (v1.group) {
        case LEGUME:
            return v2.group == Group.BRASSICA;
        case BRASSICA:
            return v2.group == Group.ALLIUM;
        case ALLIUM:
            return v2.group == Group.FRUITING;
        case FRUITING:
            return v2.group == Group.LEGUME;
        default:
            return false;
    }
}
private static void generateRotations(Set<Vegetable> crops, int seasons, List<Vegetable> rotation, Set<List<Vegetable>> rotations) {
    if (rotation.size() == seasons) {
        rotations.add(new ArrayList<>(rotation));
        return;
    }
    
    for (Vegetable crop : crops) {
        if (!rotation.contains(crop)) {
            if (rotation.isEmpty() || isValidRotation(rotation.get(rotation.size() - 1), crop)) {
                rotation.add(crop);
                generateRotations(crops, seasons, rotation, rotations);
                rotation.remove(rotation.size() - 1);
            }
        }
    }
}
public static Set<List<Vegetable>> getAllRotations(Set<Vegetable> crops, int seasons) {
    // FIXME complete this method
    if(seasons==0)
        return new HashSet<>();
    Set<List<Vegetable>> rotations = new HashSet<>();
    generateRotations(crops, seasons, new ArrayList<>(), rotations);
    return rotations;
}

The isValidRotation method is used to validate whether two vegetable crops can form a valid crop rotation. It determines if the second crop v2 complies with rotation rules by checking the group of the first crop v1.

The generateRotations method is employed to produce all possible crop rotation schemes. It traverses all potential combinations of crops using recursion and ensures the generation of valid rotations through backtracking. Here’s the gist of this method:

Firstly, we check if the current rotation’s length equals the given number of seasons. If it does, it indicates that the current rotation scheme is complete. We add it to the result set and terminate the current recursion branch.

If the rotation’s length hasn’t reached the specified number of seasons, we continue attempting to add different crops to the current rotation scheme.

We iterate through the available crops. For each crop, we verify if it’s already in the current rotation. If not, we further check if it satisfies the rotation rule, i.e., if the current crop can follow the previous one.

If the current crop adheres to the rotation rule, we add it to the rotation scheme and recursively call the generateRotations method to continue generating rotation schemes down the line.

Upon recursive return, we perform backtracking by removing the last added crop to explore other possibilities.

The getAllRotations method serves as the interface method, used to invoke generateRotations for generating all possible rotations and returning a collection containing all rotation schemes.

Q1.3 B

This question is very similar to Q1.3 A, and the solution is almost identical. Therefore, I won’t explain further.

Q1.3 C

A Sudoku puzzle consists of the numbers 1-9 arranged in a 9x9 grid, divided into nine 3x3 subgrids.In a valid solution for the puzzle, each of the numbers 1-9 appears only once in each row, column and subgrid. For example, the following is a valid solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
-------------------------
| 5 8 1 | 9 4 7 | 6 3 2 |
| 3 7 6 | 8 1 2 | 5 9 4 |
| 9 2 4 | 3 5 6 | 7 8 1 |
-------------------------
| 6 5 7 | 2 8 9 | 1 4 3 |
| 1 3 8 | 6 7 4 | 2 5 9 |
| 2 4 9 | 1 3 5 | 8 7 6 |
-------------------------
| 8 9 3 | 7 6 1 | 4 2 5 |
| 4 6 2 | 5 9 8 | 3 1 7 |
| 7 1 5 | 4 2 3 | 9 6 8 |
-------------------------

whereas the following partial layout is not valid, because the number 5 appears twice in the upper-left subgrid.

1
2
3
4
5
6
---------------
| 5 8 1 | 3 ...
| 3 7 2 | 4 ...
| 4 5 6 | 1 ...
---------------
|  ...  |   ...

The puzzle is specified as a 9x9 array of integers which holds the rows and columns of numbers in each cell of the puzzle.
For example, the number in the second row and third column of the puzzle is held in array element a[1][2].
If the setup gives zero for a number, it means that value for that cell is not specified, and must be solved. In other words, zero must be replaced with a number 1-9 to create a valid solution.
For example, the following is one possible setup for the valid solution given above:

1
2
3
4
5
6
7
8
9
10
11
12
13
-------------------------
| 0 0 1 | 9 4 7 | 0 0 0 |
| 3 7 6 | 8 1 2 | 0 9 0 |
| 9 2 4 | 3 5 0 | 0 0 0 |
-------------------------
| 0 5 7 | 0 0 9 | 1 0 0 |
| 1 3 8 | 6 0 4 | 2 5 9 |
| 0 0 9 | 1 0 0 | 8 7 0 |
-------------------------
| 0 0 3 | 0 6 1 | 4 2 5 |
| 0 6 0 | 5 9 8 | 3 1 7 |
| 0 0 0 | 4 2 3 | 9 0 0 |
-------------------------

Solution

The process of solving Sudoku can be implemented recursively. Firstly, we check if the Sudoku puzzle is fully filled. If it is, it means the Sudoku puzzle is solved. Then, we find the next empty cell and attempt to fill it with a number. For each empty cell, we try filling it with numbers from 1 to 9, and then check if it satisfies the Sudoku rules. If the number we’re trying to fill already exists in the same row, column, or subgrid, it’s not a valid move, and we backtrack to the previous state. The Sudoku solving process continues until all empty cells are filled, at which point the Sudoku puzzle is considered solved.

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
public static int[][] solve(int[][] setup) {
    // FIXME complete this method
    int[][] partial = setup.clone();
    if (solveSudoku(partial, 0, 0)) {
        return partial;
    } else {
        // No solution found
        return null;
    }
}
private static boolean solveSudoku(int[][] partial, int row, int col) {
    if (isFull(partial)) {
        // All rows are filled, puzzle is solved
        return true;
    }
    // Find the next empty cell
    if (col == SIDE_LENGTH) {
        col = 0;
        row++;
    }
    while (partial[row][col] != 0) {
        col++;
        if (col == SIDE_LENGTH) {
            col = 0;
            row++;
        }
        if (row == SIDE_LENGTH) {
            return true; // All rows are filled, puzzle is solved
        }
    }
    // Try placing a number in the empty cell
    for (int num = 1; num <= 9; num++) {
        if (isValidMove(partial, row, col, num)) {
            partial[row][col] = num;

            // Recursively try to solve the puzzle
            if (solveSudoku(partial, row, col + 1)) {
                return true;
            }

            // If the current placement leads to an invalid solution, backtrack
            partial[row][col] = 0;
        }
    }
    // No valid number found, backtrack to the previous cell
    return false;
}
private static boolean isFull(int[][] array) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if(array[i][j]==0)
                return false;
        }
    }
    return true;
}
private static boolean isValidMove(int[][] setup, int row, int col, int num) {
    // Check if the number is not in the same row or column
    for (int i = 0; i < SIDE_LENGTH; i++) {
        if (setup[row][i] == num || setup[i][col] == num) {
            return false;
        }
    }
    // Check if the number is not in the same 3x3 subgrid
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (setup[startRow + i][startCol + j] == num) {
                return false;
            }
        }
    }
    return true;
}

The remaining questions are relatively simple, please refer to the code yourself.