Tin tức và phân tích của tất cả các thiết bị di động

Làm cách nào để in tam giác Pascal bằng Python?

Hướng dẫn này sẽ hướng dẫn bạn cách in tam giác Pascal bằng Python cho một số hàng nhất định.

Bạn sẽ bắt đầu bằng cách học cách xây dựng tam giác Pascal. Sau đó, bạn sẽ chuyển sang viết một hàm Python và tìm hiểu cách tối ưu hóa nó hơn nữa.

▶️ Bắt đầu nào!

Tam giác Pascal là gì và làm thế nào để xây dựng nó?

Một câu hỏi phỏng vấn phổ biến là in tam giác Pascal cho một số hàng nhất định.

Trong tam giác Pascal n hàng, hàng thứ i có i phần tử.

Vì vậy, hàng đầu tiên có một phần tử và đó 1. Mỗi phần tử trong các hàng tiếp theo là tổng của hai số ngay phía trên nó.

Hình bên dưới giải thích cách dựng một tam giác Pascal có năm hàng.

Tam giác Pascal cho numRows = 5 (ảnh của tác giả)

Lưu ý cách bạn có thể điền số không khi bạn chỉ có một số ở trên một số nhất định.

📝 Để làm bài tập nhanh, hãy làm theo quy trình trên để dựng tam giác Pascal cho n = 6 trong = 7.

Sau đó, hãy chuyển sang viết mã. Bạn có thể chạy các đoạn mã trong newsblog.pl Python IDE trực tiếp từ trình duyệt của mình – trong khi bạn xem qua phần hướng dẫn.

Hàm Python in tam giác Pascal

Trong phần này, chúng ta sẽ viết một hàm Python hiển thị tam giác Pascal cho bất kỳ số hàng nào.

Có hai câu hỏi chính cần xem xét:

  • Làm thế nào để thể hiện các mục trong tam giác Pascal?
  • Làm cách nào để in tam giác Pascal với khoảng cách và định dạng phù hợp?

Hãy trả lời chúng ngay bây giờ.

#1. Biểu thức cho mỗi mục trong tam giác Pascal là gì?

Khi nó xảy ra, các mục trong tam giác Pascal có thể được lấy từ công thức cho nCr. Nếu bạn nhớ lại môn toán ở trường, nCr là số cách bạn có thể chọn r phần tử từ một tập hợp gồm n phần tử.

Công thức cho nCr được đưa ra dưới đây:

công thức nCr (ảnh tác giả)

Bây giờ chúng ta hãy biểu diễn các phần tử trong tam giác Pascal bằng công thức nCr.

Các mục tam giác của Pascal sử dụng nCr (ảnh của tác giả)

Bây giờ chúng ta đã tìm ra cách biểu diễn các mục trong một ma trận.

#2. Làm cách nào để điều chỉnh khoảng cách khi in mẫu?

Trong tam giác Pascal với hàng numRows #1 có một mục, dòng #2 có hai mục và như vậy. Để in mẫu dưới dạng hình tam giác, bạn cần numRows – và khoảng trắng trong hàng #i. Để làm điều này, bạn có thể sử dụng hàm phạm vi của python kết hợp với vòng lặp for.

Vì chức năng phạm vi không bao gồm điểm cuối theo mặc định, bạn cần thêm + 1để có được số lượng không gian hàng đầu cần thiết.

Bây giờ bạn đã học cách biểu diễn các mục nhập cũng như điều chỉnh khoảng cách khi in tam giác Pascal, hãy tiếp tục và xác định hàm pascal_tri.

Phân tích định nghĩa hàm

Vậy bạn muốn hàm pascal_tri để làm gì?

  • Hàm pascal_tri sẽ lấy một số hàng (numRows) làm đối số.
  • Nó sẽ in tam giác Pascal với numRows.

Để tính giai thừa, hãy sử dụng hàm giai thừa từ mô-đun toán học tích hợp sẵn của Python.

▶️ Chạy ô mã sau để nhập giai thừa và sử dụng nó trong mô-đun hiện tại.

from math import factorial

Đoạn mã sau chứa định nghĩa hàm.

