Các phương pháp cơ bản giải quyết bài toán trên máy tính

Ôn tập

Ôn tập về vòng lặp

In [1]:
ans = 0
neg_flag = False
x = int(input('Enter an integer:'))
if x < 0:
    neg_flag = True
while ans**2 < x:
    ans = ans + 1
if ans**2 == x:
    print('Square root of', x, 'is', ans)
else:
    print(x, 'is not a perfect square')
    if neg_flag:
        print('Just checking... did you mean', -x, '?')
Enter an integer:25
Square root of 25 is 5

Ôn tập về chuỗi

In [2]:
s = "abc"
len(s)
Out[2]:
3
In [3]:
s[0]
Out[3]:
'a'
In [4]:
s[1]
Out[4]:
'b'
In [5]:
s[3]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-5-2f09fd169b91> in <module>()
      1 s = "abc"
----> 2 s[3]

IndexError: string index out of range
In [6]:
s = 'abcdefgh'
s[::-1]
Out[6]:
'hgfedcba'
In [7]:
s[3:6]
Out[7]:
'def'
In [8]:
s[-1]
Out[8]:
'h'
In [9]:
s = "hello"
s[0] = 'y'
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-9-6c165964bf1c> in <module>()
      1 s = "hello"
----> 2 s[0] = 'y'

TypeError: 'str' object does not support item assignment
In [10]:
s = 'y' + s[1:len(s)]
s
Out[10]:
'yello'

Chuỗi và vòng lặp

In [11]:
s = "abcdefgh"
for index in range(len(s)):
    if s[index] == 'a' or s[index] == 'e':
        print('There is an i or u')
There is an i or u
There is an i or u
In [12]:
s = "abcdefgh"
for char in s:
    if char == 'a' or char == 'e':
        print('There is an i or u')
There is an i or u
There is an i or u
In [13]:
an_letters = 'aefhilmnorsxAEFHILMNORSX'
word = input('I will cheer for you! Enter a word:')
times = int(input('Enthusiasm level (1-10):'))
i = 0

while i < len(word):
    char = word[i]
    if char in an_letters:
        print('Give me an ' + char + "! " + char)
    else:
        print('Give me a ' + char + '! ' + char)
    i += 1
print('What does that spell?')
for i in range(times):
    print(word, "!!!")
I will cheer for you! Enter a word:HCE
Enthusiasm level (1-10):10
Give me an H! H
Give me a C! C
Give me an E! E
What does that spell?
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!
HCE !!!

Bài tập

Viết lại chương trình ngay trên bằng cách thay vòng lặp while bằng vòng lặp for.

Phương pháp xấp xỉ (Approximate Solution)

In [15]:
cube = 27
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0
while abs(guess**3 - cube) >= epsilon: # and guess <= cube:
    guess += increment
    num_guesses += 1
print('num_guesses =', num_guesses)
if abs(guess**3 - cube) >= epsilon:
    print('Failed on cube root of', cube)
else:
    print(guess, 'is close to the cube root of', cube)
num_guesses = 29997
2.999700000001906 is close to the cube root of 27

Tìm kiếm nhị phân (Bisection search)

In [16]:
x = 25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = x
ans = (high + low) / 2.0

while abs(ans**2 - x) >= epsilon:
    print('low = ' + str(ans) + ' high = ' + str(high) + ' ans = ' + str(ans))
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0
print('numGuesses = ' + str(numGuesses))
print(str(ans) + ' is close to square root of ' + str(x))
low = 12.5 high = 25 ans = 12.5
low = 6.25 high = 12.5 ans = 6.25
low = 3.125 high = 6.25 ans = 3.125
low = 4.6875 high = 6.25 ans = 4.6875
low = 5.46875 high = 6.25 ans = 5.46875
low = 5.078125 high = 5.46875 ans = 5.078125
low = 4.8828125 high = 5.078125 ans = 4.8828125
low = 4.98046875 high = 5.078125 ans = 4.98046875
low = 5.029296875 high = 5.078125 ans = 5.029296875
low = 5.0048828125 high = 5.029296875 ans = 5.0048828125
low = 4.99267578125 high = 5.0048828125 ans = 4.99267578125
low = 4.998779296875 high = 5.0048828125 ans = 4.998779296875
low = 5.0018310546875 high = 5.0048828125 ans = 5.0018310546875
numGuesses = 13
5.00030517578125 is close to square root of 25

Bài tập

Với x = -25, đoạn code trên có hoạt động hay không? Hãy sửa code trên để nó có thể làm việc với cả số âm và dương.

In [17]:
cube = 54
epsilon = 0.01
num_guesses = 0
low = 0
high = cube
guess = (high + low)/2.0
while abs(guess**3 - cube) >= epsilon:
    if guess**3 < cube :
        low = guess
    else:
        high = guess
    guess = (high + low)/2.0
    num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to the cube root of', cube)
num_guesses = 15
3.779571533203125 is close to the cube root of 54

Số thực và phân số

In [21]:
start_num = 10
num = start_num
if num < 0:
    isNeg = True
    num = abs(num)
else:
    isNeg = False
result = ''
if num == 0:
    result = '0'
while num > 0:
    result = str(num % 2) + result
    num = num // 2
if isNeg:
    result = '-' + result
print(result, 'is a binary of', start_num)
1010 is a binary of 10

Bài tập

Số thập phân tương ứng với 10011 là số nào?

In [22]:
x = float(input('Enter a decimal number between 0 and 1: '))

p = 0
while ((2**p)*x)%1 != 0:
    print('Remainder = ' + str((2**p)*x - int((2**p)*x)))
    p += 1

num = int(x*(2**p))

result = ''
if num == 0:
    result = '0'
while num > 0:
    result = str(num%2) + result
    num = num//2

for i in range(p - len(result)):
    result = '0' + result

result = result[0:-p] + '.' + result[-p:]
print('The binary representation of the decimal ' + str(x) + ' is ' + str(result))
Enter a decimal number between 0 and 1: 0.375
Remainder = 0.375
Remainder = 0.75
Remainder = 0.5
The binary representation of the decimal 0.375 is .011

Phương pháp Newton-Raphson

In [24]:
epsilon = 0.01
y = 54.0
guess = y/2.0
numGuesses = 0

while abs(guess*guess - y) >= epsilon:
    numGuesses += 1
    guess = guess - (((guess**2) - y)/(2*guess))
print('numGuesses = ' + str(numGuesses))
print('Square root of ' + str(y) + ' is about ' + str(guess))
numGuesses = 5
Square root of 54.0 is about 7.348469483546109

Bài tập

Add some code to the implementation of Newton-Raphson that keeps track of the number of iterations used to find the root. Use that code as part of a program that compares the efficiency of Newton-Raphson and bisection search. (You should discover that Newton-Raphson is more efficient.)

In [ ]: