Handed out: 1/14/03
You should have an account on the Unix machines in room 320. If your name is John Q. Smith, your account will be jqsmith. The account consists of your first initial, your middle initial and your last name, up to a total of at most 8 characters. If you do not have a middle initial, an x will be used. Your password will initially be new1User. The password is case-sensitive. That is, you must use the exact capitalization shown. You should change your password using the passwd command.
If you have difficulty with your account, ask for help.
Before starting for the first time, please run the
following commands in a terminal window. (Open a terminal window
by right-clicking the mouse on the background and
selecting terminal from the tools menu.)
chmod 700 ~
cd /export/stu/ugrad/skeleton
cp .cshrc .login ~
cd ~
|
You might want to look at the following links.
All of the numbers for this assignment are nonnegative integers.
The greatest common divisor of two numbers n and m, written gcd(m,n), is the largest number k such that k is a divisor of both m and n. For example,
One way to find the greatest common divisor of m and n is to try each possible number, starting at the smaller of m and n and counting down until a divisor of both is found. Here is a function definition in C++ that uses this approach. It uses type long for integers. We have not discussed functions yet, but look at the part inside the function that does the work.
long gcd(long m, long n)
{
long k;
if(m < n) k = m;
else k = n;
while(n % k != 0 || m % k != 0) k--;
return k;
}
Although this approach works for small values, it is
extremely slow when m and n are large.
Another approach is to find the prime factorization of m and n, and to multiply together the common factors. That also turns out to be extremely slow for large numbers.
The Greek mathematician Euclid discovered a simple and efficient way to find the greatest common divisor of two numbers quickly. It is based on the following facts.
(1) gcd(0,n) = nwhere n mod m is the remainder when you divide n by m. (It is written n % m in C++.) An algorithm starts with two variables i and j set to m and n, respectively. At each stage, it replaces i and j by j mod i and i, respectively, using the fact
(2) gcd(m,n) = gcd(n mod m, m) (when m > 0)
gcd(i,j) = gcd(j mod i, i) (when i > 0)That way, even as i and j change, gcd(i,j) is always the same. Here is a sample run for m = 10 and n = 36.
i j
_____ _____
10 36
6 10
4 6
2 4
0 2
Notice that gcd(10,36) = gcd(6,10) = gcd(4,6) = gcd(2,4) = gcd(0,2) = 2.
So, as i and j change, gcd(i,j)
is always the same as gcd(m,n),
even though m and n do not change.
The loop stops when i = 0, with the answer being j.
Question: We tried Euclid's algorithm for m = 10 and n = 36. Does Euclid's algorithm work for the case of m = 36 and n = 10? Try it. What is 10 mod 36?
Write a program that reads two integers m and n and prints the greatest common divisor of m and n. It should use Euclid's algorithm.
Make your program print the values of i and j each time around the loop, in a form similar to that shown in the description, so that you can see whether it is performing the algorithm correctly. Test your program. Do not just presume that it works. Test it on several different pairs of numbers.
Print this version. Then make a copy of your program, and remove the debugging prints so that the program only shows the greatest common divisor of the two numbers. Also print the second version.
Turn in both printouts. Please put both your name and the assignment number at the top of both versions, as comments.
Be careful about how you update i and j in the loop. Think about how to do it, then check it by hand to see whether it works.
// -Your name here- // Computer science 2611 // Programming assignment 1, submission 1 // Spring 2003 // -Date here-
See the hint and checklist page for more suggestions.