課程名稱︰計算機程式
課程性質︰電機系大一必修
課程教師︰林宗男
開課學院：電資學院
開課系所︰電機工程學系
考試日期（年月日）︰2014/11/19
考試時限（分鐘）：180分鐘(上機考)
是否需發放獎勵金：是
試題 :
Problem 1 Least Common Multiplier (15%)
Description:
Given a set of positive integers, compute their least common multiplier. For
example, if you are given 2, 3, 4, and 5, then the least common multiplier is
60, because 60 is the smallest multiplier of 2, 3, 4, and 5.
Input:
The input has a line of positive integers. You must process all integers in
this line.
Output:
The output has the least common multiplier of input integers. Note that it
is guaranteed that all the computation can be done in the range of int.
Sample Input:
2 3 4 5
Sample Output:
60
==============================================================================
Problem 2 Convert the decimal number to the binary number (10%)
Description:
You should write a function to do the conversion. Please meet the format
requirements as follows.
You must use recursive function to solve this problem or you won’t get
any points.
Please consider input a large number, and try not to regard output as
one integer variable.
Input:
One integer
Output:
Binary sequence.
Sample Input:
17
Sample Output:
10001
Involved Concepts:
recursive function
==============================================================================
Problem 3 Compute the maximum number of consecutive 1's (10%)
Description:
Write a program to compute the maximum number of consecutive 1's in their
binary representation.
For example 7 has three consecutive 1's since its binary representation
is 00000111.
25 has two because its binary representation is 00011001.
Input:
A set of positive integers no more than 2147483647, one per line.
You must process them until EOF.
Output:
The maximum number of consecutive 1's in the input, one per line.
Sample Input:
7
Sample Output:
3
==============================================================================
Problem 4 Matrix Transposition (5%)
Description:
(a) Write a program which can dynamically allocate two-dimensional integer
array with size m x n where m and n are integers known during the execution
time.
(b) Write a function with the following function prototype
void transpose (const int* const * const input, int** output, const int m,
const int n);
Your function should transpose the two-dimensional array m x n input, placing
the n x m transposed two-dimensional array into output.
Input:
A matrix whose elements are 32-bit signed integers.
A matrix is specified by its number of rows and columns, followed with its
elements row by row.
For instance, a 3x3 identity matrix will be
3 3 // row, column
1 0 0 // row 1, elements seperated by single space
0 1 0 // row 2
0 0 1 // row 3
Output:
The resulting matrix, omitting number of rows and columns.
Sample Input1:
2 2
1 2
3 4
Sample Output1:
1 3
2 4
Sample Input2:
2 3
1 2 6
3 4 9
Sample Output2:
1 3
2 4
6 9
==============================================================================
Problem 5 Matrix Multiplication (10%)
Description:
Write a program that computes multiplication of two input matrices, whose
dimension are given at runtime.
You should allocate a matrix with proper dimension to hold the multiplication
of the two input matrices. In this problem, all the 3 matrices must be
allocated dynamically, say, using operator new.
***NOTE: YOU WILL RECEIVE NO POINT IF YOU USE STATIC ARRAY***
Input:
Two matrices A and B, whose elements are 32-bit signed integers.
Assume no overflow occurs and A*B is always legal.
A matrix is specified by its number of rows and columns, followed with its
elements row by row.
For instance, a 3x3 identity matrix will be
3 3 // row, column
1 0 0 // row 1, elements seperated by single space
0 1 0 // row 2
0 0 1 // row 3
Output:
The resulting matrix, omitting number of rows and columns.
Sample Input1:
2 2
1 2
3 4
2 1
7
9
Sample Output1:
25
57
Sample Input2:
2 2
1 2
3 4
2 2
1 1
1 1
Sample Output2:
3 3
7 7
==============================================================================
Problem 6 Calculating π (15%)
Description:
This problem is a bit tricky, but it’s a good exercise in writing a program
that actually does something neat. It will also familiarize you with using
random numbers. Using a “Monte Carlo” method – that is, a randomized
simulation – we can compute a good approximation of π. Consider a circle of
radius 1, center on the origin and circumscribed by a square, like so:
Imagine that this is a dartboard and that you are tossing darts at it
randomly. With enough darts, the ratio of darts in the circle to total darts
thrown should be the ratio between total darts in the area of the circle
(call it a) and the area of the square, i.e.,
(total darts)/(darts in the circle)=4/a.
We can use this ratio to calculate a, from which we can then find π=a/r^2 .
We can simplify the math by only considering the first quadrant, calculating
the ratio of the top right square’s area to the area of the single quadrant.
Thus, we will actually find a/4 , and then compute π =4×(a/4)/r^2
Hint:
(a) Define variables to store the x and y coordinates of a particular dart
throw. Initialize them to random doubles in the range [0, 1] (simulating one
dart throw). (Hint: remember that rand() returns a value in the range [0,
RAND_MAX]; we just want to convert that value to some value in [0, 1].)
(b) Place your x and y declarations in a loop to simulate multiple dart
throws. Assume you have a variable n indicating how many throws to simulate.
Maintain a count (declared outside the loop) of how many darts have ended up
inside the circle. (You can check whether a dart is within a given radius
with the Euclidean distance formula, d^2=x^2+y^2; you may find the sqrt
function from the <cmath> header useful.)
(c) Now use your loop to build a π-calculating function. The function should
take one argument specifying the number of dart throws to run (n from part
2). It should return the decimal value of pi, using the technique outlined
above. Be sure to name your function appropriately. Don’t forget to
initialize the random number generator with a seed. You should get pretty
good results for around 5,000,000 dart throws.
Input:
There is no input for this problem. Your code will be examined manually by
TAs and the score judge girl gives you is meaningless.
However, judge girl will help you to make sure that your program is
compilable.
Output:
Calculated π value.
==============================================================================
Problem 7 Find Maximum with Recursion (15%)
Description:
Write a recursive function recursiveMaximum that takes an integer array, a
starting subscript and an ending subscript as arguments, and returns the
largest element of the array. The function should stop processing and return
when the starting subscript equals the ending subscript.
***NOTE: YOU SHOULD STRICTLY ABIDE BY THE FUNCTION PROTOTYPE***
Input:
An integer indicating array size followed by an integer array (all in range
of int).
Then the starting subscript and ending subscript (both start from zero).
Output:
The maximal integer in the array interval between the two subscripts.
Sample Input1:
5
1 2 3 4 5
0
4
Sample Output1:
5
Sample Input2:
5
1 2 3 4 5
1
3
Sample Output2:
4
==============================================================================
Problem 8 Self-avoiding Random Walk (20%)
Description:
A self-avoiding random process in an N-by-N lattice:
1. Start in the middle.
2. Move to a random neighboring intersection but do not revisit any
intersection.
3. Outcome 1 (escape): research the edge of lattice.
4. Outcome 2 (dead end): no unvisited neighbors.
Write a program to calculate the chance of reaching a dead-end. Your program
will read two integer form the standard input. The first integer is N and the
second integer is the number of trials. In the following example, the user
will type 7 and 100. Your program will perform 48 number trials of 15-by-15
lattice self-avoiding random walk and output the likelihood of reaching a
dead-end.
***NOTE: THERE IS NO STANDARD ANSWER FOR THIS PROBLEM, NEGLECT THE SCORE
JUDGE GIRL GIVES YOU!***
Input:
The lattice size and trial number.
Output:
The likelihood of reaching a dead-end.
==============================================================================
Problem 9 奇幻之樹 (15%)
Description:
很久很久以前有個地方叫做奇幻村，奇幻村裡面的東西都很神祕，裡面有奇怪的房間、
奇怪的石像、奇怪的各種顏色的光、奇怪的會講話的動物、奇怪的會施法術的人、和各種
奇怪的自然現象。例如在奇幻村裡東西水會往高處流，太陽和月亮會隨機出現，東西會從
一個地方消失又從另一個地方冒出來，魚在陸地上游泳狗在天空中飛等等。最有趣的是有
一棵從上往下長的樹，它的根部是吊在空中的，但是枝幹卻往下長，從一開始的主幹開始
分為兩個支幹，這兩個支幹又各分為兩個支幹，然後再各自分叉，這樣一直一直這樣長下
去，伸到看不見的地洞裡去。更奇怪的是這棵樹在每個分叉的地方都會有一個凹洞，每個
洞裡都很神奇的刻著一個分數，而且這些分數的排列方式竟然還是有規律可循的！我們來
看看下面這個示意圖：
我們可以這樣想像：一開始有兩個不在樹上的假想分數 0/1 和 1/0 ，把這兩個數的分母
和分子相加可以得到 1/1 = (0+1)/(1+0) ，也就是這棵樹的樹根。接下來在 0/1 、1/1
、1/0 這三個分數之中，每兩個相鄰的分數就插入一個新的分數，讓分母和分子分別等於
相鄰的兩個分數的分母和與分子和，就可以得到次高的兩個分叉點的分數，也就是 1/2
= (0+1)/(1+1) ，2/1 = (1+1)/(1+0) ，接下來又可以把 0/1 、1/2 、1/1 、2/1 、
1/0 這串分數中每兩個相鄰的數字再插入一個分數，分母和分子分別等於左右兩個相鄰分
數的分母和與分子和，就可以得到第三高的四個分叉點 1/3 、2/3 、3/2 、3/1 。對於
每一個新插入的分數，都可以視為它是從它左右相鄰的兩個分數之中，在樹上位置較低的
那個分數所分叉下來的。這顆奇妙的樹就循著這樣的規則一直無窮盡的伸展下去，誰也不
知道它的盡頭。 奇幻村的居民發現這棵奇幻的樹有一些相當奇妙的性質，例如我們如果
從任意一個樹洞沿著支幹往上走，最後一定可以回到它的根部，如果一路上遇到的第一個
小於它的數字是 m/n ，第一個大於它的數字是 m'/n' ，那麼這個數的值就剛好會是
(m'+m)/(n'+n) ！還有一個更神奇的性質是，這棵樹如果無窮無盡的長下去，我們可以
知道世界上所有的最簡分數都會出現在這棵樹的某個樹洞裡，而且恰好只會出現一次。
Input:
以空白分隔的兩個數字m n(1 <= m, n <= 300000, m/n 是最簡分數)。
Output:
輸出該數字的左子節點與右子節點。
Sample Input:
3 5
Sample Output:
4 7
5 8
試題完
( 似2005 NPSC 國中組初賽 )
==============================================================================
備註：
(1) 試題以英文為主，僅最後一題為中文試題。
(2) 考試地點為計中，可以提早到調整電腦環境。
(3) 評分方式使用批改娘線上評測。但考試時批改娘出問題，後來改為開放測資，自行
測試完，再將程式碼上傳至ceiba。