def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    # loop to get leading spaces
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # loop to get elements of row i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # print each row in a new line
	  print("n")

Chức năng hoạt động như sau:

  • Hàm pascal_tri có một tham số numRows bắt buộc: số hàng.
  • Tổng cộng có numRows. Đối với mỗi hàng i, chúng tôi thêm numRows – và khoảng trắng ở đầu trước mục nhập đầu tiên trong hàng.
  • Sau đó, chúng tôi sử dụng công thức nCr để tính các mục nhập riêng lẻ. Trong hàng i, các mục là iCj trong đó j = {0,1,2,…,và}.
  • Lưu ý rằng chúng tôi sử dụng // thực hiện phép chia số nguyên vì chúng tôi muốn các mục nhập là số nguyên.
  • Sau khi tính toán tất cả các mục trong một hàng, hãy in hàng tiếp theo trên một dòng mới.

🔗 Vì chúng tôi đã thêm tài liệu nên bạn có thể sử dụng hàm trợ giúp tích hợp sẵn của Python hoặc thuộc tính __doc__ để truy cập chuỗi tài liệu của hàm. Đoạn mã dưới đây cho thấy cách thực hiện việc này.

help(pascal_tri)

# Output
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Print Pascal's triangle with numRows.

pascal_tri.__doc__

# Output
Print Pascal's triangle with numRows.

Bây giờ, hãy tiếp tục và gọi hàm với số lượng hàng làm đối số.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

Như mong đợi, họ in đầu tiên 3 các hàng của tam giác Pascal.

In tam giác Pascal bằng đệ quy

Trong phần trước, chúng ta đã xác định biểu thức toán học cho mỗi mục trong tam giác Pascal. Tuy nhiên, chúng tôi đã không sử dụng mối quan hệ giữa các mục trong hai hàng tiếp theo.

Chúng tôi thực sự đã sử dụng hàng trước đó để tính toán các mục trong hàng tiếp theo. Chúng ta không thể sử dụng điều đó và đưa ra cách triển khai đệ quy hàm pascal_tri sao?

Vâng chúng ta hãy làm điều đó!

Trong cách triển khai đệ quy, một hàm sẽ gọi chính nó lặp đi lặp lại cho đến khi trường hợp cơ sở được đáp ứng. Khi xây dựng tam giác Pascal, chúng ta bắt đầu từ hàng đầu tiên với một mục 1và sau đó xây dựng các hàng tiếp theo.

Vì vậy gọi pascal_tri(numRows) lần lượt gọi pascal_tri(numRows-1) và cứ tiếp tục như vậy cho đến trường hợp cơ sở pascal_tri(1).

Hãy xem xét một ví dụ mà bạn cần in trước 3 các hàng của tam giác Pascal. Hình ảnh bên dưới giải thích cách gọi đệ quy được đẩy lên ngăn xếp. Và cách gọi hàm đệ quy trả về các hàng tam giác của Pascal.

Ngăn xếp cuộc gọi trong các cuộc gọi đệ quy (ảnh của tác giả)

▶️ Chạy đoạn mã dưới đây để tạo đệ quy các hàng tam giác của Pascal.

def pascal_tri(numRows):
    '''Print Pascal's triangle with numRows.'''
    if numRows == 1:
        return [[1]] # base case is reached!
    else:
        res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri
        # use previous row to calculate current row 
        cur_row = [1] # every row starts with 1
        prev_row = res_arr[-1] 
        for i in range(len(prev_row)-1):
            # sum of 2 entries directly above
            cur_row.append(prev_row[i] + prev_row[i+1]) 
        cur_row += [1] # every row ends with 1
        res_arr.append(cur_row)
        return res_arr

Dưới đây là một số điểm cần chú ý:

  • Chúng tôi đã sử dụng một danh sách lồng nhau làm cấu trúc dữ liệu, trong đó mỗi hàng trong tam giác Pascal chính là một danh sách, như sau: [[row 1], [row 2]…,[row n]].
  • Gọi pascal_tri(numRows) kích hoạt một loạt các lệnh gọi đệ quy với các đối số numRows – 1numRows – 2 đến 1. Các cuộc gọi này được đặt trên ngăn xếp.
  • Khi numRows == 1chúng tôi đã đạt đến trường hợp cơ sở và hàm trả về [[1]].
  • Giờ đây, danh sách trả về được sử dụng bởi các hàm tiếp theo trên ngăn xếp cuộc gọi – để tính toán hàng tiếp theo.
  • Nếu cur_row là hàng hiện tại, cur_row[i] = trước_hàng[i] + trước_hàng[i+1]-Tổng 2 các mục ngay phía trên chỉ mục hiện tại.

