代做C200留学生、代做Computer Science、代写Python、代做Python编程

日期：2019-04-04 11:39

C200 Programming Assignment № 8

Computer Science

School of Informatics, Computing, and Engineering

March 30, 2019

Contents

Introduction 2

Problem 1: Newton Raphson Root Finding Algorithm 4

Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Newton-Raphson Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Derivative and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Newton-Raphson Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Starting Code for Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Interactive Session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Output for Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Problem 2: Bisection Method for Root Finding 8

Bisection Algorithm from Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . 8

Starting Code for Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Problem 3: pygame 9

A Snapshot of Your Pygames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Starting Code for Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Problem 4: Root Find Secant 12

Secant Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Secant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Starting Code for Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Output for Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Assignment №9 Convergence, Recurrence, and Animation Page 1

Problem 5: Integration 14

Simpson’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Starting Code to Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

File Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Output to Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Problem 6: Seriously, Again? 17

Starting Code to Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Output to Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Assignment №9 Convergence, Recurrence, and Animation Page 2

Introduction

In this homework, you’ll work on convergence, approximation, and animation. For convergence,

you will implement three algorithms for root finding–tools that are necessary in many areas like

finance, biology, and geology. For approximation, you will implement Simpson’s Rule–a means

of computationally determining an integral. For animation, you will have fun with pygames and

a bouncing...square! Lastly, you’ll have practice with recursion and transforming it.

Add a new folder to your C200 folder named Assignment9. In this folder, you’ll have the

following Python files:

– fignewton.py

– mybisect.py

– game1.py

– secant.py

– easycalc.py

– rec.py

Make sure and commit your project and modules by 11pm, Wednesday April 3th 2019.

As always, all the work should be your own. You will complete this before Wednesday April,

3, 2019 11:00P. You will submit your work by committing your code to your GitHub repository.

You will not turn anything in on canvas. If your timestamp is 11:01P or greater, the homework

cannot be graded. So do not wait until 10:58P to commit your solution. As always, all the work

should be your own.

Assignment №9 Convergence, Recurrence, and Animation Page 3

Problem 1: Root Finding with Newton

We discussed in lecture the general problem of finding roots and how ubiquitous it is.

f(x) = 0 x ∈ [a, b] (1)

x is called a root. The Newton-Raphson is an algorithm to find roots that uses a function and

its derivative.

x0 = estimate (2)

xn+1 = xn 

To remind you, a derivative is a function that characterizes the way a function changes as inputs

change. Line 4 is the typical definition. Line 5 is the usual approximation of the derivative used

in many devices(5)

Figure 1: The root is x. Our approximation xn moves toward the root as long as we’re larger

than our threshold. Observe in the graphic that f(b) is positive and f(a) is negative insuring that

there exists a root x, f(x).

The following listing shows two versions of the Newton-Raphson for:

The first uses the explicit derivative (which isn’t very scalable) done by hand. The second

uses the approximation. With λ functions we can easily approximate the derivative and use the

algorithm without any changes.

Assignment №9 Convergence, Recurrence, and Animation Page 4

Listing 1: newton.py

1 f = lambda x: x**6 - x - 1

2 fp = lambda x: 6*(x**5) - 1

3

4 def fpa(f):

5 h = .000001

6 return lambda x: (f(x+h)-f(x-h))/(2*h)

7

8 def newton(f,fp,x,tau):

9 def n(x,i):

10 while f(x) > tau:

11 print("{0} {1:.5f} {2:.5f}".format(i,x,f(x)))

12 x = x - f(x)/fp(x)

13 i += 1

14 return x

15 n(x,0)

16

17 newton(f,fp,1.5,.0001)

18 newton(f,fpa(f),1.5,.0001)

To complete this problem, you’ll need to become a little familiar with Python’s eval() function.

This function takes an expression as a string and returns the value of the expression. Here is a

short session for you to try:

Session Intractive

>>> "lambda x: 2*x"

’lambda x: 2*x’

>>> f = "lambda x: 2*x"

>>> f(2)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

TypeError: ’str’ object is not callable

>>> eval(f)(2)

4

>>> eval("3 + 4")

7

>>> kitty = "3 + x"

>>> hello = "lambda x: "

>>> eval(hello+kitty)(3)

6

>>>

Here are three runs of the completed program:

Assignment №9 Convergence, Recurrence, and Animation Page 5

Session Output

Function: x**6-x-1

tau: .001

x0: 1.5

interations: 26

0 1.50000 8.89062

1 1.30049 2.53726

2 1.18148 0.53846

3 1.13946 0.04924

Press any key to continue . . .

Function: x**6-x-1

tau: .001

x0: 100

interations: 5

0 100.00000 999999999899.00000

1 83.33333 334897975410.20740

