解析CSE 3100、GCD因数分解讲解、辅导GCD/Matlab、解析Matlab语言程序 CSE 3100 Systems Programming

Homework #3 Due: 10/01/2018

Note that this assignment is due by midnight on October 1. You have more time to work on this assignment.

Complete your work in the hw3 folder. Remember to pull, add, commit, and push. Do NOT add object

file and executables in your repo.

Exercise 1. (50 points) GCD and factorization. Finding factors for large numbers is a hard problem.

However, the problem for small numbers is not hard. In this assignment, you implement a function that

finds all prime factors of a given number, and a function that finds the greatest common divisor (GCD) of

two numbers. The prototype of the two functions is:

unsigned int f a c t o r i n t e g e r (unsigned int n , unsigned int n f ) ;

unsigned int fi n d g c d (

unsigned int p f1 , unsigned int n f1 ,

unsigned int p f2 , unsigned int n f2 ,

unsigned int n f ) ;

factor integer() finds all prime factors of an unsigned integer n (and n > 1), stores them in a dynamically

allocated array in non-decreasing order, and returns the starting address of the array. The number

of prime factors in the array is stored in an integer pointed to by nf. The product of all elements in the

factor array should be n. Return NULL if n is 0 or 1.

For example, if n is 20, the returned array has three elements: 2, 2, 5, and *nf is 3. If n is 7, the returned

array has one element: 7, and *nf is 1.

find gcd() finds the prime factors of the greatest common divisor (GCD) of two numbers. The two

numbers are given as arrays of prime factors listed in non-decreasing order. pf1 is a pointer to the array of

prime factors for the first number and nf1 is the number of elements in the array. Similarly, pf2 is a pointer

to the array of prime factors for the second number and nf2 is the number of elements in the array. As you

may have guessed, pf1, nf1, pf2, and nf2 are generated by calling factor integer(). If the GCD of the

two numbers is greater than 1, the function returns the address of an array that stores the prime numbers

of the GCD in non-decreasing order and *nf is the number of elements in the array. The function returns

NULL if the GCD of the two numbers is 1 (i.e., the two numbers are co-prime), or either of pf1 and pf2 is

NULL.

Your main work is to implement the factor integer() and find gcd() functions (and any helper

functions you may choose to create). However, you will also need to add some lines of code near the end of

main() to clean up.

Here are some sample sessions of running the program. You can check with a calculator (e.g., using

Python and copy/paste!) if a number is indeed the product of all its prime factors and if the GCD can

divide both given numbers.

$./gcd-factor 64 192

64=2 * 2 * 2 * 2 * 2 * 2

192=2 * 2 * 2 * 2 * 2 * 2 * 3

gcd(64,192)=2 * 2 * 2 * 2 * 2 * 2=64

$./gcd-factor 123456789 1234567890

123456789=3 * 3 * 3607 * 3803

1234567890=2 * 3 * 3 * 5 * 3607 * 3803

gcd(123456789,1234567890)=3 * 3 * 3607 * 3803=123456789

./gcd-factor 2000000000 1999999973

2000000000=2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5

1999999973=1999999973

gcd(2000000000,1999999973)=1=1

1

Exercise 2. (50 points) Sparse polynomials. Many of the polynomials arising in practice are sparse,

i.e., they have a number of non-zero coefficients that is much smaller than the degree of the polynomial. In

these cases using an array representation is wasteful, and these polynomials are best represented as a linked

list. The provided template code defines structures for representing polynomials as linked lists along with

incomplete definitions of several functions that operate on them. Each function definition is preceded in the

template code by a comment detailing the expected functionality; read this carefully and follow all stated

requirements. Among others, these functions are required to read the input, dynamically allocate and free

the memory needed to store polynomials, compute the derivative of a polynomial, and compute the difference

of two polynomials. The full implementation of a function that prints a give polynomial represented as linked

list is also provided; do not modify this function to preserve the output format shown below.

Input: Your program should read from the standard input several pairs of whitespace separated integers,

with each pair representing the coefficient and exponent of a monomial. You may assume that exponents are

non-negative and that monomials are given in strictly decreasing exponent order (in particular, the input

will not contain multiple monomials with the same exponent). Coefficients are arbitrary integers and may

include zeros, however, only monomials with non-zero coefficients must be stored in the linked list. The

monomial with exponent 0 (constant term) is always present as the last monomial of the input, possibly

with a coefficient of 0. You may assume that all exponents and coefficients (both of input polynomials and

of polynomials computed from them) fit within 32-bit signed integers.

For example, the following input

7 10 0 8 -4 3 -2 1 0 0

represents the polynomial

(note the two monomials with zero coefficients that are omitted).

Output: The provided main() exercises the functions implementing polynomial operations and is expected

to produce output similar to the one listed below when your implementation is complete. Do not modify the

main function except for including cleanup code required to avoid memory leaks.

% ./poly

Enter polynomial: 1 0

P(x): 1

P’(x): empty polynomial

P(x) - P’(x): 1

P’(x) - P(x): - 1

P(x) - P(x): empty polynomial

% ./poly

Enter polynomial: 7 10 0 8 -4 3 -2 1 0 0

P(x): 7 x^10 - 4 x^3 - 2 x

P’(x): 70 x^9 - 12 x^2 - 2

P(x) - P’(x): 7 x^10 - 70 x^9 - 4 x^3 + 12 x^2 - 2 x + 2

P’(x) - P(x): - 7 x^10 + 70 x^9 + 4 x^3 - 12 x^2 + 2 x - 2

P(x) - P(x): empty polynomial

% ./poly

Enter polynomial: 1 10 10 9 90 8 720 7 0 6 0 5 0 4 3 3 6 2 1 1 1 0

P(x): x^10 + 10 x^9 + 90 x^8 + 720 x^7 + 3 x^3 + 6 x^2 + x + 1

P’(x): 10 x^9 + 90 x^8 + 720 x^7 + 5040 x^6 + 9 x^2 + 12 x + 1

P(x) - P’(x): x^10 - 5040 x^6 + 3 x^3 - 3 x^2 - 11 x

P’(x) - P(x): - x^10 + 5040 x^6 - 3 x^3 + 3 x^2 + 11 x

P(x) - P(x): empty polynomial