Harvard CS50: Tugas Minggu 3 (Kuliah 7 lan 8), Bagian 2

Harvard Programming Fundamentals Lectures CS50 Materi tambahan: notasi asimtotik, ngurutake lan nggoleki algoritma Tugas Minggu 3, bagean 1. Ngurutake lan nggoleki.

Game diwiwiti!

Iku wektu kanggo muter! Akeh wong sing kenal karo game teka-teki "Tag". Kanggo nggawe resmi, "Tag" minangka lapangan 4x4 rong dimensi, ing lapangan iki ora ana 16, nanging 15 kothak, yaiku, siji slot tetep kosong. Saben kothak ana nomer lan bisa mindhah horisontal utawa vertikal ing lapangan (yen, mesthi, ana papan kanggo mindhah). Tujuane kanggo nyelehake nomer kanthi urut, saka 1 nganti 15 saka kiwa menyang tengen saka ndhuwur nganti ngisor. Banjur papan kosong bakal ana ing pojok tengen ngisor. Gerakan saka kothak sembarang (utawa sawetara) minangka "langkah" ing papan game iki. Kombinasi sing ditampilake ing gambar ing ndhuwur wis ditumpuk, nanging elinga yen 12 utawa 15 kothak bisa didorong menyang ruang kosong. Aturan kasebut nyatakake yen kothak ora bisa dipindhah kanthi diagonal utawa dibusak saka papan dolanan. Ana akeh konfigurasi kanggo miwiti game (sampeyan bisa ngetung persis pira), nanging kanggo kesederhanaan, ayo ngatur kothak saka paling gedhe nganti paling cilik lan ninggalake papan kosong ing pojok tengen ngisor papan. . Siji-sijine, ayo ngganti 1 lan 2 supaya teka-teki kasebut bisa dipecahake. Saiki pindhah menyang direktori ~/ workbench , banjur /pset3/fifteen lan mbukak fifteen.c . Isine kode kanggo mesin game. Tugas kanggo nambah kode kanggo game. Nanging pisanan, ayo ngumpulake "mesin" kita (sampeyan mbokmenawa wis ngerti carane nindakake iki). Sanajan kasunyatane game kasebut durung rampung, sampeyan bisa miwiti aplikasi kasebut. Bakal luwih trep kanggo mbukak ing jendela terminal sing luwih gedhe tinimbang biasane, sing bisa dibukak kanthi ngeklik plus ijo (+) ing jejere salah sawijining tab kode lan pilih Terminal Anyar . Utawa sampeyan bisa mbukak jendhela terminal ing layar wutuh kanthi ngeklik lambang Nggedhekake ing pojok tengen ndhuwur console. Sampeyan ndeleng sing sawetara iku bisa piye wae. Nanging nyatane, umume game kasebut durung ditulis. Lan ing kene - siyap - sampeyan metu!

sinau

Sinau kode lan komentar saka fifteen.c banjur wangsulana pitakonan ing ngisor iki:

1. Kajaba saka papan 4x4, ukuran lapangan apa sing diidini mesin kita?
2. Apa struktur data lapangan game?
3. Fungsi apa sing diarani salam marang pemain ing wiwitan game?
4. Apa fitur sing kudu dileksanakake?
5. Cathetan: Yen sampeyan pengin mriksa otomatis kanggo ngandhani yen sampeyan mangsuli pitakon kanthi bener, ing jejere file fifteen.c, goleki file fifteen.txt lan tulisake jawaban kanggo pitakonan kasebut ing njero.

Implementasine