2 69.44444 112156653932.12268

3 57.87037 37561036350.73944

4 48.22531 12579115030.90415

number of iterations exceeded...

Press any key to continue . . .

Function: x**6-x-1

tau: .0001

x0: 100

interations: 29

0 100.00000 999999999899.00000

1 83.33333 334897975410.20740

2 69.44444 112156653932.12268

#removed for readability

26 1.14271 0.08376

27 1.13488 0.00156

Press any key to continue . . .

Assignment №9 Convergence, Recurrence, and Animation Page 6

Deliverables Programming Problem 1

Get the code to run.

Run the interactive session using Python.

Change the code presented in the listing newton.py so that:

1. The user can input the function, the threshold tau, and the initial estimate x0.

2. There is a bound on the iterations. The bound on the iterations stops the

algorithm when the loop has equaled or exceeded the bound should it not

converge with the threshold tau.

3. The user can input a value for the bound on the iterations.

Three runs of the program are shown in the output.

Put your code into a new module named fignewton.py

Assignment №9 Convergence, Recurrence, and Animation Page 7

Problem 2: Bisection

In this problem you’ll implement the bisection method. The general idea is to take an interval

[a, b] where the root x? ∈ [a, b] exists and continually move halfway to either the left or right. I’m

using the algorithm as it’s presented in Elementary Analysis 2nd ed., Atkinson. You should be

excited you can interpret the pseudo-code! Here τ is our threshold and c is the approximation

to x.

B1 Define c = (a + b)/2

B2 If b c ≤ τ , then accept c as the root and stop.

B3 If sign[f(b)] · sign[f(c)] ≤ 0, then set a = c.

Otherwise, set b = c. Return to step B1.

You are free to implement this using for, while, or recursion, though my implementation is using

a while loop. The sign() function should return -1 if the argument is non-positive (negative or

zero) and return 1 if it’s positive.

mybisect.py

1 f = lambda x: x**6 - x - 1

2

3 def sign(x):

4 # TO DO: Implement this function

5

6

7 def bisect(f,a,b,tau):

8 # TO DO: Implement this function

9 # Use the following print statement to display the data nicely

10 # the c variable is from the algorithmic specification of the ←-

bisection method seen above

11 # print("{0:.5f} {1:.5f} {2:.5f} {3:.5f} {4:.5f}".format(a,b,c,b-c,f(c←-

)))

12

13

14 bisect(f,1.0,2.0,.001)

Programming Problem 2

Complete the sign() and bisect() functions.

Use the print supplied in the comments to display the output nicely.

Extra credit if you implement the function using either a while- or a for-loop and then

also using recursion.

Put your code for this problem in a new module named mybisect.py

Assignment №9 Convergence, Recurrence, and Animation Page 8

Problem 3: pygames

In this problem, you’ll be introduced to pygames–a nice module that has features to make games.

The code we’re giving has a bouncing square. When the rectangle touches a side, it bounces

back–we added a little noise to the bounce.

Figure 2: A snapshot of the bounce game.

1 import pygame

2 import sys

3 import random as rn

4

5 pygame.init()

6

7 BLACK = ( 0,0,0)

8 WHITE = (255,255,255)

9 BLUE = (0,0,255)

10 RED = (255,0,0)

11 YELLOW = (255,255,0)

12

13 class Rectangle:

14

15 def __init__(self,color,loc):

16 self.loc = loc

17 self.color = color

18

19 def my_draw(self,screen):

20 pygame.draw.rect(screen, self.color, self.loc)

Assignment №9 Convergence, Recurrence, and Animation Page 9

21

22 def my_move(self,xoffset,yoffset):

23 self.loc = [self.loc[0]+xoffset,self.loc[1]+yoffset] + self.loc←-

[2:]

24

25

26 size = [300, 300]

27 screen = pygame.display.set_mode(size)

28 pygame.display.set_caption("C200 CHANGE")

29

30

31 r = Rectangle(RED, [0, 0, 20, 20])

32

33 while True:

34

35 pygame.time.wait(40)

36

37 for event in pygame.event.get():

38 if event.type == pygame.QUIT:

39 pygame.quit()

40 sys.exit()

41

42 screen.fill(WHITE)

43

44 r.my_draw(screen)

45

46 if r.loc[0] > 280:

47 xd = -rn.randint(1,3)

48 if r.loc[1] > 280:

49 yd = -rn.randint(1,3)

50 if r.loc[0] < 10:

51 xd = rn.randint(1,3)

52 if r.loc[1] < 10:

53 yd = rn.randint(1,3)

54 r.my_move(xd,yd)

55

56 pygame.display.flip()

Assignment №9 Convergence, Recurrence, and Animation Page 10

