Shmily

Everything Is Going To Be Alright

Metodologi Pemecahan Masalah

Leave a comment


Dalam Bab ini

Dalam bab ini kita akan membahas salah satu praktek yang disarankan untuk secara efisien memecahkan masalah pemrograman komputer dan membuat demonstrasi dengan contoh-contoh yang sesuai. Kita akan membahas prinsip-prinsip teknik dasar pemecahan masalah, mengapa kita harus mengikuti mereka ketika memecahkan masalah pemrograman komputer (prinsip yang sama juga dapat diterapkan untuk menemukan solusi dari banyak masalah matematika dan ilmiah serta) dan kami akan membuat contoh dari mereka gunakan. Kami akan menjelaskan langkah-langkah, di mana kita harus pergi dalam rangka untuk memecahkan beberapa masalah sampel dan menunjukkan kesalahan yang dapat terjadi ketika kita tidak mengikuti langkah-langkah yang sama. Kami akan memperhatikan beberapa langkah penting dari metodologi pemecahan masalah, bahwa kita biasanya melewatkan, misalnya pengujian. Kami berharap untuk dapat membuktikan bahwa Anda, dengan contoh-contoh yang tepat, bahwa pemecahan masalah pemrograman komputer memiliki “resep” dan itu sangat berguna.


Isi

1. Dalam Bab ini
2. Video
3. Persentasi
4. Pemetaan Pikiran
5. Prinsip Dasar Memecahkan Masalah Pemrograman Komputer
6. Gunakan Pen dan Kertas
7. Menghasilkan Ide dan Membiarkan Mereka dicoba!
8. Menguraikan Tugas ke sub-tugas kecil
9. Verifikasi Gagasan Anda!
10. Jika Masalah Terjadi, Menciptakan Ide Baru!

2. Ini Video nya silahkan simak


3. Ini slide persentasi nya silahkan simak

4. Pemetaan Pikiran

Gambar 1

1

Gambar 2

2

Gambar 3

4

Gambar 4

3


5. Prinsip Dasar Memecahkan Masalah Pemrograman Komputer

Anda mungkin berpikir bab ini adalah tentang omong kosong seperti “pertama kali berpikir, kemudian bertindak” atau “hati-hati ketika Anda menulis dan mencoba untuk tidak kehilangan sesuatu”. Bahkan bab ini tidak akan begitu membosankan dan akan memberikan beberapa panduan praktis untuk memecahkan masalah algoritmik serta masalah lainnya.

Tanpa membuat klaim kelengkapan, kami akan memberikan beberapa saran penting, berdasarkan pengalaman pribadi Svetlin Nakov yang diperoleh selama karyanya lebih dari 10 tahun sebagai pesaing dalam kompetisi pemrograman internasional dan Bulgaria. Svetlin telah memperoleh puluhan penghargaan internasional dari kontes pemrograman termasuk medali dari Olimpiade Internasional bidang Informatika (IOI) dan telah melatih mahasiswa dari Sofia University St Kliment Ohridski (SU), New Bulgarian University (NBU), Technical University of Sofia ( TU – Sofia ), National Academy untuk Pengembangan Software (NASD), dan Telerik Software Academy, dan pengalamannya selama 10 tahun terakhir menegaskan bahwa metodologi ini bekerja dengan baik dalam praktek.

Mari kita mulai dengan saran kunci pertama.


6. Gunakan Pen dan Kertas

Penggunaan pena dan selembar kertas dan pembuatan draft dan sketsa ketika memecahkan masalah adalah sesuatu yang normal dan alami, yang setiap ahli matematika, ahli fisika dan software engineer yang berpengalaman tidak ketika bertugas dengan masalah non-sepele.
Sayangnya, pengalaman kami dengan siswa menunjukkan kepada kita sebagian besar programmer pemula bahkan tidak membawa dengan mereka pena dan kertas. Mereka memiliki persepsi yang salah bahwa untuk memecahkan masalah pemrograman mereka hanya perlu keyboard. Sebagian besar dari mereka membutuhkan beberapa waktu dan kegagalan ujian ‘untuk akhirnya menyadari bahwa pembuatan beberapa jenis konsep di atas kertas sangat penting untuk memahami masalah dan membangun solusi yang tepat.

CATATAN: Setiap orang yang tidak menggunakan pena dan kertas akan berada dalam masalah serius ketika memecahkan masalah pemrograman komputer. Hal ini penting untuk selalu membuat konsep ide-ide Anda di atas kertas atau papan tulis bahkan sebelum mulai mengetik pada keyboard.

Mungkin, itu sedikit kuno, tetapi”di Era-nya kertas” ini belum berakhir ! Cara termudah bagi Anda untuk memvisualisasikan ide Anda untuk meletakkannya di atas kertas. Hal ini sangat sulit bagi kebanyakan orang untuk mencoba dan berpikir tentang masalah tanpa beberapa jenis visualisasi. Sistem visual dalam otak manusia, yang menyerap informasi, berhubungan erat dengan bagian-bagian otak, yang bertanggung jawab atas potensi dan logis berpikir kreatif.

Orang-orang yang telah berkembang dengan baik sistem visual mereka di otak dapat dengan mudah “melihat” solusi dari masalah dalam pikiran mereka. Kemudian mereka hanya perlu memoles ide mereka dan menerapkannya. Orang-orang ini secara aktif menggunakan memori visual mereka dan kemampuan mereka untuk menciptakan citra visual, yang merupakan alasan mengapa mereka dapat dengan cepat menciptakan ide-ide dan merenungkan algoritma untuk memecahkan masalah. Orang-orang ini dapat dengan cepat mengenali dan membuang ide-ide yang salah dan memvisualisasikan algoritma yang benar untuk masalah pemrograman dalam hitungan detik. Terlepas dari apakah Anda adalah tipe “visual” dari seseorang atau tidak, menuliskan dan membuat sketsa ide Anda sangat berguna dan pasti akan membantu pikiran Anda tentang masalah tersebut. Kebanyakan orang memiliki kemampuan untuk informasi dengan mudah hadir untuk otak visual.

Pikirkan misalnya, betapa sulitnya bagi Anda untuk mengalikan lima digit angka di kepala Anda dan bagaimana usaha yang lebih sedikit biayanya ketika Anda menggunakan pena dan kertas (kita menghilangkan kemungkinan menggunakan perangkat penghitung elektronik, tentu saja). Hal ini pada dasarnya sama dengan pemecahan masalah, ketika Anda membutuhkan pandangan yang jelas pada masalah Anda harus menggunakan pena dan kertas. Bila Anda perlu untuk memeriksa kelemahan dalam algoritma Anda, Anda harus membuat beberapa perhitungan menggunakan pena dan kertas. Bila Anda harus berpikir tentang suatu kasus dimana algoritma Anda mungkin tidak bekerja, Anda harus menggunakan pena dan kertas. Itulah mengapa Anda harus selalu menggunakan pena dan kertas !


7. Menghasilkan Ide dan Membiarkan Mereka Mencoba !

Seperti yang telah kami sebutkan sebelumnya, hal pertama yang harus dilakukan adalah membuat sketsa beberapa contoh sampel untuk masalah pada selembar kertas. Ketika kita memiliki contoh nyata dari masalah di depan kita, kita bisa bercermin di atasnya dan ide-ide datang.
Ketika ide adalah fakta, kita perlu lebih banyak contoh untuk memeriksa apakah itu adalah satu yang baik. Kemudian kita perlu beberapa contoh, disusun di atas kertas untuk memverifikasi lagi. Kita harus benar-benar yakin solusi kami adalah benar. Kemudian kita harus melalui solusi kami sekali lagi, langkah demi langkah, dengan cara yang sama seperti satu program komputer yang sebenarnya akan melakukan, dan melihat apakah semuanya berjalan dengan benar.
Hal berikutnya yang harus dilakukan adalah mencoba “melanggar” solusi kami dan memikirkan kasus, di mana ide kami tidak akan bekerja dengan baik (Contoh-Counter). Jika kita gagal pada saat itu, maka ide kami mungkin benar. Jika solusi kami pasti memiliki cacat, kita harus memikirkan cara untuk memperbaikinya. Jika ide kita tidak lulus setiap tes, kita harus menciptakan yang baru. Tidak selalu ide pertama yang datang ke pikiran Anda adalah yang benar dan merupakan solusi yang benar dari masalah.

Pemecahan masalah adalah proses berulang-ulang, yang merupakan penemuan ide dan kemudian menguji mereka atas contoh yang berbeda sampai Anda mencapai satu, yang tampaknya bekerja dengan benar dengan setiap contoh yang Anda bisa memikirkan.Kadang-kadang dapat mengambil jam bagi Anda untuk mencoba dan menemukan solusi yang tepat dari masalah yang diberikan. Ini benar-benar normal. Tidak ada yang memiliki kemampuan untuk segera menemukan solusi yang tepat dari masalah, tapi pasti lebih pengalaman yang Anda miliki semakin cepat ide-ide yang baik akan datang. Jika masalah tertentu memiliki sesuatu yang sama dengan satu yang telah dipecahkan di masa lalu, maka ide yang tepat akan datang ke pikiran Anda lebih cepat, karena salah satu karakteristik dasar dari otak manusia adalah bekerja dengan analogi. Pengalaman Anda dapatkan dari pemecahan masalah jenis tertentu akan membantu Anda dengan penemuan ide-ide untuk solusi dari masalah analogis lainnya.

Dalam rangka untuk menghasilkan ide-ide dan menguji mereka itu adalah wajib untuk memiliki selembar kertas, pena dan contoh-contoh yang berbeda, yang Anda butuhkan untuk memvisualisasikan dengan bantuan konsep, sketsa atau cara lain. Yang dapat membantu Anda banyak untuk mencoba ide-ide yang berbeda dengan cepat dan merefleksikan solusi, yang dapat terjadi kepada Anda. Hal-hal dasar yang perlu Anda lakukan ketika Anda memecahkan masalah adalah dengan logis memikirkan beberapa masalah yang analogis dengan yang sekarang, meringkas atau mencoba untuk menggunakan ide-ide umum dan kemudian membangun solusi Anda menggunakan pena dan kertas. Bila Anda memiliki sketsa di depan Anda lebih mudah untuk membayangkan apa yang mungkin bisa salah. Hal ini dapat memberi Anda ide untuk langkah berikutnya atau membuat Anda menyerah ide Anda saat ini sepenuhnya. Dengan cara ini kita bisa mendapatkan algoritma yang lengkap, kebenaran yang dapat diuji oleh sebuah contoh

CATATAN:The pemecahan masalah dimulai dengan penemuan ide dan menguji mereka. Hal ini paling baik dilakukan dengan pena dan kertas di tangan dan sampel sketsa dan konsep untuk membantu Anda pikirkan. Selalu menguji ide-ide Anda dan solusi dengan contoh-contoh yang tepat!</strong

Rekomendasi yang diberikan di atas juga sangat berguna dalam satu kasus lagi – ketika Anda berada di wawancara kerja. Setiap pewawancara yang berpengalaman bisa setuju, bahwa ketika ia memberikan masalah algoritma untuk diwawancarai ia mengharapkan dari dia untuk mengambil pena dan secarik kertas, untuk merefleksikan masalah dengan suara keras dan memberikan saran yang berbeda untuk solusi. Ini adalah tanda orang ini dapat berpikir dan memiliki pendekatan yang tepat untuk pemecahan masalah. Berpikir keras dan menolak ide-ide yang berbeda menunjukkan bahwa orang yang diwawancarai memiliki pemikiran yang tepat. Bahkan jika ia gagal untuk memecahkan masalah, perilaku ini akan membuat kesan yang baik kepada pewawancara!

8. Menguraikan Tugas ke sub-tugas kecil

Tugas-tugas kompleks selalu dapat dibagi menjadi lebih kecil subtasks lebih mudah dikelola. Kami akan menunjukkan ini dengan beberapa contoh di bawah ini. Tidak ada masalah yang kompleks tunggal di dunia ini yang telah diselesaikan dengan satu mencoba. Yang benar rumus untuk memecahkan tugas seperti itu adalah untuk membaginya menjadi tugas sederhana yang lebih kecil, yang harus independen dan berbeda satu sama lain. Jika ini subtugas yang lebih kecil terbukti menjadi rumit, kita harus memisahkan mereka lagi. Teknik ini disebut “membagi dan menaklukkan” dan itu digunakan sejak zaman Kekaisaran Romawi.
Pembagian masalah menjadi unit yang lebih kecil lebih mudah diucapkan daripada dilakukan. Inti dari pemecahan masalah algoritmik adalah teknik yang baik dari pembagian tugas yang diberikan ke submasalah sederhana dan, tentu saja, penemuan ide-ide yang baik yang dapat dicapai dengan memperoleh lebih banyak pengalaman.

CATATAN:Tugas-tugas kompleks selalu dapat dibagi menjadi lebih kecil subtasks lebih mudah dikelola. Bila Anda harus menyelesaikan tugas-tugas rumit yang besar, Anda harus selalu mencoba untuk membaginya menjadi masalah sederhana, yang mudah untuk dipecahkan.

Contoh Soal “Kartu Shuffle”

Mari kita berikan contoh berikut: kita memiliki satu dek memerintahkan kartu dan kita harus shuffle itu dalam urutan acak. Mari kita berasumsi bahwa dek direpresentasikan sebagai array atau daftar N objek (setiap kartu adalah obyek). Jenis tugas memerlukan beberapa langkah yang berulang (seri removal, menempatkan, mengganti dan penataan kembali unsur-unsur ). Setiap tahap itu sendiri adalah sederhana, lebih mudah dan lebih subtask dikelola, daripada “Kartu Shuffle” tugas secara keseluruhan. Jika kita berhasil dalam mendekomposisi tugas kompleks menjadi sub-tugas yang lebih kecil, kita pada dasarnya akan menemukan cara yang tepat untuk memecahkan masalah. Tepat ini adalah inti dari pemikiran algoritmik: kemampuan untuk menguraikan masalah yang kompleks menjadi lebih kecil dan kemudian menemukan solusi yang tepat bagi mereka. Tentu saja, prinsip ini dapat diterapkan tidak hanya untuk masalah pemrograman, tetapi juga untuk orang-orang dari disiplin ilmu lain seperti matematika dan fisika. Bahkan pemikiran algoritmik ini adalah alasan mengapa matematikawan dan fisikawan menunjukkan kemajuan pesat ketika mereka mulai belajar pemrograman komputer.

Sekarang mari kita kembali ke tugas yang diberikan dan berpikir tentang bagaimana menemukan subtasks sederhana, yang dibutuhkan dalam rangka memenuhi persyaratan untuk acak mengocok kartu.Jika kita mengambil satu dek kartu di tangan kita atau mencoba untuk membuat sketsa sesuatu di atas kertas (misalnya serangkaian sel persegi panjang, masing-masing mewakili satu kartu ), beberapa ide langsung muncul, misalnya kita perlu mengubah atau menyetel kembali elemen-elemen dari dek masing-masing.
Berpikir seperti ini, kita dapat dengan mudah mencapai kesimpulan kita perlu membuat lebih dari satu swap satu atau lebih kartu. Jika kita hanya membuat satu swap, dek kartu tidak akan benar-benar acak. Oleh karena itu kita perlu banyak operasi sederhana untuk swap tunggal ( pertukaran ).Kami mencapai titik di mana kita melakukan dekomposisi pertama ke sub-tugas yang lebih kecil: kita membutuhkan serangkaian swap, yang dapat dianggap sebagai tugas yang lebih kecil, bagian dari masalah yang lebih besar.

Subtask Pertama: Swap Tunggal

Bagaimana kita membuat swap tunggal kartu di dek? Kita bisa menjawab pertanyaan ini dalam banyak cara dan mengambil ide pertama yang datang ke pikiran kita. Jika ada gunanya, kita akan menggunakannya. Jika tidak kami akan memikirkan sesuatu yang lain.
Ide pertama kami dapat: jika kita memiliki setumpuk kartu, kita dapat membaginya di kartu acak dan kemudian memisahkan dan swap dua bagian. Sekarang kita memiliki ide untuk swap tunggal? Ya, kami memiliki. Hal berikutnya yang harus dilakukan adalah untuk memeriksa apakah solusi kami bekerja dengan benar (kami akan menunjukkan hal ini setelah beberapa saat).

Sekarang mari kita kembali ke tugas dasar: setelah menerapkan ide kita, kita membutuhkan setumpuk kartu secara acak mengocok. Sekarang kita membagi dan swap berkali-kali dan periksa hasilnya. Tampaknya bahwa algoritma kami bekerja dengan baik dan subtask “Swap tunggal” akan melakukan pekerjaan.

Subtask Kedua: Memilih Nomor Acak

Bagaimana menghasilkan nomor acak dan menggunakannya untuk membagi dek? Jika kita memiliki kartu N, kita perlu nomor acak antara 1 dan N – 1, kita tidak?
Untuk mengatasi masalah ini kita mungkin perlu bantuan tambahan. Jika kita tahu bahwa dalam. NET Framework tugas ini sudah diselesaikan, kita hanya dapat menggunakan terintegrasi nomor acak generator.Kalau tidak, kita harus memikirkan solusi mis kita dapat membaca satu baris dari keyboard dan kemudian mengukur rentang waktu antara awal program dan menekan tombol [ Enter]. Sejak saat setiap input yang berbeda (terutama , jika kita melaporkan dengan ketelitian sampai nanodetik ), kita memiliki cara untuk menghitung nomor acak. Satu-satunya masalah sekarang adalah menemukan cara untuk menempatkan nomor ini dalam interval [ 1 … N – 1 ] dan mungkin sebagian besar dari kita akan mengingat bahwa kita dapat menggunakan sisa pembagian sebesar ( N – 1 ).

Kita bisa melihat bahwa bahkan subtasks sederhana dapat dibagi menjadi tugas yang lebih kecil, yang kadang-kadang dapat sudah diselesaikan bagi kita. Ketika kita menemukan solusi yang cocok untuk subtask saat ini, kita perlu kembali ke masalah dasar dan menguji segala sesuatu dan melihat apakah itu bekerja dengan benar disatukan. Mari kita melakukan itu sekarang, akan kita?

Subtask Ketiga: Menggabungkan Swap