Inggih, ayo miwiti ngleksanakake game kasebut. Elinga, kita obah ing langkah-langkah cilik, aja nyoba nindakake kabeh bebarengan. Nanging, ayo ngetrapake fitur siji-sijine lan priksa manawa bisa digunakake sadurunge maju. Ing tartamtu, disaranake sampeyan ngleksanakake fungsi game ing urutan ing ngisor iki: init (initialization), tarik (gambar), mindhah (njupuk langkah), menang (menang). Keputusan desain (kayata pira papan sing kudu dilebokake ing antarane kothak nomer kita) dadi sampeyan. Ing lapangan playing kudu katon kaya iki: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Sawise maneh, elinga yen ing posisi wiwitan, 1 lan 2 dumunung ing urutan mbalikke (iki ditrapake kanggo lapangan 4x4 klasik yen nomer kothak aneh). Yen jumlah kothak malah lan lapangan 3x3, ora perlu kanggo ngganti loro kothak "paling". 8 7 6 5 4 3 2 1 _ Kanggo nguji implementasine "Tag", sampeyan kudu nyoba muter (aja lali, sampeyan bisa metu saka program sadurunge rampung alami kanthi mencet kombinasi tombol crtl + c). Priksa manawa program bakal bisa digunakake yen salah ngetik nomer. Lan elinga yen sampeyan ngotomatisasi input menyang golek, sampeyan bisa ngotomatisasi "walkthrough" game kasebut. Nyatane, ing folder ~ cs50 / pset3 ana file 3x3.txt lan 4x4.txt , sing ngemot kabeh urutan langkah kanggo menang ing lapangan 3x3 lan 4x4. Kanggo nyoba program, contone, nggunakake file pisanan, jalanake printah ing ngisor iki: ./fifteen 3 < ~cs50/pset3/3x3.txt Nggawe argumen sing sampeyan butuhake kanggo nyepetake animasi. Lan ing umum, yen sampeyan pengin, sampeyan bisa tansah ngganti game. Kanggo seneng-seneng karo "urutan uwal ANSI" kalebu werna. Delengen implementasine sing jelas lan priksa http://isthe.com/chongo/tech/comp/ansi_escapes.html kanggo sinau trik anyar. Yen sampeyan pengin, tulis fungsi sampeyan dhewe utawa ganti prototipe fungsi sing ditulis. Siji-sijine watesan yaiku sampeyan ora ngganti logika fungsi utama, yen ora, kita ora bakal bisa ngetrapake sawetara tes otomatis kanggo mesthekake yen program sampeyan bisa digunakake kanthi bener. Utamane, utama kudu bali 0 yen lan mung yen pangguna ngrampungake teka-teki kasebut. Nilai non-nol kudu bali kanggo kabeh opsi kesalahan. Yen ana kesalahan, nulis menyang kita. Ya, yen sampeyan pengin muter implementasine aplikasi sing disiapake dening asisten CS50, jalanake printah ing ngisor iki: ~cs50/pset3/fifteen Yen sampeyan kepengin weruh implementasine sing luwih adhem, kanthi pemecahan teka-teki otomatis, priksa versi "Hacker" saka program: ~cs50/hacker3/fifteen Tinimbang ngetik nomer ing jendhela game, ketik tembung ALLAH. Apik, ta? Yen sampeyan pengin mriksa kabeneran program sampeyan kanthi resmi nganggo check50, elinga yen check50 nganggep yen ruang kosong ing playfield diisi 0; yen sampeyan milih nilai beda, ngganti karo nul kanggo verifikasi bener. Uga, check50 nganggep yen sampeyan ngindeks kolom papan ing urutan [baris] [kolom], dudu papan [kolom] [baris]. check50 2015.fall.pset3.fifteen fifteen.c

Sinau luwih lengkap babagan implementasine Limalas fungsi game

• init (inisialisasi)
• nggambar
• obah (langkah)
• menang (menang)

init

Ing fungsi iki kita introduce lapangan playing. Kanggo nindakake iki, kita nggunakake array rong dimensi saka integer. Ukuran array yaiku MAX x MAX, ing ngendi MAX minangka konstanta sing nuduhake jumlah maksimum kothak sing bisa pas ing baris utawa kolom ing lapangan. Mangkono, kita kudu nemtokake papan int variabel[MAX][MAX] Nanging, elinga ukuran lapangan playing ditemtokake dening pangguna. Mulane, kita kudu nemtokake variabel sing bakal nuduhake ukuran papan sing kudu dilebokake pangguna. Iki int d . ngendi d iku dimensi Papan, d <= MAX. Nanging, ing C sampeyan ora bisa ngganti ukuran Uploaded, supaya sampeyan kudu dumunung kanggo ukuran maksimum. Ing init sampeyan kudu nyelehake nilai ing papan. Waca liyane babagan array rong dimensi yen sampeyan durung nggarap. Cekakipun, padha duwe loro indeks, pisanan nuduhake nomer baris, kaloro nomer kolom. Kanggo masalah kita, kita miwiti karo nomer maksimum lan mungkasi ing cilik saka d = 3 ("Eights") karo siji lan sudhut kosong. Yen kita isih duwe "Tag", banjur kita ganti 1 lan 2. Apa sing kudu dilakoni karo ruang kosong? Array kita kasusun saka integer, supaya kekosongan kudu diisi karo sawetara integer. Mulane, sampeyan kudu milih sawetara integer kanggo initialize kothak kosong (utawa, ing cilik saka game fisik, anané kothak). Loops bisa digunakake kanggo initialize Papan game lan isi karo pesawat wiwitan kothak. Kita daur ulang indeks i lan j, ing ngendi papan [i] [j] minangka kothak sing ana ing nomer baris i lan nomer kolom j. Kita ngisi papan kanthi urutan mudhun. Yen jumlah kothak (tanpa sing kosong) ganjil, ganti 1 lan 2.

nggambar

Fungsi iki kudu nyithak kahanan playfield saiki. Elinga yen kita bisa duwe nilai karo siji utawa rong digit, supaya format ayu sawise nomer 1-9 fungsi kudu print spasi ( #s ). Iki bisa ditindakake nggunakake placeholder %2d . printf (“%2d”, board[i][j]); Uga aja lali babagan sel kosong. Pilih karakter sing bakal makili (ing conto kita, iki underscore). Fungsi tarik kudu nggambar karakter iki sanalika sampeyan mencet sel kosong. Dadi daur ulang kita bakal kaya iki: for каждой строки for каждого element строки print meaning и пробел print новую строку Elinga yen urutan fungsi tarik ndudohke kothak menyang layar kudu nggambarake urutan sing ana ing array sing ditetepake ing fungsi init .

ngalih

Sawise sampeyan miwiti lapangan dolanan lan nggambar posisi kothak dhisikan, sampeyan kudu ngidini pangguna ngowahi posisi kothak, yaiku, nggawe gerakan. Dadi ing Fifteen.c program njupuk output saka pangguna, mbangun Papan game lan banjur nelpon fungsi pamindhahan lan marang iku kothak kang arep kanggo mindhah. Ati-ati: sampeyan nggunakake fungsi khusus kanggo nomer ing kothak, lan ora kanggo posisi ing Papan (ing Uploaded). Dadi sampeyan kudu golek posisi nyata kothak. Kajaba iku, sampeyan mung kudu ngidini pangguna mindhah kothak yen bisa. Ing gambar ing ndhuwur, kita mung bisa mindhah kothak nomer 2, 5 lan 8. Carane nemtokake iki? Miturut regane kothak kosong. Dadi fungsi pamindhahan kaya mangkene:

• Nampa nomer kothak sing pengin dipindhah pangguna
• Nggoleki posisi ing array (ing lapangan dolanan) kothak iki
• Elingi posisi kothak kosong
• Yen kothak kosong ana ing jejere sing pengin dipindhah pangguna, banjur diganti ing array.

menang

Fungsi iki mriksa yen game wis rampung sawise saben langkah pangguna. Ngasilake bener yen kothak ana ing urutan sing bener (kalebu posisi kothak kosong ing pojok tengen ngisor). Ing kasus iki, program bisa mungkasi. Yen kothak isih kasebar, fungsi bali palsu lan liwat reins kanggo fungsi pamindhahan . Carane ngatur pengawasan? Kaya ing kasus initializing lan drawing Papan - nggunakake loro nested kanggo puteran. Contone, sampeyan bisa nyetel kondisi sing saben nomer sakteruse ing Uploaded kudu luwih saka sadurunge. Wigati apa nilai sing ditulis ing kothak kosong. Utawa cara liyane - nggunakake counter kanggo mesthekake yen kabeh kothak ing Panggonan, yen sampeyan bisa nangani lan nulis rumus kanggo njaluk iku. Muga-muga sampeyan sukses ing eksperimen sampeyan!

Carane validasi kode lan entuk tandha

manungsa waé! Yen penting kanggo mriksa mung kabeneran tugas, banjur gunakake cs50check. Yen sampeyan pengin entuk biji ing platform edx, tindakake prosedur sing diterangake ing ngisor iki. Elinga, prosedur iki nggunakake cs50check sing padha kanggo mriksa tugas. Bentenipun mung iku ngelingi asil lan ngetung skor sakabèhé.

1. Mlebet CS50 IDE
2. Near pojok kiwa ndhuwur CS50 IDE , ngendi file browser dumunung (ora ing jendhela terminal), klik-tengen ing direktori pset3 banjur klik Download . Sampeyan kudu ndeleng manawa browser wis ndownload arsip pset3.tar.gz .
3. Ing jendhela kapisah utawa tab, mlebu menyang CS50 Kirim
4. Klik ing lambang Kirim ing sudhut kiwa ndhuwur layar
5. Ing dhaptar folder ing sisih kiwa, klik direktori Masalah Set 3 , banjur klik tombol Upload Kiriman Anyar. Ana ing sisih tengen.
6. Ing layar sing katon, klik tombol Tambah file .... Jendhela kanggo milih file saka komputer bakal mbukak.
7. Navigasi menyang folder ing ngendi sampeyan nyimpen pset3.tar.gz. Paling kamungkinan dumunung ing folder Downloads utawa ing ngendi wae browser nempatno file minangka standar. Nalika sampeyan nemokake pset3.tar.gz , klik sapisan kanggo milih, banjur klik Bukak .
8. Klik Start upload . File sampeyan bakal diunggah menyang server CS50 .
9. Ing layar sing katon, sampeyan kudu ndeleng jendhela Ora Ana File sing Dipilih . Yen sampeyan mindhah kursor mouse ngiwa, sampeyan bakal weruh dhaptar file sing diundhuh. Kanggo konfirmasi, klik saben wong. Yen sampeyan ora yakin babagan apa wae, sampeyan bisa ngunggah maneh file kanthi mbaleni langkah sing padha. Sampeyan bisa nindakake iki kaping pirang-pirang nganti pungkasan taun 2016.