课程名称︰计算机程式
课程性质︰电机系大一必修
课程教师︰林宗男
开课学院：电资学院
开课系所︰电机工程学系
考试日期（年月日）︰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。