Description
CS2310 Assignment TWO
Q1. Write a program which takes as input a sequence of positive integers, and outputs the maximum value, minimum value, and the value that occurs the most along with its occurrence. More specifically, the program works as follows:
(1) Input the number of positive integers to be received;
(2) Input each positive integer;
(3) Output the maximum value, minimum value, and the value that occurs the most along with its occurrence.
Remarks:
1. You can safely assume the maximum number of input positive integers to be 20 (so in your program you can use an array of size 20 to store the positive integers), and the number of positive integers is > = 4.
2. You can safely assume that the inputs are valid and no validity check is required.
3. If there is no value occurring more than once, your program should print “There is no value occurring more than once.” (see Running Sample 2)
4. If there is more than one positive integer value sharing the highest occurrence, your program just needs to print the smallest value. (see Running Sample 3) Running samples: Sample1: Sample 2: Sample 3:
Q2. Write a program which takes as input a square matrix and prints it in spiral form. An example is given below: Input matrix: Printed in spiral form: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Remarks:
1. You can assume that the maximum size of the input matrix is 10ⅹ10.
2. No validity check is required for the value indicating the size of the matrix. Running samples: Sample 1: Sample 2: Sample 3:
Q3. Write a program which receives as input a sequence of integers which will at least contain one Zero. Assume Zero is the invalid number and all other numbers are valid.
The program should be able to convert the sequence following these rules:
(1) If next valid number is same as current number, double the current number and replace the next valid number with Zero. Note that each checking is done over an updated sequence of numbers from the previous checking and (possible) number doubling;
(2) After all the modification has been done, rearrange the updated sequence such that all 0’s are shifted to the end.
For example, given the sequence of numbers {2, 2, 0, 5, 0}, the final converted sequence of numbers is {4, 5, 0, 0, 0}.
The conversion procedure is as follows:
(1) Starting from the leftmost ‘2’, as the next number is valid and is the same as ‘2’, so the current ‘2’ is doubled and becomes ‘4’. Meanwhile, the next valid number ‘2’ is set to ‘0’. After this checking, the updated sequence of numbers is {4, 0, 0, 5, 0}.
(2) Such kind of checking is continued until the end of the sequence. As there are no more pairs of neighboring identical valid numbers, the updated sequence of numbers will be {4, 0, 0, 5, 0} when the checking procedure is finished.
(3) Now the program should push all ‘0s’ to the end, so the final converted sequence is {4, 5, 0, 0, 0}. Remarks: 1. You can assume the maximum number of input integers to be 20 (so in your program you can use an array of size 20 to store the input integers) and that the number of input integers is >=4. 2. No validity check is required for the inputs.
Running samples: Sample 1: Sample 2: Sample 3:
Q4. Write a program which works as follows. First, it receives a sequence of integers, each of which may be positive, negative, or zero. Then, the product of all integers is computed. The program should output the number of trailing 0s in the product result.
For example, if the input sequence is {2, 3, 5}, the product is 30, so the number of trailing 0s is 1; if the input sequence is {-2, 3, 10, 5}, the product is -300, so the number of trailing 0s is 2. If the input sequence contains 0(s), the program output the number of trailing zeros as 1 (see running sample 3).
Hints: A simple approach to achieving the functionality of this program is to simply multiply all integers first and then count trailing 0s in product. However, this solution may cause integer overflow.
So, a better solution is based on the fact that 0s are formed by a combination of 2 and 5. Hence the number of zeros will depend on the number of pairs of 2 and 5 that can be formed. For example, 8 * 3 * 5 * 23 * 17 * 25 * 4 -> 2 3 ∗ 3 1 ∗ 5 1 ∗ 231 ∗ 171 ∗ 5 2 ∗ 2 2 . In this example there are 5 twos and 3 fives. Hence, we shall be able to form only 3 pairs of (2*5). Hence will be 3 Zeros in the product.
Remarks:
1. You can assume the maximum number of input integers is 20.
2. You can safely assume that the number of input integers is >=4. Running samples: Sample 1: Sample 2: Sample 3: Sample 4:
Q5. Given a square matrix, check if it’s a Toeplitz matrix or not. A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements on a diagonal are same. An example of Toeplitz matrix is shown below:
Remarks:
1. You can safely assume that the minimum size of the matrix is 3ⅹ3 and the maximum size of the matrix is 10ⅹ10.
2. No validity check is required for the inputs. Running samples: Sample 1: Sample 2: Sample 3:
Q6. Write a program which works as follows. Given a sequence of non-negative integers, the program should reverse the order of integers. Based on this reversed sequence, the following game is played: Suppose each element in the reversed sequence represents the maximum number of steps that can be made forward from that element.
You are initially placed on the first index of the sequence. Determine if you can reach the last index.
For example, if the reversed sequence is {2, 3, 1, 1, 4}, you can reach the last index; if the reversed sequence is {1, 2, 3, 4}, you can reach the last index; if the reversed sequence is {1, 0, 3, 4}, you cannot reach the last index. Remarks: 1. You can safely assume that the number of non-negative integers is >=4. 2. You can assume the inputs are valid and no validity check is required. Running samples: Sample 1: Sample 2： Sample 3: Sample 4:
