Description

C COMPUTER PROGRAMMING（I）
December 14, 2023

Exam rules
● Only Dev-C++ can be used for the exam.
● If your codes cannot be compiled by Dev-C++, it is considered as syntax error. ● Please save your codes as a c source file named after your student ID each problem.
ex. B123456789_a.c, B123456789_b.c, B123456789_c.c …
● If your codes cannot output the desired result, your points will be deducted.
● No reason for late submission.
● It is forbidden to search for information during the exam.
● The cheaters will get zero point.

Please design your program to complete the following problems.

a. (20 points)
Euclidean algorithm is a technique for finding the greatest common divisor (GCD) of two numbers. GCD is the largest number that can be divided between two without leaving a remainder.

Euclidean algorithm works as follows:
1. You take two numbers. If one number is greater than another number, divide the larger number by the smaller number and take the remainder.
2. Then, replace the larger number with the smaller number, and replace the smaller number with the remainder from step 1.
3. Repeat the process: divide the new larger number by the new smaller number and take the remainder.
4. Continue this process of substitution and division until the remainder is 0.
5. When the remainder is 0, the divisor in this step is the GCD of the original two numbers.
Please read the attachment “GCD.txt”, where each line contains two numbers, and then implement a recursive function to calculate the GCD of each line.
Sample output:

b. (20 points)
Tower of Hanoi is a mathematical puzzle where we have three towers and n disks.

To move n disks from tower A to tower C, using tower B as the intermediary, a rudimentary algorithm would look like this:
1. Move n−1 discs from A to B
2. Move one disc from A to C
3. Move n−1 discs from B to C
Please let the user enter the number of disks, then use a recursive function to output the order and number of moves.

Note:
(1) 1 <= N <= 10
(2) Your code should be able to input and output repeatedly.

Sample output:

c. (20 points)
Pascal’s triangle is a special triangle that is named after the French mathematician Blaise Pascal. The numbers in Pascal’s triangle are placed in such a way that each number is the sum of two numbers just above the number.

Please let the user enter an integer N, then use a recursive function to output the first N levels of Pascal’s triangle.
Note:
(1) 1 <= N <= 15
(2) Print each element using “%5d”.
(3) Print each whitespace character using “%5c”.
(4) Your code should be able to input and output repeatedly.

Sample output:

d. (20 points)
Please read the attachment “Student.txt”, where each line contains the student’s student number, name, Chinese, English, and math scores. Then define a structure array to store the information, and then use a recursive bubble sort function to sort these elements according to different items.

Note:
(1) The maximum length of student name is 10.
(2) Sort student ID by ascending order.
(3) Sort student name from A to Z.
(4) Sort scores by descending order.
(5) Implement swap operation by pointer.
(6) After finishes any operation, print whole array.
(7) Your code should be able to input and output repeatedly.

Sample output:

e. (20 points)
A stack is a linear data structure in which nodes can be inserted and removed from only one side of the linked list.
In a stack, we always use a pointer called top to track the last node present in the linked list.

Please read the attached file “Stack.txt” to implement a linked list containing 100 different integer nodes, and then provide a function menu to perform the stack operations:

(1) Push : Insert new node with an integer at the top of the stack.
*You can only add new node using malloc()
(2) Pop : Remove the top node from the stack and return the value.
*You should check whether stack is empty, then release memory using free()
(3) Reverse : Reverse the order of nodes in the stack by push and pop.
(4) Search : Check if a node containing the target value in the stack.
Returns the node position if it exists, otherwise outputs not found. *The first node with the target value is the target node.

Note:
(1) You should perform any operation by function call.
(2) After finishes any operation, print whole stack.
(3) Print each element using “%7d”, newline each 5 elements.
(4) Your code should be able to input and output repeatedly.

Sample output: