Chương 7: Lặp

Trở về Mục lục cuốn sách

Phép gán nhiều lần

Có thể bạn đã phát hiện thấy rằng, việc gán nhiều giá trị vào cùng một biến là điều hợp lệ. Một phép gán mới làm cho biến hiện tại tham chiếu đến một giá trị mới (và bỏ tham chiếu đến giá trị cũ).

bruce = 5
print bruce,
bruce = 7
print bruce

Kết quả của chương trình này là 5 7, vì lần đầu tiên khi bruce được in ra, giá trị của nó là 5, và đến lần thứ hai, giá trị là 7. Dấu phẩy đặt ở cuối câu lệnh print thứ nhất ngăn cản việc xuống dòng, và đáp số của hai lần tính toán đều xuât hiện trên cùng một dòng.

Sơ đồ trạng thái sau cho thấy cơ chế của một phép gán nhiều lần:

phép gán

Trong việc gán nhiều lần, ta cần đặc biệt lưu ý để phân biệt giữa một toán tử gán và một đẳng thức. Vì Python dùng dấu bằng (=) cho một lệnh gán, ta có thể bị cám dỗ bởi ý nghĩ rằng một câu lệnh kiểu như a = b là một đẳng thức. Thực ra thì không phải vậy!

Trước hết, đẳng thức là một hệ thức đối xứng còn lệnh gán thì không phải. Chẳng hạn, trong toán học, nếu a = 7 thì 7 = a. Nhưng trong Python, câu lệnh a = 7 thì hợp lệ còn 7 = a thì không.

Hơn nữa, trong toán học, một đẳng thức thì có thể luôn đúng hoặc luôn sai. Nếu bây giờ a = b thì về sau này a sẽ luôn bằng b. Trong Python, một lệnh gán có thể làm cho hai biến bằng nhau, nhưng có thể sẽ không bằng nhau mãi:

a = 5
b = a    # bây giờ a và b bằng nhau
a = 3    # a và b không còn bằng nhau 

Dòng lệnh thứ ba thay đổi giá trị của a nhưng không thay đổi giá trị của b, vì vậy chúng không còn bằng nhau.

Mặc dù việc gán nhiều lần thường có ích, song bạn cần cẩn thận khi sử dụng chúng. Việc giá trị của các biến thay đổi thường xuyên có thể làm cho mã lệnh trở nên khó đọc và khó gỡ lỗi.

Cập nhật các biến

Một trong các dạng thông dụng nhất của gán nhiều lần là một lệnh cập nhật, trong đó giá trị mới của biến phụ thuộc vào giá trị cũ.

x = x+1

Lệnh này có nghĩa là “lấy giá trị hiện thời của x, cộng thêm một, và cập nhật x với giá trị mới”.

Nếu bạn thử cập nhật một biến mà hiện không tồn tại, bạn sẽ bị báo lỗi, vì Python luôn ước lượng vế phải trước khi gán một giá trị cho x:

>>> x = x+1
NameError: name 'x' is not defined

Trước khi có thể cập nhật một biến, bạn cần phải khởi tạo nó, thường là bằng một lệnh gán:

>>> x = 0
>>> x = x+1

Việc cập nhật một biến bằng cách cộng thêm 1 được gọi là tăng; còn trừ đi 1 được gọi là giảm.

Lệnh while

Máy tính thường được dùng để tự động hoá các tác vụ có tính chất lặp lại. Việc lặp lại những thao tác giống hệt hoặc tương tự nhau mà không mắc phải lỗi chính là “sở trường” của máy tính đồng thời là việc mà con người làm rất dở.

Ta đã thấy hai chương trình, countdownprint_n, trong đó dùng đệ quy để thực hiện thao tác lặp lại, hay còn gọi là { lặp}. Vì lặp là một thao tác thường dùng, nên Python có cung cấp một số đặc điểm ngôn ngữ giúp cho việc thực hiện được dễ dàng. Một trong số đó là lệnh for mà chúng ta đã gặp trong Mục {lặp}. Chúng ta sẽ trở lại đó vào một dịp khác.

