CS102A程序讲解、辅导Java程序设计、Java编程语言调试
- 首页 >> Python编程 CS102A Fall 2020 Assignment 2
Problem 1. Hard Math Problem[Easy]
Description
Ahsoka must pass a very hard trial to become a Padawan (学徒). Now she gets stuck in a very hard
math problem: compute the integral of a polynomial. However she has never learnt to evaluate
an integral, but she knows that she can get an approximation of an integral by calculating a finite
sum. Now she seeks your help.
The integral is written as the form . is a polynomial and you can compute the
approximation by evaluating the value
, where .
Input
The program receives input from System.in .
The input consists of 3 lines.
The first line has 2 integers indicating the lower and upper bounds.
The second line has only 1 non-negative number , indicating the degree of the polynomial (which
means the polynomial is ).
The third line consists of floating point numbers, indicating the coefficients of the
polynomial.
It is guaranteed that the and all the coefficients satisfy
with at most 3 digits.
Output
Only one number, the approxiation of the integral using the given method. You should round
the answer to the nearest tenth.
Use double for more precise calculation.
Try System.out.printf("%.1f\n", ans); for auto-rounding.
Problem 2. Shattered [Hard]
Description
Ahsoka is on the run. Order 66 has been executed, and now the clone troopers are hunting down
Ahsoka at all costs. Ahsoka must leave the Jedi cruiser as soon as possible. The map of the Jedi
cruiser is given by an matrix , and (the element at the -th row, -th column of ) can
be represented by one of the following notations:
1. W - Wall
2. C - Corridor
Initially Ahsoka lies in the coordinate of the matrix, and she can travel through the corridor
to get to the exit located at the point .
Please help her escape.
Input
The first line consists of 2 positive integer .
For the following lines, each line contains marks ( W or C ).
It is guaranteed that and points are always character C . It is also
guaranteed that there is either no way out or only one path. There may exist some branch roads
which lead to dead ends, but the branches have maximum length of 1 and there are no other
branches on a branch.
Output
The first line contains one word "Yes" or “No” (without quotes) indicates whether Ahsoka can
successfully escape or not.
If the answer is “Yes” (without quotes), then print the coordinate of each step Ahsoka has to take
in order. One coordinate per line.
1 354.3
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Hint
Try using charAt() to fetch character(s) from a String .
Problem 3. Harmonic Strings [Medium]
Description
A noob guitarist is trying hard to study Java. One day he comes up with a strange idea: “Since the
character sequence is called String in Java, can it produce harmonic sounds like a guitar do?”
He wants to verify his thoughts as soon as possible, but he still has tons of bugs to fix. Fortunately,
you are so kind to help him to do the calculation.
For a string , let be the length of the string, then the frequency produced by the string is:
Where represents the modulus operation, and represent the ASCII code for the
characters in respectively.
You are given strings and you need to calculate the frequency for each string. To simplify the
problem, you only need to return the ratio of the largest and smallest one in rational number
form , where and are relatively prime (互素), i.e. .
Input
The program receives input from System.in .
The first line contains an integer , where .
For the following lines, each line contain a string with length not exceeding .
Output
Two integers and (which are described above), separated by a space.
Sample Input
Sample Output
Explanation
The frequencies of the two strings are and respectively, and .
Watch out for integer overflowing!
Problem 4. Silly Calculator [Medium]
Description
Macromogic is not getting along well with his roommate recently. He decides to hack into his
roommate’s CASIO fx-991CN calculator to mess him up in the exam. The project may be huge, so
he hires you to do the simple steps.
You are given a sequence containing digits and arithmetic operators ( + , - , * , / ). The only thing
you should do is to calculate the result from left to right, regardless of the operator
precedence. It is guaranteed that the numbers in the sequence are in the range of int type, and
you do not need to care if there is an overflow. The divisor will never be 0, and if the division
result is not an integer, just take the integral part (i.e. the maximum integer not exceeding the
number). For example:
If you can finish his task successfully, you will not get paid or receive other rewards, but you can
get full marks in this assignment.
Input
The program receives input from System.in .
The input has only one line, containing a string as described above. It is guaranteed that the string
starts with a digit.
Output
One integer, representing the calculation result.
Sample Input
Sample Output
Explanation
Problem 5. Jimmy’s Lottery [Medium]
Description
1 1+2*6/5-9
1 -6
Jimmy is a boy who is interested in lottery recently. He wants to define a new kind of lottery by
himself. The new kind of lottery is a set of number which is similar as the original lottery, but
Jimmy has changed the rule. For all sets of number in every turn, there is a standard set which will
be used to calculate the other sets’ scores. For each digit in a set, if it is the same as the digit in the
standard set at the same position, one gets 2 points for this digit. If the absolute difference
between two number is less than 3, one gets 1 point. Otherwise one gets no points. For example,
if the standard set is and your set is , then your score will be
points.
To make it more fun, Jimmy also set a lucky number. The lucky number can only be calculated by
all digits in set. The formula for the lucky number is (for given “lucky divisor” ,
and represents each digit in the set). The lucky number is also counted for final score, which
has the same rule as other digits (mentioned above). For example, the standard set is and
your set is with given , then the standard lucky number is ,
and your set's lucky number is . Their difference is 2, so for lucky number
you will get 1 point according to the rule. The final score for your set will be .
You’re a well-known programmer, so Jimmy wants you to write a program for him to calculate
each set’s score quickly.
Input
The program receives input from System.in .
The input contains several lines. The first line is the number of test cases , the length for set
and the lucky divisor . The next line shows the standard set. The following lines will show all
test cases, one in a line.
It’s guaranteed that , , . The range for numbers in set is
. All numbers are integers.
Output
Output the score for each set. One score in a line.
Sample Input 2
Sample Output 2
Problem 6. Easy Multiplication Plus
[Bonus]
Matrix multiplication, easy peasy. Right?
How about try something more challenging? Given matrices , can you calculate
?
If you do not know how to multiply matrices, please refer to your Linear Algebra textbook (or the
description in Easy Multiplication).
Input
The program receives input from System.in .
The first line contains two integer , denoting the number of matrices and the exponent index.
Then the following lines describes the matrices in order.
For the -th matrix , the first line contains two positive integers denoting that the matrix
is . Then for the next lines, each line contains integers, which represent the
entries of the matrix.
It is guaranteed that for all and .
Note that the input data may be huge, please:
1. Use the provided Reader class for input, otherwise your program will be very slow!
import java.io.*;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) {
Reader reader = new Reader(System.in);
// Write your code below.
// You may use `reader.nextInt()' to read integers.
3. Use “Quick power” algorithm to calculate the matrix power:
}
// You do not necessarily understand the code below currently.
private static class Reader {
BufferedReader in;
StringTokenizer tokenizer;
public Reader(InputStream inputStream) {
in = new BufferedReader(new InputStreamReader(inputStream));
}
private String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(in.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
The following is the pseudocode for `Quick Power' (Assume we are to
calculate a^b mod m):
ans <= 1
for all binary digits d of b (from right to left):
An square matrix, representing the total product. Entries in the same row are separated
by a space.
Problem 1. Hard Math Problem[Easy]
Description
Ahsoka must pass a very hard trial to become a Padawan (学徒). Now she gets stuck in a very hard
math problem: compute the integral of a polynomial. However she has never learnt to evaluate
an integral, but she knows that she can get an approximation of an integral by calculating a finite
sum. Now she seeks your help.
The integral is written as the form . is a polynomial and you can compute the
approximation by evaluating the value
, where .
Input
The program receives input from System.in .
The input consists of 3 lines.
The first line has 2 integers indicating the lower and upper bounds.
The second line has only 1 non-negative number , indicating the degree of the polynomial (which
means the polynomial is ).
The third line consists of floating point numbers, indicating the coefficients of the
polynomial.
It is guaranteed that the and all the coefficients satisfy
with at most 3 digits.
Output
Only one number, the approxiation of the integral using the given method. You should round
the answer to the nearest tenth.
Use double for more precise calculation.
Try System.out.printf("%.1f\n", ans); for auto-rounding.
Problem 2. Shattered [Hard]
Description
Ahsoka is on the run. Order 66 has been executed, and now the clone troopers are hunting down
Ahsoka at all costs. Ahsoka must leave the Jedi cruiser as soon as possible. The map of the Jedi
cruiser is given by an matrix , and (the element at the -th row, -th column of ) can
be represented by one of the following notations:
1. W - Wall
2. C - Corridor
Initially Ahsoka lies in the coordinate of the matrix, and she can travel through the corridor
to get to the exit located at the point .
Please help her escape.
Input
The first line consists of 2 positive integer .
For the following lines, each line contains marks ( W or C ).
It is guaranteed that and points are always character C . It is also
guaranteed that there is either no way out or only one path. There may exist some branch roads
which lead to dead ends, but the branches have maximum length of 1 and there are no other
branches on a branch.
Output
The first line contains one word "Yes" or “No” (without quotes) indicates whether Ahsoka can
successfully escape or not.
If the answer is “Yes” (without quotes), then print the coordinate of each step Ahsoka has to take
in order. One coordinate per line.
1 354.3
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Hint
Try using charAt() to fetch character(s) from a String .
Problem 3. Harmonic Strings [Medium]
Description
A noob guitarist is trying hard to study Java. One day he comes up with a strange idea: “Since the
character sequence is called String in Java, can it produce harmonic sounds like a guitar do?”
He wants to verify his thoughts as soon as possible, but he still has tons of bugs to fix. Fortunately,
you are so kind to help him to do the calculation.
For a string , let be the length of the string, then the frequency produced by the string is:
Where represents the modulus operation, and represent the ASCII code for the
characters in respectively.
You are given strings and you need to calculate the frequency for each string. To simplify the
problem, you only need to return the ratio of the largest and smallest one in rational number
form , where and are relatively prime (互素), i.e. .
Input
The program receives input from System.in .
The first line contains an integer , where .
For the following lines, each line contain a string with length not exceeding .
Output
Two integers and (which are described above), separated by a space.
Sample Input
Sample Output
Explanation
The frequencies of the two strings are and respectively, and .
Watch out for integer overflowing!
Problem 4. Silly Calculator [Medium]
Description
Macromogic is not getting along well with his roommate recently. He decides to hack into his
roommate’s CASIO fx-991CN calculator to mess him up in the exam. The project may be huge, so
he hires you to do the simple steps.
You are given a sequence containing digits and arithmetic operators ( + , - , * , / ). The only thing
you should do is to calculate the result from left to right, regardless of the operator
precedence. It is guaranteed that the numbers in the sequence are in the range of int type, and
you do not need to care if there is an overflow. The divisor will never be 0, and if the division
result is not an integer, just take the integral part (i.e. the maximum integer not exceeding the
number). For example:
If you can finish his task successfully, you will not get paid or receive other rewards, but you can
get full marks in this assignment.
Input
The program receives input from System.in .
The input has only one line, containing a string as described above. It is guaranteed that the string
starts with a digit.
Output
One integer, representing the calculation result.
Sample Input
Sample Output
Explanation
Problem 5. Jimmy’s Lottery [Medium]
Description
1 1+2*6/5-9
1 -6
Jimmy is a boy who is interested in lottery recently. He wants to define a new kind of lottery by
himself. The new kind of lottery is a set of number which is similar as the original lottery, but
Jimmy has changed the rule. For all sets of number in every turn, there is a standard set which will
be used to calculate the other sets’ scores. For each digit in a set, if it is the same as the digit in the
standard set at the same position, one gets 2 points for this digit. If the absolute difference
between two number is less than 3, one gets 1 point. Otherwise one gets no points. For example,
if the standard set is and your set is , then your score will be
points.
To make it more fun, Jimmy also set a lucky number. The lucky number can only be calculated by
all digits in set. The formula for the lucky number is (for given “lucky divisor” ,
and represents each digit in the set). The lucky number is also counted for final score, which
has the same rule as other digits (mentioned above). For example, the standard set is and
your set is with given , then the standard lucky number is ,
and your set's lucky number is . Their difference is 2, so for lucky number
you will get 1 point according to the rule. The final score for your set will be .
You’re a well-known programmer, so Jimmy wants you to write a program for him to calculate
each set’s score quickly.
Input
The program receives input from System.in .
The input contains several lines. The first line is the number of test cases , the length for set
and the lucky divisor . The next line shows the standard set. The following lines will show all
test cases, one in a line.
It’s guaranteed that , , . The range for numbers in set is
. All numbers are integers.
Output
Output the score for each set. One score in a line.
Sample Input 2
Sample Output 2
Problem 6. Easy Multiplication Plus
[Bonus]
Matrix multiplication, easy peasy. Right?
How about try something more challenging? Given matrices , can you calculate
?
If you do not know how to multiply matrices, please refer to your Linear Algebra textbook (or the
description in Easy Multiplication).
Input
The program receives input from System.in .
The first line contains two integer , denoting the number of matrices and the exponent index.
Then the following lines describes the matrices in order.
For the -th matrix , the first line contains two positive integers denoting that the matrix
is . Then for the next lines, each line contains integers, which represent the
entries of the matrix.
It is guaranteed that for all and .
Note that the input data may be huge, please:
1. Use the provided Reader class for input, otherwise your program will be very slow!
import java.io.*;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) {
Reader reader = new Reader(System.in);
// Write your code below.
// You may use `reader.nextInt()' to read integers.
3. Use “Quick power” algorithm to calculate the matrix power:
}
// You do not necessarily understand the code below currently.
private static class Reader {
BufferedReader in;
StringTokenizer tokenizer;
public Reader(InputStream inputStream) {
in = new BufferedReader(new InputStreamReader(inputStream));
}
private String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(in.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
The following is the pseudocode for `Quick Power' (Assume we are to
calculate a^b mod m):
ans <= 1
for all binary digits d of b (from right to left):
An square matrix, representing the total product. Entries in the same row are separated
by a space.