| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11198 | GCD & LCM |
|
| 11199 | Tower of Hanoi |
|
Description
In this problem, you are required to write 2 finctions, gcd() and lcm(), that can help calculate the Greatest Common Divisor (最大公因數) and Least Common Multiple (最小公倍數). The main function will receive multiple positive integers as input values, and it will print the GCD and LCM of all numbers.
The definition of the 2 functions only calculate the GCD or LCM of 2 numbers. These functions are defined as following:
int gcd( int a, int b ) ; // This returns the GCD of positive integer a and b
int lcm( int a, int b ) ; // This returns the LCM of positive integer a and b
Please implement these 2 functions in a C source file, we will take care of the input and output.
Hint:
You should have already learned about how to calculate GCD by recursive or sequential ways, then we can calcute LCM of 2 numbers a and b by the result of GCD. Suppose D=gcd(a,b), and let a equals p*D and b equals q*D (p and q are relatively prime), then LCM of a and b should be p*q*D, or any other equivalent formats you prefer.
Input
The input contains several (at least 2) positive integers in a line. There are at most 10 integers in the input, and the result of Least Common Multiple can be stored by a 32-bit signed integer.
Output
Print 2 lines as the sample. The first line contains texts like "The Greatest Common Divisor is *." while the second line seems like "The Least Common Multiple is *."
In this homework, you are not required to take care the I/O, yet we hope you can stiil be inspired by the provide the main function.
Sample Input Download
Sample Output Download
Partial Judge Code
11198.cPartial Judge Header
11198.hTags
Discuss
Description
The Tower of Hanoi is a mathematical game or puzzle. It consists of 3 rods, and N disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
- Only 1 disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.
In this problem, you are given 3 rods named rod 1, 2 and 3, with N disks in a stack onto rod 1. Your mission is to move all disks onto disk 2 in minimal steps without breaking the riles provided. You have to print all moves.
You only have to implement the function "hanoi()" to achive the goal. Here is the defination of hanoi():
void hanoi( int rod_N, int rod_A, int rod_B, int rod_C ) ;
rod_N is the number of disks to be move right now, while rod_A, _B, and _C denoted the rod ID, which should be 1, 2, or 3. The function is to "Move the top rod_N disks from rod_A to rod_B via rod_C", and our main() function will hanoi(N, 1, 2, 3) without printing anything.
Input
The input consists of only one positive integers, denoting there are N disks given. At most 8 disks may be given.
Output
For the input, print all required steps of moving. Each move should be printed as an one-lined message like "Move from rod 1 to rod 2.\n". Please replace the rod ID on your own.