Một cách khác là dùng lệnh while. Sau đây là một phiên bản của { countdown} có dùng lệnh while:

def countdown(n):
    while n > 0:
        print n
        n = n-1
    print 'Bùm!'

Bạn gần như có thể đọc lệnh while giống cách đọc tiếng Anh: “Khi n còn lớn hơn 0, hãy hiển thị giá trị của n rồi giảm giá trị của n đi 1. Khi đạt đến 0, hãy hiển thị chữ Bùm!

Nói một cách hệ thống hơn, luồng thực hiện của câu lệnh while như sau:

  1. Ước lượng điều kiện, trả lại True hoặc False.
  2. Nếu điều kiện không thoả mãn, thoát khỏi khối lệnh while rồi thực hiện câu lệnh kế tiếp.
  3. Nếu điều kiện được thoả mãn, thực hiện phần thần và quay trở lại bước 1.

Dạng luồng thực hiện này được gọi là một vòng lặp vì sau bước thứ 3 quay trở về bước đầu tiên.

Phần thân của vòng lặp sẽ thay đổi giá trị của một hoặc nhiều biến sao cho cuối cùng thì điều kiện sẽ không thoả mãn và vòng lặp kết thúc. Còn nếu không thì vòng lặp sẽ tiếp diễn mãi mãi, và được gọi là một vòng lặp vô hạn. Một câu chuyện đùa về nhà khoa học máy tính xuất phát từ việc quan sát thấy dòng chữ trên hướng dẫn sử dụng lọ dầu gội đầu: “Lather, rinse, repeat”, (Xoa dầu, xối nước và lặp lại) là một vòng lặp vô hạn.

Trong trường hợp của countdown, chúng ta có thể chứng tỏ rằng vòng lặp sẽ kết thúc vì biết rằng giá trị của n là hữu hạn, và mỗi khi lặp lị thì giá trị của n sẽ nhỏ đi. Vì vậy cuối cùng nó sẽ phải trở về 0. Với các trường hợp khác, có thể sẽ không dễ chứng tỏ điều đó:

def sequence(n):
    while n != 1:
        print n,
        if n%2 == 0:        # n chẵn
            n = n/2
        else:               # n lẻ 
            n = n*3+1

Điều kện cho vòng lặp này là n != 1, vì vậy vòng lặp sẽ tiếp tục đến khi n bằng 1, khi đó điều kiện sẽ bị vi phạm.

Mỗi lần lặp, chương trình sẽ in ra giá trị của n và kiểm tra xem nó là chẵn hay lẻ. Nếu là chẵn, n được đem chia cho 2. Nếu lẻ giá trị của n được thay thế bởi n*3+1. Chẳng hạn, nếu tham biến được truyền cho sequence là 3, thì chuỗi số thu được sẽ là 3, 10, 5, 16, 8, 4, 2, 1.

n đôi khi tăng và đôi khi giảm, nên không có một chứng minh rõ ràng nào cho thấy n sẽ đạt được giá trị 1, hay là chương trình kết thúc. Với một số giá trị riêng của n, ta có thể chứng minh sự kết thúc này. Chẳng hạn, nếu giá trị ban đầu là một số lũy thừa của 2 thì giá trị của n sẽ là chẵn trong mỗi lần lặp và đến khi nó đạt bằng 1. Ở ví dụ trước đây, chuỗi cũng kết thúc theo cách tương tự kể từ số 16.

Câu hỏi được đặt ra là liệu ta có thể chứng minh rằng chương trình sẽ kết thúc với mọi giá trị dương của n hay không. Cho đến giờ1, chưa ai có đủ khả năng chứng minh hoặc bác bỏ nó!

Viết lại hàm print_n ở Mục {đệ quy} dùng cách lặp thay vì đệ quy.

break

Đôi khi bạn chỉ biết được rằng đã đến lúc kết thúc vòng lặp trong khi đang thực hiện một nửa phần thân của vòng lặp đó. Trường hợp này bạn có thể dùng câu lệnh break để thoát khỏi vòng lặp.

Chẳng hạn, giả sử như bạn muốn nhận dữ liệu nhập vào bởi người dùng cho đến lúc họ gõ xong. Bạn có thể viết như sau:

