Apa yang akan menjelaskan observasi ini?
- Rutin pencarian yang bekerja sempurna pada daftar demonstrasi gagal seketika saat register kosong. Kesalahan bukan pada kode: kasus batas tidak pernah ada dalam kontrak.
Bangun modelnya
- Program mengimplementasikan prosedur terbatas untuk tugas yang dinyatakan: kontraknya menyatakan kondisi input dan output yang diharapkan.
- Rancang tes dari spesifikasi, bukan hanya jalur bahagia.
- Kasus batas: koleksi kosong (jika diperbolehkan), duplikat, dan nilai tidak valid.
- Diagnosis kegagalan dalam tiga kategori: algoritma yang salah, implementasi yang salah, atau persyaratan yang tidak lengkap.
- kasus batas: Input di tepi kondisi input yang dinyatakan.
*Kontrak program menghubungkan input yang dinyatakan, prosedur, dan output yang diharapkan untuk setiap kategori yang diuji
Pilih bukti yang dapat mengujinya
- Telusuri pencarian atas daftar terurut fiktif kecil; nyatakan konvensi indeksasi.
- Untuk pencarian biner, perbarui batas agar interval sisa mengecil setiap langkah.
- Tolak input yang tidak terurut kecuali pengurutan merupakan bagian dari tugas.
Di laboratorium: Tulis kontrak terlebih dahulu: kondisi input, output yang diharapkan, dan daftar batas; baru kemudian lakukan pelacakan atau penulisan kode.
Bekerja dari kuantitas yang diketahui
- Diketahui: daftar terurut [3, 9, 14, 20, 27], dicari nilai 20, dengan pengindeksan berbasis satu.
- Pencarian linear membandingkan 3, 9, 14, 20: empat perbandingan untuk menemukan kecocokan.
- Pencarian biner: interval 1-5, tengah 14 (rendah, karena 20 > 14); interval 4-5, tengah 20: ditemukan dalam dua perbandingan.
- Perilaku batas untuk rutinitas yang sama: daftar kosong mengembalikan hasil tidak ditemukan tanpa membaca elemen apa pun.
Giliran Anda: Lakukan pelacakan pencarian biner yang sama untuk nilai 3 dan hitung jumlah perbandingan.
Periksa kesimpulan dan batasannya
- Tes membuktikan perilaku pada input yang diuji; kategori yang tidak diuji tetap menjadi tanggung jawab kontrak.
- Duplikat memerlukan aturan yang dinyatakan (kecocokan pertama, kecocokan sembarang, semua kecocokan) sebelum pelacakan dapat dinilai.
Tidak benar: Lulus tes membuktikan program tersebut benar. Tes menunjukkan bahwa perilaku yang stated berlaku untuk input yang diuji; daftar batas, bukan keberuntungan, yang menentukan cakupan.
Kunci:
- Kontrak terlebih dahulu: kondisi input, output yang diharapkan, daftar batas.
- Nyatakan konvensi pengindeksan sebelum melakukan pelacakan apa pun.
- Waspadai: input tidak terurut pada pencarian biner.
Tulis dari daftar batas
- Kontrak fungsi menerima bilangan bulat dari 1 hingga 20 termasuk.
- Beri nama tes batas: 1 dan 20 (tepi), 0 dan 21 (sedikit di luar), serta satu nilai rentang tengah—tepi kontrak dan tetangganya.
Tulis dari pencarian biner dua-probe
- Cari nilai 12 dalam daftar 2, 5, 7, 9, 12, 15 dengan pengindeksan berbasis 1.
- Tengah dari 1..6 adalah posisi 3 (nilai 7) — lanjutkan ke kanan; tengah dari 4..6 adalah posisi 5 (nilai 12) — ditemukan dalam dua probe, konvensi stated terlebih dahulu.
Tulis berdasarkan jebakan input tidak terurut
- Algoritma yang sama berjalan pada 9, 2, 15, 5.
- Apa yang bisa salah? Logika nilai tengah mengasumsikan keterurutan — nilai yang ada dapat terlewat; kontrak harus MEMERLUKAN input terurut, atau jejaknya akan menyesatkan.
Tulis berdasarkan kontrak tertulis
- Tulis kontrak untuk fungsi yang mengembalikan nilai terkecil dari sebuah daftar: kondisi input (daftar angka non-kosong), output yang diharapkan (anggota dari daftar, lebih kecil atau sama dengan setiap anggota), kasus batas (daftar satu elemen mengembalikan elemen tersebut).
- Kontrak ditulis SEBELUM kode — kondisi input, hubungan output, batas-batas — sehingga setiap uji coba selanjutnya memiliki landasan yang jelas.