>> JASON Hirschhorn: Selamat Datang untuk minggu ketiga, semua orang.
Kami memiliki sibuk tapi menarik Bagian depan kami.
Jadi pertama, karena kami telah membuat beberapa Headway dengan kursus tapi kami masih
telah banyak belajar tersisa untuk dilakukan, aku akan menunjukkan kalian beberapa sumber daya
yang harus membuktikan menjadi sangat membantu karena Anda tidak hanya mendekati Anda
masalah set, tetapi juga mencerna semua bahan kami memberikan kalian di
kuliah dan celana pendek dan bagian.
>> Kemudian kita akan menghabiskan 20 pertama sampai 25 menit bagian akan lebih dari
GDB, yang mungkin atau mungkin tidak memiliki digunakan pada saat ini, tetapi merupakan
sangat membantu alat yang akan membantu Anda debug program Anda.
Banyak dari Anda mungkin telah menggunakan printf dalam tengah program anda untuk mencari
apa variabel setara.
GDB bahkan lebih baik daripada printf dan tidak mengacaukan kode Anda karena Anda
menjalankannya pada file eksekusi.
Jadi kita akan pergi selama 10 paling membantu perintah yang Anda butuhkan untuk GDB, dan kami
akan pergi latihan bersama sehingga dalam masalah menetapkan tiga dan seterusnya, Anda
dapat menggunakan GDB untuk membantu debug program Anda.
Dan akhirnya, kita akan membahas beberapa pemilahan dan pencarian algoritma
Anda lihat di kuliah, dan kami akan benar-benar kode, bukan hanya
pseudocode, tetapi kode pencarian biner, bubble sort, dan selection sort.
>> Jadi pertama, saya ingin pergi atas sumber daya.
Ini adalah daftar yang luas, dan itu font yang lebih kecil karena saya punya banyak untuk
muat di sini.
Tapi ini tidak hanya akan membantu Anda, lagi, dengan set masalah dan
mencerna informasi yang Anda pelajari, tapi pasti, datang waktu kuis, ini akan
akan sangat membantu.
Jadi pertama, kuliah catatan.
Jika Anda pergi ke cs50.net/lectures dan gulir ke minggu dan hari tertentu,
Anda akan melihat bahwa ada catatan untuk setiap kuliah, yang tidak hanya
transkrip, tetapi versi diedit dari apa yang dicakup dalam perkuliahan dengan kode
potongan dan tidbits bermanfaat lainnya.
Saya sangat merekomendasikan pergi atas mereka.
Dan kemudian juga, ada kode sumber tersedia dari setiap kuliah.
Dan lagi, slide ini juga akan tersedia online di cs50.net/sections
malam ini.
>> Jadi kedua adalah celana pendek setiap minggu yang topik penutup, biasanya 5 sampai 15
menit panjangnya.
Dan orang-orang diharapkan akan memberi Anda primer besar pada topik yang berbeda.
Ketiga -
dan ini adalah merek baru ini tahun - adalah study.cs50.net.
Jika Anda belum check it out, saya sangat menyarankan Anda melakukannya.
Anda bisa memilih topik.
Kami memiliki puluhan topik di sana.
Jadi misalnya, Anda memilih Fungsi.
Ini memberi Anda beberapa slide dan catatan pada fungsi.
Mereka sebenarnya slide yang TF dianjurkan untuk menggunakan selama kami
presentasi dalam bagian.
Ada juga tips dan trik untuk menangani dengan fungsi, dan ada
latihan soal yang membantu Anda bekerja dengan fungsi.
Kami juga memberikan link ke pendek pada fungsi dan waktu yang berfungsi
telah datang dalam kuliah.
Jadi study.cs50.net, merek baru ini tahun, sumber daya yang fantastis.
>> Selanjutnya, saya memiliki seorang pria, yang merupakan manual perintah yang dapat dijalankan di
baris perintah.
Jadi jika Anda memiliki pertanyaan tentang perintah, misalnya, rand, yang kita
ditemui pekan lalu selama bagian dan Anda memiliki kemungkinan ditemui dalam
masalah Anda mengatur kapan akan melalui menghasilkan kode, tetapi jika Anda mengetik man
rand, Anda akan mendapatkan halaman yang memberitahu Anda semua tentang rand.
Ini memberi Anda apa yang diperlukan, yang parameter yang diperlukan, serta pengembalian
jenis dan deskripsi singkat fungsi itu.
>> Jadi memeriksa rand.
Hal ini dapat menjadi sedikit bertele-tele dan membingungkan, jadi kadang-kadang saya menemukan bahwa
Googling hanya apa yang saya ingin tahu adalah cara terbaik untuk menemukan jawabannya.
Jadi berlatih dengan Google.
Dapatkan baik di Google.
Ini akan menjadi teman terbaik Anda.
>> Serta Google, jika Anda tidak dapat menemukannya di Google, cs50.net/discuss, itu
forum diskusi.
Kemungkinannya adalah jika Anda memiliki pertanyaan, satu Anda 700 + rekan-rekan juga bahwa
pertanyaan dan mungkin bertanya sudah di bahas
forum dan memilikinya menjawab.
Jadi jika Anda memiliki pertanyaan umum atau Anda memiliki pertanyaan yang menurut Anda
mungkin orang lain mungkin telah mengalami, memeriksa cs50.net/discuss.
>> Akhirnya, dua terakhir, jika Anda ingin berbicara dengan manusia, kantor nyata
jam Senin sampai Jumat.
Ada juga jam kantor online bagi mahasiswa ekstensi.
Dan terakhir tetapi tentu tidak sedikit, saya, tanda seru.
Anda semua memiliki informasi kontak saya.
Jika Anda butuh sesuatu, tolong jangan ragu untuk menghubungi saya.
Selalu merasa bebas untuk melakukannya.
Sangat sedikit dari Anda telah menambahkan saya di Gchat, sehingga telah mengecewakan,
tapi mudah-mudahan itu akan berubah antara ini dan bagian berikutnya.
Setiap pertanyaan sejauh pada sumber daya?
Besar.
>> Akhirnya, steker lain untuk umpan balik, sayat.me/cs50.
Anda dapat memberikan umpan balik anonim tentang bagaimana saya lakukan.
Itu benar-benar membantu pekan lalu.
Aku punya beberapa komentar dari kalian tepat setelah bagian, ditambah dari
siswa lain yang menyaksikannya selama seminggu, dan itu
sangat membantu.
Saya akan mencoba dan membatasi penggunaan saya kata "manis," tapi aku akan menunjukkan saya
semangat dan kegairahan dengan cara lain.
Tapi ada tambahan lainnya masukan substantif,
baik plus dan delta.
Jadi tolong, saya memberikan kalian umpan balik pada set masalah Anda.
Jangan ragu untuk memberikan umpan balik pada pengajaran saya.
Aku di sini untuk kalian.
>> Besar.
Itu semua yang saya miliki untuk bagian pertama.
Ada yang punya pertanyaan sejauh ini?
Dan aku punya catatan untuk pusat kontrol.
Mahasiswa ekstensi telah mengirim pesan saya mengatakan mereka tidak mendapatkan audio,
tapi itu keluar dari kekuasaan saya untuk memperbaikinya.
Jadi mudah-mudahan, yang mendapat diselesaikan segera.
Jika Anda sedang menonton online, hi, tetapi Anda tidak bisa mendengar saya.
>> Jadi pertama, kita akan untuk pergi melalui GDB.
GDB, seperti yang saya diisyaratkan sebelumnya, adalah alat debugging
jauh lebih baik daripada printf.
Jadi untuk memulai dengan GDB, kalian, jika Anda ingin membuka alat Anda
dan mengambil file yang saya diemail ke Anda sebelumnya - file ini juga akan
tersedia secara online dalam sedikit -
dan menjalankan GDB. / nama file.
Pertama, tentu saja, Anda harus melakukan compile mengajukan karena GDB hanya bekerja pada
file yang dapat dieksekusi.
>> Tetapi jika Anda pernah ingin memulai GDB, hal pertama yang Anda lakukan,
Anda menjalankan GDB. / Caesar.
Jadi itulah nama program kami akan pergi dengan itu sekarang.
Jadi aku akan menulis membuat Caesar, yang akan memberikan saya sebuah file eksekusi
di sini disorot dalam warna hijau.
Dan kemudian aku akan menjalankan GDB. / Cesar.
>> Dan di sana Anda pergi.
Anda lihat kita memiliki beberapa teks mengatakan tentang versi GDB, memberi saya
beberapa informasi garansi, dan kemudian kita memiliki prompt PDB, yang terlihat semacam
seperti command prompt baris kami, tetapi Anda melihat itu terbuka
paren, GDB, paren dekat.
Sebelum kita melanjutkan dan debug file ini yang saya kirimkan untuk Anda semua, mari kita lihat
beberapa perintah yang berguna sehingga kita memiliki arti dari apa yang kita akan menutupi.
>> Perintah-perintah ini tercantum di sini di urutan di mana saya biasanya menggunakannya.
Jadi saya memulai program saya dengan menjalankan GBD / nama program.,
dalam hal ini, Caesar.
Dan kemudian hal pertama yang saya lakukan 99,9% waktu adalah jenis istirahat berarti.
Yang menetapkan titik istirahat di utama.
Pada dasarnya, apa yang Anda lakukan di sana adalah program ini akan berhenti di
utama sehingga Anda dapat mulai memeriksanya baris demi baris, bukan berjalan semua
jalan melalui.
Anda dapat mematahkan di berbagai titik dalam kode Anda, tetapi utama umumnya merupakan
Tempat yang baik untuk memulai.
>> Perintah berikutnya saya jalankan adalah lari.
Yang dimulai program berjalan, dan jika Anda perlu memasukkan baris perintah
argumen, Anda menjalankannya perintah itu.
Jalankan dengan argumen.
Jadi karena kita akan lebih versi C, yang merupakan program yang kalian
menulis untuk pset dua -
yang satu ini, tentu saja, memiliki beberapa bug di dalamnya yang mudah-mudahan kita akan menemukan -
kita akan menjalankan run dengan beberapa perintah argumen baris karena Caesar,
seperti yang kalian tahu per masalah mengatur spec, mengambil beberapa
argumen baris perintah.
>> Pasangan berikutnya perintah, berikutnya satu sebenarnya disebut berikutnya.
Yang mengambil baris demi baris Anda melalui program Anda.
Jadi memukul n kemudian Masukkan membawa Anda ke baris berikutnya, melaksanakan
baris sebelumnya.
Langkah tidak hanya membawa Anda ke baris berikutnya, tetapi
membawa Anda di dalam fungsi.
Jadi jika Anda telah menulis sebuah fungsi dalam kode Anda atau jika Anda ingin menjelajahi
untuk i, misalnya, Anda dapat menekan s, dan daripada pergi ke baris berikutnya
file yang Anda akan melalui hak sekarang, Anda benar-benar akan masuk ke
fungsi ini dan melihat kodenya.
>> Daftar menunjukkan, dalam sangat user friendly Format, 10 atau lebih baris sekitar
Anda saat ini dalam kode Anda sehingga Anda benar-benar dapat melihat file
daripada harus menukar kembali dan balik antara pandangan yang berbeda.
Cetak seperti printf, seperti namanya.
Itu menunjukkan apa variabel sama.
>> Info penduduk setempat benar-benar membantu.
Ini adalah versi khusus cetak.
Info penduduk setempat menunjukkan Anda semua lokal variabel, mencetak mereka semua keluar untuk Anda
yang tersedia saat ini.
Jadi saya biasanya, daripada harus mencetak empat variabel yang aku
ingin tahu tentang jika saya di untuk loop, untuk Misalnya, saya hanya menulis informasi penduduk setempat,
dan itu akan menunjukkan apa yang kontra i saya sama, serta array yang saya
bekerja pada equals.
>> Akhirnya, lanjutkan.
Mengetik istirahat berhenti Anda pada titik istirahat.
Anda dapat berjalan melalui baris demi Sejalan dengan berikutnya dan langkah.
Lanjutkan berjalan program untuk Anda berikutnya istirahat titik atau sampai selesai jika
tidak ada lagi break point.
Nonaktifkan menghilangkan break point jika Anda memutuskan istirahat di utama adalah
tidak pantas, Anda ingin mengaturnya di tempat lain.
Dan akhirnya q, berhenti, keluar dari GDB.
>> Jadi program ini,. / Caesar, kita akan untuk melihat melalui sekarang dan kami
akan menggunakan GDB untuk menemukan bug dalam program ini.
Aku berlari program ini sebelumnya dengan Periksa 50, dan aku punya satu cemberut.
Segala sesuatu itu ada, itu dikompilasi, itu melewati banyak tes, tetapi untuk
beberapa alasan, itu tidak lulus kelima tes, mengubah BARFOO, semua topi, ke
E-D-U-I-R-R, semua topi, menggunakan tiga sebagai kunci.
Aku cukup dekat.
Aku turun oleh satu huruf.
Jadi ada beberapa kesalahan kecil di sini.
Saya telah melihat melalui kode saya.
Aku tidak bisa mengetahuinya.
Mudah-mudahan, kalian bisa membantu saya mencari tahu apa bug ini.
>> Jadi itulah kesalahan kita mencari.
Mari kita pindah ke GDB.
Sekali lagi, saya sudah menjalankan GDB. / Caesar, jadi sekarang kita berada di GDB.
Dan apa yang pertama hal yang harus saya lakukan?
Aku baru saja masuk GDB.
Seseorang memberi saya baik perintah untuk masuk.
>> MAHASISWA: Break utama.
>> JASON Hirschhorn: Break utama.
Fantastic.
Mari kita ketik yang masuk
Kalian dapat menonton di sini atau mengikuti bersama pada komputer Anda.
Istirahat utama, dan Anda akan melihat break point yang ditetapkan sebesar -
itu memberi saya beberapa alamat memori yang aneh, dan juga memberi saya nomor baris.
Jika saya melihat kembali file ini, Saya akan menyadari utama yang
terjadi pada baris 21.
Apa yang harus saya jalankan selanjutnya?
Apakah program saya berjalan?
Tidak.
Jadi apa yang harus saya jalankan selanjutnya?
>> MAHASISWA: Jalankan.
>> JASON Hirschhorn: Jalankan.
Haruskah saya hanya menjalankan run, atau harus Saya menambahkan beberapa hal lain dalam?
>> MAHASISWA: Jalankan dengan argumen.
>> JASON Hirschhorn: Jalankan dengan argumen perintah.
Dan karena aku debugging sangat spesifik kasus, saya harus memasukkan bahwa
argumen baris perintah.
Jadi saya akan melakukan menjalankan tiga, yang, sekali lagi, output saya dapatkan dari Periksa 50.
Memulai program.
Kami pergi melalui beberapa baris.
Sekarang Anda akan melihat bahwa kita berada di jalur 21.
Bagaimana saya tahu bahwa kami berada di jalur 21?
Karena jika Anda melihat ke kiri jendela terminal saya, ada
ia mengatakan line 21.
Dan itu memberi saya, sebenarnya, kode yang di line 21.
Jadi aku salah bicara sebelumnya.
Main sebenarnya bukan pada baris 21.
Main adalah beberapa baris di atas 21.
Tetapi pada line 21, itu di mana kita melanggar.
Ini baris kode memiliki belum dieksekusi.
Itu penting.
Garis yang Anda lihat belum telah dieksekusi belum.
Itulah baris berikutnya kode Anda akan mengeksekusi.
>> Jadi baris berikutnya, seperti yang kalian mungkin akrab dengan, apakah ini
Kondisi memeriksa untuk melihat apakah saya memiliki memasuki argumen baris perintah.
Dan untuk saya, apa yang kedua bagian dari itu lakukan?
Apa itu untuk i?
>> MAHASISWA: Mengubah ke integer.
>> JASON Hirschhorn: Maaf?
>> SISWA: Ini mengubah Argumen ke integer.
>> JASON Hirschhorn: Jadi untuk i perubahan arg v1 dari string ke integer.
Lalu apa itu memeriksa?
>> MAHASISWA: Jika ada kedua argumen baris perintah, selain
dari menjalankan program.
>> JASON Hirschhorn: Dan apa paruh kedua ini
Ekspresi Boolean memeriksa?
Bagian ini di sini, untuk i?
>> MAHASISWA: Jika hasilnya negatif.
>> JASON Hirschhorn: Memastikan apa?
>> MAHASISWA: Membuat yakin itu adalah, pada kenyataannya, positif.
>> JASON Hirschhorn: Tepat.
Hal ini memeriksa untuk melihat apakah itu negatif, dan jika negatif, saya
punya perasaan kekuatan baris berikutnya akan saya berteriak pada pengguna.
Jadi mari kita memukul end untuk mengeksekusi baris ini.
Kami tidak melihat garis bahwa kalian mungkin diharapkan untuk melihat berteriak di
pengguna dan kemudian kembali, karena baris ini tidak mengeksekusi.
Aku masuk 3.
Jadi saya, pada kenyataannya, masukkan dua perintah argumen baris, dan 3 adalah
lebih besar dari nol.
Jadi kita melihat garis itu, kami dieksekusi, tapi kami tidak melangkah
dalam jika kondisi.
>> Jadi sekarang, selanjutnya, saya melihat aku pengaturan kunci int sama untuk i arg v1.
Jadi itulah saya menciptakan kunci variabel.
Jadi jika saya mencetak kunci yang tepat sekarang, karena yang memungkinkan Anda untuk melihat
nilai dalam variabel, key sama dengan 47.
Itu aneh, tapi tentu saja, itu karena saya belum
dieksekusi baris yang belum.
Jadi sekarang jika aku memukul n, mengeksekusi baris tersebut, dan melakukan tombol cetak, tombol akan sama 3,
yang adalah apa yang kita harapkan untuk sama.
>> Jadi sekali lagi, di GDB, garis Anda melihat Anda belum dieksekusi belum.
Anda harus memukul n atau s atau nomor perintah lain untuk benar-benar
mengeksekusi garis itu.
Tombol Print.
Key pada 3.
Sejauh ini, begitu baik.
String adalah teks biasa.
Mari kita mengeksekusi garis itu.
Saya mendapatkan string dari pengguna.
>> Mari kita lihat di saya Periksa 50, I masukkan BARFOO semua topi, sehingga
itulah yang akan saya masukkan.
Jika sekarang saya mencetak teks biasa.
Anda akan melihat itu sama dengan string.
Ini memberi saya beberapa heksadesimal aneh lainnya jumlah, tetapi tidak di
Fakta mengatakan bahwa saya string adalah BARFOO.
Jika saya ingin melihat apa kunci setara di titik ini, bagaimana saya bisa memeriksa kunci?
>> MAHASISWA: tombol Print.
>> JASON Hirschhorn: tombol Print, tepatnya.
Dan sebenarnya, ada jalan pintas.
Jika Anda bosan mengetik cetak, Anda hanya bisa mengetik p.
Jadi kuncinya p melakukan hal yang persis sama.
Dan lagi, saya lihat itu sama dengan 3.
>> Jika saya ingin mencari tahu apa kunci keberhasilan dan BARFOO setara pada saat yang sama
tapi aku lelah mengetik masing-masing satu individual, saya
bisa mengetik Info penduduk setempat.
Itu memberi saya sama dengan kunci 3.
Plain text sama BARFOO.
Ini juga memberi saya dua hal aneh di atas, variabel ini saya dan
n variabel ini.
>> Mereka benar-benar ada dalam program utama saya.
Kami belum menemukan mereka lagi, tetapi sebagai preview, mereka
ada di saya untuk loop.
Jadi sekarang, mereka sama beberapa aneh nomor karena mereka belum
diinisialisasi, tapi mereka masih ada dalam memori, jadi mereka hanya mengatur
untuk beberapa nilai sampah.
Tapi kita lihat kunci di dataran teks di sana.
>> Jadi aku akan mengeksekusi baris ini, baris 34, untuk loop.
Kita akan melompat ke untuk loop dengan menekan n.
Dan kami berada di dalam untuk loop.
Kami berada di cek pertama kami.
Dan lagi, ini harus semacam terlihat akrab bagi Anda karena ini adalah
Program Caesar yang ditulis, tetapi lagi, memiliki semacam bug.
>> Dan sekarang jika saya melakukan Info penduduk setempat, karena aku dalam yang untuk loop, Anda akan melihat
bahwa saya sama dengan nol, seperti yang kita harapkan.
Itulah apa yang kita set ke dan diinisialisasi Untuk itu dalam untuk loop.
n sama dengan 6.
Itu juga masuk akal karena kita menetapkan ke strlen teks biasa.
Jadi saya ingin melakukan Info penduduk setempat atau cetak variabel sering untuk memastikan bahwa
semuanya selalu apa Saya berharap untuk sama.
Dalam hal ini, semuanya apa yang saya harapkan untuk sama.
>> Jadi mari kita mulai bergerak melalui ini untuk loop.
Garis aku di baris adalah 36, jika polos teks i lebih besar dari dan polos
teks i kurang dari atau sama dengan z.
Saya tahu masalah saya bukan dengan pertama saya surat, itu dengan surat kedua.
Jika kita melihat kembali pada tarif 50, B pergi ke E baik-baik saja.
Aku mengambil A dan meninggalkan sebagai A, tidak berubah ke D. Jadi
ada sesuatu yang salah dengan surat kedua.
Jadi aku akan pindah sana dalam detik.
>> Tapi jika saya ingin memeriksa apa polos teks Aku setara dalam hal ini khususnya
kasus, saya pikir itu harus menjadi apa?
Apa yang harus saya teks biasa sama dalam hal ini babak pertama melalui untuk loop?
>> MAHASISWA: Zero?
>> JASON Hirschhorn: teks Plain I?
Jadi harus modal B. Aku, tentu saja, sama dengan nol, tetapi teks biasa
braket braket nol tertutup sama dengan B karena string, seperti yang kita lihat minggu lalu,
adalah array, jadi kita mendapatkan karakter pertama dari itu.
Jadi sekali lagi, jika saya dicetak plain text Aku, aku, pada kenyataannya, mendapatkan karakter
B. Dan itu rapi, kan?
Saya tidak benar-benar memiliki teks biasa I. Itu bukan salah satu variabel saya set
atau diinisialisasi, tetapi Anda dapat mencetak out seluruh host hal-hal
jika Anda ingin.
>> Tapi mari kita bergerak melalui.
Jika teks biasa saya lebih besar dari A dan teks biasa saya kurang dari atau sama dengan
Z, yang jelas-jelas benar karena kita memiliki a B. modal aku akan menjalankan
beberapa perintah di atasnya.
Kami melihat matematika yang minggu lalu, jadi kita akan menerima begitu saja bahwa ia bekerja
tepat sesuai dengan Periksa 50.
>> Ini kurung kurawal, yang pertama menunjukkan bahwa saya keluar jika
kondisi, yang kedua menunjukkan bahwa aku keluar untuk loop.
Dan sekarang ketika saya menekan Berikutnya, kita akan melihat kita kembali pada for loop lagi.
Kita akan melalui untuk loop lagi.
Mari kita benar-benar masuk ke kedua iterasi untuk loop dan tipe
Info penduduk setempat.
>> Jadi kita pada iterasi kedua loop untuk kami.
Aku sama dengan 1, yang kita harapkan.
N sama dengan 6, yang kita harapkan.
Key sama dengan 3, yang kita harapkan.
Dan teks biasa, Anda akan melihat, sama dengan EARFOO sekarang, bukan lagi karena BARFOO
dalam iterasi kami sebelumnya, B adalah berubah menjadi modal E. Jadi kita tentang
menghadapi masalah, jadi ini adalah di mana kita akan
menyelam ke debugging.
Tapi apakah ada yang memiliki pertanyaan tentang apa yang telah kita lakukan sejauh ini?
Fantastic.
>> Jadi kita akan mengeksekusi ini jika kondisi, braket teks biasa aku menutup
braket lebih besar dari A dan teks biasa saya kurang dari atau sama dengan Z. Tapi sebelum
Saya pergi ke dalam, karena ini adalah di mana Saya tahu kesalahan saya, saya ingin menunjukkan
out plain text I. Jadi mari kita print out.
Itu sama karakter A, sehingga tampaknya sejauh ini, semuanya baik-baik dan baik.
>> Jadi saya berharap baris ini per logika saya, baris ini harus benar.
Ini adalah huruf kapital.
Tapi jika aku memukul n, kita menyadari bahwa ini line, pada kenyataannya, tidak mengeksekusi.
Aku melompat ke lain jika.
Mengapa itu terjadi?
>> Karena Anda memiliki kondisi Anda: STUDENT teks biasa lebih besar
dari A, tidak sama atau lebih besar dari.
>> JASON Hirschhorn: Jadi saya harus teks biasa saya Aku lebih besar dari A, tidak lebih besar
dari atau sama dengan.
Jadi jelas, ibukota A tidak memicu ini jika kondisi, dan kami melakukan
tidak melangkah ke dalamnya, dan kami melakukan tidak melakukan perubahan yang diperlukan.
Jadi itu saja, sebenarnya.
Aku tahu bug saya.
Aku bisa kembali ke file sumber saya, mengubahnya, dan memperbaruinya dan
jalankan Periksa 50 lagi.
>> Tapi kita akan lihat, hanya untuk pedagogi ini sake, jika saya terus berjalan.
Lain jika tidak mengeksekusi baik, tapi apa bukannya sama adalah perintah
yang tidak berubah.
Jadi itu tidak berubah sama sekali, dan jika saya mencetak teks biasa di sini, kita akan melihat akan
melalui itu untuk loop tidak, pada kenyataannya, mengubah bahwa karakter kedua sama sekali.
Ini masih modal A.
>> Jadi sekali lagi, kami debugged kesalahan kami.
Kami menyadari bahwa ada beberapa logika yang hilang.
Dan kami debugged depan dari waktu sebelum benar-benar melaksanakan garis itu,
tetapi Anda akan menyadari telah kami hanya tekan Next dan melompat ke yang lain jika,
itu berarti bahwa jika kondisi itu tidak benar.
Kami tidak, pada kenyataannya, dapatkan hasilnya kami harapkan.
Jadi kita bisa saja diminta, memiliki Kami tidak pernah begitu cerdik, untuk melihat
bahwa jika kondisi dan memeriksa apakah, pada kenyataannya, kondisi kita harus mengevaluasi untuk
benar dalam konteks saat ini.
>> Itu semua untuk debugging program ini.
Apakah Ada yang punya pertanyaan?
Perintah apa yang bisa aku memukul berhenti GDB?
Q. Dan kemudian aku akan diminta, berhenti sih?
Ya atau tidak.
Aku akan memukul ya, dan aku akan telah berhenti GDB.
>> Jadi itu adalah primer cepat untuk GDB.
Sebenarnya, dalam skenario nyata, Saya melakukan ini pada jam-jam kantor.
Saya GDBed program ini tepat pada jam kantor dengan mahasiswa.
Dan jika kita kembali ke perintah yang kita lihat sebelumnya, kami menggunakan istirahat utama, pertama
hal yang kita lakukan.
Kami menggunakan run dengan argumen baris perintah, Hal kedua yang kita lakukan.
Kami menggunakan berikutnya banyak bergerak kita melalui garis.
Dan lagi, versi pendek dari selanjutnya adalah n.
Itu dalam tanda kurung dalam abu-abu pada slide.
>> Kami tidak menggunakan langkah, tapi kami tidak selalu perlu untuk kasus ini.
Tapi kita mungkin menggunakannya dalam sedikit kemudian pada hari ini jika kita debugging, untuk
Misalnya, pencarian biner ketika biner pencari yang disebut dalam terpisah
fungsi tapi ada beberapa error dengan itu.
Kita akan ingin untuk melangkah ke panggilan untuk pencarian biner dan
sebenarnya debug itu.
Daftar kita tidak menggunakan baik karena kami memiliki rasa yang baik dari kode kita, tetapi jika aku
memang ingin mendapatkan rasa apa kode saya sekitar, saya hanya bisa menggunakan daftar.
>> Cetak kami digunakan, info lokal yang kita gunakan.
Lanjutkan kita tidak perlu untuk digunakan dalam hal ini kasus, juga tidak kita perlu menggunakan
menonaktifkan, tapi kami lakukan menggunakan berhenti.
Sekali lagi, ini 10 perintah, mempraktekkannya.
Jika Anda memahami ini 10 perintah, Anda harus ditetapkan untuk debugging setiap
masalah dengan GDB.
>> Jadi kita akan pergi, sekali lagi, untuk Inti dari bagian hari ini, akan lebih
ini pemilahan dan pencarian algoritma.
Sebelum kita melakukannya, sekali lagi, pertanyaan, komentar, keprihatinan untuk GDB?
Jadi ini semua orang akan menggunakan GDB daripada printf?
Jadi semua orang, demi lamanya itu, semua orang menganggukkan kepala hak mereka
sekarang, jadi saya akan melihat Anda pada jam-jam kantor dan semua TF akan melihat Anda dan
mereka akan mengatakan, tunjukkan saya bagaimana menggunakan GDB, dan Anda akan dapat
untuk menunjukkan kepada mereka, kan?
Jenis?
Mungkin mudah-mudahan.
Keren.
>> Jadi kita akan pindah ke pemilahan dan pencarian.
Anda akan melihat saya memiliki daftar yang sudah diurutkan bagi kita, tapi itu tidak akan
menjadi kasus selalu.
Jadi dalam masalah mengatur spesifikasi untuk Masalah menetapkan tiga, Anda memiliki celana pendek
bahwa Anda dapat menonton, dan itu benar-benar meminta Anda untuk menonton mereka celana pendek.
Juga dalam kuliah minggu lalu, kami pergi banyak algoritma ini, jadi aku
tidak akan menghabiskan waktu di kelas akan lebih algoritma ini lagi atau menggambar
gambar untuk bagaimana algoritma bekerja.
Sekali lagi, informasi yang Anda dapat menonton kembali kuliah, atau informasi yang
ditangkap luar biasa pada celana pendek untuk pencarian tersebut, semua
yang tersedia di cs50.net.
>> Jadi sebagai gantinya, apa yang kita akan lakukan adalah menulis program ini.
Kami memiliki arti, model mental, bagaimana mereka bekerja, dan jadi apa kita akan
lakukan adalah kode mereka nyata.
Kita akan mengubah model mental, gambar itu, jika Anda mau, ke dalam
kode aktual.
Dan jika Anda sedikit bingung atau kabur pada model mental, saya benar-benar
mengerti.
>> Kami tidak benar-benar akan melompat ke kode langsung.
Jadi sementara yang cepat ini dalam slide ini meminta Anda untuk kode pencarian biner, dan
sebenarnya, versi iteratif pencarian biner, hal pertama yang saya
benar-benar ingin Anda lakukan adalah menulis beberapa pseudocode.
Jadi Anda memiliki model mental ini bagaimana biner bekerja pencarian.
Ambil selembar kertas jika Anda memiliki satu tersedia, atau membuka
editor teks, dan saya ingin semua orang untuk menulis.
Mengambil empat menit untuk menulis pseudocode untuk pencarian biner.
>> Sekali lagi, pikirkan bahwa model mental.
Aku akan datang sekitar jika Anda memiliki pertanyaan dan kita dapat menarik gambar keluar.
Tapi pertama-tama, sebelum kita mulai pemrograman, Aku ingin menulis
pseudocode untuk pencarian biner sehingga ketika kita menyelam, kami memiliki beberapa arah sebagai
di mana kita harus kepala.
>> MAHASISWA: Dapatkah kita asumsikan array nilai-nilai yang kita dapatkan sudah diurutkan?
>> JASON Hirschhorn: Jadi untuk pencarian biner untuk bekerja - pertanyaan yang sangat bagus - Anda
harus mengambil di diurutkan array nilai.
Jadi menganggap itu akan bekerja.
Kita akan kembali ke slide ini.
Anda akan melihat di ungu fungsi deklarasi bool int binary_search
nilai, nilai-nilai int, int n.
Ini harus tampak akrab jika Anda sudah sudah mendekati atau mendapatkan Anda
tangan kotor dengan set masalah.
>> Tapi itu deklarasi fungsi Anda.
Sekali lagi, tidak perlu khawatir tentang yang banyak pada saat ini.
Apa yang saya benar-benar ingin Anda lakukan adalah mengambil empat menit ke biner pseudocode
pencarian, dan kemudian kami akan pergi lebih dari itu sebagai sebuah kelompok.
Dan aku akan datang sekitar.
Jika Anda memiliki pertanyaan, jangan bebas untuk mengangkat tangan Anda.
>> Mengapa Anda tidak mengambil dua menit lagi untuk menyelesaikan pseudocode tersebut?
Saya tahu ini mungkin tampak konyol bahwa kita menghabiskan begitu banyak waktu di
sesuatu yang bahkan tidak benar-benar di C, tetapi terutama untuk ini lebih
algoritma menantang dan masalah set bahwa kita harus mencari tahu,
dimulai pada pseudocode tidak khawatir tentang sintaks, hanya mengkhawatirkan
logika, sangat membantu.
Dan dengan cara itu, Anda tidak memecahkan dua masalah sangat sulit sekaligus.
Kau hanya fokus pada logika, dan maka Anda pindah ke sintaks.
>> OK.
Mari kita mulai akan melalui pseudocode.
Saya telah menulis di sini, biner pencarian pseudocode.
Kami akan menulis ini pada naik bersama-sama.
Atau aku akan menulis dan Anda akan memberikan saya petunjuknya saya butuhkan.
Jadi siapa pun dapat memberikan saya yang pertama garis pseudocode Anda
menulis untuk pencarian biner?
Ya, Annie?
>> MAHASISWA: Sementara panjang daftar lebih besar dari nol.
>> JASON Hirschhorn: Sementara panjang dari daftar lebih besar dari nol.
Dan lagi, kita melihat beberapa C-cari hal sintaksis di sini.
Tapi sebagian besar ini adalah dalam bahasa Inggris.
Apakah ada yang memiliki garis mereka menempatkan sebelum ini dalam pseudo-kode mereka?
>> MAHASISWA: Dapatkan array dari diurutkan angka.
>> JASON Hirschhorn: Anda menulis "mendapatkan array nomor disortir. "Per
fungsi deklarasi, kita akan melewati array nomor diurutkan.
>> SISWA: [Tak terdengar].
>> JASON Hirschhorn: Jadi kita akan memiliki itu.
Tapi ya, jika kita tidak memiliki itu, kita akan perlu untuk mengurutkan array kita
angka, karena pencarian biner hanya bekerja pada array diurutkan.
Jadi sementara panjang daftar sama dengan nol, aku akan dimasukkan ke dalam beberapa kurung kurawal
untuk membuatnya terlihat sedikit lebih seperti C. Tapi sementara, tampaknya untuk memetakan ke sebuah
while, sehingga dalam sementara ini lingkaran apa yang kita butuhkan untuk
lakukan untuk pencarian biner?
>> Orang lain yang tidak memberi saya menjawab belum tapi yang menulis ini?
>> MAHASISWA: Pergi ke tengah daftar.
>> JASON Hirschhorn: Tom.
Pergi ke tengah daftar.
Dan pertanyaan tindak lanjut, apa yang kita lakukan setelah kita berada di
tengah daftar?
>> MAHASISWA: Lakukan cek apakah itu jumlah yang Anda cari.
>> JASON Hirschhorn: Excellent.
Pergi tengah daftar dan cek jika nilai kita ada -
fantastis.
Apakah ada yang punya apa-apa lagi yang berbeda dari ini?
Itu tepat sekali.
>> Hal pertama yang kita lakukan dalam pencarian biner adalah pergi ke tengah daftar dan
memeriksa untuk melihat apakah nilai kita ada di sana.
Jadi saya berasumsi jika nilai kita ada, apa yang kita lakukan?
>> MAHASISWA: Kami kembali nol [Tak terdengar].
>> JASON Hirschhorn: Ya, jika kami nilai yang ada, kami menemukan itu.
Jadi kita bisa katakan beberapa cara, namun hal ini fungsi didefinisikan, kita memberitahu pengguna
kami menemukan itu.
Jika tidak ada, meskipun, itu di mana hal ini akan sulit.
Jadi jika tidak ada, orang lain yang bekerja pada pencarian biner atau
telah ide sekarang, apa yang kita lakukan?
>> MAHASISWA: Pertanyaan.
>> JASON Hirschhorn: Ya?
>> MAHASISWA: Apakah array sudah diurutkan?
>> JASON Hirschhorn: Ya, kita mengasumsikan array sudah diurutkan.
>> MAHASISWA: Jadi maka Anda harus memeriksa apakah nilai yang Anda lihat adalah lebih besar dari
nilai yang Anda inginkan, Anda dapat memindahkan ke tengah setengah lainnya.
>> JASON Hirschhorn: Jadi jika tengah daftar lebih besar dari apa yang kita
mencari, maka kita apa?
Kami berpindah-pindah tempat?
>> STUDENT: Anda ingin pindah ke setengah dari daftar dengan
angka yang lebih rendah dari itu.
>> JASON Hirschhorn: Jadi kita akan menyebutnya kiri.
Jadi jika tengah lebih besar, kita dapat mencari setengah kiri daftar.
Dan kemudian oleh pencarian, apa yang saya maksud dengan pencarian?
>> SISWA: [Tak terdengar].
>> JASON Hirschhorn: Kami pergi ke tengah.
Kami benar-benar mengulangi hal ini.
Kami kembali melalui loop sementara kami.
Aku akan memberikan yang terakhir -
lain, jika, tengah kurang dari apa yang yang kita lakukan, apa yang kita lakukan di sini?
>> MAHASISWA: Pergi ke kanan.
>> JASON Hirschhorn: Cari kanan.
Ini terlihat bagus, tetapi apakah ada yang memiliki apa pun yang kita mungkin hilang atau
apa pun yang Anda masukkan dalam pseudo-kode Anda?
Jadi ini adalah apa yang kita miliki sejauh ini.
Sementara panjang daftar adalah lebih besar dari nol, kita akan pergi
ke tengah daftar dan memeriksa apakah nilai kita ada di sana.
>> Jika tengah lebih besar, kita akan cari kiri, lain jika tengah adalah
kurang, kita akan mencari kanan.
Jadi kita semua memiliki beberapa keakraban dengan istilah yang kami gunakan dalam ilmu komputer
dan alat yang kita miliki.
Tapi Anda sudah akan melihat kami berbicara dalam bahasa Inggris, tapi kami menemukan
banyak hal yang tampaknya untuk memetakan ke alat yang kita miliki dalam coding tool kit kami.
Jadi langsung dari kelelawar, kita tidak akan benar-benar kode belum.
>> Apa yang kita lihat di sini dalam bahasa Inggris bahwa peta ke hal-hal yang kita dapat menulis di C?
>> MAHASISWA: Sementara.
>> JASON Hirschhorn: Sementara.
Jadi sementara ini di sini peta pada apa?
>> SISWA: Sebuah loop sementara.
>> JASON Hirschhorn: Sebuah loop sementara?
Atau mungkin, lebih umum, satu lingkaran.
Kami ingin melakukan sesuatu berulang-ulang.
Jadi kita akan kode loop.
Dan kita sudah tahu, karena kami telah melakukan ini beberapa kali dan kami
memiliki banyak contoh di luar sana, bagaimana sebenarnya menulis
Indeks ini untuk loop.
Sehingga harus cukup mudah.
Kita harus bisa mendapatkan bahwa mulai cukup cepat.
>> Apa lagi yang kita lihat di sini?
Apa lain struktur sintaks, hal-hal bahwa kita akrab dengan C, kita
sudah memiliki rasa Berbasis off dari kata-kata yang kita gunakan?
Ya, Anna?
[Tak terdengar]
hanya bercanda.
Anna, pergi ke depan.
>> MAHASISWA: Jika dan yang lain.
>> JASON Hirschhorn: Jika dan lain - di sini.
Jadi apa yang mereka terlihat seperti?
>> SISWA: Sebuah jika pernyataan lain.
>> JASON Hirschhorn: Ya, kondisi, kan?
Jadi kita mungkin harus menulis beberapa kondisi.
Dan lagi, meskipun mungkin membingungkan pada pertama, kita umumnya memiliki rasa sekarang
bagaimana menulis kondisi dan sintaks untuk kondisi.
Dan jika kita tidak, kita hanya melihat pada sintaks untuk kondisi, cut and paste
itu, karena kita tahu bahwa kita membutuhkan kondisi di sini.
Hal-hal lain kita melihat peta yang ke hal yang mungkin perlu dilakukan di C?
Ya, Aleha?
>> SISWA: Ini mungkin jelas, dengan hanya memeriksa jika
Nilai sama dengan sesuatu.
>> JASON Hirschhorn: Jadi bagaimana kita memeriksa dan - jadi pergi ke tengah daftar
dan memeriksa apakah nilai kita di sana?
Bagaimana kita melakukan itu di C?
Apa sintaks untuk itu?
>> MAHASISWA: Sama, sama.
>> JASON Hirschhorn: Sama, sama.
Jadi cek ini mungkin akan menjadi sederajat, sama.
Jadi kita akan tahu bahwa kita perlu tempat itu.
Dan sebenarnya, hanya secara tertulis itu, kita melihat hal-hal lain.
Kita akan harus melakukan beberapa operator perbandingan di sana -
fantastis.
Jadi itu benar-benar terlihat seperti, oleh dan besar, kami belum ditulis
kata kode C belum.
Tapi kami punya mental model bawah melalui ceramah dan mereka celana pendek.
>> Kami menulis pseudo-code sebagai sebuah kelompok.
Dan sudah, kita memiliki 80% jika tidak 90% dari apa yang perlu kita lakukan.
Sekarang, kita hanya perlu kode itu, yang sekali lagi, adalah
masalah non-sepele untuk memecahkan.
Tapi setidaknya kita terjebak pada logika.
Setidaknya sekarang ketika kita pergi ke jam kantor, Saya dapat mengatakan, saya tahu apa yang saya butuhkan
untuk dilakukan, tetapi dapat Anda mengingatkan saya sintaks?
Atau bahkan jika jam kantor yang penuh sesak, Anda dapat Google untuk sintaks, bukan
daripada terjebak pada logika.
>> Dan lagi, daripada mencoba untuk memecahkan logika dan masalah sintaks semua
sekaligus, sering lebih baik untuk memecahkan dua masalah hard off ke
dua yang lebih mudah dikelola dan melakukan pseudo-code pertama dan kemudian kode di C.
Jadi mari kita lihat apa yang saya lakukan untuk semu-kode sebelumnya.
>> Sementara panjang daftar adalah lebih besar dari nol, melihat tengah
daftar.
Jika nomor ditemukan kembali benar, yang lain jika nomor yang lebih tinggi, pencarian kiri.
Lain jika angka yang lebih rendah, pencarian kanan, kembali palsu.
Jadi yang terlihat hampir identik jika tidak hampir identik dengan apa yang kita tulis.
Sebenarnya, Tom, apa yang Anda katakan pertama, melanggar tengah daftar dan jika
jumlah yang ditemukan dalam dua pernyataan sebenarnya apa yang saya lakukan.
>> Saya menggabungkan mereka di sana.
Saya harus mendengarkan Anda pertama kali.
Jadi itu adalah pseudo-code yang kita miliki.
Jika Anda ingin sekarang, maaf, pergi kembali ke masalah awal kami.
Mari kita kode binary.c.
Jadi menerapkan versi iteratif pencarian biner menggunakan berikut
deklarasi fungsi.
>> Dan Anda tidak perlu menyalin ke bawah dulu.
Aku benar-benar akan membuka up di sini binary.c.
Jadi ada fungsi deklarasi di tengah-tengah layar.
Dan Anda akan melihat saya mengambil pseudo-code dari di sisi saya, tapi hampir identik
dengan apa yang kita tulis, dan menempatkan bahwa untuk Anda.
Jadi sekarang, mari kita lima menit untuk kode fungsi ini.
>> Dan lagi, jika Anda memiliki pertanyaan, mengangkat tangan Anda, biarkan aku tahu, aku akan
datang sekitar.
>> SISWA: [Tak terdengar].
>> JASON Hirschhorn: Jadi saya mengambil biner definisi pencarian di bagian
atas, pada baris 12.
Itulah apa yang saya dapatkan untuk slide saya.
Dan kemudian semua ini pseudo-kode saya hanya copy dan disisipkan dari slide,
pseudo-code slide.
Aku masih tidak mendengar [Tak terdengar].
>> Jadi jika Anda telah selesai Anda implementasi, saya ingin memeriksa itu.
Saya diemail Anda file helpers.h sebelumnya di kelas ini.
Dan itu akan tersedia secara online juga untuk di-download untuk orang-orang menonton
bagian ini waktu tertunda.
Dan aku hanya menggunakan distribusi generik kode dari pset3.
Jadi saya mengambil find.C, menggunakan file helpers.h saya daripada file helpers.h
yang diberikan dalam kode distribusi.
>> Dan saya harus membuat satu perubahan lain dalam find.C daripada menelepon hanya cukup
pencarian, panggilan binary_search.
Jadi jika Anda ingin menguji kode Anda, tahu bahwa itu adalah bagaimana melakukannya.
Bahkan, ketika kita akan menjalankan kode ini sekarang, saya hanya membuat salinan
direktori pset3 saya, sekali lagi, bertukar keluar file pembantu dan kemudian dibuat bahwa
perubahan find.C untuk memanggil binary_search bukan sekadar mencari.
>> JASON Hirschhorn: Ya.
Anda memiliki pertanyaan?
>> MAHASISWA: Nevermind.
>> JASON Hirschhorn: Jangan khawatir.
Nah, mari kita mulai.
Kami akan kode ini sebagai sebuah kelompok.
Satu catatan lain.
Sekali lagi, ini, dapat dengan mudah bertukar in untuk Masalah Set Tiga.
Aku punya file helpers.h saya yang, agak dari helpers.h kita diberi,
menyatakan pencarian biner, gelembung sort, dan selection sort.
Dan di find.c Anda akan melihat on line, apa itu, baris 68, kita sebut biner
mencari daripada pencarian.
Jadi sekali lagi, kode yang tersedia secara online atau kode bahwa Anda
menciptakan sekarang dapat dengan mudah bertukar in untuk p set 3 untuk memeriksanya.
>> Tapi pertama-tama, mari kita kode pencarian biner.
Deklarasi fungsi kami, kita kembali bool.
Kami mengambil integer disebut nilai.
Kami mengambil sebuah array bilangan bulat disebut nilai-nilai, dan kita mengambil n menjadi
ukuran array.
Pada baris 10, di sini, saya memiliki tajam termasuk stdbool.h.
Apakah ada yang tahu mengapa itu ada?
Jadi apa yang baris kode lakukan?
>> MAHASISWA: Hal ini memungkinkan Anda untuk menggunakan jenis bool kembali.
>> JASON Hirschhorn: Tepat.
>> MAHASISWA: Atau itu sebuah perpustakaan yang memungkinkan menggunakan jenis bool kembali.
>> JASON Hirschhorn: Jadi tajam termasuk baris stdbool.h memberi saya beberapa
definisi dan deklarasi untuk hal-hal bahwa saya diizinkan untuk digunakan dalam
perpustakaan ini.
Jadi di antara mereka mengatakan bahwa ada Jenis ini disebut bool, dan dapat
benar atau salah.
Jadi itulah yang garis yang tidak.
Dan jika saya tidak memiliki jalur itu, saya akan mendapat kesulitan untuk menulis ini
kata yang tepat di sini, bool, di sana.
Tepat.
Jadi aku butuh bahwa dalam kode ini.
OK.
Jadi ini, sekali lagi, adalah berulang versi, tidak satu rekursif.
Jadi mari kita mulai.
>> Mari kita mulai dengan ini dulu baris kode semu.
Dan mudah-mudahan, kita akan - atau tidak mudah-mudahan.
Kita akan pergi di sekitar ruangan.
Kita akan pergi baris demi baris, dan saya akan membantu Anda mengetahui garis yang kita butuhkan
untuk menulis pertama.
Jadi sementara panjang daftar lebih besar dari nol.
Mari kita mulai di depan.
Apa yang harus saya menulis baris di sini, dalam kode?
>> MAHASISWA: Sementara kurung n lebih besar dari 0.
>> JASON Hirschhorn: Sementara n besar dari 0.
Jadi n adalah ukuran dari daftar, dan kami sedang memeriksa apakah -
>> [Interposing SUARA]
>> JASON Hirschhorn: - maaf?
>> MAHASISWA: Bagaimana kita tahu bahwa n adalah ukuran dari daftar?
>> JASON Hirschhorn: Maaf.
Per spesifikasi pset, pencarian dan semacam fungsi yang Anda butuhkan untuk menulis,
n adalah ukuran dari daftar.
Aku lupa menjelaskan bahwa di sini.
Tapi ya. n adalah ukuran daftar, dalam kasus ini.
Jadi sementara n lebih besar dari 0.
OK.
Yang mungkin terbukti sedikit bermasalah meskipun, jika hal-hal pergi.
Karena kita akan terus untuk mengetahui ukuran daftar sepanjang ini
fungsi, tapi mengatakan kami memulai dengan sebuah array dari 5 bilangan bulat.
Dan kami pergi melalui dan kami sudah sekarang mempersempitnya ke
array 2 bilangan bulat.
Yang 2 bilangan bulat itu?
Ukurannya 2 sekarang bahwa kita ingin melihat, tapi yang 2 itu?
Apakah itu masuk akal, pertanyaan itu?
>> OK.
Aku akan bertanya lagi.
Jadi kita mulai dengan array ini dari 5 bilangan bulat, dan n sama dengan 5, kan?
Kami akan berjalan melalui sini.
kami mungkin akan mengubah ukuran, benar, sebagai hal-hal pergi.
Yang adalah apa yang kita katakan kita ingin lakukan.
Kami tidak ingin mencari hal penuh lagi.
Jadi katakan kita mengubahnya ke 2.
Kami mengambil setengah daftar yang aneh.
Jadi hanya memilih 2.
Jadi sekarang n sama dengan 2.
Saya minta maaf untuk orang miskin spidol menghapus kering.
Benar?
Dan kami sedang mencari melalui daftar lagi dengan daftar ukuran 2.
Nah, array kita masih ukuran 5.
Kami mengatakan kami hanya ingin mencari 2 titik di dalamnya.
Jadi yang 2 tempat itu?
>> Apakah itu masuk akal?
Apakah mereka kiri 2 tempat?
Apakah mereka benar 2 tempat?
Apakah mereka tengah 2 tempat?
Kami telah rusak masalah turun, tapi kami sebenarnya tidak tahu bagian yang
masalah kita masih melihat, hanya dengan memiliki 2 variabel tersebut.
Jadi kita perlu sedikit lebih kemudian, sementara n lebih besar dari 0.
Kita perlu tahu di mana itu n dalam array kita yang sebenarnya.
>> Jadi apakah ada yang memiliki mengubah baris ini?
Sebagian dari baris ini adalah sempurna benar.
Apakah ada tambahan lain?
Bisakah kita menukar sesuatu untuk n untuk membuat baris ini sedikit lebih baik?
Mm-hm?
>> MAHASISWA: Dapatkah Anda menginisialisasi variabel seperti panjang ke n yang kemudian akan digunakan
kemudian dalam fungsi?
>> JASON Hirschhorn: Jadi menginisialisasi panjang variabel n,
dan kita gunakan nanti?
Tapi kemudian kami hanya memperbarui panjang dan kami masih mengalami masalah ini di mana kita
mengurangi panjang masalah kita, tapi kita tidak pernah tahu di mana, sebenarnya,
panjang yang memetakan ke.
>> MAHASISWA: Bukankah itu akan terjadi kemudian, ketika Anda katakan, cari kiri,
cari kan?
Kau akan pergi ke yang berbeda wilayah Anda -
>> JASON Hirschhorn: Kami akan pergi ke suatu daerah, tetapi bagaimana kita tahu
yang pergi ke?
Jika kita hanya memiliki array dan ini n, bagaimana kita tahu di mana untuk
pergi ke dalam array.
Di bagian belakang, ya?
>> MAHASISWA: Apakah Anda memiliki, seperti, lebih rendah terikat dan variabel batas atas atau
sesuatu seperti itu?
>> JASON Hirschhorn: OK.
Jadi ini adalah ide lain.
Daripada hanya melacak ukuran, kita melacak lebih rendah dan
variabel batas atas.
Jadi bagaimana kita menghitung ukuran dari batas bawah dan batas atas?
>> [Interposing SUARA]
>> JASON Hirschhorn: Pengurangan.
Dan juga melacak lebih rendah terikat dan batas atas untuk memberitahu kami tahu,
kita mencari kedua?
Apakah kita mencari kedua di sini?
Apakah kita mencari dua tengah?
Mungkin tidak dua tengah, karena ini, pada kenyataannya, adalah pencarian biner.
Tapi sekarang kita akan bisa mendapatkan ukuran, tetapi juga batas-batas array.
Pada dasarnya, jika kita memiliki raksasa kami buku telepon, kami merobek menjadi dua.
Kita sekarang tahu di mana yang lebih kecil buku telepon.
Tapi kami tidak benar-benar merobek buku telepon di setengah.
Kita masih perlu tahu di mana batas baru dari masalah kita adalah.
Apakah Ada yang punya pertanyaan tentang itu?
Ya?
>> MAHASISWA: Apakah itu bekerja dengan menciptakan variabel, i, yang kemudian hanya bergeser
posisi saya relatif terhadap posisi saat ini, dan panjang, n?
>> JASON Hirschhorn: Dan apa i?
>> MAHASISWA: Seperti saya menjadi seperti semacam -
Seperti Anda akan menginisialisasi i menjadi Posisi tengah array.
Dan kemudian, jika nilai pada posisi i di tengah array dalam ditemukan
kurang dari nilai yang Anda butuhkan, saya sekarang menjadi panjang array, ditambah
nilai i dibagi 2.
Seperti, lihat, Anda menggeser i -
>> JASON Hirschhorn: Benar.
>> SISWA: - sampai -
>> JASON Hirschhorn: Jadi saya hampir positif yang akan bekerja.
Tapi titik makhluk, Anda memerlukan dua potongan informasi di sini.
Anda dapat melakukannya dengan awal dan akhir, atau Anda dapat melakukannya dengan ukuran, dan kemudian
beberapa penanda.
Tapi Anda perlu dua potong informasi di sini.
Anda tidak dapat bertahan dengan hanya satu.
Apakah itu masuk akal?
>> Jadi kita akan pergi melalui, dan kita akan melakukan [Tak terdengar]
dan membuat beberapa spidol.
Jadi, apa yang Anda tulis dalam kode Anda?
>> SISWA: Aku hanya berkata int terikat satu adalah sama dengan 0.
>> JASON Hirschhorn: Mari kita sebut bahwa int, dimulai.
>> MAHASISWA: OK.
>> JASON Hirschhorn: Itu membuat lebih masuk akal bagi saya.
Dan?
>> SISWA: saya katakan, saya kira, int berakhir.
>> JASON Hirschhorn: int berakhir.
>> SISWA: Saya kira, n dikurangi 1, atau sesuatu seperti itu.
Seperti, elemen terakhir.
>> JASON Hirschhorn: Jadi Anda tulis, int mulai equals 0, titik koma, dan int
ending sama n dikurangi 1, titik koma.
Jadi pada dasarnya, apa yang kita lakukan di sini, 0 posisi pertama.
Dan seperti yang kita tahu dalam array, mereka tidak pergi sampai n, mereka pergi ke n dikurangi 1.
Jadi kita memiliki beberapa batas-batas array kita.
Dan ini batas awal akan terjadi batas awal masalah kita.
OK.
Sehingga suara yang baik.
Kemudian jika kita kembali ke baris ini, sementara panjang daftar lebih besar dari 0,
apa, bukannya n, harus kita masukkan ke dalam sini?
>> MAHASISWA: Menulis berakhir dikurangi awal.
>> JASON Hirschhorn: Sementara mengakhiri dikurangi awal lebih besar dari 0?
OK.
Dan kita bisa, jika kita ingin membuat sedikit lebih bagus, apa
lain yang bisa kita lakukan?
Jika kita ingin membersihkan kode ini sedikit?
Bagaimana kita bisa menyingkirkan 0?
Ini hanya pertanyaan gaya.
Ini benar sekarang.
>> MAHASISWA: Ending tidak awal yang sama?
>> JASON Hirschhorn: Kita bisa melakukan apa?
>> [Interposing SUARA]
>> MAHASISWA: Ending lebih besar?
>> JASON Hirschhorn: Ya.
Kami hanya bisa dilakukan sementara berakhir lebih besar dari awal.
Benar.
Kami menambahkan mulai ke sisi lain itu, dan kami menyingkirkan 0.
Jadi ini hanya terlihat sedikit lebih bersih.
OK.
Jadi, sementara panjang daftar adalah 0, kami menulis bahwa, sementara akhir lebih besar
dari awal.
Kita akan dimasukkan ke dalam diperlukan kami kurung kurawal, dan kemudian hal pertama
kami ingin lakukan adalah melihat mereka dalam daftar kecil.
Anda?
Dapatkah Anda memberi saya -
>> MAHASISWA: Jika kurung square bracket -
>> JASON Hirschhorn: Jika kurung square bracket.
>> MAHASISWA: Mengakhiri dibagi 2.
>> JASON Hirschhorn: Ending?
>> SISWA: Saya melihat masalah dengan Anda -
>> JASON Hirschhorn: OK.
Yah, lihat tengah.
Bagaimana kita tahu apa yang tengah adalah?
Ya.
Jadi biarkan aku menghapus kode tersebut.
Bagaimana kita tahu apa yang tengah adalah?
Dalam apa pun, ketika Anda memiliki awal dan akhirnya, bagaimana Anda menemukan
tengah?
>> STUDENT: Anda rata-rata.
>> STUDENT: Anda menambahkan mereka bersama-sama dan kemudian -
>> JASON Hirschhorn: Tambahkan mereka bersama-sama dan kemudian?
>> MAHASISWA: Dan Anda rata-rata.
Membaginya dengan 2.
>> JASON Hirschhorn: Tambahkan mereka bersama-sama dan dibagi dengan 2.
Jadi int tengah sama?
Tom, Anda dapat memberikannya kepada saya?
>> MAHASISWA: Awal ditambah berakhir -
>> JASON Hirschhorn: Awal ditambah berakhir.
>> MAHASISWA: Semua, braket, dibagi 2.
>> JASON Hirschhorn: Semua, dalam tanda kurung, dibagi 2.
Sehingga memberi saya tengah apa pun, benar?
>> STUDENT: Anda juga perlu putaran itu.
>> JASON Hirschhorn: Apa yang Anda Maksudku, aku perlu putaran itu?
>> [Interposing SUARA]
>> MAHASISWA: Karena kalau Ini aneh nomor, maka itu seperti -
>> JASON Hirschhorn: Well, OK.
Jadi saya bisa mengumpulkan itu.
Tapi kalau itu ganjil, 5, saya bisa mengambil 1 jauh dari tengah.
Atau jika itu adalah bilangan genap, lebih tepatnya, itu kasus yang lebih baik.
Jika itu 4, kita hanya memiliki 4, saya bisa mengambil pertama "tengah", kutipan, tanda kutip atau
kedua "tengah" satu.
Entah akan bekerja untuk pencarian biner, jadi saya tidak benar-benar perlu untuk melengkapi itu.
Tapi ada satu hal lain yang saya perlu melihat baris ini.
Kita mungkin belum menyadarinya, tapi kami akan kembali ke sana.
Karena baris ini sebenarnya masih membutuhkan satu hal lain.
>> Namun sejauh ini, kami telah menulis empat baris kode.
Kami punya awal kami dan berakhir spidol.
Kami memiliki loop sementara kami, yang memetakan secara langsung ke pseudocode kami.
Kami mencari di tengah yang memetakan langsung ke pseudocode kami.
Aku akan mengatakan ini pergi ke tengah daftar, baris kode.
Dan kemudian, setelah kami pergi ke tengah-tengah daftar, hal berikutnya yang perlu kita lakukan
adalah memeriksa apakah nilai kami ada untuk pseudocode kami tulis sebelumnya.
>> Jadi bagaimana kita memeriksa apakah nilai kami berada di tengah-tengah daftar?
Anda.
Mengapa Anda tidak melakukan hal ini?
>> MAHASISWA: Jika nilai kita adalah di tengah adalah sama dengan
apa pun yang kita mengatur -
Maksudku sama sebesar -
>> JASON Hirschhorn: It -
OK.
>> SISWA: Saya tidak yakin apa yang variabel yang kita cari
karena meskipun, karena -
>> [Interposing SUARA]
>> SISWA: [Tak terdengar].
>> JASON Hirschhorn: Tepat.
Per deklarasi fungsi, kita sedang mencari nilai.
Jadi kita mencari nilai dalam array nilai.
Jadi kau benar.
Anda akan lakukan, jika nilai paren terbuka braket tengah ditutup equals braket
sama dengan nilai, dan di dalamnya ada apa yang perlu kita lakukan?
Jika nilai kita di sana, apa yang perlu kita lakukan?
>> [Interposing SUARA]
>> MAHASISWA: Kembali nol.
>> JASON Hirschhorn: Kembali benar.
>> MAHASISWA: Kembali benar.
>> JASON Hirschhorn: Michael, apa baris ini lakukan?
>> SISWA: [Tak terdengar] program ini telah dijalankan nya saja, dan itu sudah berakhir, dan
Anda sudah apa yang harus Anda lakukan?
>> JASON Hirschhorn: Program atau apa?
Dalam kasus ini?
>> SISWA: Fungsi.
>> JASON Hirschhorn: Fungsi.
Jadi, untuk kembali ke apa pun yang disebut dan memberikan nilai, benar.
Tepat.
Main.
Apa jenis kembali dari utama, Michael?
>> MAHASISWA: int, integer?
>> JASON Hirschhorn: int, tepatnya.
Integer.
Itu hanya pertanyaan untuk memastikan kalian telah di atasnya.
Apa biasanya kembali, jika segala sesuatu bekerja dengan baik?
>> MAHASISWA: Zero.
>> JASON Hirschhorn: Zero.
Tepat.
>> MAHASISWA: Jika hal ini hanya mengembalikan nilai true, tidak ada informasi yang diberikan
tentang apa -
Oh, ini hanya mengatakan bahwa nilai di dalam array.
>> JASON Hirschhorn: Tepat.
Program ini tidak memberikan informasi dari mana tepatnya nilai tersebut.
Ini hanya mengatakan, ya, kami menemukan , atau tidak, kami tidak menemukan itu.
Jadi, jika jumlah yang ditemukan, kembali benar.
Well, sebenarnya kita hanya melakukan yang benar-benar cepat dengan satu baris kode.
Jadi saya akan pindah bahwa garis pseudocode.
>> MAHASISWA: Jangan kita perlu untuk mengubah array?
Seharusnya nilai, bukan nilai, kan?
>> JASON Hirschhorn: Maaf.
Terima kasih.
>> MAHASISWA: Ya.
>> JASON Hirschhorn: Baris ini harus nilai-nilai.
Tepat.
OK.
Jadi kita telah melihat daftar tengah.
Jika nomor ditemukan return true.
Melanjutkan dengan pseudocode kami, jika tengah lebih besar, pencarian kiri.
Jadi aku di sini, jika nomor lebih tinggi, cari kiri.
Constantine, Anda dapat memberikan saya baris kode?
>> MAHASISWA: Jika nilai tengah -
>> JASON Hirschhorn: Jadi, jika nilai -
jika paren terbuka nilai braket tengah braket dekat -
>> MAHASISWA: Apakah lebih kecil dari nilai?
>> JASON Hirschhorn: Apakah kurang dari.
>> MAHASISWA: Kurang dari nilai.
>> JASON Hirschhorn: Nilai.
Well, sebenarnya, Anda ingin memeriksa apakah nomor tersebut -
Maaf.
Ini sedikit membingungkan.
Tapi lain jika nomor di tengah daftar lebih besar.
>> MAHASISWA: Oh, OK.
>> JASON Hirschhorn: Aku akan mengubah itu.
Lain jika tengah lebih tinggi, kita ingin mencari kiri, OK?
Dan apa yang kita lakukan di dalam ini jika kondisi?
>> SISWA: Dapatkah saya melakukan perubahan kecil untuk kondisi tersebut, mengubahnya menjadi lain jika?
>> JASON Hirschhorn: Else if?
OK.
Jadi kode ini akan mengeksekusi hampir sama.
Tetapi hal baik tentang penggunaan if, else jika, lain jika atau jika, lain jika, lain
berarti bahwa hanya salah satu dari mereka akan diperiksa, tidak semua tiga dari mereka,
berpotensi.
Dan yang membuatnya sedikit lebih baik pada komputer yang
menjalankan program Anda.
>> Jadi [? Constantine,?]
kita di dalam baris ini, lain jika nilai-nilai, braket braket tengah dekat
lebih besar dari nilai.
Apa yang perlu kita lakukan?
Kita perlu mencari kiri.
Bagaimana kita melakukannya?
Aku akan memberi Anda mulai.
>> Kami memiliki dua hal yang disebut awal dan akhir.
Jadi apa yang harus terjadi ke awal?
Jika Anda ingin mencari di sebelah kiri daftar, kita mendapatkan awal kami saat ini.
Apa yang perlu kita lakukan itu?
>> MAHASISWA: Kami menetapkan awal ke tengah ditambah 1.
>> JASON Hirschhorn: Jadi jika kita mencari kiri?
>> MAHASISWA: Maaf, dikurangi tengah -
sehingga akhir akan tengah dikurangi 1 dan awal -
>> JASON Hirschhorn: Dan apa terjadi pada awal?
>> SISWA: Ini tetap sama.
>> JASON Hirschhorn: Jadi artinya tetap sama.
Jika kita sedang mencari kiri, kami menggunakan awal yang sama -
tepat.
Dan berakhir?
Maaf, apa yang berakhir sama lagi?
>> MAHASISWA: dikurangi Tengah 1.
>> JASON Hirschhorn: dikurangi Tengah 1.
Sekarang, mengapa dikurangi 1, bukan hanya tengah?
>> SISWA: tengah adalah keluar dari gambar sudah, karena kami memiliki
memeriksa bahwa itu keluar?
>> JASON Hirschhorn: Itu tepat.
Tengah adalah keluar dari gambar.
Kami sudah memeriksa tengah.
Jadi kita tidak ingin "tengah," kutipan tanda kutip, untuk terus berada di
Array yang kita cari.
Jadi ini adalah fantastis.
>> Lain jika nilai braket tengah lebih besar dari nilai akhir equals
dikurangi tengah 1.
Jeff, bagaimana dengan baris terakhir ini?
>> MAHASISWA: Lain.
Nilai tengah adalah kurang dari nilai?
>> JASON Hirschhorn: Kami akan Anda memberi saya lain.
Jadi, jika Anda tidak memberi saya -
>> MAHASISWA: Jadi mulai akan tengah ditambah 1.
>> JASON Hirschhorn: Awal equals tengah ditambah 1, sekali lagi, untuk hal yang sama
Alasan bahwa Constantine memberi kami sebelumnya.
Dan pada akhirnya, yang belum memberikan saya baris kode belum?
Kembali palsu, Aleha, apa kita menulis di sini?
>> MAHASISWA: Kembali palsu.
>> JASON Hirschhorn: Kembali palsu.
Dan kita perlu melakukan itu, karena jika kita tidak menemukannya, kita harus mengatakan kita
tidak menemukannya.
Dan kita mengatakan kita akan kembali bool, jadi kita pasti harus kembali
suatu tempat bool.
>> Jadi mari kita menjalankan kode ini.
Aku benar-benar akan -
jadi kita di terminal.
Kami akan membersihkan jendela kita.
Mari Membuat Semua.
Kami menemukan ada satu kesalahan.
Ada kesalahan on line 15, diharapkan koma di akhir
deklarasi.
Jadi apa yang saya lupa?
>> MAHASISWA: Titik koma.
>> JASON Hirschhorn: Titik koma sampai di sini.
Saya pikir itu kode Tom.
Jadi Tom, [Tak terdengar].
Just kidding.
Mari kita lakukan Membuat Semua lagi.
>> SISWA: Apa direktori Dropbox kita harus di atas ini?
>> JASON Hirschhorn: Jadi Anda bisa hanya menonton sebentar ini.
Tetapi sekali lagi, jika Anda ingin pindah ini kode ke direktori pset3 Anda untuk mencoba
keluar, itulah yang saya lakukan.
Jika Anda akan melihat di sini - maaf, pertanyaan yang bagus.
>> [? LS,?]
Saya ada di sini kode find.c dari kode distro minggu ini.
Aku punya helpers.h.
Aku punya file Membuat aku benar-benar diedit sedikit untuk menyertakan baru
file kita menulis.
Semua kode yang akan tersedia, tidak kode distribusi, tetapi baru
Membuat berkas, file helpers.h baru akan tersedia secara online untuk di-download.
Sekali lagi, sehingga mereka adalah Kode tambahan yang kita miliki.
>> Jadi membuat semua, per baris ini, membuat menemukan, biner, seleksi gelembung - merek
mereka bertiga dan mengkompilasi menjadi kode dieksekusi ini menemukan.
Jadi secara umum, kita tidak ingin untuk langsung ke check50.
Kami ingin menjalankan beberapa tes pada kita sendiri.
Tapi hanya supaya kita bisa mempercepat ini sedikit, check50 2013 pset3.find akan melewati
di helpers.c-- saya buruk.
>> Saya tidak punya itu sekarang.
Jadi kita benar-benar akan menjalankan kode nyata.
Usage.find /, Anda tahu apa artinya?
>> STUDENT: Anda perlu kedua baris perintah di atasnya.
>> JASON Hirschhorn: Saya perlu baris perintah kedua.
Dan per spesifikasi, saya perlu untuk memasukkan apa yang kita cari.
Jadi mari kita lihat selama 42.
Kami akan tetap di disortir, karena kita tidak menulis fungsi semacam belum -
42, 43, 44.
>> Dan Kontrol D tidak menemukan jarum di tumpukan jerami.
Itu buruk.
Ini jelas ada.
Mari kita mencoba sesuatu yang lain.
Mungkin karena saya menaruh itu di awal.
>> Mari kita lakukan 41, 42, 43.
Di sana kami pergi.
Ini menemukannya.
Mari kita letakkan di akhir sekarang, hanya sehingga kita bisa menyeluruh -
40, 41, 42.
Tidak menemukan jarum.
Jadi saya sebutkan ini sebelumnya.
Sayangnya, aku tahu ini yang akan terjadi.
>> Tapi untuk tujuan pedagogis, ada baiknya untuk menjelajahinya.
Ini tidak bekerja.
Untuk beberapa alasan, hal itu tidak dapat menemukannya.
Kita tahu apa yang ada di sana, tapi kita tidak menemukan itu.
Jadi satu hal yang kita bisa lakukan adalah pergi melalui GDB untuk menemukannya, tapi apakah ada yang,
tanpa melalui GDB, memiliki rasa mana kita kacau?
[? Madu? ?]
>> SISWA: Saya pikir mungkin ketika berakhir sama dengan awal, dan itu
hanya daftar satu elemen.
Kemudian hanya mengabaikan itu sebagai gantinya untuk benar-benar memeriksa itu.
>> JASON Hirschhorn: Itu tepat.
Ketika akhir sama dengan awal, kita masih memiliki unsur dalam daftar kami?
>> MAHASISWA: Ya.
>> JASON Hirschhorn: Ya, pada kenyataannya, kita memiliki satu dan hanya satu elemen.
Dan itu kemungkinan besar akan terjadi ketika, per kode kita diuji, kita berada di
depan tumpukan jerami atau di akhir tumpukan jerami.
Di situlah awal dan akhir akan sama
satu, dengan pencarian biner.
Jadi dalam kedua kasus itu tidak berhasil, karena berakhir sama dengan awal.
>> Tapi jika berakhir sama dengan awal, apakah while ini mengeksekusi?
Itu tidak.
Dan kita bisa diperiksa yang lagi melalui GDB.
Jadi bagaimana kita bisa memperbaiki kode ini, karena saat saat akhir adalah sama dengan
dimulai, kami juga ingin ini while untuk menjalankan.
>> Jadi apa yang bisa kita buat fix ke baris 18?
>> SISWA: [Tak terdengar] lebih besar dari atau sama dengan.
>> JASON Hirschhorn: Tepat.
Sementara akhir lebih besar dari atau sama dengan awal.
Jadi sekarang, kita pastikan untuk mendapatkan bahwa pojok kasus di akhir.
Dan mari kita lihat.
Mari kita menjalankan ini sekali lagi.
>> Mari kita membuat semua.
Sekali lagi, Anda harus hanya ikuti bersama di sini.
Cari 41 kali ini.
Hanya tetap konsisten.
>> Cari 42.
Mari kita letakkan di awal -
42, 43, 44.
Kami menemukan itu.
Jadi itu memang perubahan kita perlu membuat.
>> Itu banyak coding kita hanya melakukan, pencarian biner.
Apakah Ada yang punya pertanyaan sebelum Aku pindah ke baris kami menulis dalam
pencarian biner atau bagaimana kami pikir apa yang kita tahu?
Sebelum kita melanjutkan, saya juga ingin menunjukkan bahwa pada umumnya, kami dipetakan
kami pseudo-kode yang satu ke kode kita.
>> Kami memiliki hal yang rumit untuk mencari tahu dengan
awal dan akhir.
Tapi apakah Anda tidak mengetahuinya, Anda akan menulis cukup banyak
kode identik, kecuali mereka atas dua baris.
Dan kemudian Anda akan menyadari ketika Anda membuatnya dalam bentuk cek dan kasus-kasus yang
Anda perlu sesuatu yang lain.
Jadi bahkan jika Anda telah mengikuti kami pseudo-kode baris ke baris, Anda akan sudah
mendapatkan semua kecuali dua baris kode yang Anda butuhkan untuk menulis.
>> Dan aku akan berani bertaruh bahwa kalian akan semua mengetahuinya
cukup cepat, yang Anda butuhkan untuk menempatkan semacam penanda di sana untuk mencari
tahu di mana Anda berada.
Artinya lagi, adalah kekuatan melakukan semu-kode sebelumnya.
Jadi kita bisa melakukan logika yang pertama, dan kemudian kita bisa khawatir tentang sintaks.
>> Telah kita bingung tentang logika ketika mencoba untuk menulis kode ini di C,
kita akan mendapatkan semua kacau.
Dan kemudian kami akan mengajukan pertanyaan tentang logika dan sintaks dan meshing
mereka semua bersama-sama.
Dan kita akan mendapatkan hilang dalam apa yang dapat dengan cepat menjadi
masalah yang sangat sulit.
Jadi mari kita lanjutkan sekarang untuk selection sort.
>> Kami memiliki 20 menit tersisa.
Jadi saya punya perasaan kita tidak akan mampu melewati semua selection sort
dan bubble sort.
Tapi mari kita setidaknya upaya untuk menyelesaikan selection sort.
Jadi menerapkan selection sort menggunakan berikut deklarasi fungsi.
>> Sekali lagi, ini diambil dari masalah set spesifikasi.
Nilai Int adalah kurung, adalah sebuah array bilangan bulat.
Dan int.n adalah ukuran array.
Selection sort akan untuk mengurutkan array ini.
>> Jadi per model mental kita seleksi sort, kita tarik -
pertama, kita pergi melalui daftar pertama waktu, menemukan nomor terkecil,
meletakkannya di awal, menemukan kedua nomor terkecil, meletakkannya di
posisi kedua jika kita ingin semacam dalam urutan menaik.
Saya tidak memaksa Anda untuk menulis semu-kode sekarang.
>> Tetapi sebelum kita melakukan kode sebagai sebuah kelas dalam lima menit, kita akan menulis
pseudo-code sehingga kita memiliki beberapa pengertian dari mana kita akan pergi.
Jadi mencoba untuk menulis pseudo-code Anda sendiri.
Dan kemudian berusaha untuk mengubah itu pseudo-kode ke kode.
Kami akan melakukan itu sebagai sebuah kelompok dalam lima menit.
>> Dan tentu saja, beritahu saya jika Anda memiliki pertanyaan.
>> MAHASISWA: Itu saja?
>> JASON Hirschhorn: Lihat seberapa jauh Anda bisa dalam dua menit lagi.
Saya memahami Anda tidak akan bisa menyelesaikan.
Tapi kita akan membahas hal ini sebagai sebuah kelompok.
>> Kalian semua coding jadi [Tak terdengar], jadi aku Maaf untuk jeda apa yang Anda lakukan.
Tapi mari kita pergi melalui ini sebagai sebuah kelompok.
Dan lagi, pencarian biner, Anda semua memberi saya satu jika tidak lebih baris kode.
Terima kasih untuk itu.
Kita akan melakukan hal yang sama di sini, kode bersama-sama sebagai sebuah kelompok.
>> Jadi selection sort - mari kita menulis beberapa cepat pseudo-code.
Per model mental, bisa seseorang memberi saya baris pertama dari pseudo-code, please?
Apa yang ingin saya lakukan?
>> MAHASISWA: Sementara daftar adalah rusak.
>> JASON Hirschhorn: OK, sementara daftar ini rusak.
Dan apa maksudmu "rusak?"
>> SISWA: Sementara [Tak terdengar]
belum diurutkan.
>> JASON Hirschhorn: Sementara daftar adalah rusak, apa yang kita lakukan?
Beri aku baris kedua, silahkan, Marcus.
>> MAHASISWA: Jadi menemukan berikutnya nomor terkecil.
Ini akan menjorok.
>> JASON Hirschhorn: Jadi menemukan selanjutnya nomor terkecil.
Dan kemudian orang lain?
Setelah kita menemukan terkecil berikutnya nomor, apa yang kita lakukan?
Aku akan mengatakan menemukan nomor terkecil.
Itulah yang ingin kita lakukan.
>> Jadi menemukan jumlah terkecil.
Lalu apa yang kita lakukan?
>> SISWA: [Tak terdengar] ke awal.
>> JASON Hirschhorn: Maaf?
>> MAHASISWA: Tempatkan dalam awal daftar.
>> JASON Hirschhorn: Jadi menempatkannya di awal daftar.
Dan apa yang kita lakukan untuk hal tersebut yang pada awalnya
dari daftar, kan?
Kami Timpa sesuatu.
Jadi di mana kita menempatkan itu?
Ya, Anna?
>> MAHASISWA: Dimana terkecil nomor itu?
>> JASON Hirshhorn: Jadi menempatkan awal daftar di mana
nomor terkecil adalah.
Jadi sementara daftar ini rusak, menemukan jumlah terkecil, tempatkan dalam
awal daftar, menempatkan mulai dari daftar di mana
nomor terkecil adalah.
Marcus, yang dapat Anda ulang kata-kata baris ini sementara daftar ini rusak?
>> MAHASISWA: Sementara jumlah belum diurutkan?
>> JASON Hirshhorn: OK, jadi untuk tahu bahwa angka-angka belum
diurutkan, apa yang perlu kita lakukan?
Berapa banyak kita perlu pergi melalui daftar ini?
>> SISWA: Jadi saya kira untuk loop, atau sementara, sedangkan angka diperiksa kurang
dari panjang daftar?
>> JASON Hirshhorn: OK, itu bagus.
Saya pikir saya misphrased pertanyaan saya buruk.
Aku hanya mencoba untuk mendapatkan kita akan harus pergi
melalui seluruh daftar.
Jadi sementara daftar ini rusak, bagi saya, sulit untuk memetakan.
Tapi pada dasarnya, itulah Saya berpikir tentang hal ini.
Pergi melalui seluruh daftar, menemukan nomor terkecil, menempatkannya di
awal - sebenarnya, kau benar.
Mari kita menempatkan mereka berdua.
>> Jadi sementara daftar ini rusak, kita perlu pergi melalui seluruh daftar
sekali, menemukan nomor terkecil, tempat di awal daftar, menempatkan
awal daftar di mana nomor terkecil adalah, dan kemudian jika
Daftar ini masih rusak, kita sudah harus pergi melalui ini
proses lagi, kan?
Itu sebabnya selection sort, Big-O runtime dari selection sort, anyone?
>> MAHASISWA: n kuadrat.
>> JASON Hirshhorn: n kuadrat.
Karena seperti Marcus dan aku baru sadar sini, kita akan harus
pergi melalui daftar daftar beberapa kali.
Jadi akan melalui sesuatu panjang n n beberapa kali
adalah pada kenyataannya n kuadrat.
>> Jadi ini adalah pseudocode kami.
Hal ini terlihat sangat baik.
Apakah Ada yang punya pertanyaan tentang pseudocode itu?
Karena sebenarnya selection sort harus mungkin datang 1-1, kode dari
pseudocode.
Jadi pertanyaan tentang logika pseudocode tersebut?
Silahkan bertanya sekarang.
>> Selection sort - sementara daftar keluar ketertiban, kita akan pergi melalui itu
dan menemukan terkecil setiap kali dan meletakkannya di depan.
Jadi sementara daftar ini rusak, bisa seseorang memberi saya bahwa baris kode yang
tidak memberi saya garis kode belum, please?
Kedengarannya seperti apa?
>> MAHASISWA: Itu untuk loop.
>> JASON Hirshhorn: Kedengarannya seperti untuk loop.
OK, bisa Anda memberi saya untuk loop?
Untuk -
>> MAHASISWA: i Setara 0.
>> JASON Hirshhorn: i atau -
apa yang kita hilang?
Apa yang terjadi di sini?
>> MAHASISWA: Int.
>> JASON Hirshhorn: Tepat.
(Int i = 0; -
>> MAHASISWA: i <n; i + +).
>> JASON Hirshhorn: Dipaku itu, Jeff.
Kita akan melalui daftar, kan?
Kami telah melihat kode itu sebelumnya.
Sempurna.
Jadi mari kita menempatkan kurung kurawal kami di sini.
Aku akan menaruh beberapa kurung kurawal di sini.
>> Jadi sementara itu 0, kita harus pergi melalui seluruh daftar.
Jadi setiap kali kita pergi melalui daftar, apa yang kita ingin melacak?
>> MAHASISWA: Jika ada swap yang dibuat.
>> JASON Hirshhorn: Cari nomor terkecil.
Jadi kita mungkin harus melacak jumlah terkecil setiap kali.
Jadi baris yang dapat saya lakukan untuk melacak dari jumlah terkecil?
Aleha, bagaimana saya bisa tetap melacak sesuatu?
>> MAHASISWA: Mulai variabel baru.
>> JASON Hirshhorn: Mulai variabel baru.
Jadi mari kita membuat sebuah variabel.
Apa jenis?
>> MAHASISWA: Int.
>> JASON Hirshhorn: Int.
Mari kita menyebutnya terkecil.
Dan apa itu sama ketika kami baru memulai?
Kami belum pergi melalui daftar belum.
Kami berada di bagian pertama dari daftar pertama kalinya kami melalui.
Apa itu sama, nomor terkecil?
>> MAHASISWA: Nilai i.
>> JASON Hirshhorn: Nilai i.
Kedengarannya tepat, kan?
Jumlah terkecil di awal adalah di mana kita berada.
Jadi sekarang kita memiliki terkecil kami, dan kita perlu untuk pergi melalui seluruh daftar dan
membandingkan ini terkecil untuk segala sesuatu yang lain.
Jadi kita pergi melalui daftar lagi?
Michael?
>> STUDENT: Anda perlu membuat lain untuk loop.
>> JASON Hirshhorn: lain untuk loop.
Mari kita lakukan.
Berikan saya beberapa kode.
>> MAHASISWA: Untuk lingkaran -
untuk terkecil -
hanya int j, bisa Anda katakan?
= 0; sehingga -
>> JASON Hirshhorn: Nah, jika kita ingin untuk pergi melalui seluruh daftar -
>> MAHASISWA: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Kita akan pergi melalui untuk loop sekali lagi.
Dan bagaimana kita menemukan nomor terkecil?
Tom?
Kami memiliki jumlah terkecil saat ini, jadi bagaimana kita menemukan terkecil baru?
>> MAHASISWA: Kita bisa memeriksa apakah terkecil jumlah yang kita miliki lebih besar dari
nilai braket j.
>> JASON Hirshhorn: Jadi jika terkecil adalah lebih besar dari nilai braket j.
Jadi jika kami terkecil saat ini lebih besar dari -
Aku akan memindahkan dua baris kode di luar sana untuk kedua.
Karena sebelum kita melakukan swapping apapun, kami perlu pergi melalui seluruh daftar.
Jadi pseudocode ini harus benar-benar berada di luar itu batin untuk loop.
Jadi pergi melalui seluruh daftar.
Jika terkecil lebih besar dari nilai j lalu apa?
>> MAHASISWA: Kemudian terkecil sama dengan nilai j.
>> JASON Hirshhorn: Fantastic.
Satu pertanyaan singkat -
pertama kalinya kami pergi melalui lingkaran ini, i akan sama dengan 0, j yang terjadi
untuk sama 0 sekali kita masuk ke sini.
Jadi kita akan membandingkan nomor untuk dirinya sendiri.
Apakah itu efisien?
Tidak, itu tidak benar-benar efisien.
Jadi tidak j kami harus pergi dari 0 sampai n setiap kali?
Apakah kita selalu perlu memeriksa melalui seluruh daftar?
[Tak terdengar]?
>> MAHASISWA: Mulailah dengan saya sebagai gantinya.
>> JASON Hirshhorn: j dapat mulai dengan apa?
>> MAHASISWA: i.
>> JASON Hirshhorn: j bisa mulai dengan i.
Jadi sekarang kita membandingkan mulai dengan yang kita berada.
Tetapi bahkan kemudian, adalah bahwa sebagai seefisien mungkin?
>> MAHASISWA: i + 1.
>> JASON Hirshhorn: i + 1 tampaknya yang paling efisien, karena kita
sudah i.
Kami menyatakan bahwa sebagai terkecil di baris 15.
Kita akan mulai dengan berikutnya secara otomatis.
Jadi kita pergi melalui untuk loop.
Kita akan pergi melalui setiap kali.
Kita akan pergi melalui beberapa kali.
Sekarang kita sudah melalui ini batin untuk loop.
Kami memiliki nilai terkecil menghemat.
Kita perlu menempatkannya di awal daftar.
Jadi bagaimana cara menempatkannya di awal daftar?
Apa variabel yang merujuk ke awal daftar?
Kami berada di luar ini untuk loop, jadi apa mengacu pada
awal daftar?
>> MAHASISWA: Nilai i.
>> JASON Hirshhorn: Tepat.
Nilai i adalah awal -
atau maaf, bukan awal.
Itu membingungkan.
Ini adalah di mana kita berada di awal bagian unsorted daftar.
Jadi nilai i.
Dan apa yang sama?
>> MAHASISWA: Terkecil.
>> JASON Hirshhorn: Nilai i sama dengan apa?
>> MAHASISWA: Terkecil.
>> JASON Hirshhorn: Terkecil.
Tepat.
Jadi kita menempatkannya di awal dari daftar, dan sekarang kita perlu menempatkan
awal daftar di mana jumlah terkecil adalah.
Jadi bagaimana cara menulis di mana nomor terkecil adalah?
Nilai-nilai apa?
>> MAHASISWA: 0.
>> JASON Hirshhorn: The small nomor pada 0?
>> MAHASISWA: Ya.
>> JASON Hirshhorn: Bagaimana jika terkecil nomor itu pada akhir
daftar unsorted ini?
>> MAHASISWA: Maaf, apa pertanyaannya?
>> JASON Hirshhorn: Dimana jumlah terkecil?
Kami mengambil terkecil dan meletakkannya di dimulai, dengan baris ini di sini.
>> MAHASISWA: Seharusnya telah disimpan di beberapa -
>> MAHASISWA: Nilai j.
>> JASON Hirshhorn: Yah, itu belum tentu nilai j.
Ia bahkan tidak ada pada saat ini.
>> STUDENT: Anda harus menyatakan variabel sebelumnya dan
kemudian menetapkan ke -
ketika Anda menemukan jumlah terkecil, menetapkan indeks dari jumlah tersebut untuk
beberapa variabel atau sesuatu seperti itu.
>> JASON Hirshhorn: Jadi bisa Anda mengatakan itu lagi?
>> MAHASISWA: Jadi di mana Anda menyatakan int terkecil, Anda juga harus mendeklarasikan int
Indeks terkecil = i, atau sesuatu seperti itu.
>> JASON Hirshhorn: Jadi di mana saya int terkecil, aku seharusnya tidak hanya melacak
dari nilai tapi lokasi.
int smallest_location = dalam hal ini kasus, kita akan lakukan i.
Kita perlu tahu di mana itu.
Kita harus akhir kode, dan kami menyadari bahwa kami tidak tahu di mana itu.
Dan lagi, kita pemetaan ini pada 00:59.
Kalian coding ini pada kemauan Anda sendiri mungkin sampai ke masalah yang sama.
Bagaimana sih saya menemukannya?
Dan kemudian Anda menyadari, tunggu, aku perlu melacak itu.
>> Jadi jika terkecil lebih besar dari nilai j.
Kami menetapkan terkecil sama dengan nilai j.
Apa lagi yang kita perlu berubah?
Constantin, apa lagi yang kita perlu mengubah?
>> SISWA: Lokasi.
>> JASON Hirshhorn: Tepat.
Jadi beri saya bahwa baris kode.
>> MAHASISWA: smallest_location = j.
>> JASON Hirshhorn: Tepat.
Dan kemudian turun di akhir, jika kita ingin menempatkan awal daftar di mana
jumlah terkecil adalah, bagaimana kita lihat di mana
nomor terkecil adalah?
Marcus?
>> SISWA: Jumlah terkecil adalah terletak di lokasi terkecil.
>> JASON Hirshhorn: Jadi pada nilai-nilai smallest_location.
Dan apa yang kita diletakkan di sana?
Awal daftar, apa itu?
>> SISWA: Yah, kita tidak benar-benar tahu lagi karena kita menimpa.
Jadi itu adalah lokasi bertukar dari dua baris?
Jika Anda beralih dua baris sekitar.
>> JASON Hirshhorn: OK, jadi kami tidak lagi, karena kami sudah me-reset baris
sebelum nilai i ke terkecil.
Jadi kita kehilangan bahwa nilai awal.
Jadi, Anda mengatakan pertukaran dua baris.
Jadi sekarang menempatkan awal daftar dimana jumlah terkecil adalah.
Jadi smallest_location sama dengan nilai i.
Itu bergerak awal ini Bagian unsorted daftar ke
lokasi terkecil.
Dan kemudian ke nilai i kita bergerak nomor terkecil.
>> Apakah itu masuk akal mengapa kita harus membuat swap?
Kami akan ditimpa nilai tersebut - hal lain yang mungkin akan memiliki
tahu dan ditemukan dalam PDB.
Jadi kita sudah diurus semua pseudocode.
Apakah ada hal lain yang kita perlu untuk menulis di sini?
Ada yang bisa memikirkan apa pun?
>> MAHASISWA: Bagaimana Anda tahu ketika Anda sudah selesai?
>> JASON Hirshhorn: Bagaimana kita tahu kapan kita sudah selesai?
Pertanyaan besar.
Jadi bagaimana kita tahu ketika kita sudah selesai.
>> MAHASISWA: Buat variabel untuk menjaga count dari jika ada swap dibuat atau tidak
dan pergi melalui lulus.
>> JASON Hirshhorn: OK.
Yang akan bekerja dalam bubble sort.
Tapi untuk selection sort, jika kita tidak membuat swap, yang mungkin saja
karena nilai terkecil adalah di dalamnya lokasi yang tepat.
Kita mungkin memiliki daftar 1, 2, 4, 3.
Kedua kalinya melalui kami tidak akan membuat swap.
Kami akan berada di nomor 2, tapi kita akan masih perlu untuk terus berjalan.
Jadi kita perlu melacak ketika kita sudah selesai, atau kita hanya ingin pergi
sampai ini selesai?
>> MAHASISWA: Kami hanya bisa pergi sampai selesai.
>> JASON Hirshhorn: Kita bisa hanya pergi sampai ini selesai.
Dalam bubble sort, kau benar, Jeff dan Aleha, dengan solusi Anda -
itu sangat bagus untuk melacak berapa banyak swap yang Anda buat, karena dalam gelembung
sort, jika anda sebenarnya tidak membuat swap, Anda sudah selesai dan Anda mungkin dapat memotong Anda
masalah turun sedikit.
Tapi untuk selection sort, Anda sudah benar-benar harus pergi sampai akhir
daftar setiap kali sekitar.
>> Jadi ini adalah bahwa.
Kami memiliki dua menit tersisa.
Mari kita membuat semua.
Mari saya hanya membuka Cari di sini dan membuat yakin aku bahkan menelepon -
Aku tidak menelepon bubble sort.
Mari kita mengubahnya ke selection sort.
membuat semua. / cari.
Mari kita cari 42.
Kali ini kita akan lulus Daftar disortir, karena harus memilah
pertama, per kode find - harus memilah pertama yang menggunakan fungsi semacam kami dan kemudian
mencari sesuatu.
Semoga semua orang.
>> Oh ya ampun.
Whoa, hati saya berdetak.
Jadi yang benar.
Bahkan, jika kita berlari ini lebih ekstensif, kode, sejauh yang saya bisa
mengatakan, adalah hal yang benar.
Ada beberapa saran Saya akan memiliki untuk Anda.
Sebagai contoh, 15 dan 16 tampak sedikit berlebihan.
Sepertinya Anda tidak perlu perlu untuk menghemat mereka.
Jika Anda memiliki lokasi terkecil, Anda dapat dengan mudah menemukan nilai terkecil
hanya mengetik nilai i.
>> Jadi jika saya harus dengan kadar kode Anda, yang akan saya sebenarnya menjadi, saya akan
mungkin melepas titik jika Anda termasuk baik dari ini, karena Anda
tidak perlu kedua.
Jika Anda memiliki lokasi, Anda dapat sangat mudah mendapatkan nilai.
Dan tampaknya sedikit aneh untuk menyimpan keduanya.
Mungkin bahkan tidak mengambil titik, tapi tentu berkomentar bahwa itu mungkin
bukan pilihan gaya Anda perlu membuat.
Tentu saja, kode masih berjalan dengan baik.
>> Jadi sayangnya kami tidak sampai ke bubble sort.
Saya minta maaf soal itu.
Kami melakukan finish selection sort.
Apakah Ada yang punya pertanyaan akhir tentang selection sort?
>> OK, sebelum kita kepala keluar, aku ingin kau untuk membuka browser Chrome Anda.
Maaf, itu hanya plug terang-terangan untuk satu jenis browser internet.
Anda dapat membuka semua jenis browser, tapi mungkin akan Chrome.
Dan pergi ke situs berikut ini -
sayat.me/cs50.
Jika Anda tidak mengetik di komputer Anda sekarang, kau jelas
tidak melakukannya, Tom.
>> Dan silakan lakukan itu baik kanan sekarang atau pada jam berikutnya -
memberi saya beberapa umpan balik.
Ini hanya bagian dua.
Kami memiliki lebih banyak bersama-sama, jadi saya memiliki banyak ruang untuk meningkatkan.
Saya mudah-mudahan juga melakukan beberapa hal dengan baik.
Sehingga Anda dapat membuat saya merasa semuanya buruk, tapi jika Anda juga ingin memberikan smiley
wajah, saya akan menghargai itu juga.
Isi yang masuk
>> Dan dengan satu menit tersisa, itu minggu ketiga.
Aku akan berdiri di luar untuk sedikit jika Anda memiliki pertanyaan.
Aku akan melihat kalian di kuliah besok.