Vì mảng trả về là một danh sách lồng nhau (danh sách các danh sách) nên chúng ta cần điều chỉnh khoảng cách và in các mục như trong ô mã bên dưới.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # leading spaces
  for j in row:
    print(j, end=" ") # print entries
  print("n")  # print new line

Kết quả là chính xác như bạn có thể thấy dưới đây!

# Output

       1

      1 1

     1 2 1

    1 3 3 1

   1 4 6 4 1

Hàm Python để in tam giác Pascal cho numRows ≤ 5

Cả hai phương pháp bạn đã học sẽ hoạt động để hiển thị tam giác Pascal cho bất kỳ số numRow nào.

Tuy nhiên, có những lúc bạn cần in tam giác Pascal cho ít hàng hơn. Và khi số hàng bạn cần in nhiều nhất 5 – bạn có thể sử dụng một kỹ thuật đơn giản.

Đi qua bản vẽ dưới đây. Và hãy quan sát xem lũy thừa của 11 giống như thế nào với các phần tử trong tam giác Pascal. Cũng lưu ý rằng điều này chỉ hoạt động đến lũy thừa thứ tư của 11. Tức là, 11 lũy thừa {0, 1, 2, 3, 4} cung cấp các mục trong các hàng từ 1 xuống 5 tam giác Pascal.

Hãy viết lại định nghĩa hàm như hình dưới đây:

def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # compute power of 11
    print(' '.join(str(11**i)))

Đây là cách hoạt động của hàm pascal_tri:

  • Như trong các ví dụ trước, chúng tôi điều chỉnh khoảng cách.
  • Sau đó, chúng tôi sử dụng toán tử lũy thừa của Python (**) để tính lũy thừa của 11.
  • Vì lũy thừa của 11 là số nguyên theo mặc định, hãy chuyển đổi chúng thành một chuỗi bằng str(). Bây giờ bạn có lũy thừa là 11 dưới dạng chuỗi.
  • Các chuỗi trong Python có thể lặp lại – vì vậy bạn có thể lặp qua chúng và truy cập từng ký tự một.
  • Sau đó, bạn có thể sử dụng phương thức join() với cú pháp: .join() để nối các phần tử bằng cách sử dụng làm dấu phân cách.
  • Ở đây bạn cần một khoảng trắng giữa các ký tự, vì vậy nó sẽ là ”, đó là một chuỗi: lũy thừa của 11.

Hãy kiểm tra xem chức năng có hoạt động như dự định không.

pascal_tri(5)

# Output
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Một ví dụ khác, gọi pascal_tri với 4 như một lý lẽ.

pascal_tri(4)

# Output
     1
    1 1
   1 2 1
  1 3 3 1

Tôi hy vọng bạn biết cách dễ dàng in tam giác Pascal cho numRows trong phạm vi 1 xuống 5.

Đăng kí

Đây là những gì chúng tôi đã học được:

  • Cách dựng tam giác Pascal với số hàng cho trước. Mỗi số trong mỗi hàng là tổng của hai số ngay phía trên nó.
  • Viết một hàm Python sử dụng công thức nCr = n!/(nr)!.r! để tính toán các mục của tam giác Pascal.
  • Sau đó, bạn đã học cách thực hiện hàm đệ quy.
  • Cuối cùng bạn đã học được phương pháp tối ưu nhất để dựng tam giác Pascal cho numRows 5 – sử dụng sức mạnh của 11.

Nếu bạn muốn nâng cao kỹ năng Python của mình, hãy học cách nhân ma trận, kiểm tra xem một số có phải là số nguyên tố hay không và giải các bài toán với phép toán chuỗi. Chúc mừng mã hóa!

Mục lục