Mari kita kembali ke tugas utama. Kami telah mencapai kesimpulan kita harus membuat banyak “tunggal swap” operasi yang diperlukan untuk menjamin setumpuk kartu akan dikocok dengan benar. Ide ini tampaknya benar dan kami harus mencobanya.Sekarang ini menimbulkan pertanyaan berapa banyak operasi “Swap single” cukup? 100 cukup? Bukankah mereka terlalu banyak? Dan bagaimana dengan 5 kali? Dalam rangka memberikan jawaban yang baik untuk pertanyaan ini, kita perlu berpikir untuk sementara waktu. Berapa banyak kartu yang kita miliki? Jika kita memiliki beberapa kartu di dek, kita perlu swap sedikit. Dan jika kita memiliki banyak kartu, kita perlu lebih banyak swap, kan? Oleh karena itu jumlah swap tergantung pada jumlah kartu di dek.

Untuk melihat berapa banyak swap yang cukup, kita bisa mengambil satu deck standar kartu. Berapa banyak kartu yang ada dalam satu deck standar? Sebagian besar dari kita tahu ada 52 kartu di dalamnya. Nah kemudian mencoba untuk mencari tahu berapa banyak “Swap Pertama” operasi yang diperlukan untuk secara acak mengocok satu dek 52 kartu. Apakah 52 cukup? Sepertinya cukup karena jika kita menukar 52 kali pada posisi acak ada kemungkinan bahwa kami akan membagi dek di setiap kartu ( kesimpulan ini jelas bahkan jika kita tidak tahu apa-apa tentang Probabilitas dan Statistik ). 52 “Swap pertama” operasi tampaknya terlalu banyak, bukan? Mari kita berpikir tentang jumlah yang lebih kecil. Bagaimana dengan separuh dari jumlah 52? Tampaknya baik juga, tetapi akan lebih sulit untuk menjelaskan mengapa.

Beberapa dari Anda mungkin berpikir bahwa cara terbaik untuk menemukan nomor yang benar adalah dengan menggunakan rumus yang kompleks dari teori probabilitas, tapi apakah itu masuk akal? Nomor 52 adalah cukup kecil dan tidak perlu untuk mencari nomor lain. Salah satu loop 52 iterasi cukup cepat. Kartu di dek tidak akan miliaran, akan mereka? Oleh karena itu kita tidak harus berpikir ke arah itu. Kami berasumsi bahwa jumlah yang benar “Swap single” sama dengan jumlah kartu di dek-tidak terlalu besar atau terlalu kecil. Dan ini adalah akhir dari subtask saat ini.

Contoh lain: Nomor Sorting

Mari kita pikirkan contoh lain. Kita diberi array angka dan tugas kita adalah untuk semacam itu dalam urutan menaik. Ada banyak algoritma untuk masalah ini dan beberapa dari mereka secara konseptual berbeda satu sama lain. Bahkan Anda bisa memikirkan beberapa ide untuk memecahkan masalah ini, beberapa dari mereka akan benar dan lain-lain-tidak cukup.

Jadi kita harus menyelesaikan tugas ini dan kami tidak diperbolehkan untuk menggunakan built-in. NET Framework metode pengurutan. Hal yang jelas pertama yang harus dilakukan adalah untuk mengambil pena dan selembar kertas dan memikirkan satu contoh dan kemudian untuk merefleksikan tugas. Dengan demikian kita bisa menciptakan beberapa dan sangat berbeda ide-ide seperti:

-Ide Pertama:

kita dapat menemukan nomor terkecil, mencetaknya dan kemudian menghapusnya dari array angka. Hal berikutnya yang harus dilakukan adalah untuk mengulang tindakan yang sama sampai array kosong. Berpikir seperti ini, kita dapat menguraikan tugas ini menjadi tugas-tugas sederhana: menemukan nomor terkecil dalam array; menghapus nomor dari berbagai; mencetak angka.

-Ide Selanjutnya:

kita dapat menemukan nomor terkecil dan meletakkannya pada posisi pertama dari array ( operasi swap ). Kemudian kita bisa melakukan tindakan yang sama untuk sisa array. Karena kita telah menempatkan angka pada posisi pertama, kita pergi ke yang berikutnya. Jika kita ulangi ini k kali, kita akan memiliki pertama k nomor terkecil dari array di posisi k pertama. Pendekatan ini membawa kita alami untuk suatu tugas, yang bisa sangat mudah dibagi menjadi sub-tugas yang lebih kecil: menemukan nomor dengan nilai terkecil di bagian dari array dan bertukar posisi dua angka dari array. Subtask kedua dapat dibagi sekali lagi: menghapus elemen dari posisi tertentu dan menempatkan elemen pada posisi tertentu.

-Ide lainnya:

yang menggunakan metode, konseptual berbeda dari dua solusi sebelumnya: kita membagi array menjadi dua subarrays dengan sekitar jumlah yang sama elemen. Kemudian kita mengurutkan mereka secara individu dan akhirnya kami menggabungkan mereka menjadi satu. Kita bisa melakukan tindakan ini secara rekursif dengan setiap subarray sampai setiap satu dari mereka memegang tepat satu elemen. Array dengan satu elemen adalah satu disortir. Di sini, seperti di dua ide sebelumnya, kita dapat membagi masalah yang kompleks menjadi lebih kecil masalah lebih mudah dikelola: membelah satu array menjadi dua bagian dengan jumlah kira-kira sama elemen; penggabungan dua array ke dalam satu array besar.

Tidak perlu untuk terus, kan? Hal ini jelas bahwa setiap satu dari Anda bisa memikirkan beberapa solusi yang berbeda atau Anda dapat membaca tentang subyek dalam sebuah buku tentang algoritma. Kami menunjukkan bahwa setiap masalah rumit dapat dibagi menjadi masalah yang lebih kecil sederhana. Ini adalah pendekatan yang tepat untuk memecahkan masalah pemrograman komputer-untuk memikirkan tugas besar seperti itu adalah kumpulan subtasks lebih mudah lebih kecil. Teknik ini mungkin sulit untuk belajar, tetapi dalam waktu Anda akan mendapatkan digunakan untuk itu.

9. Verifikasi Gagasan Anda

Tampaknya kita sudah tahu segalanya. Kami punya ide, Tampaknya untuk bekerja dengan baik. Satu-satunya hal yang kita lakukan adalah untuk memeriksa apakah ide kami adalah benar atau hanya benar dalam pikiran kita. Setelah itu kita bisa mulai dengan pelaksanaannya. Cara memverifikasi ide? Biasanya hal ini terjadi dengan bantuan beberapa contoh. Kita harus memilih contoh yang sepenuhnya menutupi semua kasus yang berbeda, yang algoritma kita harus bisa lulus.

Contoh-contoh sampel tidak boleh terlalu mudah bagi algoritma Anda, tetapi juga mereka tidak harus begitu sulit untuk membuat sketsa. Kami menyebutnya jenis tertentu contoh “perwakilan baik dari kasus umum”. Misalnya jika tugas kita adalah untuk mengurutkan array dalam urutan , maka contoh yang cocok akan menjadi sebuah array dengan elemen 5-6. Dua nomor dalam array harus sama dan yang lainnya-yang berbeda. Angka-angka harus secara acak ditempatkan dalam array. Ini adalah contoh yang baik, karena mencakup sebagian besar kasus yang umum , di mana algoritma kita harus bekerja.

Ada banyak contoh yang tidak pantas untuk masalah nomor pemilahan yang tidak bisa membantu Anda menguji ide Anda dengan benar. Sebagai contoh jika Anda menggunakan sebuah array dari hanya dua elemen. Solusi Anda bisa bekerja dengan benar dengan hal itu, tetapi ide inti Anda bisa benar-benar salah. Contoh lain yang tidak pantas adalah sebuah array dari jumlah yang sama. Setiap algoritma sorting akan bekerja dengan benar dengan itu. Dan contoh buruk lain-kita dapat menggunakan sebuah array yang sudah diurutkan. Algoritma juga bisa bekerja dengan benar dan belum tahu itu mungkin bisa salah.

CATATAN:Ketika memverifikasi ide-ide Anda, pilih contoh Anda dengan hati-hati. Mereka harus sederhana dan cukup mudah bagi Anda untuk dapat membuat sketsa mereka turun dengan tangan dalam satu menit dan pada saat yang sama mereka harus mewakili kasus yang paling umum di mana ide Anda harus bekerja. Contoh Anda harus perwakilan baik dari kasus umum dan mencakup sebanyak kasus mungkin tanpa menjadi terlalu besar dan rumit.

Masalah Pada “Kartu Shuffle”: Memeriksa Verifikasi Ide

Mari kita memikirkan satu contoh sampel untuk kami “Kartu Shuffle” tugas. Katakanlah kita memiliki 6 kartu. Dalam rangka contoh kita menjadi baik, dek kami kartu tidak boleh terlalu kecil (misalnya 2-3 kartu), karena dengan cara ini contoh kita mungkin menjadi sangat mudah. Juga, jika kita ingin dengan mudah memeriksa ide kami dengan dek, itu tidak boleh terlalu besar.

Awalnya itu adalah ide yang baik untuk mendapatkan enam kartu dan memesannya di dek. Dengan cara ini akan lebih mudah bagi kita untuk melihat apakah kartu dikocok atau sebagian dikocok atau tidak beringsut sama sekali. Jadi salah satu hal terbaik yang harus dilakukan adalah memilih 6 kartu tanpa jas mereka dan memerintahkan mereka dengan nilai. Sekarang kita sudah memiliki satu contoh, yang merupakan perwakilan baik dari kasus umum dari masalah kita. Mari kita sekarang sketsa itu di selembar kertas dan periksa algoritma kami di atasnya. Kita harus membagi dek menjadi dua bagian, pada posisi acak 6 kali dan kemudian swap mereka. Kartu kami yang diperintahkan oleh nilai. Pada akhirnya kita mengharapkan mereka untuk secara acak mengocok.

Mari kita lihat apa yang akan terjadi:
ok

Tidak perlu untuk melakukan 6 swap. Setelah hanya 3 swap kami kembali ke posisi awal. Ini mungkin bukan kecelakaan. Apa yang terjadi? Kami baru saja menemukan kesalahan dalam algoritma kami. Ketika kita merenungkan masalah kita dapat melihat bahwa dengan setiap pertukaran pada posisi acak kita memutar dek ke kiri dan setelah N kali ia pergi ke posisi awal. Jadi itu adalah hal yang baik bahwa kita diuji ide kami bahkan sebelum mulai menulis beberapa kode, bukan?

Menyorting Nomor: Memeriksa Ide
Ini adalah waktu untuk memeriksa ide pertama kami mempertimbangkan masalah nomor penyortiran. Kita dapat dengan mudah melihat apakah itu benar atau salah. Kita mulai dengan sebuah array dari elemen N dan kami menemukan nomor terkecil, mencetaknya dan kemudian menghapusnya dari array N kali. Bahkan jika kita tidak sketsa ide, tampaknya sempurna. Masih mari kita memikirkan satu contoh dan melihat apa yang akan terjadi. Kami mengambil 5 angka, dua di antaranya adalah sama: 3, 2, 6, 1, 2. Kami memiliki 5 langkah yang harus dilakukan:

1) 3, 2, 6, 1, 2 → 1
2) 3, 2, 6, 2 → 2
3) 3, 6, 2 → 2
4) 3, 6 → 3
5) 6 → 6

Sepertinya logika algoritma Anda bekerja. Hasilnya adalah benar dan kami tidak memiliki alasan untuk berpikir bahwa ide kami tidak akan bekerja dengan contoh lain ..

10. Jika Masalah Terjadi, Buatlah Ide Baru!

Bila Anda menemukan ide Anda belum begitu benar, hal yang jelas untuk di lakukan adalah untuk menciptakan sebuah gagasan/ide baru, ide yang lebih baik. Kita bisa melakukannya dengan dua cara: kita dapat mencoba untuk memperbaiki ide lama kami atau membuat yang benar-benar baru. Mari kita lihat bagaimana ini bekerja dengan masalah kartu mengocok kami, akan kita?…

CATATAN:Pembuatan solusi untuk masalah pemrograman komputer adalah proses berulang-ulang, yang terdiri dari menciptakan ide, memverifikasi mereka dan kadang-kadang, ketika masalah terjadi, menciptakan yang baru. Kadang-kadang ide pertama yang datang ke pikiran kita adalah yang benar, tetapi sebagian besar kali kita perlu pergi melalui banyak ide yang berbeda sampai kita mencapai yang terbaik.

Mari kita kembali ke masalah mengocok kartu. Pertama mari kita melihat mengapa ide utama kita adalah salah dan apakah mungkin untuk memperbaikinya? Masalahnya di sini adalah mudah dikenali: pemisahan terus-menerus dan kartu swapping, tidak mengocok mereka secara acak; itu hanya perputaran mereka ke kiri.Cara menyelesaikan algoritma ini? Kita perlu memikirkan cara baru dan lebih baik untuk membuat “tunggal swap” operasi, bukan? Ide baru kami untuk satu pertukaran tunggal: memilih acak dua kartu dari dek dan bertukar tempat mereka. Jika kita melakukan ini jumlah N dikalikan, kita mungkin akan mendapatkannya secara acak dan mengocoknya di dek. Ide ini terlihat lebih baik dari yang sebelumnya dan mungkin itu akan bekerja dengan benar saat ini.

