Thành phần yếu, bất biến vòng lặp và truy vết lưu đồ
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| loop invariant/luːp ɪnˈveərɪənt/ | bất biến vòng lặp |
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | phân rã yếu |
Quyết định trước khi trả lời
- Phân bổ các token giống hệt nhau vào các hộp có tên khác với việc chọn người nhận có thứ tự cho các token khác nhau. Sự thay đổi nhỏ trong mô hình đếm có thể làm thay đổi đáp án theo một hệ số lớn.
- Mục tiêu của bạn: Đếm số cách phân phối không phân biệt được với ràng buộc phi âm hoặc dương.
Đọc mối quan hệ
- Số nghiệm nguyên phi âm của x₁+⋯+x_k=n là C(n+k−1,k−1), với n≥0 và k≥1. Biểu diễn n ngôi sao giống hệt nhau phân chia vào k hộp có tên bằng k−1 thanh ngăn; các thanh ngăn liền kề và thanh ở đầu cho phép giá trị bằng 0. Các hộp có thể phân biệt, các đối tượng thì không. Nếu đếm các token phân biệt, ta sẽ gán mỗi token độc lập, cho k^n trước các ràng buộc khác. Hãy quyết định mô hình dựa vào ý nghĩa của đối tượng và người nhận, chứ không dựa vào hệ thức nhị thức quen mắt.
- Theo dõi lưu đồ theo thứ tự câu lệnh với hành vi đặt lại đúng.
How many ways put 11 identical tokens into 4 named boxes, allowing empty boxes?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
There are 11 stars and 3 bars. Choose the 3 bar positions among 14 positions: C(14,3)=364.
Áp dụng quy tắc xác định
- Đối với các phân phối dương x_i ≥ 1, đặt z_i = x_i − 1; tổng còn lại là n−k, cho C(n−1, k−1) khi n≥k. Các giới hạn dưới tổng quát hơn x_i ≥ a_i được xử lý bằng cách trừ đi mỗi a_i. Ít nhất một số không là phần bù của mọi thành phần dương: trừ C(n−1, k−1) từ tổng phi âm. Các trường hợp giao nhau như đúng hai hộp trống cần đếm riêng; việc trừ từng trường hợp hộp trống độc lập sẽ làm trùng lặp phần giao.
- Sử dụng bất biến vòng lặp và đo lường tiến trình để chứng minh tính đúng đắn của thuật toán.
Starting from S=0, add successive odd numbers 1,3,5,… until S≥10. What is S at exit?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The successive sums are 1,4,9,16. The first sum at least 10 is 16, so the test overshoots rather than declaring 10 square.
Check the conditions
- Theo dõi lưu đồ từng câu lệnh thực thi một, ghi nhận các biến vào bảng. Phân biệt gán giá trị với phép kiểm tra bằng đẳng thức toán học; vế phải của câu lệnh gán sử dụng giá trị cũ trước khi thay thế. Ghi nhận nhánh nào sẽ thực thi tiếp theo và những biến nào được đặt lại. Một ứng viên vòng lặp ngoài mới có thể đặt lại tổng nội bộ mà không đặt lại chính ứng viên đó. Đối với quá trình cộng 1,3,5,… vào S từ 0, sau m lần cộng S = m² và số hạng tiếp theo là 2m+1.
- Sử dụng bất biến vòng lặp và đo lường tiến trình để chứng minh tính đúng đắn của thuật toán.
Phân phối 11 token giống nhau vào 4 hộp có tên. Số phân bổ phi âm là C(14,3)=364; số phân bổ hoàn toàn dương là C(10,3)=120. Do đó 244 phân bổ có ít nhất một hộp trống. Đối với bài kiểm tra tổng lẻ với N=10, S tiến triển 0,1,4,9,16; nó vượt quá và bác bỏ 10. Đối với N=9 nó thoát ra tại S=9 sau ba lần cộng. Các số hạng tiếp theo là 1,3,5,7,9; cột tổng và cột số hạng tiếp theo không được nhầm lẫn.
Of the 364 nonnegative allocations of 11 tokens to 4 boxes, 120 have every box positive. The count with at least one empty box is ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Subtract the all-positive complement once: 364−120=244.
Áp dụng định dạng nhiệm vụ
- Một bất biến vòng lặp đúng trước và sau mỗi lần lặp. Bất biến tổng bình phương ban đầu đúng tại m=0 và được bảo toàn vì m²+(2m+1)=(m+1)². Chỉ một bất biến không chứng minh được sự kết thúc. Để kiểm tra xem số nguyên N≥0 có phải là số chính phương hay không bằng cách cộng các số lẻ cho đến khi S≥N, S tăng không giới hạn; tương đương m tăng và phải đạt đến một cận như N. Tại thời điểm thoát, đẳng thức có nghĩa là số chính phương và vượt quá có nghĩa là không phải số chính phương. Một giá trị được in ra phải đạt được trên một đường thi hành thực tế; một quy tắc số học hợp lý đơn thuần không phải là một bản ghi.
- Sử dụng bất biến vòng lặp và đo lường tiến trình để chứng minh tính đúng đắn của thuật toán.
Các vật thể giống hệt nhau và các vật thể khác nhau sử dụng các mô hình khác nhau. Ít nhất một hộp trống không giống với đúng một hộp trống. Trong lưu đồ, giữ thứ tự cập nhật và chỉ đặt lại những biến mà đường thực thi đã chạy qua thực sự đặt lại.
Câu trả lời nào phù hợp với trường hợp này?
Đếm số cách phân phối không phân biệt được với ràng buộc phi âm hoặc dương
A preserved loop invariant alone proves that every execution of the loop terminates.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An infinite loop can preserve a property forever. Termination also needs a progress argument or decreasing well-founded measure.
Giữ nguyên sự phân biệt
- phân phối yếu — Một phân phối có thứ tự của tổng thành các phần tử số nguyên phi âm.
- bất biến vòng lặp — Một tính chất được bảo toàn trước và sau mỗi lần lặp của vòng lặp.
- Đếm các phân phối không phân biệt được với các ràng buộc phi âm hoặc dương.
- Theo dõi lưu đồ theo thứ tự câu lệnh với hành vi đặt lại đúng.
- Sử dụng bất biến vòng lặp và đo lường tiến trình để chứng minh tính đúng đắn của thuật toán.
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.