Công cụ sau đây trực quan hóa những gì máy tính đang làm từng bước khi nó thực thi chương trình nói trên
Trình chỉnh sửa mã Python
Có một cách khác để giải quyết giải pháp này?
Trước. Viết chương trình Python để thực hiện làm phẳng sâu một danh sách.
Tiếp theo. Viết chương trình Python để kiểm tra xem hai danh sách đã cho có chứa các phần tử giống nhau không phân biệt thứ tự.
Mức độ khó của bài tập này là gì?
Dễ dàng trung bình khóKiểm tra kỹ năng Lập trình của bạn với bài kiểm tra của w3resource
con trăn. Lời khuyên trong ngày
Vòng lặp for và other
Đối với việc xây dựng khác đôi khi gây nhầm lẫn ngay cả những lập trình viên Python dày dặn nhất. Nhưng nó thực sự không phức tạp chút nào
Mệnh đề khác được thực thi sau khi vòng lặp for kết thúc. Có thể khó biết liệu vòng lặp có hoàn thành thành công hay không, đặc biệt nếu có câu lệnh ngắt trong vòng lặp. Tuyên bố khác ở đây đảm bảo với chúng tôi rằng vòng lặp đã chạy thành công trong suốt
for j in range[6]:
print[j]
else:
print["No"]
đầu ra
0 1 2 3 4 5 No
Vì vậy, nó có vẻ dư thừa do đó có sự nhầm lẫn nhưng hãy nhìn nhận nó theo cách này. Điều gì sẽ xảy ra nếu có một câu lệnh ngắt trong vòng lặp
Tập hợp lũy thừa của một tập hợp là tập hợp tất cả các tập hợp con có thể có của một tập hợp. tôi. e. đối với danh sách
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]0, bộ nguồn là
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]1. [wikipedia có thêm]
Trình tạo trong Python là một khái niệm mạnh mẽ và cho phép bạn có các danh sách mà bạn có thể tạo khi thực hiện. Vì vậy, bạn không cần tính toán tất cả các mục trong danh sách trước khi sử dụng chúng. Như bạn có thể thấy từ ví dụ trên, số phần tử trong tập quyền hạn của danh sách lớn hơn nhiều so với số phần tử trong danh sách ban đầu. Nếu có n mục trong danh sách ban đầu, thì có 2ⁿ mục trong bộ nguồn. Ví dụ: tập sức mạnh của danh sách 5 phần tử có 32 mục, tập quyền hạn của danh sách 10 phần tử có 1.024 mục, v.v. Vì các bộ quyền hạn rất lớn, nên các trình tạo rất hữu ích ở đây, vì bạn không phải tạo [và lưu trữ] danh sách 1.024 phần tử trước khi thực hiện phép tính của mình. Đây là một hàm tạo đơn giản trong python sẽ trả về [hoặc 'mang lại'] tất cả các danh sách trong bộ quyền hạn của danh sách
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]2
Ghi chú. mã ban đầu xuất hiện trên trang web cũ của tôi
Cho đến nay, chúng tôi đã sử dụng đệ quy một cách rút gọn. chúng tôi nhận một đầu vào và chắt lọc nó thành tổng, tích, số nguyên hoặc thậm chí là boolean. Chúng tôi đã đơn giản hóa một danh sách lồng nhau thành một danh sách phẳng và trong bài tập cuối cùng, đã rút ra một giá trị tối thiểu từ bất kỳ danh sách lồng nhau nào, bất kể độ sâu của việc lồng trong danh sách đó. Việc áp dụng đệ quy cho các loại bài toán này là hợp lý, vì bản thân phép đệ quy dựa trên việc rút gọn bài toán thành các bài toán con ngày càng nhỏ hơn cho đến khi chúng ta nhận được phát biểu đơn giản nhất có thể của bài toán. Có một sự hài hòa về nhận thức nhất định khi biết câu trả lời bạn cần nhận được từ thông tin đầu vào và phương pháp được sử dụng để thực hiện điều đó, hoạt động theo cùng một 'hướng'. Nhưng điều gì sẽ xảy ra nếu chúng ta muốn lấy một đầu vào và kiếm được nhiều hơn từ nó?
Ví dụ của chúng tôi ở đây là tập lũy thừa hoặc tập hợp tất cả các tập hợp con của một tập hợp nhất định. Bộ sức mạnh là một cửa ngõ thiết yếu để hiểu được một nhóm lớn các vấn đề xoay quanh tối ưu hóa tổ hợp. Để làm rõ, trong Python, một
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code9 là một tập hợp các phần tử duy nhất, trong khi một
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]0 có thể chứa các phần tử trùng lặp. Chúng ta sẽ sử dụng các danh sách để thảo luận về bộ sức mạnh của mình, vì một bộ tạo ra bộ sức mạnh không nhất thiết phải bao gồm các phần tử duy nhất [ví dụ: 'táo, chuối, chuối, xoài' chỉ có nghĩa là bạn đang làm việc với hai quả chuối . Ngoài ra, chúng ta có thể tận dụng một số kinh nghiệm trước đây của mình với các danh sách để tiếp cận vấn đề tốt hơn
Một điều chúng ta có thể thiết lập ngay lập tức là trường hợp cơ bản. Theo định nghĩa, bất kỳ tập hợp
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1 nào cũng là một thành viên của tập hợp sức mạnh. Tập hợp rỗng cũng luôn là thành viên của tập hợp lũy thừa. Do đó, chúng tôi biết rằng tập sức mạnh của tập hợp trống chứa tập hợp trống là thành viên duy nhất của nó
powerSet[[]] == [[]]
Sử dụng mẫu cơ bản của chúng tôi, điều này cung cấp cho chúng tôi những phác thảo đầu tiên về mã của chúng tôi
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code
Thật tốt khi thấy một vấn đề hoạt động như thế nào, độc lập với cách chúng ta có thể cố gắng giải quyết nó. Nếu bạn dành thời gian để giải quyết một vài lần lặp lại hoặc các trường hợp của một vấn đề, bạn có thể thực hiện các quan sát hoặc xác định các mẫu sẽ giúp ích rất nhiều cho việc thiết kế thuật toán. Nếu bạn có thể viết nhanh một đoạn mã, thật tuyệt - nhưng đôi khi lấy bút chì và giấy còn tốt hơn. Có thể lập luận theo cách của bạn để tìm ra giải pháp từ các nguyên tắc đầu tiên là một trong những cách tốt nhất để học tư duy thuật toán. Vì vậy, trước khi chúng ta xem phần còn lại của mã, hãy xem chúng ta có thể học được gì bằng cách phát triển bộ sức mạnh 'trong cuộc sống thực'
Chúng ta đã biết rằng một tập hợp rỗng [hoặc danh sách - tôi sẽ sử dụng các thuật ngữ thay thế cho nhau ở đây] sẽ luôn trả về một phần tử - chính nó - là tập sức mạnh của nó. Sau đó, chúng tôi nhận được một số mở rộng khá nghiêm trọng
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]
Đếm các thành viên [danh sách con] của mỗi nhóm, chúng tôi thấy rằng tập hợp sức mạnh cho thấy sự tăng trưởng theo cấp số nhân, hoặc
________số 8
Một kết luận thú vị khác mà chúng ta có thể rút ra từ một số trường hợp trên là tập hợp năng lượng có tính cộng. Nếu
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]2, thì tập hợp sức mạnh của nó sẽ chứa tập hợp sức mạnh của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]3. Nói cách khác, chúng ta không biết tập hợp sức mạnh của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]2 là gì cho đến khi chúng ta biết tập hợp sức mạnh của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]3. Nếu chúng tôi yêu cầu
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]6 tính toán
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]2, chúng tôi có thể nhận được phản hồi sau
- Tôi không thể tính tập lũy thừa của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]
2 vì trước tiên tôi cần tính tập lũy thừa của[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]
3 - Tôi không thể tính tập lũy thừa của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]
3 vì trước tiên tôi cần tính tập lũy thừa củalen[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]
1 - Tôi không thể tính tập lũy thừa của
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]
1 vì trước tiên tôi cần tính tập lũy thừa củalen[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]
3
Nói cách khác, “Tôi không thể làm 'x' cho đến khi tôi hoàn thành 'y' và tôi không thể làm 'y' cho đến khi tôi hoàn thành 'z'. ” Bất cứ khi nào bạn thấy mình trong một tình huống như thế này, cơ hội cho một giải pháp đệ quy là khá tốt
Theo tinh thần đó, chúng tôi muốn giảm
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1 cho đến khi chúng tôi đưa nó xuống tập hợp trống. Như chúng ta đã làm với thuật toán palindrome của mình, chúng ta có thể sử dụng các lát cắt để gửi một danh sách ngày càng nhỏ hơn làm đối số cho mỗi lệnh gọi đệ quy. Lần này, chúng tôi áp dụng các lát cắt không phải cho chuỗi mà cho danh sách. Đối với mục đích của chúng tôi, kết quả là như nhau
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code2
Một lần tại
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]5, chúng ta sẽ có trong tay tuyên bố nhỏ nhất về vấn đề.
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6. Trên đường đi, chúng tôi cũng sẽ tạo từng khung hình với các phiên bản giảm dần của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1. Có vẻ như chúng ta đã xử lý được ít nhất phần đệ quy trước của thuật toán
Câu hỏi. Xem kỹ những gì được trả lại từ trường hợp cơ sở.
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6 có giống với
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]9 tại
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]5 không?
Hãy thêm theo dõi bản in thông thường của chúng tôi để chúng tôi có thể bắt đầu theo dõi các khung. Ngoài ra, sẽ rất tốt nếu thấy không gian tên cho
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1 trong mỗi khung
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]0
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1
Giá trị duy nhất được trả về trong suốt tầng hậu đệ quy tại thời điểm này là
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6, vì vậy bây giờ chúng tôi sẽ bỏ qua việc in các giá trị trả về đó. Tuy nhiên, mã này phải đủ để giúp chúng tôi tiếp tục. Bây giờ chúng ta có một cấu trúc nhận ra bản chất cộng của tập hợp sức mạnh, nhưng được đặt trong các thuật ngữ đệ quy
Đúng hạt giống trong khung bên phải¶
Bây giờ chúng ta hãy nghĩ về những gì chúng ta mong đợi sẽ xảy ra trong mỗi khung và giao tiếp giá trị sau đệ quy giữa các khung có thể trông như thế nào
Bắt đầu từ trường hợp cơ sở, chúng tôi trả về
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6. Trong ví dụ của chúng tôi, chúng tôi biết rằng trong khung 4, không gian tên của
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1 là
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code25. Hậu đệ quy, chúng ta có thể thử tạo tập lũy thừa cho tập hợp gồm hai phần tử,
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6 và
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code25. Nếu chúng ta có thể lấy kết quả đó và đưa nó trở lại khung 3, chúng ta có thể làm tương tự cho khung đó và lặp lại cho đến khi chúng ta có bộ hoàn chỉnh
Nói cách khác, mỗi khung có một phần tử duy nhất hoạt động trên nhiều phần tử hiện có để tạo ra các hoán vị cần thiết cho khung đó. Hãy gọi những gì đến từ khung được gọi là
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 và những gì đang chờ đợi nó là
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]0
Rõ ràng là kết quả của mỗi khung hình trở thành
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 của khung hình đã gọi nó [hãy nhớ rằng chúng ta đang rời khỏi trường hợp cơ sở hiện tại]. Vì vậy, chúng tôi biết rằng
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 sẽ lưu trữ kết quả của cuộc gọi đệ quy
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]02. Bây giờ chúng ta phải tính toán sự tương tác của
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 và
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29, thêm các kết quả đó vào
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 và trả lại toàn bộ nội dung cho khung tiếp theo
Trước tiên, chúng tôi sẽ giải quyết sự tương tác giữa
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code28 và
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29, mô phỏng trạng thái được tìm thấy trong khung 4
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]9
powerSet[[]] == [[]]0
Cắm cái này vào bản nháp hiện có của chúng tôi về
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]6
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code0
Nếu bạn chạy mã này cho
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]09, bạn sẽ nhận được câu trả lời đúng, nhưng đối với bất kỳ
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]1 nào khác thì nó không hoàn toàn hoạt động. Chúng tôi vẫn còn thiếu một mảnh cuối cùng. Nhớ lại những gì chúng ta để lại trong mỗi khung hình trên đường đến trường hợp cơ sở
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code1
Bạn có thể thấy mục cuối cùng trong danh sách là
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29 của chúng tôi. Và thật dễ dàng để chỉ định mục cuối cùng trong bất kỳ danh sách nào với
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]12. Vì vậy, tất cả những gì chúng ta phải làm là thay thế
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]13 bằng
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]14 để tạo trường hợp tổng quát
Một điều thú vị ở đây là làm thế nào chúng ta có được
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29. Giảm danh sách ban đầu theo lát có hai mục đích. đi đến trường hợp cơ sở và thiết lập một tình huống trong đó
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]12 sẽ cung cấp cho chúng tôi giá trị chính xác cho
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code29 cho mọi khung hình. Trên thực tế, sẽ rất khó để tách rời hai
Điều này thực sự hiệu quả, nhưng lưu ý rằng chúng ta cũng có thể viết lại vòng lặp
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]18 dưới dạng hiểu danh sách ngắn gọn hơn nhiều và chèn trực tiếp vào câu lệnh return. Khi bạn biết mã hoạt động như thế nào, nó sẽ dễ đọc hơn nhiều
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code2
Câu hỏi. Tại sao chúng tôi viết
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]12?
Câu hỏi. Chúng ta có thể đặt
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]01 trước cuộc gọi đệ quy không?
Và đây là phiên bản có dấu vết in hoàn chỉnh
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code3
Như với hầu hết các thuật toán, có nhiều cách để tạo ra tập hợp sức mạnh. Tôi đã chọn cái này vì tôi nghĩ nó là một ví dụ tốt về cách chúng ta có thể suy nghĩ đệ quy thông qua vấn đề, từng bước một. Nhưng nó luôn mang tính hướng dẫn để xem xét các giải pháp khác
Từ Wikipedia
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code4
Câu hỏi. Điều này khác nhau như thế nào về thứ tự mà bộ nguồn được xây dựng?
Ngoài ra còn có một số giải pháp lặp đi lặp lại. Bạn có thể thất vọng khi nhận ra rằng chúng khá giống với đệ quy. Một điều mà giải pháp lặp gợi ý là
len[powerSet[[]]] == 1 len[powerSet[['a']]] == 2 len[powerSet[['a', 'b']]] == 4 len[powerSet[['a', 'b', 'c']]] == 8 len[powerSet[['a', 'b', 'c', 'd']]] == 16 len[powerSet[L]] == 2**len[L]6 là một loại MacGuffin toán học, một cái cớ để tiến hành quy trình đệ quy, nhưng cuối cùng nó thực sự chẳng là gì cả. Bạn sẽ không sai
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code5
def powerSet[L]: if len[L] == 0: return [[]] else: # a bunch of code6
Câu hỏi. Sự khác biệt giữa việc sử dụng các phương pháp danh sách
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]03 và
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]04 là gì?
Heuristics và Bài tập¶
♦ Đệ quy không cần phải rút gọn;
♦ Trước khi nghĩ về một vấn đề theo thuật ngữ đệ quy, có thể hữu ích nếu mô phỏng đầu vào và đầu ra mong muốn bằng cách tạo các 'mô-đun' nhỏ sẽ tạo ra kết quả mong muốn, sau đó sử dụng mô-đun đó để chỉ định câu lệnh trả về và tính toán bên trong mỗi khung. Nếu bạn chỉ làm việc từ trường hợp cơ bản, các bước tiếp theo có thể không rõ ràng
♦ Việc gieo khung trước đệ quy có nhiều chức năng hơn là chỉ đơn giản là giảm xuống cơ sở;
Tập thể dục. Viết một hàm đệ quy
[] == [[]] ['a'] == [[], ['a']] ['a', 'b'] == [[], ['a'], ['b'], ['a', 'b']] ['a', 'b', 'c'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']] ['a', 'b', 'c', 'd'] == [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']]09, đưa ra một danh sách các phần tử duy nhất, trả về một danh sách bổ sung các biểu diễn nhị phân của mỗi tập hợp con của danh sách đó. Ví dụ: nếu danh sách đầu vào là