$24
Lab 03 more repetition Solution
Int ro d uc t i o n
Important: Please read Lab Guidelines before you continue.
This lab requires you to do 3 exercises, mainly on functions with address parameters, repetition control structure, and pseudo-random numbers. To receive the attempt mark for this lab assignment, you must submit all 3 programs and get a passing feedback mark for each of the program.
The maximum number of submissions for each exercise is 15.
If you have any questions on the task statements, you may post your queries on the relevant IVLE discussion forum. However, do not post your programs (partial or complete) on the forum before the deadline!
Please be reminded that lab assignments must be done in your own effort.
Important notes applicable to all exercises here:
As you have already gone through two rounds of lab assignment and know our expectation by now, we are going to be stricter in our marking schemes. That means mistakes will be more heavily penalised from now on. This is to give you a more accurate feedback and to better prepare you for PE2.
Note that you are NOT allowed to use array, string functions or recursion for the exercises here. Using it would amount to violating the objective of this lab assignment.
You are NOT allowed to use global variables. (A global variable is one that is not declared in any function.)
You are free to introduce additional functions if you deem it necessary. This must be supported by well-thought-out reasons, not a haphazard decision. By now, you should know that you cannot write a program haphazardly.
In writing functions, please put function prototypes before the main() function, and the function definitions after the main() function.
1 E xerc i s e 1: Ho urg l as s
1.1 Learning objectives
Using selection and repetition statements.
Writing function with address parameters.
Problem solving.
1.2 Task statement
Write a program hourglass.cto read in 3 positive integers: aand bwhich are the durations of two hourglasses, and cwhich is the duration you want to measure. All values are in minutes. The program then determines if you can measure cexactly using the hourglasses, and if so, the number of times you need to flip the two hourglasses such that the total number of flips is the minimum.
You may assume that a< b< c, and that you can only use one hourglass at a time, as the desk is too small to accommodate two hourglasses at the same time.
For example, if you have 4-minute and 7-minute hourglasses, and you want to measure 28 minutes, you need only flip the 7-minute hourglass 4 times. If you want to measure 29 minutes, the solution is to flip the 4-minute hourglass twice and the 7-minute hourglass thrice, giving a total of 5 flips. If you want to measure 9 minutes, then it is impossible to solve.
As another example, if you have 6-minute and 9-minute hourglasses, and you want to measure 42 minutes. There are two ways: flip the 6-minute hourglass once and the 9-minute hourglass four times, hence a total of 5 flips; or flip the 6-minute hourglass four times and the 9-minute hourglass twice, hence a total 6 flips. The first solution is better as it gives the minimum total number of flips.
Your program should include a function int compute_flips(int, int, int, int *, int *). It returns 1 (true) if it is possible to measure the given duration c, or 0 (false) if impossible. The first 3 parameters are a, band c. The function passes back the number of flips for the two hourglasses through the last two parameters, if it is possible to measure. (If it is not possible to measure, then the values in these last two parameters are immaterial.)
(The above description uses symbols such as a, b, and c. In your program, you should use more descriptive variable names.)
1.3 Sample run
Sample runs using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
Sample run #1:
gcc -Wall hourglass.c -o hourglass
hourglass
Enter 3 inputs: 4 7 29 Possible!
2 flip(s) for 4-minute hourglass and 3 flip(s) for 7-minute hourglass
Sample run #2:
Enter 3 inputs: 4 7 9
Impossible!
Sample run #3:
Enter 3 inputs: 6 9 42
Possible!
1 flip(s) for 6-minute hourglass and 4 flip(s) for 9-minute hourglass
1.4 Skeleton program and Test data
The skeleton program is provided here: hourglass.c
Test data: Input files | Output files
1.5 Important notes
The mandatory function compute_flips()as described in section 1.2 above. You must not change the function prototype given in the skeleton program, or marks will be deducted.
You may write other appropriate function(s) if necessary.
Hint: You may find some similarity between this exercise and the Coin Change problem you have seen in class.
1.6 Estimated development time
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
This exercise might take you a lot of time testing and debugging.
Devising and writing the algorithm (pseudo-code): 30 minutes
Translating pseudo-code into code: 15 minutes
Typing in the code: 15 minutes
Testing and debugging: 1 hour
Total: 2 hours
2 E xerc i s e 2: B i s ec t i o n Met ho d
2.1 Learning objectives
Using selection and repetition statements.
Using constant.
Writing function.
2.2 Task
Numerical analysis is an important area in computing. One simple numerical method we shall study here is the Bisection method, which computes the root of a continuous function. The root, r, of a function f is a value such that f(r) = 0.
How does bisection method work? It is best explained with an example. Given this polynomial
function p(x) = x3 + 2x2 + 5, we need to first provide two endpoints a and b such that the signs of p(a) and p(b) are different. For example, let a=-3 (hence p(a)=-4) and b=0 (hence p(b)=5).
The principle is that, the root of the polynomial (that is, the value r where p(r) = 0) must lie somewhere between a and b. So for the above polynomial, the root r must lie somewhere between -3 and 0, because p(-3) and p(0) have opposite signs. (NOT because -3 and 0 have opposite signs!)
This is achieved as follows. The bisection method finds the midpoint m of the two endpoints a and b, and depending on the sign of p(m) (the function value at m), it replaces either a or b with m (so m now becomes one of the two endpoints). It repeats this process and stops when one of the following two events happens:
when the midpoint m is the root, or
when the difference between the two endpoints a and b falls within a threshold, that is, when they become very close to each other. We shall set the threshold to 0.0001 for this exercise. Then the midpoint m is calculated as (a+b)/2, and this is the approximated root.
Figure 2 below shows the two endpoints a (-3) and b (0), their midpoint m (-1.5), and the function values at these 3 points: p(a) = -4, p(b) = 5, p(m) = 6.125.
Since p(m) has the same sign as p(b) (both values are positive), this means that m will replace b in the next iteration.
Figure 2. Graph of p(x) = x3 + 2x2 + 5
The following table illustrates the iterations in the process. The end-point that is replaced by the mid-point value computed in the previous iteration is highlighted in pink background.
iteration
endpoint
endpoint
midpoint
function value
function value
function value
a
b
m
p(a)
p(b)
p(m)
1
-3.000000
0.000000
-1.500000
-4.000000
5.000000
6.125000
2
-3.000000
-1.500000
-2.250000
-4.000000
6.125000
3.734375
3
-3.000000
-2.250000
-2.625000
-4.000000
3.734375
0.693359
4
-3.000000
-2.625000
-2.812500
-4.000000
0.693359
-1.427002
5
-2.812500
-2.625000
-2.718750
-1.427002
0.693359
-0.312714
6
-2.718750
-2.625000
-2.671875
-0.312714
0.693359
0.203541
7
-2.718750
-2.671875
-2.695312
-0.312714
0.203541
-0.051243
8
-2.695312
-2.671875
-2.683594
-0.051243
0.203541
0.076980
9
-2.695312
-2.683594
-2.689453
-0.051243
0.076980
0.013077
10
-2.695312
-2.689453
-2.692383
-0.051243
0.013077
-0.019031
11
-2.692383
-2.689453
-2.690918
-0.019031
0.013077
-0.002964
12
-2.690918
-2.689453 -2.690186 -0.002964
0.013077
0.005059
13
-2.690918
-2.690186
-2.690552
-0.002964
0.005059
0.001048
14
-2.690918
-2.690552
-2.690735
-0.002964
0.001048
-0.000958
15
-2.690735
-2.690552
-2.690643
-0.000958
0.001048
0.000045
16
-2.690735
-2.690643
-2.690689
-0.000958
0.000045
-0.000456
Hence the root of the above polynomial is -2.690689 (because the difference between a and b in the last iteration is smaller than the threshold 0.0001), and the function value at that point is -0.000456, close enough to zero.
(Some animations on the bisection method can be found on this website: Bisection method. Look at the first one.)
Write a program bisection.cthat asks the user to enter the integer coefficients (c3, c2, c1, c0) for a polynomial of degree 3: c3*x3 + c2*x2 + c1*x + c0. It then asks for the two endpoints,
which are real numbers. You may assume that the user enters a continuous function that has a real root. You may use the doubledata types for real numbers. To simplify matters, you may also assume that the two endpoints the user entered have function values that are opposite in signs.
Your program should have a function double polynomial(double, int, int,
int, int)to compute the polynomial function value. This is mandatory.
In the output, real numbers are to be displayed accurate to 6 decimal digits (see output in sample runs below).
2.3 Sample runs
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
Only the last 2 lines shown in bold purple are what your program needs to produce. The iterations are shown here for your own checking only.
The sample run below shows the output for the above example. Note that the iterations end when the difference of the two endpoints is less than 0.0001, and the result (root) is the midpoint of these two endpoints.
gcc -Wall bisection.c -o bisection
bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 1 2 0 5
Enter endpoints a and b: -3 0
#1: a = -3.000000; b = 0.000000; m = -1.500000
p(a) = -4.000000; p(b) = 5.000000; p(m) = 6.125000
#2: a = -3.000000; b = -1.500000; m = -2.250000
p(a) = -4.000000; p(b) = 6.125000; p(m) = 3.734375
#3: a = -3.000000; b = -2.250000; m = -2.625000
p(a) = -4.000000; p(b) = 3.734375; p(m) = 0.693359
#4: a = -3.000000; b = -2.625000; m = -2.812500
p(a) = -4.000000; p(b) = 0.693359; p(m) = -1.427002
#5: a = -2.812500; b = -2.625000; m = -2.718750
p(a) = -1.427002; p(b) = 0.693359; p(m) = -0.312714 (... omitted for brevity ...)
#15: a = -2.690735; b = -2.690552; m = -2.690643
p(a) = -0.000958; p(b) = 0.001048; p(m) = 0.000045
#16: a = -2.690735; b = -2.690643; m = -2.690689
p(a) = -0.000958; p(b) = 0.000045; p(m) = -0.000456 root = -2.690689
p(root) = -0.000456
The second sample run below shows how to find the square root of 5. For polynomial where there are more than one real root, only one root needs to be reported.
$ bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 0 1 0 -5
Enter endpoints a and b: 1.0 3.0
#1: a = 1.000000; b = 3.000000; m = 2.000000
p(a) = -4.000000; p(b) = 4.000000; p(m) = -1.000000
#2: a = 2.000000; b = 3.000000; m = 2.500000
p(a) = -1.000000; p(b) = 4.000000; p(m) = 1.250000 (... omitted for brevity ...)
#16: a = 2.236023; b = 2.236084; m = 2.236053
p(a) = -0.000201; p(b) = 0.000072; p(m) = -0.000065 root = 2.236053
p(root) = -0.000065
The third sample run below shows how to find the root of the function 2x2 - 3x. Since the midpoint of the given endpoints a and b is 1.5 which is the root of the function, the loop ends after the first iteration.
$ bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 0 2 -3 0
Enter endpoints a and b: 0.5 2.5
#1: a = 0.500000; b = 2.500000; m = 1.500000
p(a) = -1.000000; p(b) = 5.000000; p(m) = 0.000000 root = 1.500000
p(root) = 0.000000
2.4 Skeleton program and Test data
The skeleton program is provided here: bisection.c
Test data: Input files | Output files
2.5 Important notes
You are reminded that only two lines of output (those shown in bold purple in the sample runs above) are the required output. Your program is not to display the iterations in your output.
The loop should terminate when the midpoint is the root, or when the two endpoints a and b are very close to each other, not when the two function values p(a) and p(b) are very close to each other. This is a common mistake.
You should define a constant for the threshold (0.0001) in your program.
The mandatory function is polynomial()as described in section 2.2 above. You must not change the function prototype given in the skeleton program, or marks will be deducted.
Hint: You may use the fabs()function in math.h.
2.6 Estimated development time
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
This exercise might take you a lot of time testing and debugging.
Devising and writing the algorithm (pseudo-code): 30 minutes
Translating pseudo-code into code: 15 minutes
Typing in the code: 15 minutes
Testing and debugging: 1 hour
Total: 2 hours
3 E xerc i s e 3: Mo nt e Carl o
3.1 Learning objectives
Using the selection and repetition statements.
Generating pseudo-random numbers.
Writing function.
3.2 Task statement
(Note: You should have read through Week 6 Discussion Sheet "Section III Exploration -- Question 6" on the functions rand()and srand()before you attempt this exercise.)
p, or pi, is a well-known constant 3.14159265..., which is the ratio of a circle's circumference to its diameter.
Consider the 1. Its area is pi/4.
unit circle which, in cartesian coordinates, is defined by the equation x*x + y*y = pi, and hence the area of the part of the unit circle that lies in the first quadrant is
Figure 3.
Imagine that you throw darts at random at the unit square (in the first quadrant) so that the darts land randomly on (x, y) coordinates satisfying 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1. Some of these darts will land inside the unit circle's quadrant. As shown in Figure 3 above, the unit square is the square box which contains the unit circle's quadrant (the purple-shaded region).
Since the unit circle's quadrant has area pi/4 and the unit square has area 1, if you program it such that the darts always land within the unit square, then the proportion of darts you randonly throw that land in the unit circle's quadrant will be approximately pi/4.
(How do you determine if a dart lands inside the unit circle's quadrant?)
Write a program montecarlo.cthat asks the user to enter the number of darts to throw.
Pass this value to a function throwDarts(int). This is a mandatory function.
In the function, generate the appropriate random numbers to simulate the throwing of darts. Calculate the number of darts that land inside the unit circle's quadrant. (Consider the dart to
have landed inside if x2 + y 2 ≤ 1, i.e. including the unlikely event that it lands exactly on the boundary of the unit circle's quadrant.) Return this number back to the caller, which then computes the approximate value of pi.
It is reasonable to expect that the more darts we throw, the more accurately the computed value of piapproximates the real value of p.
Your program should output the number of darts that landed inside the unit circle's quadrant, and the value of picomputed correct to 4 decimal places.
3.3 Sample runs
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
gcc -Wall montecarlo.c -o montecarlo
montecarlo
How many darts? 5000
Darts landed inside unit circle's quadrant = 3934 Approximated pi = 3.1472
Second sample run:
$ montecarlo
How many darts? 90000000
Darts landed inside unit circle's quadrant = 70686491 Approximated pi = 3.1416
3.4 Skeleton program and Test data
The skeleton program is provided here: montecarlo.c
No test data since your program generates random values.
3.5 Important notes
Write a function int throwDarts(int)to take in the number of darts, and compute and return the number of darts that landed inside the unit circle. The caller than uses this result to compute the value of pi. This is a mandatory function. You must not change the function prototype given in the skeleton program, or marks will be deducted.
Ensure that the random values generated are within the desired range.
The rand()function returns an integer in the range [0, RAND_MAX]. The constant
RAND_MAX is defined in <stdlib.h. You may use printf("%d\n", RAND_MAX);to see its value. You may need to use RAND_MAX in your program to ensure that the generated random values are real numbers in the range [0.0, 1.0].
You should test your program with several values of the numbers of darts to be thrown, some of which should be very large (but within the range of int).
Since your program generates random values, there will not be any test data to test your program. Hence, CodeCrunch will not be able to perform tests on your program. It will give you a grade of "E", which you may ignore. Your grader will go through your program manually to check.
3.6 Estimated development time
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
Devising and writing the algorithm (pseudo-code): 20 minutes
Translating pseudo-code into code: 5 minutes
Typing in the code: 10 minutes
Testing and debugging: 15 minutes
Total: 50 minutes
4 Dead l i ne
The deadline for submitting all programs is 5 October 2013, Saturday, 9am. Late submission will NOT be accepted.
0
Introduction
1
Exercise 1: Hourglass
1.1
Learning objectives
1.2
Task statement
1.3
Sample run
1.4
Skeleton program and Test data
1.5
Important notes
1.6
Estimated development time
2
Exercise 2: Bisection Method
2.1
Learning objectives
2.2
Task statement
2.3
Sample runs
2.4
Skeleton program and Test data
2.5
Important notes
2.6
Estimated development time
3
Exercise 3: Monte Carlo
3.1
Learning objectives
3.2
Task statement
3.3
Sample runs
3.4
Skeleton program and Test data
3.5
Important notes
3.6
Estimated development time
4
Deadline
Aaron Tan
Sunday, September 15, 2013 02:59:20 PM SGT