while True:
    line = raw_input('> ')
    if line == 'xong':
        break
    print line

print 'Xong!'

Điều kiện lặp là True, tức là luôn đúng, vì vậy vòng lặp tiếp diễn đến khi nó gặp phải lệnh break.

Ở mỗi lần lặp, nó nhắc người dùng bằng cách hiện ra kí hiệu ’>’. Nếu người dùng gõ vào chữ xong, lệnh break sẽ giúp thoát khỏi vòng lặp. Còn không thì chương trình sẽ hiện lại bất cứ dòng chữ gì người dùng đã nhập vào, rồi trở lại đầu vòng lặp. Sau đây là một lần chạy thử:

> chưa xong
chưa xong

> xong
Xong!

Cách viết vòng lặp while như thế này rất thường gặp vì bạn có thể kiểm tra điều kiện ở bất kì nơi nào trong vòng lặp (chứ không riêng ở đầu vòng lặp) và có thể khẳng định điều kiện dừng lặp (“hãy dừng ngay khi điều này xảy ra”) thay vì chỉ nói một cách phủ định (“cứ tiếp tục đến khi điều đó xảy ra”.).

Căn bậc hai

Các vòng lặp thường được dùng trong những chương trình ở đó có tính các trị số bằng cách bắt đầu với một ước lượng rồi liên lục tính lặp để có được xấp xỉ tốt hơn.

Chẳng hạn, một cách tính căn bậc hai là phương pháp Newton. Giả sử bạn muốn tính căn bậc hai của a. Nếu bạn bắt đầu với một giá trị ước lượng bất kì, x, bạn có thể tính ra một ước lượng khác tốt hơn theo công thức:

y = (x + a/x)/2 $
Chẳng hạn, nếu a bằng 4 và x bằng 3:

>>> a = 4.0
>>> x = 3.0
>>> y = (x + a/x) / 2
>>> print y
2.16666666667

Tức là giá trị mới đã sát hơn kết quả đúng (√4 = 2). Nếu ta tiếp tục lặp lại quá trình này bằng giá trị ước lượng mới, kết quả thu được còn gần đúng nữa:

>>> x = y
>>> y = (x + a/x) / 2
>>> print y
2.00641025641

Sau một số lần tính (cập nhật), kết quả ước lượng sẽ gần như chính xác:

>>> x = y
>>> y = (x + a/x) / 2

>>> print y
2.00001024003
>>> x = y
>>> y = (x + a/x) / 2
>>> print y
2.00000000003

Nhìn chung ta không thể nói trước rằng sẽ cần tính lặp bao nhiêu lần để thu được kết quả đúng, nhưng ta biết rằng khi ta tiến đến giá trị đúng thì các giá trị ước lượng tìm được sẽ không còn dao động nữa:

>>> x = y
>>> y = (x + a/x) / 2
>>> print y
2.0

>>> x = y
>>> y = (x + a/x) / 2
>>> print y
2.0

Khi y == x, ta có thể dừng lại. Sau đây là một vòng lặp bắt đầu bằng một giá trị ước lượng, x, và sau đó điều chỉnh nó đến khi giá trị này ngừng dao động:

while True:
    print x
    y = (x + a/x) / 2
    if y == x:
        break
    x = y

Với phần lớn các giá trị của a cách làm này khá hiệu quả, nhưng nói chung việc kiểm tra điều kiện bằng nhau giữa hai số thập phân float là nguy hiểm. Các giá trị số có phần thập phân chỉ gần đúng: hầu hết các số hữu tỉ, như 1 / 3, và vô tỉ, như $\sqrt{2}$, đều không thể biểu diễn được chính xác dưới dạng float.

Thay vì kiểm tra xem xy có đúng bằng nhau không, cách làm an toàn hơn là dùng hàm có sẵn abs để tính giá trị tuyệt đối, hay độ lớn của hiệu giữa hai số này:

    if abs(y-x) < epsilon:
        break

trong đó epsilon nhận một giá trị như 0.0000001 tùy thuộc vào yêu cầu độ chính xác mà ta cần là bao nhiêu.

