辅导 program、讲解 C++编程语言
Problem 1. Basic knowledge
Problem 2. Polynomial evaluation
Input format
Output format
Example
Notes
Problem 3. GCC argument descriptor
Problem background
Problem description
1. -Wall
2. -Wpedantic
3. -Wextra
4. -Werror
5. -o xxx
6. -I xxx
7. -std=xxx
8. Other
Notes
Example
Problem 4. 6174
Hint
Input format
Output format
Example
Note
Problem 5: CPU emulator
Description
Input format
Output format
Example
Note
Problem 1. Basic knowledge
1. Suppose c is a variable of type char. If c is a decimal digit character, how
can we obtain its numeric value?
int(c)
c - 48
c - '0'
c - '\0'
*(int *)&c
2. Regarding undefined behaviors, which of the following statements is/are
true?
An undefined behavior results in one of a set of valid results. For example,
the following code (assuming int is 32-bit) will assign the variable x with
some value, but the value is not valid.
int ival = 10000000;
int x = ival * ival;
An undefined behavior means that there are no restrictions on the behavior
of the program. The standard does not require such programs to do
anything meaningful.
An undefined behavior means that two or more behaviors are permitted by
the standard and that the compiler will choose a meaningful one. The
behavior remains unchanged when the program is run again, although we
don't know what the behavior is.
Correct C programs shall not have undefined behaviors.
3. Suppose int is 32-bit and long long is 64-bit. Select the code snippet(s)
that involve(s) integer overflow.
int x = 42 / 0;
int ival = 1000000;
long long llval = ival * ival;
unsigned uval = -42;
unsigned u1 = 10000000;
unsigned u2 = u1 * u1;
4. Select the code snippet(s) that involve(s) undefined behavior.
int random(void) {
int x;
return x;
}
int main(void) {
printf("%d\n", random());
}
unsigned uval = -5;
printf("%u\n", uval);
int table[100];
int exists_in_table(int value) {
for (int i = 0; i <= 100; ++i)
if (table[i] == value)
return 1;
return 0;
}
int foo(int value) {
printf("%d\n", value);
}
int main(void) {
int x = 42;
int y = foo(x);
printf("%d\n", x + y);
}
int i = 42;
printf("%d%d\n", i, i++);
double pi = 3.14;
printf("%d\n", pi);
5. Read the following code.
void swap(int *pa, int *pb) {
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
int main(void) {
int x = 10, y = 15;
swap(&x, &y);
printf("%d %d\n", x, y);
}
(1) Which of the following statements is/are true?
The asterisk (*) in the function parameter declaration int *pa is a part of
int *, meaning that pa is a pointer to int.
The asterisk (*) in the statement int tmp = *pa is the dereference operator,
which is used to access the object that pa points to.
The asterisk (*) in the statement *pb = tmp is the pointer symbol, meaning
that pb is a pointer.
The asterisk (*) in the statement *pb = tmp is the dereference operator,
which is used to access the object that pb points to.
(2) Which of the following statements is/are true?
If we rewrite the function swap as follows
void swap(int a, int b) {
int tmp = a;
a = b;
b = tmp;
}
and replace swap(&x, &y) with swap(x, y) in the main function, the values
of x and y are still exchanged successfully.
The parameter declarations of swap can be rewritten as int *pa, pb,
because pa and pb are of the same type.
The parameter declarations of swap can be rewritten as int *pa, *pb,
because pa and pb are of the same type.
The function swap will output the values of *pa and *pb.
None of the above.
(3) Write down the type of each expression. For pointer types, place exactly one
space between the pointee type and the first asterisk, and no spaces between
consecutive asterisks (e.g. int *, int **, or int ***, but not int* or int * *).
Expression pa *pa &pa x &x
Type
6. Read the following code.
int min_element(int *array, int l, int r) {
int pos = l;
while (l < r) {
if (array[l] < array[pos])
pos = l;
++l;
}
return pos;
}
int a[] = {1, 4, 2, 8, 5, 7};
(1) Which of the following statements is/are true?
min_element(array, l, r) returns array[i] .
min_element(array, l, r) returns array[i] .
min_element(array, l, r) returns the index of the first occurrence of
array[i] .
min_element(array, l, r) prints the index of the first occurrence of
array[i] to the standard output.
To make min_element(array, l, r) return the index of the last occurrence
of array[i] , replace array[l] < array[pos] (on line 4)
with array[l] <= array[pos].
(2) Suppose we have the following main function.
int main(void) {
printf("%d\n", min_element(a, 0, 6));
}
min{ ∣ i ∈ [l,r)}
min{ ∣ i ∈ [l,r]}
min{ ∣ i ∈ [l,r)}
min{
∣ i ∈ [l,r)}
min{ ∣ i ∈ [l,r)}
Which of the following statements is/are true?
The function main contains undefined behavior.
The type of a is int [6].
The type of a is int *.
The type of the parameter array is int [6].
The type of the parameter array is int [], where the length is determined
at run-time and may change.
The type of the parameter array is int *.
Since we want to find the minimum element in the entire array a, we can
simply write min_element(a), and the parameters l and r will be assigned
with 0 and 6 automatically.
7. Given the functions swap and min_element as defined in the previous two
questions. Read the following code.
void sort(int *array, int n) {
for (int i = 0; i < n - 1; ++i) {
int min_pos = min_element(array, i, n);
swap(&array[i], &array[min_pos]);
// Note: If you have difficulty understanding this function, uncomment the
following lines, run the code and look at the output.
// for (int i = 0; i < n; ++i)
// printf("%d ", array[i]);
// printf("\n");
}
}
int main(void) {
int a[] = {8, 5, 7, 1, 4, 2};
sort(a, 6);
for (int i = 0; i < 6; ++i)
printf("%d ", a[i]);
printf("\n");
}
(1) Regarding the sort function, which of the following statements is/are true?
swap(&array[i], &array[min_pos]) is equivalent to swap(array + i,
array + min_pos).
At each iteration, the smallest element in {array[i], ..., array[n - 1]}
is found and then placed at index i by swapping with array[i].
The effect of sort on the array is not changed if we rewrite the loop
condition as i < n.
sort(array, n) sorts the elements {array[0], ..., array[n - 1]} in
non-decreasing order.
(2) Which of the following statements is/are true?
The program prints 1 2 4 5 7 8.
If we replace sort(a, 6) as sort(a, 4), the output becomes 1 2 4 5 8 7.
If we replace sort(a, 6) as sort(a, 3), the output becomes 5 7 8 1 4 2.
If we replace sort(a + 2, 4), the output becomes 8 5 1 2 4 7, i.e. only
the last four elements are sorted.
Problem 2. Polynomial evaluation
Given a polynomial P(x) of degree n
n
P(x) = a0 + a1x + ⋯ + anx
n = ∑ aix
i
,
i=0
we want to evaluate the polynomial at several points x0, x1, ⋯ , xm−1.
Input format
On the first line, a nonnegative integer n, which is the degree of the polynomial.
On the second line, n + 1 numbers a0
, a1
, ⋯ , an separated by space, which are
the coefficients of the polynomial.
On the third line, a nonnegative integer m.
Then m lines follow, the i-th of which is a number xi(i = 0, 1, ⋯ , m − 1).
Output format
m lines, the i-th of which (i = 0, 1, ⋯ , m − 1) is a number P (xi), rounded to
three decimal places.
Example
Input
2
-0.5 1 2.5
5
0
-6.6
1000
-1
32
Output
-0.500
101.800
2500999.500
1.000
2591.500
Notes
It is guaranteed that n ⩽ 30. An array is enough to store the coefficients. Do not
use heap memory.
Your program will not be compiled and linked against the math library, so
do not use the functions in .
The evaluation of P (xi) at a given point xi
should be done using only one loop
without call to standard library functions. Think about how to do this efficiently.
Problem 3. GCC argument descriptor
Problem background
To compile C/C++ code, we need to execute a command that calls the compiler
with some arguments. For example:
gcc hello.c -o hello.exe -std=c17 -Wall -Wpedantic -Wextra
This command compiles the C source code file hello.c with gcc, setting the
output file to be hello.exe, setting the language standard to be ISO C17, and
enabling some kinds of warnings and errors by -Wall -Wpedantic -Wextra.
Taking a look at GCC's manual, you will find an overwhelmingly long list of
supported arguments. Is there a tool that can generate some explanations of
the arguments, or at least for some of the most common ones? For example,
suppose the name of that tool is gcc_descriptor.exe (without .exe on Mac OS
X and Linux). It would be helpful if the following command (with .\ replaced by
./ on Mac OS X and Linux)
.\gcc_descriptor hello.c -o hello.exe -std=c17 -Wall -Wpedantic -Wextra
could print
hello.c: C source code as input file.
-o hello.exe: Place the primary output in file hello.exe.
-std=c17: Set the language standard to ISO C17.
-Wall: Enable all the warnings about constructions that some users consider
questionable, and that are easy to avoid (or modify to prevent the warning).
-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject
all programs that use forbidden extensions.
-Wextra: Enable some extra warning flags that are not enabled by -Wall.
Your task is to implement such a tool that generates explanations for some very
common GCC arguments.
Problem description
Write a program that accepts command-line arguments, which are the
arguments that we want to pass to GCC, and print the descriptions for them.
The supported kinds of arguments are as follows.
1. -Wall
Description:
-Wall: Enable all the warnings about constructions that some users consider
questionable, and that are easy to avoid (or modify to prevent the warning).
2. -Wpedantic
Description:
-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject
all programs that use forbidden extensions.
3. -Wextra
Description:
-Wextra: Enable some extra warning flags that are not enabled by -Wall.
4. -Werror
Description:
-Werror: Make all warnings into errors.
5. -o xxx
Description:
-o xxx: Place the primary output in file xxx.
where xxx is replaced by the actual file name (see the example below). Note that
this option consists of two arguments, where the first one is -o and the second
one is the file name.
6. -I xxx
Description:
-I xxx: Add the directory xxx to the list of directories to be searched for header
files during preprocessing.
where xxx is replaced by the actual directory name (see the example below).
Note that this option consists of two arguments, where the first one is -I and
the second one is the directory name.
7. -std=xxx
Description:
-std=xxx: Set the language standard to yyy.
where xxx is replaced by the actual value (see the example below) and yyy is
replaced by the name of the standard according to the following table.
xxx yyy example example output
cN ISO CN c17 ISO C17
c++N ISO C++N c++20 ISO C++20
gnuN GNU dialect of CN gnu11 GNU dialect of C11
gnu++N GNU dialect of C++N gnu++14 GNU dialect of C++14
N consists of two digits. For example, the 2003 ISO C++ standard is named
C++03.
8. Other
Anything that does not match the patterns above is treated as an input file.
Description:
xxx: yyy as input file.
where xxx is replaced by the file name and yyy is replaced by the type of the file
according to the following table.
xxx yyy example
*.c C source code hello.c
*.h C/C++ header file stdio.h
*.cpp, *.C, *.cc, *.cxx C++ source code checker.cc, game.cpp
*.hpp, *.hxx C++ header file utils.hpp
Notes
There is no input for this problem. The arguments to be explained are given as
the command line arguments of your program.
It is guaranteed that the arguments are valid: Anything that does not match the
patterns in 1 ~ 7 must be a valid C/C++ source or header file name as described
in the table above. For the language standards (pattern 7), you don't need to
check whether the standard that it refers to actually exists. Things like -
std=c++100000 won't appear.
The names of the files and directories involved in the arguments do not contain
whitespaces or quotes.
The name following -o or -I is not a C/C++ source or header file.
Print the explanations in order of the arguments.
Please be extremely careful about the output contents, especially the
spaces, newlines and punctuations.
Example
Suppose the name of your program (executable) is my_program.exe (without
.exe on Mac OS X and Linux). If the following command (with .\ replaced by ./
on Mac OS X and Linux) is executed,
.\my_program -std=c++20 -Wall -Wpedantic -Wextra a.c b.hxx c.cpp -Werror -o
output_file -I /usr/local/boost_1_80_0/
the output is
-std=c++20: Set the language standard to ISO C++20.
-Wall: Enable all the warnings about constructions that some users consider
questionable, and that are easy to avoid (or modify to prevent the warning).
-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject
all programs that use forbidden extensions.
-Wextra: Enable some extra warning flags that are not enabled by -Wall.
a.c: C source code as input file.
b.hxx: C++ header file as input file.
c.cpp: C++ source code as input file.
-Werror: Make all warnings into errors.
-o output_file: Place the primary output in file output_file.
-I /usr/local/boost_1_80_0/: Add the directory /usr/local/boost_1_80_0/ to the list
of directories to be searched for header files during preprocessing.
Problem 4. 6174
The number 6174 is known as Kaprekar's constant after the Indian
mathematician D. R. Kaprekar. This number is renowned for the following rule:
1. Take any four-digit number, using at least two different digits (leading zeros
are allowed).
2. Arrange the digits in descending and then in ascending order to get two
four-digit numbers, adding leading zeros if necessary.
3. Subtract the smaller number from the bigger number.
4. Go back to step 2 and repeat.
The above process, known as Kaprekar's routine, will always reach its fixed point,
6174, in at most 7 iterations. Once 6174 is reached, the process will continue
yielding 7641 − 1467 = 6174. For example, choose 1459:
Write a program that simulates this process. Note that
The input number should not contain more than 4 digits and should
contain at least two different digits (i.e. not a repdigit like , , ...).
These numbers are said to be invalid.
The input number may contain less than 4 digits. For example, start with :
Hint
The functions given in [Problem 1] Basic knowledge may be helpful for this
problem.
Input format
On the first line, a nonnegative integer .
Then lines follow, the -th of which contains a nonnegative integer . It is
guaranteed that is representable by int.
Output format
For each of the input integers, either report that it is invalid or simulate the
Kaprekar's routine and print the steps (see below).
If for some the integer contains more than 4 digits, print xxx contains more
than 4 digits. where xxx is replaced with . If contains no more than 4
9541
8820
8532
− 1459
− 288
− 2358
= 8082
= 8532
= 6174
1111 2222
9
9000
9981
8820
8532
− 9
− 1899
− 288
− 2358
= 8991
= 8082
= 8532
= 6174
n
n i xi
xi
n
i xi
xi xi
digits but is a repdigit, print xxx is a repdigit. where xxx is replaced with xi
.
A step in the Kaprekar's routine should be printed in the form xxx - yyy = zzz,
where xxx, yyy and zzz are replaced with the corresponding numbers. Note that
leading zeros are not printed (see the example below). The process stops when
zzz reaches 6174.
If the input is already 6174, you should print nothing and start processing next
input.
You don't have to start printing after all inputs are consumed! Do not waste
efforts saving the things to be printed.
Example
Input
5
123456
0
22
4444
1459
Output
123456 contains more than 4 digits.
0 is a repdigit.
2200 - 22 = 2178
8721 - 1278 = 7443
7443 - 3447 = 3996
9963 - 3699 = 6264
6642 - 2466 = 4176
7641 - 1467 = 6174
4444 is a repdigit.
9541 - 1459 = 8082
8820 - 288 = 8532
8532 - 2358 = 6174
Note
Your program will not be compiled and linked against the math library, so
do not use the functions in .
Problem 5: CPU emulator
Description
To understand how the computer executes your program, let me give a short
introduction to CPU. The CPU basically contains 2 parts: registers and ALU. You
can consider registers as an array. Each cell of this array has a name (for
example, x0, x1, x2, …, x31 in RISC-V), and can store a single number. Arithmetic
calculations (addition, subscription, multiplication, division, ...) are done by ALU.
When executing your program, the assembly codes (written in binary) are sent
to CPU. Each line of assembly code specifies some operation of registers, and
CPU will use a special register named PC (program counter) to identify the
current execution line number. For example, if the code is add x3 x1 x2, then
CPU will take the values in registers x1 and x2, add them up and store the result
in the register x3. This is shown in the figure below (only 5 registers shown here).
Then, the CPU increments PC by 1 to execute the next instruction.
In this problem, you are required to implement a toy emulator which is able to
execute a very simple assembly language (similar to RISC-V). You only need to
consider 6 registers, named x0, x1, x2, x3, x4 and x5, all in lowercase, and each
register stores a 16-bit integer. The x0 register is a special one, whose value is
always zero. Also, there are only has 6 instructions in this assembly language:
add, sub, mul, div, let and print, which are introduced below.
In this problem, we use a 16-bit machine code. An example of a 16-bit
instruction is as follows.
The instructions add, sub, mul and div are similar. The syntax is shown in the
following table. Note that in these operations, the imm part is discarded.
Instruction Syntax Explanation OpCode
add add r1 r2 value in r1 += value in r2 000
sub sub r1 r2 value in r1 -= value in r2 001
mul mul r1 r2 value in r1 *= value in r2 010
div div r1 r2 value in r1 /= value in r2 011
The let instruction is used to assign value to a register. The syntax is:
Instruction Syntax Explanation OpCode
let let r1 imm value in r1 = imm 100
where r1 is the name of some register (x0 to x5), and imm is an integer within the
range . In this instruction, the r2 part is discarded and the imm part is
used. For example, the execution of instruction let x1 80 is shown below.
Also, we need a print instruction to print the value in some register so that we
can test whether the execution result is correct. For example, if the value in
register x1 is 5, your emulator should print x1 = 5 on the screen when the
instruction print x1 is executed. The r2 part is also discarded in this instruction.
Instruction Syntax Explanation OpCode
print print r1 print value in r1 101
[0, 2
7 − 1]
Notes:
1. In the div instruction, the division result is truncated towards zero, and the
denominator will always be non-zero.
2. Value in all registers should be initialized to 0 before execution.
3. Remember that the value in x0 is always zero. Any instruction that attempts
to modify it should have no effect.
4. We only consider unsigned immediate in this problem.
Input format
The first line of the input is a number n, indicating the total lines of code.
The following n lines are the instructions written in hexadecimal.
Output format
Your emulator should execute the input program, and only print the result
when a print instruction is executed. It is guaranteed that the input and
output are both non-empty.
Example
Input:
2
0x8401
0xA400
Output:
x1 = 1
Input:
10
0x8401
0x8801
0x8C01
0x9001
0x9401
0xA400
0xA800
0xAC00
0xB000
0xB400
Output:
x1 = 1
x2 = 1
x3 = 1
x4 = 1
x5 = 1
Explanation:
0x8401 is 1000010000000001 in binary, whose opcode is 100, r1 is 001 (x1), r2
is 000 (x0) and imm is 0000001 (1). From the opcode we know that this is a
let instruction, so the instruction is let x1 1.
0xA400 is 1010010000000000 in binary, whose opcode is 101 and r1 is 001
(x1). This is a print instruction, so the instruction is print x1.
Note
Your program will not be compiled and linked against the math library, so
do not use the functions in .