Kita sudah tahu bahwa sebelum kita bahkan mulai berpikir untuk menerapkan algoritma baru lebih baik untuk memeriksa dan melihat apakah itu bekerja dengan benar. Kita dapat memverifikasi ide kami dengan menggunakan pena dan kertas dan contoh dengan 6 kartu yang kita gunakan di atas. Pada saat ini kita berpikir tentang ide yang lebih baik, bukannya memilih 2 kartu acak dari dek, mengapa tidak hanya memilih satu kartu acak dan swap dengan kartu pertama dari dek? Bukankah ide ini sederhana dan lebih mudah untuk menerapkan? Hasilnya harus acak juga. Mari kita mulai dengan memilih kartu acak pada posisi k1 dan swap dengan kartu pertama.

Sekarang kita memiliki kartu acak pada posisi pertama dan kartu pertama adalah pada posisi k1. Pada langkah berikutnya dari algoritma kita memilih kartu lain secara acak posisi k2 dan kemudian menukar dengan kartu dari posisi pertama (sebelumnya kartu dari posisi k1 ). Hal ini jelas bahwa dengan hanya 2 langkah kami telah mengubah tempat yang pertama, k1-st dan kartu k2-nd dari dek dengan kartu acak. Tampaknya bahwa pada setiap langkah satu kartu berubah posisinya dengan satu acak. Setelah jumlah N langkah kita dapat berharap bahwa setiap kartu dari dek telah berubah posisinya rata-rata satu kali. Oleh karena itu solusi kami bekerja dan kartu harus dikocok dengan baik.

Sekarang kita harus menguji ide baru kami. Apakah itu bekerja dengan baik? Mari kita pastikan bahwa apa yang terjadi terakhir kali tidak akan terjadi lagi, akan kita? Mari kita benar-benar memeriksa ide ini juga. Sekali lagi, kita bisa mengambil contoh 6 kartu, yang mewakili sebagian besar kasus umum dari masalah kartu acak (perwakilan baik dari kasus umum). Kemudian menggunakan algoritma baru dan mengocok mereka. Kita harus melakukan ini 6 kali berturut-turut. Ini adalah hasilnya:

ok1

Dari contoh di atas kita dapat melihat bahwa hasilnya adalah benar. kami telah secara acak mengocok enam kartu. Jika algoritma kami bekerja dengan baik dengan 6 kartu, harus bekerja dengan deck dengan nomor yang berbeda dari kartu juga. Jika kita tidak yakin dalam hal itu, kita harus memikirkan contoh lain yang lebih rumit dan kemudian menguji algoritma lagi.
Kalau tidak, kita bisa menghindari gambar contoh baru dan melanjutkan tugas kami.
Mari kita simpulkan apa yang telah kita lakukan sejauh ini dan bagaimana dengan tindakan berturut-turut kami telah menemukan solusi untuk masalah kita. Seperti yang telah kita pergi melalui setiap langkah, kita lakukan sejauh ini langkah-langkah berikut:

– Kami telah menggunakan selembar kertas dan pena untuk membuat sketsa setumpuk kartu . Kami telah secara visual mewakili setumpuk kartu sebagai array dari kotak.
– Seperti kita telah memiliki umpan balik visual, kita bisa dengan mudah memikirkan beberapa ide contoh:
pertama kita harus membuat semacam operasi swap tunggal dan kedua kita melakukan ini jumlah N kali.
– Kami telah memutuskan bahwa “swap tunggal” operasi kami akan membelah dek pada posisi acak ke bagian kiri dan kanan dan kemudian swap mereka.
– Kami telah memutuskan bahwa kami harus melakukan ini “Swap pertama” sebanyak dikalikan jumlah kartu di dek yang diberikan.
– Kami telah mempertimbangkan masalah memilih nomor acak, tapi akhirnya memutuskan untuk menggunakan solusi siap untuk pekerjaan itu.
– Kami telah membagi masalah utama menjadi tiga sub-tugas yang lebih kecil: “swap tunggal” operasi; memilih titik perpecahan acak; menggabungkan urutan “swap tunggal” operasi.
– Kami telah memeriksa ide kami untuk kesalahan dan menemukan satu. Itu adalah hal yang baik untuk memeriksa ketika kita lakukan, karena itu tidak terlalu terlambat untuk memperbaikinya.
– Kami telah memikirkan solusi, lebih dapat diandalkan baru dari operasi swap tunggal.
– Kami telah memeriksa ide baru kami dengan sebuah contoh yang tepat dan kami meyakinkan diri sendiri bahwa saat ini solusi yang tepat.
Sekarang kita akhirnya memiliki ide untuk bekerja, didukung dengan contoh yang baik. Ini adalah hal yang paling penting untuk dilakukan dalam rangka untuk memecahkan masalah tertentu-menciptakan algoritma. Semakin mudah bagian tetap-implementasi ide kami. Mari kita lihat bagaimana hal ini dapat dilakukan.

Advertisements

Author: shmily49

saya orang yang ingin tau banyak hal

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s