T.11 · Weak compositions, loop invariants and flowchart tracing

Chuẩn bị GRE đại học. Mục tiêu cục bộ nằm trong phạm vi ETS đã xem xét; đây là giảng dạy nguyên bản, không phải bài thi chính thức hoặc dự đoán điểm số.

Kiến thức nền: Hệ số nhị thức, phần bù và theo dõi gán giá trị.

• Đếm số cách phân phối không phân biệt được với ràng buộc không â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à thước đo tiến độ để chứng minh thuật toán

phân rã yếu: Một cách phân phối có thứ tự của một tổng thành các phần là số nguyên không â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.

Số nghiệm nguyên không â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 vào k hộp có tên bằng k−1 thanh ngăn; các thanh ngăn liền kề và ở đầu cuối cho phép các ô trống bằng 0. Các hộp có thể phân biệt được, nhưng các vật thể thì không. Nếu đếm các token riêng biệt thay vào đó sẽ gán độc lập cho từng token, dẫn đến k^n trước khi áp dụng các ràng buộc khác. Hãy quyết định mô hình dựa vào ý nghĩa của các vật thể và người nhận, chứ không dựa vào hình thức quen thuộc của hệ số nhị thức.

Đối với các phân bổ 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 cậ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 giá trị bằng 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 chồng chéo như đúng hai hộp trống cần một phép đếm khác; trừ từng trường hợp hộp trống độc lập sẽ tính trùng giao của chúng.

Theo dõi lưu đồ từng câu lệnh một, ghi lại 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 toán học; vế phải của phép gán sử dụng giá trị cũ trước khi thay thế. Ghi lại nhánh nào sẽ thực thi tiếp theo và những biến nào bị đặt lại. Một ứng viên vòng lặp mới có thể đặt lại tổng bên trong 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 thì S=m² và số hạng tiếp theo là 2m+1.

Một bất biến vòng lặp là đú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ỉ có bất biến thì chưa đủ để chứng minh sự dừng. Để kiểm tra xem số nguyên N≥0 có phải là số chính phương bằng cách cộng các số lẻ cho đến khi S≥N, S sẽ tăng vô hạn; tương đương với m tăng và phải đạt đến một ngưỡng như N. Tại thời điểm thoát, bằng nhau 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ị in ra phải đạt được trên một đường thực thi cụ thể; chỉ có mẫu số học hợp lý thì chưa đủ để coi là một phép theo dõi.

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.

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.

Đếm các nghiệm không âm của $a+b+c=8$ với $a\ge2$. Có bao nhiêu nghiệm thỏa mãn $b,c\ge1$? Trong số các nghiệm đầu tiên, có bao nhiêu nghiệm có ít nhất một trong b hoặc c bằng 0?

Giải mẫu

Đặt $u=a-2$. Khi đó $u+b+c=6$ có $\binom82=28$ nghiệm không âm. Yêu cầu b, c là số dương và trừ đi 1 từ mỗi biến sẽ thu được tổng cộng bốn nghiệm trong ba biến không âm, được đếm bởi $\binom62=15$. Số lượng phần bù là $28-15=13$. Trực tiếp b=0 cho bảy nghiệm, c=0 cho bảy nghiệm, và trường hợp cả hai đều bằng 0 bị đếm hai lần, dẫn đến $7+7-1=13$.

Theo dõi thuật toán này với N=15 và N=16: khởi tạo S=0, k=1; trong khi S<N, thực thi S=S+k, sau đó k=k+2; báo cáo liệu S=N hay không. Phát biểu một bất biến, và chứng minh sự hội tụ đối với số nguyên $N\ge0$.

Kiểm tra sau khi đã làm

Sau m bước lặp, $S=m^2$ và $k=2m+1$. Các cặp (S,k) theo dõi là $(0,1),(1,3),(4,5),(9,7),(16,9)$. Do đó 15 bị loại bỏ do vượt quá và 16 được chấp nhận. Bất biến ban đầu đúng và được bảo toàn vì $m^2+(2m+1)=(m+1)^2$. Tổng tăng vô hạn, nên cuối cùng nó sẽ đạt hoặc vượt quá N; ví dụ, m=N đủ khi N là số dương. Đối với N=0, vòng lặp bị bỏ qua và điều kiện bằng nhau được thỏa mãn. Chỉ riêng một bất biến thì không đủ để khẳng định sự hội tụ.