Tag: python

  • Pumped-up performance Python with Pyston

    Pumped-up performance Python with Pyston

    Pumped-up performance Python with Pyston

    Python developers can look forward to faster implementations with the release of Pyston v2.2, while Facebook is developing its own internal implementation called Cinder from which it aims to upstream improvements to CPython.

    👉Hướng dẫn lập trình Python – Python Guide

    Pyston is one such project, and the just released version 2.2 is claimed to be 30 percent faster than standard Python in the Pyston team’s own web server benchmarks. Pyston is a fork of CPython, and the foundational technology powering Pyston v2.2 is the same as that found in earlier versions, but the project team says it has tuned and optimised more areas and found additional ways to boost performance, particularly in the JIT and attribute cache mechanisms.

    One of the ways the team found to squeeze out a bit of extra performance is by removing many of the rarely-used debugging features that Python supports, because they are expensive (i.e. time consuming) when not needed. Doing just this has resulted in a two percent speedup. Developers who want debugging features can apparently still use the “debug build” of stock Python, because of the compatibility between the two.

    Pumped-up performance Python with Pyston

    The Pyston project has had a shaky start, with development hitting a hiatus after Dropbox pulled its sponsorship back in 2017. Now the feedback from potential customers has convinced the project team that Pyston can thrive on an open-source business model, and so the code for Pyston v2.2 is available on GitHub.

    Python with Pyston v2.2: faster and open source

    pyston logo

    Pyston’s developers are proud to announce Pyston v2.2, the latest version of our faster implementation of the Python programming language. This version is significantly faster than previous ones, and importantly is now open source.

    They also merged in many changes from CPython and are now based on CPython 3.8.8.

    Pyston v2.2: Performance

    Pyston v2.2 is 30% faster than stock Python on our web server benchmarks. This is a significant improvement over our previous performance, and if we were feeling cheeky, we would advertise it as “50% more speedup.”

    The foundational technology powering Pyston v2.2 is the same as that found in earlier versions, but we have tuned and optimized more areas and found additional speedups, particularly in our JIT and attribute cache mechanisms.

    One noteworthy change is that we decided to remove many of the rarely-used debugging features that Python supports because they are expensive even when not needed. Doing so collectively resulted in a 2% speedup, which was remarkable to us: of all the computers in the world running Python, 2% of them are executing debugging checks. We’ve disabled those checks and are positioning ourselves as an “optimized build” similar to binaries without debugging information. Those who still want debugging features can use the “debug build” of stock Python because they are interchangeable. For a full list of the features we removed in Pyston v2.2, please see our wiki.

    Pyston v2.2: Open source

    As we’ve continued talking to potential customers we now feel convinced that Pyston can thrive on an open-source business model, primarily by starting with support services. This means that we’ve open sourced Pyston v2.2, which you can find at our GitHub here.

    We’ve archived our old repository to reduce confusion, but you can still find that here.

    We are looking into which of our newest changes can be upstreamed to CPython. Throughout this process, we welcome your contributions. Help with getting Pyston packaged for additional platforms would be especially useful.

    Pyston v2.2: Moving forward

    We continue to try and make Pyston as compelling and easy to use as possible. Working Pyston into your projects should be as easy as replacing “python” with “pyston.” If that’s not the case, we’d love to hear about it on our GitHub issues tracker or on our Discord channel. We hope you’ll give Pyston a try and see that it really is the easiest way to speed up your Python code.

  • Python: Bài toán xếp hậu sử dụng đệ quy

    Python: Bài toán xếp hậu sử dụng đệ quy

    Python: Bài toán xếp hậu sử dụng đệ quy

    Bài toán xếp hậu là một bài toán kinh điển thường được giới thiệu trong các cuốn sách về thuật toán. Ở đây, chúng ta sẽ giải quyết bài toán bằng các sử dụng giải thuật đệ quythuật toán quay lui (vét cạn).

    Xem thêm: Thuật toán giải sudoku bằng quay lui backtracking

    Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột hoặc cùng đường chéo. Hãy tìm các xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào.

    Ví dụ một cách xếp với n = 8

    bài toán xếp hậu với n=8

    1. Giải bài toán xếp hậu sử dụng đệ quy

    Để giải quyết bài toán xếp 8 quân hậu này, chúng ta sử dụng list (mảng) a có kích thước bằng 8 với quy ước a[i]=j để đánh dấu vị trí xếp quân hậu thuộc dòng i ở cột thứ j.

    1.1. Tạo danh sách để lưu vị trí các quân hậu

    Để khởi tạo mảng a, chúng ta dùng lệnh

    n = 8
    a = n*[0]

    Lưu ý rằng các list danh sách trong Python được đánh chỉ số từ 0, do đó vị trí của quân hậu ở dòng thứ nhất được lưu ở a[0]

    Ví dụ a=[0, 4, 7, 5, 2, 6, 1, 3]có ý nghĩa, quân hậu ở dòng thứ nhất sẽ ở cột thứ nhất, quân hậu ở dòng thứ hai sẽ ở cột thứ 5, quân hậu ở dòng thứ 3 sẽ ở cột thứ 8…

    1.2. Viết hàm in vị trí các quân hậu dạng ma trận

    Chúng ta sẽ viết một hàm print_board() để in ra màn hình vị trí các quân hậu dạng ma trận (bảng), ví dụ với mảng a ở trên, in ra màn hình được:

    1 0 0 0 0 0 0 0 
    0 0 0 0 1 0 0 0 
    0 0 0 0 0 0 0 1 
    0 0 0 0 0 1 0 0 
    0 0 1 0 0 0 0 0 
    0 0 0 0 0 0 1 0 
    0 1 0 0 0 0 0 0 
    0 0 0 1 0 0 0 0

    Hàm in vị trí các quân hậu như sau:

    def print_board(b):
       l = len(b)
       for i in range(l):
          for j in range(l):
             if j == a[i]:
                print(1, end = " ")
             else:
                print(0, end = " ")
          print()

    1.3. Viết hàm kiểm tra vị trí (d,c) có còn đặt được quân hậu mới không?

    Chúng ta quy ước dc là vị trí của dòng và cột đang xét để xem có khả năng đặt được quân hậu mới hay không.

    Rõ ràng, ta chỉ cần kiểm tra xem trong các dòng từ 0 tới d-1 đã có quân hậu nào mà có thể ăn được quân hậu nếu đặt ở ô đang xét hay không, do đó chỉ cần duyệt từ các dòng có chỉ số thuộc range(d).

    Chúng ta viết hàm possible(d,c) để kiểm tra vị trí d,c còn có khả năng đặt hậu hay không. Khi đó, kết quả trả về là False nếu một trong 3 khả năng sau xảy ra:

    • Tại cột c đã có quân hậu ở dòng i nào đó, điều kiện là a[i] == c
    • Tại 2 đường chéo đi qua điểm (d,c) đã có một quân hậu nào đó.

    Lưu ý rằng các đường chéo sẽ song song hoặc trùng với các tia phân giác của góc phần tư trong hệ tọa độ Oxy. Các tia phân giác có phương trình là y = x hoặc y = - x. Do đó phương trình các đường chéo đi qua điểm có tọa độ (d,c) sẽ là c - d =y -x  hoặc c + d = y  + x. Từ đó suy ra điều kiện:

    a[i] == c  or c - d == a[i] - i or c + d == a[i] + i

    Mã nguồn của hàm kiểm tra vị trí có thể đặt hậu như sau:

    def possible(x, y):
       for i in range(x):      
          if a[i] == y  or y - x == a[i] - i or y + x == a[i] + i:
             return False
       return True

    1.4. Hàm đệ quy để sinh ra các vị trí đặt quân hậu

    def gen(i, n):
       for j in range(n):
          if possible(i,j):
             a[i] = j
             if i == n - 1:
                print(a)
             gen(i+1, n)

    Chương trình bắt đầu với lời gọi gen(0, n).

    Mã nguồn hoàn chỉnh bằng Python của bài toán xếp hậu như sau:

    n = 8
    a = n*[0]
    
    def print_board(b):
       l = len(b)
       for i in range(l):
          for j in range(l):
             if j == a[i]:
                print(1, end = " ")
             else:
                print(0, end = " ")
          print()
    
    def possible(d, c):
       for i in range(d):
          # if a[i] == y or abs(i - x) == abs(a[i] - y):
          if a[i] == c  or c - d == a[i] - i or c + d == a[i] + i:
             return False
       return True
    
    def gen(i, n):
       for j in range(n):
          if possible(i,j):
             a[i] = j
             if i == n - 1:
                print(a)
             gen(i+1, n)
    
    gen(0, n)

    Kết quả trả về là tất cả các phương án mỗi phương án là một danh sách chứa vị trí các quân hậu. Nếu muốn in một phương án nào đó, chúng ta sử dụng hàm print_board()

    2. Bài toán xếp hậu quay lui

    Chúng tôi giới thiệu thêm bài toán xếp hậu sử dụng thuật toán quay lui để bạn đọc tham khảo. Cách làm này có thời gian chạy khá chậm, và mỗi lần chỉ in ra một phương án xếp các quân hậu. Muốn tìm được phương án khác, chúng ta cần thay đổi giá trị của mảng board ban đầu.

    Cách giải này tôi có tham khảo từ bài viết này.

    board = [
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0]
          ]
    
    
    def print_board(bo):
        for d in bo:        
            for c in d:
                print(c, end = " ")
            print()
    
    
    def solve(bo):
       l = len(bo)
       for d in range(l):
          for c in range(l):
             if bo[d][c] == 0:
                if possible(bo, d, c):
                   bo[d][c] = 1
                   solve(bo)
                if sum(sum(a) for a in bo) == l:
                   return bo
                else:
                   bo[d][c] = 0
       return bo		
    
    
    def possible(bo, d, c):
       l = len(bo)
       for i in range(l):
          if bo[i][c] == 1:
             return False
       for i in range(l):
          if bo[d][i] == 1:
             return False
       for i in range(l):
          for j in range(l):
             if bo[i][j] == 1:
                if c-d == j-i or c+d == i+j:
                   return False
       return True
    
    solve(board)
    print_board(board)
  • Thuật toán giải sudoku bằng quay lui backtracking

    Thuật toán giải sudoku bằng quay lui backtracking

    Thuật toán giải sudoku bằng quay lui backtracking

    Trong bài này chúng ta sẽ sử dụng thuật toán quay lui để giải quyết bài toán giải Sudoku. Để hiểu thuật toán quay lui là gì mời bạn xem bài Thuật toán quay lui và minh họa.

    Xem thêm: Python: Bài toán xếp hậu sử dụng đệ quy

    Bài viết tham khảo từ techwithtim.net

    1. Giới thiệu luật chơi và cách giải Sudoku

    Sudoku là một trò chơi giải đố theo wiki định nghĩa như sau:

    Sudoku (数独すうどく (số độc) sūdoku?) (suːˈdoʊkuː/, /-ˈdɒ-/, /sə-/, ban đầu có tên gọi là Number Place) là một trò chơi câu đố sắp xếp chữ số dựa trên logic theo tổ hợp. Mục tiêu của trò chơi là điền các chữ số vào một lưới 9×9 sao cho mỗi cột, mỗi hàng, và mỗi phần trong số chín lưới con 3×3 cấu tạo nên lưới chính (cũng gọi là “hộp”, “khối”, hoặc “vùng”) đều chứa tất cả các chữ số từ 1 tới 9. Câu đố đã được hoàn thành một phần, người chơi phải giải tiếp bằng việc điền số. Mỗi câu đố được thiết lập tốt có một cách làm duy nhất.

    Cách giải trò chơi Sudoku, mời các bạn xem video hướng dẫn sau:

    2. Thuật toán giải Sudoku

    Sau đây ta sẽ tìm thuật toán giải Sudoku bằng kỹ thuật backtracking, ngôn ngữ lập trình sử dụng là Python. Các bước tiến hành như sau:

    • Viết hàm in câu đố Sudoku ra màn hình.
    • Tìm vị trí các ô trống trong Sudoku.
    • Với mỗi vị trí ô trống vừa tìm được, lần lượt thử đặt số từ 1 đến 9 vào ô trống đó. Kiểm tra xem sau khi thử đặt số đó vào ô trống đó thì có hợp lệ (thỏa mãn các điều kiện về luật chơi của Sudoku hay không). Nếu hợp lệ thì tiếp tục tìm các ô trống tiếp theo và lại thử, nếu không thì thử với số_tiếp_theo
    • Lặp lại quy trình trên cho đến khi không còn ô trống nào trên câu đố, hoặc không tìm được lời giải.

    Input, một câu đố sudoku biểu diễn bởi danh sách list 2 chiều (một danh sách gồm 9 phần tử, mỗi phần tử là dòng – lại là một danh sách gồm 9 phần tử  tương ứng với 9 ô trong một dòng) với các ô trống được quy ước điền bởi số 0, ví dụ Sudoku cau_do được biểu diễn như sau:

    cau_do = [
        [7,8,0,4,0,0,1,2,0],
        [6,0,0,0,7,5,0,0,9],
        [0,0,0,6,0,1,0,7,8],
        [0,0,7,0,4,0,2,6,0],
        [0,0,1,0,5,0,9,3,0],
        [9,0,4,0,6,0,0,0,5],
        [0,7,0,3,0,0,0,1,2],
        [1,2,0,0,0,7,4,0,0],
        [0,4,9,2,0,6,0,0,7]
    ]

    Chú ý rằng chỉ số index trong Python được đánh từ 0 trở đi, do đó các vị trí của từng ô trong bảng số sẽ là cau_d0[0][0] cho đến cau_do[8][8], ở đây cau_do[d][c] là ô số ở vị trí dòng d và cột c.

    2.1. Viết hàm in câu đố Sudoku ra màn hình

    Ở đây chúng ta sử dụng giao diện dòng lệnh, chưa sử dụng giao diện đồ họa GUI nên sẽ sử dụng hàm print() của Python để in một đối tượng ra màn hình CMD.

    Ta sẽ viết hàm in_sudoku để in một câu đố Sudoku có tên là q ra màn hình, sử dụng biến dc để biểu diễn dòng và cột.

    Nếu dòng d là dòng thứ 3 hoặc 6 thì ta sẽ in ra màn hình một dòng gồm các kí tự - - - - - - - - - - - để ngăn cách, mục đích là biểu diễn cho các khối ô vuông 3x3 của Sudoku. Tương tự, nếu cột ở vị trí 3 hoặc 6 thì ta sẽ in ra kí tự | để ngăn cách. Nếu cột ở vị trí thứ 8 thì ta sẽ xuống dòng mới.

    def in_sudoku(q):
        for d in range(len(q)):
            if d % 3 == 0 and d != 0:
                print("- - - - - - - - - - -")
            for c in range(len(q[0])):
                if c % 3 == 0 and c != 0:
                    print("| ", end ="")
                if c == 8:
                    print(str(q[d][c]))
                else:
                    print(str(q[d][c]) + " ", end = "")

    Thử in với cau_do ở phần đầu, chúng ta được kết quả như sau, ở đây tôi dùng SublimeText để code:

    thuật toán giải sudoku

    2.2. Viết hàm tìm các ô trống trong Sudoku

    Mục tiêu của chúng ta là tìm các vị trí ô trống trong câu đố q

    def tim_o_trong(q):
        for d in range(len(q)):
            for c in range(len(q[0])):
                if q[d][c] == 0:
                    return d, c
        return None

    2.3.  Viết hàm kiểm tra tính hợp lệ của một câu đố

    def kiem_tra(q, gia_tri, dong, cot):
        for i in range(len(q[0])):
            if q[i][cot] == gia_tri and i != dong:
                return False
        for i in range(len(q)):
            if q[dong][i] == gia_tri and i != cot:
                return False
    
        x = cot // 3
        y = dong // 3
    
        for i in range(y*3, y*3+3):
            for j in range(x*3, x*3+3):
                if q[i][j] == gia_tri and i != dong and j != cot:
                    return False
        return True

    2.4. Viết hàm chính để tìm lời giải cho một câu đố Sudoku

    def giai(q):
        tim_thay = tim_o_trong(q)
        if not tim_thay:
            return True
        else:
            d, c = tim_thay
        for i in range(1,10):
            if kiem_tra(q, i, d, c):
                q[d][c] = i
                if giai(q):
                    return True
                else:
                    q[d][c] = 0
            
        return False

    3. Chương trình Python giải Sudoku hoàn chỉnh

    cau_do = [
        [7,8,0,4,0,0,1,2,0],
        [6,0,0,0,7,5,0,0,9],
        [0,0,0,6,0,1,0,7,8],
        [0,0,7,0,4,0,2,6,0],
        [0,0,1,0,5,0,9,3,0],
        [9,0,4,0,6,0,0,0,5],
        [0,7,0,3,0,0,0,1,2],
        [1,2,0,0,0,7,4,0,0],
        [0,4,9,2,0,6,0,0,7]
    ]
    
    def in_sudoku(q):
        for d in range(len(q)):
            if d % 3 == 0 and d != 0:
                print("- - - - - - - - - - -")
            for c in range(len(q[0])):
                if c % 3 == 0 and c != 0:
                    print("| ", end ="")
                if c == 8:
                    print(str(q[d][c]))
                else:
                    print(str(q[d][c]) + " ", end = "")
    
    
    def giai(q):
        tim_thay = tim_o_trong(q)
        if not tim_thay:
            return True
        else:
            d, c = tim_thay
        for i in range(1,10):
            if kiem_tra(q, i, d, c):
                q[d][c] = i
                if giai(q):
                    return True
                else:
                    q[d][c] = 0
            
        return False
            
        
    
    def tim_o_trong(q):
        for d in range(len(q)):
            for c in range(len(q[0])):
                if q[d][c] == 0:
                    return d, c
        return None
    
    
    def kiem_tra(q, gia_tri, dong, cot):
        for i in range(len(q[0])):
            if q[i][cot] == gia_tri and i != dong:
                return False
        for i in range(len(q)):
            if q[dong][i] == gia_tri and i != cot:
                return False
    
        x = cot // 3
        y = dong // 3
    
        for i in range(y*3, y*3+3):
            for j in range(x*3, x*3+3):
                if q[i][j] == gia_tri and i != dong and j != cot:
                    return False
        return True
    
    in_sudoku(cau_do)
    giai(cau_do)
    print('Loi giai cua Sudoku tren la:')
    in_sudoku(cau_do)

    Cho chạy chương trình, chúng ta được kết quả như hình sau:

    giải sudoku bằng Python

  • Thuật toán quay lui và minh họa

    Thuật toán quay lui và minh họa

    Thuật toán quay lui và minh họa

    1. Thuật toán quay lui là gì?

    Thuật toán quay lui (Backtracking) là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

    2. Thuật toán quay lui sử dụng khi nào?

    Thuật toán quay lui thường được sử dụng để giải bài toán liệt kê các cấu hình (như bài toán sinh các xâu nhị phân). Mỗi cấu hình được xây dựng bằng cách xác định từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.
    Các bước trong việc liệt kê cấu hình dạng X[1…n]:
    • Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
    • Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho tới bước:
    • Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
    • Thông báo cấu hình tìm được.

    Để cài đặt thuật toán quay lui, chúng ta sử dụng một chương trình con (hàm function, thủ tục procedure) và gọi đến hàm đó trong chương trình chính của mình. Mô hình của thuật toán quay lui sử dụng ngôn ngữ Python như sau:

    def quay_lui(i):
       for j in [tập_các_phương_án_x[i] có thể nhận]:
          <thử đặt x[i] = j>
          if <x[i] là phần tử cuối cùng trong cấu hình>:
             <thông báo cấu hình>
          else:
             <ghi nhận việc cho x[i] nhận giá trị j nếu cần>
             <gọi đệ quy đến quay_lui(i+1)>
             <bỏ ghi nhận việc cho x[i] nhận giá trị j để thử giá trị khác nếu cần>

    Thuật toán quay lui sẽ bắt đầu bằng lời gọi quay_lui(1)

    3. Minh họa của thuật toán quay lui (Backtracking)

    3.1. Sử dụng thuật toán quay lui để sinh các dãy nhị phân độ dài n

    Dưới đây, chúng ta cùng xem mã chương trình sinh các dãy nhị phân có độ dài n bằng cách sử dụng thuật toán quay lui.

    n = 3
    x = n*[0]
    
    
    def fine_print(x):
       tmp = ''
       for i in x:
          tmp += str(i)
       return tmp
    
    
    def bin_gen(i):
       for j in range(0,3):
          x[i] = j
          if i == n-1:
             print(fine_print(x))
          else:
             bin_gen(i+1)
    
    bin_gen(0)

    Các giải khác bằng cách sử dụng vòng lặp, xin mời bạn đọc xem tại đây Thuật toán sinh các dãy nhị phân có độ dài n

    3.2. Sử dụng backtracking để giải Sudoku

    thuật toán giải sudoku

    Mời các bạn xem chi tiết trong bài Thuật toán giải sudoku bằng quay lui backtracking

    3.3. Sử dụng quay lui để giải bài toán xếp hậu

    Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột hoặc cùng đường chéo. Hãy tìm các xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào. Mời bạn xem chi tiết trong bài Python: Bài toán xếp hậu sử dụng đệ quy

    bài toán xếp hậu với n=8

    4. Đặc điểm của thuật toán quay lui

    Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).
    • Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.
    • Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:
    • Rơi vào tình trạng “thrashing”: quá trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
      • Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
      • Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết được nhánh tìm kiếm sẽ đi vào bế tắc.
  • Thuật toán sinh các dãy nhị phân có độ dài n

    Thuật toán sinh các dãy nhị phân có độ dài n

    Thuật toán sinh các dãy nhị phân có độ dài n

    Trong bài viết này chúng ta sẽ tìm cách liệt kê toàn bộ các dãy nhị phân có độ dài n cho trước.

    • Yêu cầu: Liệt kê tất cả các dãy nhị phân có độ dài n. (dãy nhị phân là dãy chỉ gồm hai số 01)
    • Input: Nhập vào n – độ dài của chuỗi nhị phân cần in ra.
    • Output : In ra màn hình tất cả các chuỗi nhị phân có độ dài n nhập từ đầu vào.

    Ví dụ:

    • Input: 3
    • Output:
    • 000   001   010   011   100   101   110   111

    1. Liệt kê các dãy nhị phân độ dài n bằng phương pháp sinh tuần tự

    Phương pháp sinh tuần tự sử dụng để liệt kê tất cả các phương án [cấu hình] của bài toán tổ hợp, sao cho các bài toán đó thỏa mãn:

    • Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể biết đượccấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó.
    • Xây dựng được thuật toán từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó.

    Theo đó, thuật toán sinh tuần tự các cấu hình được mô tả như sau:

    <Xây dựng cấu hình đầu tiên>
    while True:
       <Đưa ra cấu hình đang có>
       <Từ cấu hình đang có sinh ra cấu hình kế tiếp nếu còn>
       if <hết cấu hình>:
          break

    Lưu ý rằng, Python không có câu lệnh điều khiển luồn repeat... until như một số ngôn ngữ khác, nên ta phải sử dụng vòng lặp while (Xem chi tiết trong bài Bài 7. Câu lệnh vòng lặp while trong Python)

    Vì kiểu xâu string là immutable nên chúng ta sẽ sử dụng kiểu danh sách list để thao tác trên đó, và định nghĩa hàm fine_print() để in toàn bộ các phần tử của danh sách dưới dạng xâu kí tự.

    Một lưu ý là các chỉ số index trong Python luôn được đánh số từ 0, do đó phần tử thứ nhất của một danh sách list x sẽ có chỉ số là 0, tức là phần tử x[0]

    n = 3
    s = n*[0]
    
    def fill_char(s,i):
       for j in range(i,n):
          s[j] = 0
    def fine_print(x):
       tmp = ''
       for i in x:
          tmp += str(i)
       return tmp
    
    
    while True:
       print(fine_print(s))
       i = n - 1
       while (i > -1) and s[i] == 1:
          i = i - 1
       s[i] = 1
       fill_char(s,i+1)
       if i == -1:
          break

    Kết quả thu được như sau:

    000
    001
    010
    011
    100
    101
    110
    111

    2. Sinh các dãy nhị phân độ dài n bằng thuật toán quay lui (Backtracking)

    liệt kê các chuỗi nhị phân bằng thuật toán quay lui

    Vẫn sử dụng kiểu danh sách list và hàm fine_print() như ở phần trên, chúng ta có chương trình liệt kê tất cả các xâu nhị phân có độ dài n sử dụng thuật toán quay lui như sau:

    n = 3
    x = n*[0]
    
    
    def fine_print(x):
       tmp = ''
       for i in x:
          tmp += str(i)
       return tmp
    
       
    def bin_gen(i):
       for j in range(0,2):
          x[i] = j
          if i == n-1:
             print(fine_print(x))
          else:
             bin_gen(i+1)
    
    bin_gen(0)

    Thuật toán quay lui có ưu điểm là rất dễ cài đặt so với phương pháp sinh tuần tự, hơn nữa có thể dễ dàng mở rộng để giải quyết nhiều bài toán khác nhau. Chẳng hạn, ta dễ dàng giải quyết bài toán sinh các dãy tam phân bằng cách thay range(0,2) bởi range(0,3). Kết quả thu được như sau:

    000
    001
    002
    010
    011
    012
    020
    021
    022
    100
    101
    102
    110
    111
    112
    120
    121
    122
    200
    201
    202
    210
    211
    212
    220
    221
    222

     

  • Python Arrays – Python Lists

    Python Arrays – Python Lists

    Python Arrays – Python Lists

    Does python have an array?

    • Arrays are used to store multiple values in one single variable.
    • Python does not have built-in support for Arrays, but Python Lists can be used instead.

    What is Python Lists/Python Arrays?

    Python Lists are used to store multiple items in a single variable. For example, fruits_list has 4 items apple, banana, cherry, orange

    fruits_list = ["apple", "banana", "cherry", "orange"]

    Lists are one of 4 built-in data types in Python used to store collections of data, the other 3 are Tuple, Set, and Dictionary, all with different qualities and usage.

    Lists are created using square brackets []

    Python List/Array Methods

    Python has a set of built-in methods that you can use on lists/arrays.

    Method Description
    append() Adds an element at the end of the list
    clear() Removes all the elements from the list
    copy() Returns a copy of the list
    count() Returns the number of elements with the specified value
    extend() Add the elements of a list (or any iterable), to the end of the current list
    index() Returns the index of the first element with the specified value
    insert() Adds an element at the specified position
    pop() Removes the element at the specified position
    remove() Removes the first item with the specified value
    reverse() Reverses the order of the list
    sort() Sorts the list

    Python Lists/Python Arrays Items

    • List items are ordered, changeable, and allow duplicate values.
    • List items are indexed, the first item has index [0], the second item has index [1] etc. For example, fruits_list = ["apple", "banana", "cherry", "orange"] then fruits_list[0]="apple", fruits_list[1]=banana

    Ordered

    • When we say that lists are ordered, it means that the items have a defined order, and that order will not change.
    • If you add new items to a list, the new items will be placed at the end of the list.
    • Note: There are some list methods that will change the order, but in general: the order of the items will not change.
    • Changeable
    • The list is changeable, meaning that we can change, add, and remove items in a list after it has been created.

    Python List Items Allow Duplicates

    • Since lists are indexed, lists can have items with the same value:
    • Example

    fruits_list = ["apple", "banana", "cherry", "apple", "cherry"]

     

    Python List Length

    • To determine how many items a list has, use the len() function:

    Example

    Print the number of items in the list:

    fruits_list = ["apple", "banana", "cherry", "apple", "cherry"]
    len(fruits_list)

    List Items – Data Types

    • List items can be of any data type.

    Example: String, int and boolean data types:

    list1 = ["apple", "banana", "cherry"]
    list2 = [1, 5, 7, 9, 3]
    list3 = [True, False, False]
    • A list can contain different data types:

    Example: A list with strings, integers and boolean values:

    my_list = ["abc", 34, True, 40, "male"]

    type()

    • From Python’s perspective, lists are defined as objects with the data type ‘list’:
    • <class ‘list’>
    • Example: What is the data type of a list?

    mylist = ["apple", "banana", "cherry"]
    print(type(mylist))

    The list() Constructor

    • It is also possible to use the list() constructor when creating a new list.
    • Example

      Using the list() constructor to make a List:

      thislist = list(("apple", "banana", "cherry")) # note the double round-brackets
      print(thislist)

    Python List of Lists (Python List in list)

    A list of lists in Python is a list object where each list element is a list by itself. Create a list of list in Python by using the square bracket notation to create a nested list [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

    Create a List of Lists in Python

    Create a list of lists by using the square bracket notation. For example, to create a list of lists of integer values, use [[1, 2], [3, 4]]. Each list element of the outer list is a nested list itself.

    Convert List of Lists to One List

    Say, you want to convert a list of lists [[1, 2], [3, 4]] into a single list [1, 2, 3, 4]. How to achieve this? There are different options:

    • List comprehension [x for l in lst for x in l] assuming you have a list of lists lst.
    • Unpacking [*lst[0], *lst[1]] assuming you have a list of two lists lst.
    • Using the extend() method of Python lists to extend all lists in the list of lists.

    Find examples of all three methods in the following code snippet:

    lst = [[1, 2], [3, 4]]
    
    # Method 1: List Comprehension
    flat_1 = [x for l in lst for x in l]
    
    # Method 2: Unpacking
    flat_2 = [*lst[0], *lst[1]]
    
    # Method 3: Extend Method
    flat_3 = []
    for l in lst:
    flat_3.extend(l)
    
    ## Check results:
    print(flat_1)
    # [1, 2, 3, 4]
    
    print(flat_2)
    # [1, 2, 3, 4]
    
    print(flat_3)
    # [1, 2, 3, 4]

    Due its simplicity and efficiency, the first list comprehension method is superior to the other two methods.

  • Python Get input from Console

    Python Get input from Console

    Python Get input from Console

    How to prompt for user input and read command-line arguments. Python user input from the keyboard can be read using the input() built-in function. The input from the user is read as a string and can be assigned to a variable. After entering the value from the keyboard, we have to press the “Enter” button. Then the input() function reads the value entered by the user.

    See more:

    1. What is Console in Python?

    Console (also called Shell) is basically a command-line interpreter that takes input from the user i.e one command at a time and interprets it. If it is error free then it runs the command and gives required output otherwise shows the error message. A Python Console looks like this.

    python get input from console

    2. Python Get input from Console

    To read user input you can try the cmd module for easily creating a mini-command line interpreter (with help texts and autocompletion) and raw_input (input for Python 3+) for reading a line of text from the user.

    text = raw_input("prompt") # Python 2 
    text = input("prompt") # Python 3

    There are two modules for parsing command line options: optparse (deprecated since Python 2.7, use argparse instead) and getopt. If you just want to input files to your script, behold the power of fileinput.

    Note that, raw_input is no longer available in Python 3.x. But raw_input was renamed input, so the same functionality exists.

    3. String and Numeric input

    The input() function, by default, will convert all the information it receives into a string.  Numbers, on the other hand, need to be explicitly handled as such since they come in as strings originally.

    To converts the string into a integer, you can use int()function. Converts the string into decimal format, use float()function.

    user_input1 = input ("Enter a integer number: ")
    int_number = int(user_input1)
    print ("The number you entered is: ", input_number)
    
    user_input2 = input ("Enter a decimal number: ") 
    float_number = float(user_input2)
    print ("The number you entered is: ", float_number)

    Another way to do the same thing is as follows:

    int_number = int(input ("Enter a integer number: "))
    print ("The number you entered is: ", input_number)
    
    float_number = float(input ("Enter a decimal number: "))
    print ("The number you entered is: ", float_number)
  • Python Solve Quadratic Equation

    Python Solve Quadratic Equation

    Python Solve Quadratic Equation

    Given a quadratic equation the task is solve the equation or find out the roots of the equation. Standard form of quadratic equation is $$ax^2+ bx + c =0$$ where, $a, b$, and $c$ are coefficient and real numbers and also $a \ne 0$ 0. If $a$ is equal to $0$ that equation is not valid quadratic equation.

    See more: Hướng dẫn lập trình Python – Python Guide

    1. Python Solve Quadratic Equation Using the Direct Formula

    Using the below quadratic formula we can find the root of the quadratic equation.

    Let $\Delta =b^2-4ac$, then:

    • If $b^2 – 4ac<0$, then roots are complex (not real).
    • If $b^2 – 4ac=0$, then roots are real and both roots are same $x=\frac{-b}{2a}$.
    • If $b^2 – 4ac>0$, then roots are real and different $$ x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}.$$
    # Python program to find roots of quadratic equation 
    import math 
    
    
    # function for finding roots 
    def equationroots(): 
    
       a = float(input('Enter coefficient a: '))
       while a == 0:
          print("Coefficient a can not equal 0")
          a = float(input('Enter coefficient a: '))
       b = float(input('Enter coefficient b: '))
       c = float(input('Enter coefficient c: '))
       
       # calculating dcriminant using formula 
       d = b * b - 4 * a * c 
       
       # checking condition for dcriminant 
       if d > 0: 
          print("Your equation has real and different roots:") 
          print((-b + math.sqrt(d))/(2 * a)) 
          print((-b - math.sqrt(d))/(2 * a)) 
       
       elif d == 0: 
          print("Your equation has real and same roots:") 
          print(-b / (2 * a)) 
       
       # when dcriminant is less than 0 
       else: 
          print("Your equation has complex roots:") 
          print(- b / (2 * a), " +", math.sqrt(-d),'i') 
          print(- b / (2 * a), " -", math.sqrt(-d),'i') 
    
    
    equationroots() 
    

    2. Python Solve Quadratic Equation Using the Complex Math Module

    First, we have to calculate the discriminant and then find two solution of quadratic equation using cmath module.

    cmath module — Mathematical functions for complex numbers — provides access to mathematical functions for complex numbers. The functions in this module accept integers, floating-point numbers or complex numbers as arguments. They will also accept any Python object that has either a __complex__() or a __float__() method: these methods are used to convert the object to a complex or floating-point number, respectively, and the function is then applied to the result of the conversion.

    # Python program to find roots of quadratic equation 
    import cmath 
    
    
    # function for finding roots 
    def equationroots(): 
    
       a = float(input('Enter coefficient a: '))
       while a == 0:
          print("Coefficient a can not equal 0")
          a = float(input('Enter coefficient a: '))
       b = float(input('Enter coefficient b: '))
       c = float(input('Enter coefficient c: '))
       
       # calculating dcriminant using formula 
       d = b * b - 4 * a * c 
       
       if d == 0: 
          print("Your equation has real and same roots:") 
          print(-b / (2 * a)) 
       
       # when dcriminant is not equal 0 
       else: 
          print("Your equation has complex roots:") 
          print(- b / (2 * a), " +", cmath.sqrt(d)) 
          print(- b / (2 * a), " -", cmath.sqrt(d)) 
    
    
    equationroots() 
    
    input()
    

     

  • Hàm trong Python

    Hàm trong Python

    Hàm trong Python

    1. Khái niệm hàm trong Python

    Trong lập trình, để thực hiện một công việc nào đó, và công việc này lặp đi lặp lại, chúng ta sử dụng hàm sẽ tiết kiệm được công sức. Chính bạn đã sử dụng một số hàm đã được xây dựng sẵn trong Python, ví dụ như hàm print(), type()

    Chẳng hạn, trong chương trình chúng ta có một nhiệm vụ là giải phương trình bậc hai năm lần, thì mỗi lần người dùng sẽ nhập vào các hệ số a, b, c từ bàn phím, chương trình sẽ giải phương trình với các hệ số đó và trả lại kết quả là vô nghiệm, có nghiệm kép hay hai nghiệm phân biệt và in các nghiệm đó. Nếu không sử dụng hàm ta phải đánh máy đoạn chương trình sau 5 lần!

    from math import sqrt
    
    a = int(input("a = "))
    b = int(input("b = "))
    c = int(input("c = "))
    d = b**2 – 4*a*c
    if d < 0:
          print("Phương trình vô nghiệm.")
    elif d == 0:
          print("Phương trình có nghiệm kép x = ", -b /(2*a))
    else:
          print("Phương trình có hai nghiệm ", (-b + sqrt(d))/(2*a), " và ",\   (-b - sqrt(d))/(2*a))

    Khi đó, chương trình trông sẽ dài dòng phức tạp, hơn nữa, mỗi lần giải một phương trình mới ta lại phải gõ lại đoạn mã  này, tính tái sử dụng không[1] có. Lúc này, chúng ta cần sử dụng đến hàm.

    2. Khai báo hàm trong Python

    Để khai báo một hàm trong Python chúng ta sử dụng từ khóa def với cú pháp:

    def name([arg,... arg=value,... *arg, **arg]):
        """Mô tả về hàm nếu (nên) có (phần này thường gọi là docstring)"""
        <khối lệnh>
        return [giá trị trả về]

    Trong đó name là tên của hàm, được đặt tên theo đúng quy tắc đặt tên và theo sau phải là cặp ngoặc tròn (). Bên trong cặp ngoặc tròn, ta có arg là các tham số nếu có, value là giá trị mặc định của tham số – nếu người dùng không cung cấp một giá trị cho tham số khi gọi hàm thì giá trị mặc định này sẽ được sử dụng, *arg**arg là các tham số kiểu tuple, tức một bộ các tham số.

    Một hàm trong Python có thể có tham số hoặc không. Cần lưu ý rằng, nếu hàm có tham số nhận các giá trị mặc định, thì các tham số này phải được khai báo sau các tham số không nhận giá trị mặc định. Chẳng hạn, khai báo hàm bậc hai y=a*x**2+b*x+c thì thường giá trị mặc định là a=1, nhưng ta không thể khai báo tham số a lên trước, mà bắt buộc phải khai báo tham số a cuối cùng, chẳng hạn

    def ham_bac_hai(b, c, a = 1):
        <khối lệnh thực thi hàm>

    Tiếp theo là dấu hai chấm : và xuống dòng để bắt đầu vào phần thân của hàm. Phần này có thể gồm chú thích mô tả về hàm để giúp cho các lập trình viên khác, và chính bản thân chúng ta sau này, hiểu rõ hơn về hàm và khối lệnh chính của hàm để thực hiện nhiệm vụ đề ra.

    Cuối cùng là từ khóa return để thoát khỏi hàm và trở về chương trình chính, hoặc trả về giá trị của hàm đối với hàm có giá trị trả về; phần này không bắt buộc phải có.

    Một hàm nếu được khai báo trong một lớp thì còn được gọi là một phương thức method của lớp.

    3. Lời gọi đến hàm trong Python

    Để gọi một hàm có tên là name đã được định nghĩa, ta sử dụng câu lệnh name(). Hãy quay trở lại ví dụ giải phương trình bậc hai để hiểu rõ hơn.

    from math import sqrt
    def giai_pt():
          a = int(input("a = "))
          b = int(input("b = "))
          c = int(input("c = "))
          d = b**2 – 4*a*c
          if d < 0:
                print("Phương trình vô nghiệm.")
          elif d == 0:
                print("Phương trình có nghiệm kép x = ", -b /(2*a))
          else:
                print("Phương trình có hai nghiệm ", (-b + sqrt(d))/(2*a),
                " và ", (-b – sqrt(d))/(2*a))

    Như vậy, hàm giai_pt ở trên không có tham số truyền vào và cũng không có kết quả trả về, bởi bản thân các lệnh trong hàm đã in ra nghiệm của phương trình rồi. Để gọi hàm này ta chỉ đơn giản là dùng câu lệnh giai_pt().

    Ở cách làm này, trong bản thân hàm đã có các câu lệnh để người dùng nhập vào giá trị của các hệ số a, b, c của phương trình. Nếu muốn truyền các hệ số khi gọi hàm giai_pt() ta có thể viết lại như sau:

    from math import sqrt
    def giai_pt(a, b, c):
          d = b**2 – 4*a*c
          if d < 0:
                print("Phương trình vô nghiệm.")
          elif d == 0:
                print("Phương trình có nghiệm kép x = ", -b /(2*a))
          else:
                print("Phương trình có hai nghiệm ", (-b + sqrt(d))/(2*a),\
                " và ", (-b – sqrt(d))/(2*a))

    Lúc này, để giải phương trình bậc hai với các hệ số a = 1, b = -3, c = 5 ta chỉ việc gọi hàm bằng cách sử dụng câu lệnh giai_pt(1, -3, 5).

    4. Giá trị trả về của hàm

    Hàm trong Python có thể có hoặc không có giá trị trả về. Điều này khác với các hàm số trong toán học bắt buộc phải nhận một giá trị trả về, thì hàm trong Python có thể chỉ thực hiện một nhiệm vụ nào đó như in ra màn hình một chuỗi, xóa hết các phần tử của một tập hợp…

    Trong trường hợp hàm có kết quả trả về ta sử dụng từ khóa return, theo sau là giá trị trả về của hàm. Khi đó hàm có thể được sử dụng như một biến để tính toán. Hãy xét một hàm đơn giản, tên là cong để cộng hai số nguyên ab, giá trị trả về chính là tổng của hái số đó, định nghĩa như sau:

    def cong(a, b):
          return a + b

    Chúng ta sẽ thử gọi hàm này với các tham số truyền vào  a = 3, b =7.

    >>> cong(3, 7)
    10
    >>> cong(3, 7) + 5
    15

    Nếu ta thực hiện chương trình này trong trình thông dịch Python, thì ở lần gọi hàm thứ nhất kết quả trả về là 10, ở lần gọi thứ hai, bản thân hàm được sử dụng như một biến số để thực hiện tiếp phép cộng, và kết quả trả về là 15.

    Tuy nhiên, nếu các bạn soạn một script có nội dung như sau

    def cong(a, b):
          return a + b
    
    cong(3, 7)
    cong(4, 7) + 5

    và lưu lại với tên có phần mở rộng .py rồi chạy script này thì kết quả là không xuất hiện gì cả trên màn hình! Lí do là chương trình vẫn tính a + b, và vẫn trả về kết quả này và được sử dụng để tính toán tiếp nhưng không được in ra màn hình. Lúc này, muốn in kết quả ra chúng ta phải sử dụng đến hàm print() của Python.

    def cong(a, b):
          return a + b
    
    print(cong(3, 7))
    print(cong(4, 7) + 5)

    Theo sau từ khóa return là một giá trị, một biểu thức, một câu lệnh, thậm chí lại là một hàm[2] hoặc không có gì cả. Nếu không có gì, thì chương trình chỉ đơn giản là thoát khỏi hàm mà thôi và trả về giá trị None. Mỗi khi gặp từ khóa return thì hàm sẽ kết thúc, chương trình sẽ thoát khỏi hàm và thực hiện câu lệnh tiếp theo. Hãy xem ví dụ sau để hiểu rõ hơn:

    def test():
          print(1)
          return
          print(2)

    Chúng ta sẽ chạy thử.

    >>> test()
    1
    >>> print(test())
    1
    None

    Ta thấy ngay, câu lệnh print(2) không được thực thi vì trước đó chương trình đã thực hiện lệnh return rồi. Hơn nữa, lệnh return này không trả về gì cả, nên nếu ta dùng lệnh print(test()) thì chương trình sẽ trả về kết quả None. Còn số 1 kia được in ra là do bản thân trong hàm có câu lệnh print(1) mà thôi.

    Bài tập

    • Viết hàm giải hệ phương trình bậc nhất hai ẩn, sử dụng định thức cấp hai.
    • Viết chương trình kiểm tra xem số tự nhiên n có phải là số nguyên tố không.
    • Viết chương trình tìm ước chung lớn nhất của hai số tự nhiên.

    5. Tham số của hàm trong Python

    Như đã nói, một hàm có thể có tham số hoặc không. Đối với hàm có tham số thì nếu số lượng tham số xác định, chúng ta có thể khai báo hết các tham số/đối số đó. Nhưng đối với các hàm có số lượng tham số chưa biết, ví dụ như tính tổng của một dãy số mà chưa biết dãy đó có bao nhiêu phần tử, thì chúng ta phải cần đến các tham số đặc biệt, khai báo với các dấu sao * trước danh sách tham số/đối số.

    Phần này có tham khảo từ blog https://icewolf-blog.herokuapp.com/post/8

     5.1. Cách truyền tham số dạng *args**kwargs trong python (abittrary arguments)

    Kiểu truyền tham số này thường được sử dụng khi định nghĩa những hàm không biết trước số lượng tham số truyền vào. Thực sự thì không nhất thiết phải là *args**kwargs, điều quan trọng là tham số có 1 dấu sao * hay là 2 dấu sao **. Đặt tên tham số là *var hay **vars hay bất cứ thứ gì bạn muốn. Nhưng để dễ hiểu thì nên dùng tên chuẩn là *args**kwargs

    5.2. *args**kwargs dùng để làm gì?

    Khi khai báo một hàm trong Python, sử dụng *args**kwargs cho phép bạn truyền vào nhiều tham số/đối số mà không cần biết trước số lượng.

    #giả sử các tham số truyền vào đều là số
    
    def sum(*args):
       total = 0
       for number in args:
         total += number
     return total
    
    # gọi hàm
    sum(1, 2, 3, 19)
    sum(1, 100)
    
    def myFun(*argv): 
        for arg in argv: 
            print (arg)
       
    myFun('Hello', 'Welcome', 'to', 'GeeksforGeeks')

    5.3. *args**kwargs khác gì nhau?

    Khi gọi hàm trong Python, có 2 kiểu truyền tham số:

    • Truyền tham số theo tên.
    • Truyền tham số bình thường theo thứ tự khai báo đối số.

    Ví dụ

    def register(name, password):
     ....
    
    #Truyền tham số theo kiểu thông thường, phải theo đúng thứ tự
    register( 'Coulson', 'hail_Hydra')
    
    #Truyền tham số theo tên, Không cần phải theo thứ tự khai báo thao số
    register( password='cookHim', name='Skye')
    • *args nhận các tham số truyền bình thường, sử dụng args như một list.
    • **kwargs nhận tham số truyền theo tên, sử dụng kwargs như một dictionary.
    def test_args(*args):
      for item in args:
         print item
    
    >>>test_args('Hello', 'world!')
    Hello
    world!
    
    def test_kwargs(*kwargs):
      for key, value in kwargs.iteritems():
         print '{0} = {1}'.format(key, value)
    
    >>test_kwargs(name='Dzung', age=10)
    age = 10
    name = Dzung

    5.4. Thứ tự sử dụng và truyền tham số *args, **kwargs và tham số bình thường

    Khi sử dụng hàm, ta phải khai báo đối số theo thứ tự ưu tiên đối số/tham số xác đinh, tiếp theo là *args và cuối cùng là **kwargs.  Đây là thứ tự bắt buộc. Và khi truyền tham số bạn cũng phải truyền theo đúng thứ tự này. Không thể truyền lẫn lộn giữa 2 loại.

    Khi sử dụng đồng thời *args**kwargs thì không thể truyền tham số bình thường theo tên

    def show_detail(name, *args, **kwargs):
    ...
    
    show_detail(name='Coulson', 'agent', age='40', level='A')
    >>> Lỗi
    
    def show_detail_2(name, **kwargs):
    ...
    
    show_detail_2(name=Coulson', age='40', level='A')
    >>> Chạy OK

    6. Lời gọi đệ quy đến hàm trong Python

    Một hàm có thể gọi lại chính nó, lúc này ta gọi là các lời gọi đệ quy[3] recursion.

    Ví dụ, cho cấp số cộng un với u1 = 5 và công sai d = 7 thì, chẳng hạn, muốn tìm số hạng thứ 20 ta lấy số hạng thứ 19 cộng thêm 7, nhưng muốn tính số hạng thứ 19 ta lại phải lấy số hạng thứ 18 cộng thêm 7 và cứ như thế cho đến số hạng thứ nhất thì đã có sẵn u1 = 5. Tổng quát, ta có công thức truy hồi như sau

    Nếu ta viết hàm cap_so_cong(n) để tính số hạng thứ n thì trong bản thân hàm này sẽ gọi lại chính nó với tham số truyền vào là n - 1:

    def cap_so_cong(n):
          if n == 1:
                return 5
          else:
                return cap_so_cong(n-1) + 7

    Lúc này, để tìm số hạng thứ n ta chỉ việc gọi hàm và truyền vào tham số n, chẳng hạn tính số hạng thứ 50 thì gọi hàm và truyền vào cho nó tham số n = 50, cap_so_cong(50):

    >>> cap_so_cong(50)
    348

    Một hàm có thể gọi lại chính nó nhiều lần, ví dụ, chúng ta xét dãy số Fibonacci

    Chúng ta có chương trình như sau

    def fibonacci(n):
          if n == 1 or n == 2:
                return 1
          else:
                return fibonacci(n-1) + fibonacci(n-2)

    Khi chạy chương trình, thử tìm số Fibonacci thứ 30 ta được kết quả

    >>> fibonacci(30)
    832040

    Tuy nhiên, trong lập trình, chúng ta nên hạn chế các lời gọi đệ quy, vì như thế chương trình sẽ cần rất nhiều bộ nhớ, chẳng hạn, ta tìm số Fibonacci thứ 100 thôi đã phải đợi rất lâu, vì bản thân mỗi lần gọi hàm, chương trình sẽ gọi lại chính nó hai lần và cứ như thế, do đó số lượng lời gọi hàm sẽ tăng lên rất nhiều với tốc độ cấp số nhân!

    Bài tập

    • Viết hàm cap_so_nhan(n) để tìm số hạng thứ n của một cấp số nhân với số hạng đầu bằng 7 và công bội bằng 2.
    • Viết hàm giai_thua(n) để tính giai thừa[4] của số tự nhiên n, chẳng hạn giai_thua(6) trả về kết quả 720.
    • Tìm tất cả các số tự nhiên hai chữ số mà khi đảo trật tự của hai chữ số đó sẽ thu được một số nguyên tố cùng nhau với số đã cho.
    • Tìm các số tự nhiên lẻ có ba chữ số. Ba chữ số này, theo trật tự từ trái qua phải tạo thành một cấp số cộng.
    • Tìm các số tự nhiên có ba chữ số. Ba chữ số này, theo trật tự từ trái qua phải tạo thành một cấp số nhân với công bội là một số tự nhiên khác 0.

    7. Biến toàn cục, biến cục bộ

    Trong Python không có sự phân biệt giữa tham số và tham số giá trị như trong ngôn ngữ khác, Pascal chẳng hạn, nên tất cả các giá trị được truyền vào một hàm chúng ta đều gọi là tham số của hàm. Ở đây, chúng ta chỉ cần phân biệt khái niệm biến toàn cục global và biến cục bộ (biến địa phương) local mà thôi.

    Một biến được định nghĩa bên trong một hàm chỉ có thể được sử dụng bên trong hàm đó và được gọi là biến cục bộ. Các tham số và biến cục bộ này chỉ được phép sử dụng bởi các lệnh nằm bên trong hàm. Khi hàm được thực thi thì biến sẽ tồn tại và sẽ bị hủy khi chúng ta thoát khỏi hàm.

    a = 1
    def bien_cuc_bo(a):
        a = 5
        print(a)
    
    bien_cuc_bo(a) # chương trình  trả về kết quả là 5
    print(a) #chương trình vẫn trả về kết quả là 1

    Nhưng nếu như biến mà có kiểu dữ liệu là list thì những thay đổi bên trong hàm sẽ được giữ lại.

    a = [0, 5, 10, 15]
    def bien_cuc_bo(a):
        a[1] = 100
        print(a)
    
    bien_cuc_bo(a) # chương trình  trả về kết quả là [0, 100, 10, 15]
    print(a) #chương trình vẫn trả về kết quả là [0, 100, 10, 15]

    Để ghi nhận lại những thay đổi giá trị của một biến do các câu lệnh bên trong hàm tạo nên, chúng ta có thể sử dụng từ khóaglobal (biến toàn cầu, biến toàn cục). Khi một biến được khai báo là global thì chúng ta có thể gọi và thay đổi giá trị của nó từ bất kỳ đâu trong chương trình, kể cả trong thân hàm. Lưu ý rằng biến toàn cục chỉ có thể khai báo bên trong hàm và nó không thể là tham số/đối số của hàm.

    Như ví dụ sau, biến a lúc đầu có giá trị là 1, và trong hàm a được khai báo global đồng thời nhận giá trị mới là 5 thì ra bên ngoài hàm, giá trị mới này vẫn được ghi lại chứ không như ví dụ trước.

    a = 1
    def bien_toan_cuc():
       global a
       a = 5
       print(a)
    
    bien_toan_cuc() # chương trình  trả về kết quả là 5
    print(a) #chương trình vẫn trả về kết quả là 5

    8. Hàm nặc danh

    Chúng ta sử dụng từ khoá lambda được dùng để tạo một hàm số nặc danh (một hàm số không có tên). Nó là một hàm số trên một dòng và không có câu lệnh return. Nó chỉ bao gồm một biểu thức mà kết quả của biểu thức này chính là giá trị trả về của hàm. Ví dụ:

    a = lambda x: x*2
    for i in range(1,6):
          print(a(i))

    Kết quả

    2
    4
    6
    8
    10

    Ở đây, chúng ta tạo ra một hàm số chỉ trong một dòng lệnh, nó được dùng để nhân đôi giá trị của đối số nhận vào, sử dụng câu lệnh lambda. Sau đó, chúng ta dùng hàm này để nhân đôi các giá trị của một danh sách các số nguyên từ 1 đến 5.

    Mời bạn xem chi tiết trong bài Hàm ẩn danh trong Python

    [1]Bạn chỉ có thể tái sử dụng bằng cách Copy – Paste mà thôi 🙂

    [2]Xem phần đệ quy hàm để rõ hơn.

    [3]Thực ra, thử tìm hiểu từ đệ quy thì thấy rất khó hiểu, ta cứ hiểu nôm na như là phép quy nạp trong Toán học.

    [4]Giai thừa của một số tự nhiên n, kí hiệu là n!, được tính bởi công thức