Hãy “gói” vòng lặp này vào trong một hàm có tên square_root nhận a làm tham số, chọn một giá trị hợp lý của x, và sau đó trả lại ước lượng xấp xỉ căn bậc hai của a.

Thuật toán

Phương pháp Newton là ví dụ cho một thuật toán: đó là một quá trình, một cơ chế để giải một lớp các bài toán (trong trường hợp này là bài toán tính căn bậc hai).

Thật không dễ định nghĩa một thuật toán. Có lẽ để tiện hơn, ta sẽ xét một thứ không phải là thuật toán. Khi bạn học cách nhân hai chữ số với nhau, có thể bạn đã thuộc lòng bảng cửu chương. Như vậy bạn đã ghi nhớ được 100 kết quả phép tính riêng biệt. Những kiến thức như vậy không phải là thuật toán.

Nhưng nếu “lười biếng”, bạn có thể dùng mẹo để tính nhẩm. Chẳng hạn, để tìm tích số giữa n và 9, bạn có thể viết chữ số đầu là n - 1 và chữ số sau là 10 - n. Mẹo này cho lời giải tổng quát với mọi phép tính giữa số có một chữ số với 9. Đó chính là thuật toán!

Tương tự, kĩ thuật mà bạn đã được học như phép cộng / trừ có nhớ, phép chia có nhớ đều là các thuật toán. Một trong những thuộc tính của thuật toán là để thực hiện chúng thì không cần trí thông minh. Đó là những quá trình trong đó gồm các bước nối tiếp nhau dựa trên một số quy luật đơn giản.

Theo tôi, thật đáng ngạc nhiên là chúng ta lại dành quá nhiều thời gian ở trường để học cách thực thi các thuật toán mà về bản chất thì chúng không có tính trí tuệ chút nào.

Trái lại, quá trình thiêt kế các thuật toán mới thú vị, đầy tính thử thách về trí tuệ, và là phần trọng tâm của việc mà ta gọi là lập trình.

Có những việc mà chúng ta làm một cách tự nhiên, chẳng chút khó khăn hay phải nghĩ ngợi gì, lại chính là những điều khó diễn giải thành thuật toán nhất. Một ví dụ điển hình là việc hiểu ngôn ngữ tự nhiên. Tất cả chúng ta đều có khả năng này, nhưng đến nay chưa ai giải thích được là bằng cách nào mà chúng ta hiểu nó, ít nhất là giải thích không cần dưới hình thức một thuật toán.

Gỡ lỗi

Khi bạn bắt đầu viết những chương trình lớn, bạn có thể sẽ phải dành nhiều thời gian hơn để gỡ lỗi. Nhiều dòng mã lệnh đồng nghĩa với nhiều khả năng mắc lỗi và nhiều chỗ dễ phát sinh ra lỗi hơn.

Một cách cắt giảm thời gian gỡ lỗi là “phân đôi”. Chẳng hạn, nếu chương trình của bạn có 100 dòng lệnh và nếu bạn cần kiểm tra lần lượt từng dòng một sẽ mất 100 bước.

Thay vì vậy, hãy thử chia đôi bài toán. Nhìn vào khu vực giữa của chương trình, kiếm lấy một giá trị trung gian mà bạn có thể kiểm tra được. Thêm vào một câu lệnh print (hoặc là một cách nào khác để tạo ra một hiệu ứng giúp ta kiểm tra) rồi chạy chương trình.

Nếu lần kiểm tra ở điểm giữa này mà không đạt, thì chắc chắn nửa đầu chương trình sẽ chứa lỗi. Nếu đạt, thì lỗi nằm ở nửa sau chương trình.

Mỗi khi kiểm tra như thế này, bạn đã chia nửa số dòng lệnh cần thiết phải tìm kiếm. Ít nhất là vết mặt lý thuyết thì sau sáu bước (tức là ít hơn 100), bạn sẽ có thể giảm số dòng lệnh cần kiểm tra xuống còn 1 đến 2 dòng mà thôi.