Change

You’ll need to install the pygames module.

Run the code. We provide the code in game1.py.

Modify the code that so that when the square hits the

– top, its color is changed to yellow

– bottom, its color is changed to blue

– left side, its color is changed to red

– right side, its color is changed to dark green. You do not need to change any

code in the class (we will learn more about classes and objects soon) – use

the code that changes the direction as a hint on how to change the color.

You should decide what suffices for dark green.

Put your code in a module named game1.py

Assignment №9 Convergence, Recurrence, and Animation Page 11

Problem 4: Secant Method

The secant method uses two numbers to approximate the root, the two numbers being endpoints

of a line whose intercept approximates x?. The graphic shows one of the circumstances (there

are two, but it’s not necessary for the implementation here).

Figure 3: The root is x. We use two points, x0, x1 to determine x2 which is the approximation

Although the recurrence looks a little intimidating, the code is actually minimal!

secant.py

1 def secant(f,x0,x1,tau):

2 # TO DO: Implement function

3 # Use the following print statement to display the data nicely

4 # print("{0:.5f} {1:.5f} {2:.5f} {3:.5f}".format(x0,f(x0),f(x1),x0-x1)←-

)

5

6

7 secant(f,2.0,1.0,.0001)

Assignment №9 Convergence, Recurrence, and Animation Page 12

Output

2.00000 61.00000 -1.00000 1.00000

1.00000 -1.00000 -0.91537 -0.01613

1.01613 -0.91537 0.65747 -0.17445

1.19058 0.65747 -0.16849 0.07292

1.11766 -0.16849 -0.02244 -0.01488

1.13253 -0.02244 0.00095 -0.00229

Deliverables Programming Problem 4

Complete the secant() function.

Use the print supplied in the comments to display the output nicely.

Extra credit if you implement the function using a while- or for-loop and then using

recursion.

Put your code for this problem in a new module named secant.py

Assignment №9 Convergence, Recurrence, and Animation Page 13

Problem 5: Simpson’s Rule

In this problem, we will implement Simpson’s Rule–a loop that approximates integration over an

interval. Suppose we want to find the value of the integral below:

Z b

a

f(x) dx (9)

We could use those pesky rules of integration–who’s got time for all that, right Or, as computer

scientists, we could implement virtually all integration problems. Simpson’s Rule is way of

approximating an integration using parabolas (See Fig. 4). For the integration, we have to pick

an even number of subintervals n and sum them up.

Figure 4: The function f(x) integrated over a, b is approximated by ?f(x) using n equally sized

invervals. The yellow illustrates the error of the approximation.

The rule is found on lines (14)-(15). Observe that when the index is odd that there is a

coefficient of 4; when the index is even (excluding start and end), the coefficient is 2.

(10)

xi = a + ix, i = 0, 1, 2, . . . , n 1, n (11)

x0 = a + 0x = a (12)

xn = a + n

[f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + 2f(x4) + . . . (14)

+ 2f(xn2 + 4f(xn1) + f(xn)] (15)

1 import math

2

3 # INPUT function fn, start is a, end is b,

4 # n is an even number of intervals

Assignment №9 Convergence, Recurrence, and Animation Page 14

5 # RETURN approximate area under the curve

6 def simpson(fn,a,b,n):

7 delta_x = (b - a)/n

8 interval = lambda i: a + i*delta_x

9 # TO DO: Implement the function

10

11 # convert string to either number or expression

12 def convert(x):

13 if x.isnumeric():

14 return float(x)

15 else:

16 return eval(x)

17

18 with open("funny.txt", "r") as xfile:

19 xlines = [d.split(",") for d in xfile.read().split("\n")]

20

21 for i in xlines:

22 body = i[0]

23 fn = eval("lambda x : " + body)

24 a = convert(i[1])

25 b = convert(i[2])

26 n = convert(i[3])

27 answer = convert(i[4])

28 integration = simpson(fn,a,b,n)

29 error = abs((answer - integration)/answer)

30 print("f(x) = {0} over [{1},{2}] is {3:.3f}".format(body,a,b,←-

integration))

31 print("Actual answer is {0:.3f}".format(answer))

32 print("Error is {0:.3f}".format(error))

The csv is a file that contains the function, the start of the integration, the end of the integration,

the number of intervals and the actual integration. The file (See Table 1.) has the

following:

3x

2 + 1, 0, 6, 2, 222

x

2

, 0, 5, 6, 125/3

sin(x), 0, π, 4, 2

1/x, 1, 11, 6, ln(11)

Table 1: The csv file.

For example, the third row is the approximation to the integral

Z π

0

sin(x) dx = 2

using n = 4 intervals.

Assignment №9 Convergence, Recurrence, and Animation Page 15

f(x) = 3*(x**2) + 1 over [0,6] is 222.000

Actual answer is 222.000

Error is 0.000

f(x) = x**2 over [0,5] is 41.667

Actual answer is 41.667

Error is 0.000

f(x) = math.sin(x) over [0,3.141592653589793] is 2.005

Actual answer is 2.000

Error is 0.002

f(x) = 1/x over [1,11.0] is 2.449

Actual answer is 2.398

Error is 0.021

Programming Problem 5

Put the file integralfile.txt in your project to make it easy to read in.

Complete the code.

Put your finished code in a new module easycalc.py

Assignment №9 Convergence, Recurrence, and Animation Page 16

Problem 6: Making Recurrence Behave

In this problem, we will be given two RE and you’ll implement it recursively, with tail-recursion,

with memoization, and linearization. In this version, I think I’ve found a weakness in the dictionary

– see if you find it too. Here are the equations:

b(1) ∨ b(2) = 0 (16)

b(n) ∧ even(n) = n 1 + b(n 1) (17)

b(n) ∧ odd(n) = n

2 + 1 + b(n 1) (18)

gg(0) = 1 (20)

gg(n) = 1 + 2gg(n1) (21)

1 #TIMER FUNCTION -- deprecated in 3.8 FYI

2 #so you might get messages -- you can ignore them for now

3 import time

5 def ftimer(f,args):

6 time_start = time.clock()

7 f(args)

8 time_elapsed2 = (time.clock()-time_start)

9 return time_elapsed2

12 def even(x):

13 #TO DO: IMPLEMENT

16 def odd(x):

17 #TO DO:IMPLEMENT

20 #Recursive

21 #INPUT n

22 #OUTPUT RE value

23 def b(n):

24 #TO DO: IMPLEMENT

27 #TAIL RECURSIVE FOR 3

28 def btr(n,s):

29 #TO DO: IMPLEMENT

32 #MEMOIZATION

Assignment №9 Convergence, Recurrence, and Animation Page 17

33 #USE THIS DICTIONARY

34 d = {2:0,1:0}

35 def bm(n):

36 #TO DO: IMPLEMENT

39 # LINEARIZATION

40 def bL(n):

41 #TO DO: IMPLEMENT

43 for i in range(1,10):

44 print("f({0}) = {1}, {2}, {3}, {4}".format(i, b(i),btr(i,0),bm(i),bL(i←-) ))

46 fblist = [b, lambda i: btr(i,0), bm ,bL]

47 tlist = [round(ftimer(f,700)*10**5,2) for f in fblist]

48 print(tlist)

49 print()

53 #RECURSIVE IMPLMENTATION

54 #INPUT N

55 #OUTPUT RE VALUE

56 def gg(n):

57 #TO DO: IMPLEMENT

60 #TAIL RECURSIVE

61 def gtr(n,s):

62 #TO DO:IMPLEMENT

65 #MEMOIZATION DICTIONARY INSIDE

66 def gm(n):

67 #TO DO: IMPLEMENT

70 #LINEARIZATION

71 def gL(n):

72 #TO DO:IMPLEMENT

74 fglist = [gg, lambda i: gtr(i,0),gm, gL]

76 for i in range(0,10):

77 print("f({0}) = {1}, {2}, {3}, {4}".format(i,gg(i),gtr(i,0),gm(i),gL(←-

i)))

Assignment №9 Convergence, Recurrence, and Animation Page 18

78

79 tlist = [round(ftimer(f,700)*10**5,2) for f in fglist]

80 print(tlist)

f(1) = 0, 0, 0, 0

f(2) = 0, 0, 0, 0

f(3) = 10, 10, 10, 10

f(4) = 13, 13, 13, 13

f(5) = 39, 39, 39, 39

f(6) = 44, 44, 44, 44

f(7) = 94, 94, 94, 94

f(8) = 101, 101, 101, 101

f(9) = 183, 183, 183, 183

[99.59, 45.61, 6973.75, 28.6]

f(0) = 1, 1, 1, 1

f(1) = 3, 3, 3, 3

f(2) = 7, 7, 7, 7

f(3) = 15, 15, 15, 15

f(4) = 31, 31, 31, 31

f(5) = 63, 63, 63, 63

f(6) = 127, 127, 127, 127

f(7) = 255, 255, 255, 255

f(8) = 511, 511, 511, 511

f(9) = 1023, 1023, 1023, 1023

[35.0, 34.79, 41.02, 20.12]

Deliverables Programming Problem 6

Put the file rec.py in your project to make it easy to read in.

Complete the code.

The file to turn in is rec.py

Assignment №9 Convergence, Recurrence, and Animation Page 19