# 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 [ ]: