Lab 2?–?CPS?106

?

?

This lab gives you more practice on dealing with iterations and approximations in python.

?

1)??Write a program that converts a given positive integer to its binary representation.

Hint: write the program using a for loop. To?get?the?number?of?bits?in?a?given?integer,?use?the?function bit_length() in python. For example, for a = 983265982365,?a.bit_length() will be 40.

Test your program with following integers:

a?=?87324834345,

a?=?65234242,

a?=?576762341243968.

Compare your results with the built-in function bin(int a) in python.

2)??Let?f(x)?=?x**5 ?+?52*x**3?-?29?be?a?function.?This?function?has?only?one?root?in?the?real?numbers. Write a bisection search algorithm to find that?root?up?to?two?digits?of accuracy, i.e.,?for epsilon?= 0.01?as?in?the?class.

3)??Solve?question?2 using?the Newton-Raphson method.?Compare?the?number?of iterations with?the bisection search.

代碼

2-2 bisectionSearch

# -*- coding: utf-8 -*-

"""

Created on Sat Jan? 7 10:50:46 2023

@author: pc

"""

def f(x):

? ? return x**5 + 52*x**3 - 29

#for i in range( 10 ):

#? ? print(f(i))

? ??

i = 0

f1 = 0.1

while(i < 3 ):

? ? i = i + 1

? ? f1 = f(f1)

? ? print( f1 )

? ??

d = 0.3

xn = 1.5

for i in range(1,10):

? ? xn = xn * (2-xn*d)

? ? print("iteration %d: 1/d=%0.10f" % (i, xn))

#bisection search

left = 0.7

right = 1.0

epsilon = 0.01

if f(left) > 0:

? ? print("error!")

else:

? ? counter = 0

? ? while left < right:

? ? ? ? mid = float((left + right) /2)

? ? ? ? counter += 1

? ? ? ? if f(mid) < 0.0:

? ? ? ? ? ? left = mid + epsilon

? ? ? ? if f(mid) > 0.0:

? ? ? ? ? ? right = mid - epsilon

? ? ? ? ? ??

print("iteration %d: l=%0.10f r=%0.10f" % (counter, left, right))

2-2-2 bisectionSearch

# -*- coding: utf-8 -*-

"""

Created on Sun Jan? 8 09:02:36 2023

@author: pc

"""

def ComputerFunction(x):

? ? return x**5 + 52*x**3 - 29

a = 0

c = 2

b = a + (c - a)/2

epslon = b - a

count = 0

while epslon > 0.00001:

? ? if ComputerFunction(a) * ComputerFunction(b) < 0:

? ? ? ? a = a

? ? ? ? c = b

? ? ? ? b = a + (c - a)/2

? ? else:

? ? ? ? a = b

? ? ? ? c = c

? ? ? ? b = a + (c - a)/2

? ? epslon = b - a

? ? count+=1

print(a)

print("The number of iterations is:",count)

2-3 Newton-Raphson

# -*- coding: utf-8 -*-

"""

Created on Sat Jan? 7 23:58:10 2023

@author: pc

"""

def f(x):

? ? return x**5 + 52*x**3 - 29? ? ? ?#'''定義 f(x) = (x-3)^3'''

?

def fd(x):

? ? return 5*x**4 + 52*3*x**2? ? ? ? #'''定義 f'(x) = 3*((x-3)^2）'''

?

def newtonMethod(n,assum):

? ? time = n

? ? x = assum

? ? Next = 0

? ? A = f(x)

? ? B = fd(x)

? ? print('A = ' + str(A) + ', B = ' + str(B) + ', time = ' + str(time))

? ? if f(x) == 0.0:

? ? ? ? return time,x

? ? else:

? ? ? ? Next = x - A/B

? ? ? ? print('Next x = '+ str(Next))

? ? if abs(A - f(Next)) < 0.001:? ?#1e-6:? ? ? ? ? ? ? ? ?#0.000001

? ? ? ? print('Meet f(x) = 0,x = ' + str(Next))? #'''設(shè)置迭代跳出條件，同時(shí)輸出滿足f(x) = 0的x值'''

? ? else:

? ? ? ? return newtonMethod(n+1,Next)

?

newtonMethod(0, 1)? ? #'''設(shè)置從0開(kāi)始計(jì)數(shù)，x0 = 4.0'''