Trên thực tế, “điểm giữa của chương trình” thường không rõ ràng và đôi khi ta không thể kiểm tra được ở đó. Vì vậy việc đếm số dòng và tìm chính xác điểm giữa là vô nghĩa. Thay vào đó, hãy nghĩ đến những chỗ trong chương trình mà có nhiều khả năng xảy ra lỗi và những chỗ dễ dàng đặt kiểm tra. Sau đó chọn một chỗ kiểm tra mà bạn nghĩ khả năng xảy ra lỗi trước và sau điểm đó là ngang nhau.

Thuật ngữ

phép gán nhiều lần:
Việc thực hiện hơn một lần gán giá trị cho cùng một biến khi thực thi một chương trình.

cập nhật:
Một phép gán trong đó giá trị mới của biến phụ thuộc vào giá trị cũ.

khởi tạo:
Một phép gán gán trị ban đầu cho một biến mà sau này sẽ được cập nhật.

tăng:
Việc cập nhật bằng cách cộng thêm vào giá trị sẵn có của một biến (thường là thêm 1).

giảm:
Việc cập nhật bằng cách bớt đi giá trị sẵn có của một biến.

lặp:
Việc thực hiện liên tục nhiều lần một nhóm các lệnh bằng cách gọi hàm đệ quy hoặc một vòng lặp.

vòng lặp vô hạn:
Một vòng lặp trong đó điều kiện kết thúc không bao giờ được thỏa mãn.

Bài tập

Để kiểm tra thuật toán căn bậc hai trong chương này, bạn có thể so sánh nó với math.sqrt. Hãy viết một hàm có tên test_square_root để in ra một bảng như sau:

1.0 1.0           1.0           0.0
2.0 1.41421356237 1.41421356237 2.22044604925e-16
3.0 1.73205080757 1.73205080757 0.0
4.0 2.0           2.0           0.0
5.0 2.2360679775  2.2360679775  0.0
6.0 2.44948974278 2.44948974278 0.0
7.0 2.64575131106 2.64575131106 0.0
8.0 2.82842712475 2.82842712475 4.4408920985e-16
9.0 3.0           3.0           0.0

Cột đâu tiên có chứa một số, a; cột thứ hai là căn bậc hai của a được tính bằng hàm ở Bài tập {square_root}; cột thứ ba là căn bậc hai được tính từ math.sqrt; cột thứ tư là giá trị tuyệt đối của chênh lệch giữa hai kết quả tính được theo hai cách trên.

Hàm dựng sẵn eval nhận vào một chuỗi và dùng trình thông dịch Python để định giá trị của nó. Chẳng hạn:

>>> eval('1 + 2 * 3')
7
>>> import math
>>> eval('math.sqrt(5)')
2.2360679774997898
>>> eval('type(math.pi)')
<type 'float'>

Hãy viết một hàm tên là eval_loop để lặp lại các thao tác nhắc người dùng nhập vào chuỗi biểu thức, định giá trị nó bằng eval, và sau đó in ra kết quả.

Vòng lặp cần tiếp tục đến tận khi người dùng nhập vào 'xong', và kết thúc bằng việc trả lại giá trị của biểu thức được định giá trị sau cùng.

Nhà toán học xuất sắc Srinivasa Ramanujan đã tìm ra một chuỗi số vô tận2 có thể được dùng để phát sinh ra một giá trị xấp xỉ cho số π:

Hãy viết một hàm tên là estimate_pi dùng công thức này để tính và trả lại giá trị xấp xỉ của π. Hãy dùng một vòng lặp while để tính các số hạng trong tổng đến khi số hạng cuối cùng nhỏ hơn 1e-15 (vốn là cách biểu diễn của Python cho 10 - 15). Bạn có thể kiểm tra kết quả tính được bằng cách so sánh nó với math.pi.

Bạn có thể tham khảo đáp án của tôi ở thinkpython.com/code/pi.py.

Advertisements

2 phản hồi

Filed under Think Python

2 responses to “Chương 7: Lặp

  1. Pingback: Think Python: Cách tư duy như nhà khoa học máy tính | Blog của Chiến

  2. Pingback: Think Python: Cách tư duy như nhà khoa học máy tính » Book Python

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s