Komposisi lemah, invarian loop dan pelacakan flowchart
Diperkenalkan| English | Makna |
|---|---|
| loop invariant/luːp ɪnˈveərɪənt/ | invarian perulangan |
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | komposisi lemah |
Keputusan sebelum jawaban
- Mengalokasikan token identik ke kotak bernama berbeda dengan memilih penerima berurutan untuk token yang berbeda. Perubahan kecil dalam model penghitungan dapat mengubah jawaban dengan faktor yang besar.
- Tujuan Anda: Hitung alokasi yang tak dapat dibedakan dengan batasan nonnegatif atau positif.
Bacalah hubungannya
- Jumlah solusi bilangan bulat nonnegatif dari x₁+⋯+x_k=n adalah C(n+k−1,k−1), untuk n≥0 dan k≥1. Representasikan n bintang identik yang dipisahkan ke dalam k kotak bernama dengan k−1 baris; baris berdampingan dan baris ujung memungkinkan entri nol. Kotak dapat dibedakan, objek tidak. Menghitung token yang berbeda sebaliknya akan menetapkan setiap token secara independen, memberikan k^n sebelum batasan lain. Tentukan model dari apa yang diwakili oleh objek dan penerima, bukan dari koefisien binomial yang terlihat familiar.
- Jejakkan diagram alur berdasarkan urutan pernyataan dengan perilaku reset yang benar.
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.
Gunakan aturan penentu
- Untuk alokasi positif x_i≥1, letakkan z_i=x_i−1; total sisa adalah n−k, memberikan C(n−1,k−1) ketika n≥k. Batas bawah lebih umum x_i≥a_i ditangani dengan mengurangi setiap a_i. Minimal satu nol adalah komplemen dari setiap entri positif: kurangi C(n−1,k−1) dari total nonnegatif. Kasus tumpang tindih seperti tepat dua kotak kosong memerlukan penghitungan berbeda; mengurangi setiap kasus kotak kosong secara independen menghitung ganda irisan mereka.
- Gunakan invarian loop dan ukuran kemajuan untuk membenarkan algoritma.
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.
Periksa syarat-syaratnya
- Jejakkan diagram alur satu pernyataan dieksekusi pada satu waktu, mencatat variabel dalam tabel. Bedakan penugasan dari tes kesamaan matematis; sisi kanan penugasan menggunakan nilai lama sebelum pengganti. Catat cabang mana yang akan dieksekusi selanjutnya dan variabel mana yang direset. Kandidat loop luar baru mungkin menjumlahkan ulang jumlah dalam tanpa mereset kandidat itu sendiri. Untuk proses yang menambahkan 1,3,5,… ke S dari nol, setelah m penambahan S=m² dan penambah berikutnya adalah 2m+1.
- Gunakan invarian loop dan ukuran kemajuan untuk membenarkan algoritma.
Bagikan 11 token identik di antara 4 kotak bernama. Alokasi nonnegatif berjumlah C(14,3)=364; alokasi semua-positif berjumlah C(10,3)=120. Oleh karena itu 244 alokasi memiliki setidaknya satu kotak kosong. Untuk uji jumlah ganjil dengan N=10, S berkembang 0,1,4,9,16; ia melewati dan menolak 10. Untuk N=9 ia keluar pada S=9 setelah tiga penambahan. Tambah berikutnya adalah 1,3,5,7,9; kolom jumlah dan tambah berikutnya tidak boleh tertukar.
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.
Terapkan format tugas
- Invarian perulangan adalah benar sebelum dan setelah setiap iterasi. Invarian jumlah kuadrat berlaku pada awal m=0 dan terpelihara karena m²+(2m+1)=(m+1)². Invarian saja tidak membuktikan terminasi. Untuk menguji apakah bilangan bulat N≥0 merupakan bilangan kuadrat dengan menambahkan bilangan ganjil hingga S≥N, S akan tumbuh tanpa batas; ekuivalennya, m meningkat dan harus mencapai batasan seperti N. Pada saat keluar, kesamaan berarti bilangan kuadrat dan overshoot berarti bukan bilangan kuadrat. Nilai yang dicetak harus dicapai melalui jalur eksekusi aktual; pola numerik yang masuk akal saja bukan merupakan jejak.
- Gunakan invarian loop dan ukuran kemajuan untuk membenarkan algoritma.
Objek identik dan objek berbeda menggunakan model yang berbeda. Setidaknya satu kotak kosong tidak sama dengan tepat satu. Dalam flowchart, pertahankan urutan pembaruan dan reset hanya variabel yang memang direset oleh jalur eksekusi.
Jawaban mana yang sesuai dengan kasus ini?
Menghitung alokasi yang tak terbedakan dengan batasan negatif atau positif
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.
Jaga pembedaan
- komposisi lemah — Alokasi terurut dari sebuah total ke dalam bagian-bagian bilangan bulat nonnegatif.
- invarian perulangan — Sifat yang terpelihara sebelum dan setelah setiap iterasi perulangan.
- Hitung alokasi tak terpilah dengan batasan nonnegatif atau positif.
- Jejakkan diagram alur berdasarkan urutan pernyataan dengan perilaku reset yang benar.
- Gunakan invarian loop dan ukuran kemajuan untuk membenarkan algoritma.
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.