Trăn tam giác pascal

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

▶️ Started

lục mục

• Tam giác Pascal là gì và làm thế nào để xây dựng nó?
• Hàm Python trong tam giác Pascal
  • Phân vùng định nghĩa hàm
• Trong tam giác Pascal bằng đệ quy
• Hàm Python to in tam giác Pascal cho numRows ≤ 5
  • Đăng kí

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à trong 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ó phần tử

Vì vậy, hàng đầu tiên có một phần tử và đó là 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 xây dựng tam giác Pascal có hàng năm

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 để xây 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 trong 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 để có thể hiển thị các mục trong tam giác Pascal?
• Làm cách nào để nhập 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 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à một số cách bạn có thể chọn r phần tử từ một tập hợp bao gồm phần tử

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

công thức nCr [ảnh 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 màn hình lớn

#2. Làm cách nào để điều chỉnh khoảng cách khi ở 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. To in the form under shape tam giác, you need numRows – and white distance in rows #i. Để làm điều này, bạn có thể sử dụng phạm vi hàm của python kết hợp với vòng lặp cho

Vì phạm vi chức năng không bao gồm điểm cuối theo mặc định, bạn cần thêm + 1 để có 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 ở trong tam giác Pascal, hãy tiếp tục và xác định hàm pascal_tri

Phân vùng định nghĩa hàm

Vì 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ẽ trong 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 đoạn thừa và sử dụng nó trong mô-đun hiện tại

from math import factorial

Sau code code contains chức năng định nghĩa

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"]

Active function like after

• Hàm pascal_tri has a numRows tham số bắt buộc. số lượng hàng
• Total plus has numRows. Đối với mỗi hàng i, chúng tôi thêm numRows – và khoảng trống ở đầu 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 cho phép chia số nguyên vì chúng tôi muốn 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 vào hàng tiếp theo trên một dòng mới

🔗 Vì chúng tôi đã bổ sung 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. Dưới đây là đoạn mã để tìm cách thực hiện công 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, they in first 3 rows of tam giác Pascal

Trong 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 phát triển khai đệ quy hàm pascal_tri sao?

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

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

Vì vậy đã gọi pascal_tri[numRows] một lần như vậy gọi pascal_tri[numRows-1] và cứ tiếp tục như vậy cho đến trường hợp nhất pascal_tri[1]

Hãy xem xét một ví dụ mà bạn cần ở trước 3 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 đưa 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ừng 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. [[hàng 1], [hàng 2]…,[hàng n]]
• Call pascal_tri[numRows] kích hoạt một chuỗi 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 == 1 chúng tôi đã đạt được 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 cộng 2 mục ngay trên mục hiện tại

Vì khoả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à trong 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ể tìm thấy dưới đây

# Output

       1

      1 1

     1 2 1

    1 3 3 1

   1 4 6 4 1

Hàm Python to 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 trong tam giác Pascal để ít hàng hơn. Và khi số hàng bạn cần trong 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 phần 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 phần 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 đến 5 tam giác Pascal

Vui lòng 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 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ử tích lũy của Python [**] để tính toán tích lũy của 11
• Vì lũy thừa của 11 là nguyên số 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ó sẵn khoảng trống 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[] to connect các phần tử bằng cách sử dụng dấu phân cách
• Ở đây bạn cần khoảng trắng giữa các ký tự, vì vậy nó sẽ là ”, đó là một chuỗi. gạch thừa của 11

Vui lòng kiểm tra xem chức năng có hoạt động như dự kiến ​​không

________số 8

Một ví dụ khác, call pascal_tri with 4 as a reason

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 trong tam giác Pascal cho numRows trong phạm vi từ 1 đến 5

Đăng kí

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

• Cách xây 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. /[không]. 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 để xây 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 chuỗi phép toán. Chúc mừng mã hóa