Strategi algoritmik dan pemrograman (sap)
B. Berpikir Komputasional
Berpikir komputasional ini merupakan suatu kerangka dan proses berpikir yang mencakup perangkat keras, perangkat lunak, dan menalar (reasoning) mengenai sistem dan persoalan. Moda berpikir (thinking mode) ini didukung dan dilengkapi dengan pengetahuan teoritis dan praktis, serta teknik untuk menganalisis, memodelkan dan menyelesaikan persoalan. Berikut ini pembahasan beberapa konsep dan strategi berpikir komputasional yang biasa digunakan dalam menyelesaikan persoalan komputasi.
1. Rekursi
Pada bagian ini kalian akan mempelajari tentang konsep rekursi dan beberapa contoh permasalahan yang dapat diselesaikan dengan menggunakan konsep tersebut, salah satunya adalah barisan Fibonacci.
Suatu masalah dapat didekomposisi menjadi permasalahan yang serupa, namun ukurannya lebih kecil. Saat kita diminta untuk memindahkan satu kardus buku yang sangat berat dan tidak dapat kita angkat, kita akan membagi kardus tersebut ke dalam beberapa kardus yang lebih ringan sehingga pekerjaan tersebut menjadi lebih mudah untuk dikerjakan. Ketika menghitung suatu nilai faktorial, kita pun harus menghitung nilai faktorial yang lebih kecil. Misalnya, ketika menghitung 10 faktorial, kita juga harus menyelesaikan 1 faktorial, 2 faktorial, hingga 9 faktorial terlebih dahulu.
Secara alami, terdapat banyak permasalahan yang dapat dimodelkan dengan lebih mudah menggunakan konsep rekursif ini. Pada bagian ini, kalian akan mempelajari konsep dasar rekursi yang akan sangat berguna untuk melakukan dekomposisi pada suatu permasalahan besar dalam bentuk permasalahan yang lebih kecil dan lebih mudah untuk diselesaikan. Rekursi didefinisikan sebagai "sesuatu" yang mengandung "sesuatu" itu sendiri. Dapatkah kalian melihat rekursi dalam gambar-gambar sebagai berikut (lihat Gambar 2.5)
fungsi atau barisan tersebut ditentukan/tergantung dari nilai fungsi/barisan itu sendiri secara rekursif, pada urutan nilai-nilai sebelumnya. Misalnya, kita memiliki sebuah barisan ai, j = 1, 2 ,...,n sebagai berikut:
\{a_{i}\} = 1, 3, 5, 7, m
Dimana nilai pertama dari barisan (a,) adalah 1, dan kemudian nilai-nilai berikutnya dalam barisan tersebut dihitung dengan cara menambahkan nilai 2 kepada nilai barisan sebelumnya. Kita dapat menuliskan dalam notasi rekursif sebagai berikut:
1. jika i = 1
Pada definisi sebuah barisan/fungsi rekursif, selalu ada minimal dua hal yang harus ditentukan, yaitu:
• Basis: menunjukkan dasar/nilai awal dari fungsi/barisan tersebut. Misalnya, pada contoh di atas, a_{1} = 1
• Rekursi: menunjukkan hubungan antara nilai dari fungsi/ barisan tersebut dengan nilai-nilai sebelumnya yang telah diketahui. Misalnya, pada contoh di atas: apa,+2, jika i > 1 .
Sebuah fungsi/barisan rekursif bisa jadi ditentukan dari tidak hanya satu buah nilai sebelumnya saja, tetapi dapat juga dari 2, 3,... dan seterusnya, nilai sebelumnya. Sebagai contoh sebuah barisan dapat didefinisikan sebagai berikut:
1. jika i i=1 atau i=2
Barisan ini dimulai dengan nilai 1, kemudian untuk menentukan nilai berikutnya, kita hitung dengan cara menjumlahkan dua nilai sebelumnya pada barisan tersebut, sehingga didapatkan barisan sebagai berikut:
{a. 1, 1, 2, 3, 5, 8, 13, 21, ...
Barisan di atas biasa disebut sebagai barisan Fibonacci, karena dipopulerkan oleh seorang matematikawan Italia bernama Fibonacci (nama lengkap Leonardo Bonacci, 1170 - 1250 М). Perlu diperhatikan bahwa karena pada bagian rekursi, kita memerlukan dua nilai terakhir, pada bagian basis, kita perlu mendefinisikan dua nilai pertama dari barisan tersebut. Secara umum, banyaknya nilai yang harus didefinisikan pada bagian basis ditentukan oleh banyaknya suku barisan yang diperlukan pada bagian definisi rekursi.
2. Algoritma Greedy
Greedy secara harfiah berarti rakus atau tamak. Meskipun dalam pengertian sehari-hari, kata "rakus" dan "tamak" memiliki konotasi negatif, namun dalam konteks Informatika, kita mengartikan greedy dalam konteks sebagai sebuah strategi penyelesaian masalah yang dapat berguna dalam merancang sebuah algoritma atau solusi bagi sebuah permasalahan komputasional. Oleh karena itu, diharapkan tidak ada konotasi negatif pada kata greedy dalam konteks ini.
Teknik greedy adalah salah satu teknik penyelesaian masalah yang biasa digunakan untuk menyelesaikan permasalahan optimasi. Permasalahan optimasi berarti kita ingin menghitung sebuah hasil yang terbaik dari sebuah proses tertentu. Terbaik disini dapat berarti nilai yang paling kecil ataupun paling besar, tergantung dari jenis permasalahannya. Dalam menyelesaikan permasalahan optimasi seperti ini, algoritma greedy akan menerapkan prinsip "mengambil serangkaian langkah terbaik pada setiap saat".
Contoh 1: Membawa Ikan 1
Budi ingin membawa beberapa ekor ikan yang sudah tersimpan dalam kantong-kantong plastik untuk diangkut di dalam mobilnya. Terdapat 8 buah kantong dengan yang berisi masing-masing 3, 5, 2, 8, 4, 6, 6, dan 3 ekor ikan. Namun sayangnya, mobilnya hanya mampu membawah 4 buah kantong. Kantong-kantong manakah yang harus dibawa oleh Budi agar jumlah ikan yang dibawanya sebanyak mungkin?
Jawab:
Untuk dapat membawa sebanyak mungkin ikan, Budi harus memilih kantong-kantong dengan sebanyak mungkin ikan. Oleh karena itu, algoritma greedy dapat diterapkan disini, dengan cara kita mengambil kantong mulai dari yang berisi ikan paling banyak terlebih dahulu, sampai didapatkan 4 buah kantong. Dengan demikian, kita harus mengurutkan kantong-kantong terlebih dahulu mulai dari yang paling banyak ikannya, sampai dengan yang paling sedikit, sehingga urutannya menjadi: 8, 6, 6, 5, 4, 3, 3, 2. Jika kita ambil 4 buah kantong pertama, maka total banyaknya ikan yang dapat dibawa adalah 8+6 +6 + 5 = 25 ekor ikan. Tentunya tidak ada pilihan 4 kantong yang akan menghasilkan total banyaknya ikan lebih dari 25 ekor.
Contoh 2: Membawa Ikan 2
Kali ini, Budi harus membawa sedikitnya 15 ekor ikan. Tentukan jumlah kantong terkecil yang harus dibawa oleh Budi, agar terdapat minimal 15 ekor ikan yang terbawa!
Jawab:
Sama seperti pada permasalahan sebelumnya, kita dapat menerapkan algoritma greedy untuk menyelesaikan permasalahan ini. Dalam hal ini, untuk memperkecil banyaknya kantong yang harus dibawa, maka kita juga selalu memilih kantong dengan jumlah ikan terbanyak terlebih dahulu. Jika kita memilih kantong dengan jumlah ikan 8 dan 6, maka kita sudah memiliki 14 ekor ikan. Selanjutnya, kita hanya perlu mengambil 1 kantong lagi (yang mana saja) agar total jumlah ikan menjadi lebih dari 15. Oleh karena itu, jawaban yang diinginkan adalah 3 buah kantong. Jelas bahwa tidak ada pilihan yang memungkinkan kita mendapatkan 15 ekor ikan dengan 2 atau kurang kantong.
Pada kedua contoh di atas, terdapat satu langkah yang penting yang biasa diterapkan pada penyelesaian masalah secara greedy, yaitu proses mengurutkan sebuah data agar menjadi terurut (mungkin dari kecil ke besar, atau sebaliknya), agar kemudian kita dapat melakukan serangkaian pengambilan langkah secara greedy pada data yang sudah terurut tersebut. Pola seperti ini umum digunakan pada penyelesaian permasalahan secara greedy.
3. Pemrograman Dinamis
Saat menyelesaikan sebuah (mencari nilai optimasi permasalahan terbesar/terkecil), terkadang kita harus memperhitungkan beberapa kemungkinan pengambilan langkah untuk menyelesaikan permasalahan tersebut. Kemungkinan-kemungkinan tersebut mungkin memiliki akibat/konsekuensi terhadap langkah-langkah selanjutnya, sehingga pendekatan seperti teknik greedy mungkin tidak akan menghasilkan jawaban yang optimal. Dalam hal ini, teknik pemrograman dinamis atau dynamic programming (DP) mungkin akan lebih sesuai diterapkan. Teknik DP mengandung dua unsur utama, yaitu:
1. Optimasi (mencari nilai terkecil/terbesar) melalui serangkaian pilihan. Serupa dengan teknik greedy, kita harus menentukan rangkaian langkah apa yang akan menghasilkan nilai optimal di akhir. Namun, berbeda dengan permasalahan yang dapat diselesaikan dengan teknik greedy, permasalahan yang sesuai untuk teknik DP memiliki struktur sedemikian rupa sehingga pilihan langkah terbaik saat ini belum tentu merupakan pilihan terbaik secara keseluruhan, sehingga prinsip greedy belum tentu dapat diterapkan, dan semua kemungkinan kombinasi pilihan langkah harus diperhitungkan.
2. Nilai optimal yang diinginkan untuk permasalahan tersebut biasanya dapat dinyatakan sebagai kombinasi optimal dari sub-sub permasalahan yang sama, tetapi dengan ukuran yang lebih kecil (atau dengan kata lain, dapat dinyatakan secara rekursif). Namun, sub-sub permasalahan yang harus dipertimbangkan, biasanya memiliki overlap (persinggungan) sehingga dalam proses perhitungannya, diperlukan cara yang efisien untuk menghitung solusi untuk sub-sub permasalahan yang diperlukan, agar tidak terjadi perulangan/duplikasi dalam proses perhitungan. Cara yang umum digunakan adalah dengan menyimpan semua solusi dari subproblem yang sudah diketahui dalam sebuah tempat penyimpanan/ tabel. Teknik ini biasa disebut sebagai teknik memorisasi.
Contoh 1:
Agria ingin memanen tanaman cabai di halaman rumahnya. Tanaman tersebut ditata dalam bentuk kotak-kotak persegi seperti ilustrasi di bawah ini. Angka pada setiap kotak mewakili jumlah cabai yang ada di masing-masing tanaman.
1
2
3
10
10
2
10
10
5
3
6
0
4
0
2
20
5
1
0
▲ Gambar 2.8 Ilustrasi jumlah Cabai yang dipanen Agria
Agria tidak punya waktu banyak karena ia harus segera pergi ke kampus. Oleh karena itu, ia tidak bisa memetik seluruh cabai tersebut. Ia hanya bisa mulai dari kotak manapun di kolom paling kiri, dan berhenti di kotak manapun di kolom paling kanan. Agria hanya bisa bergerak ke kotak di tepat setelah kanannya
atau bawahnya. Berikut adalah salah satu dari sekian banyak kemungkinan jalur yang dapat dilalui oleh Agria untuk memetik cabai.
Gambar 2.9 Kemungkinan Jalur Memetik Cabal Agria
Berapakah jumlah cabai terbanyak yang bisa dikumpulkan oleh Agria?
Jawab:
Pertama, perlu dipahami bahwa penggunaan teknik greedy pada permasalahan ini tidak akan menghasilkan jawaban yang benar/optimal. Dapat dilihat bahwa jika kita menggunakan prinsip greedy, maka kita akan memilih untuk memulai dari kolom pertama baris terakhir, dengan nilai jumlah cabai terbesar, yaitu 20. Namun, jika kita memulai dari sini, maka tidak ada pilihan lain untuk langkah-langkah selanjutnya, selain bergerak terus ke kanan. Maka nilai total cabai yang akan didapatkan adalah 20+5+1+0+0 26. Jelas bahwa ada pilihan-pilihan jalur lain yang akan menghasilkan total nilai cabai > 26, misalnya langkah sebagai berikut akan menghasilkan jumlah total cabai = 0+10+2+10+10+5=37
Menggunakan prinsip DP, yang perlu kita lakukan adalah pertama-tama menyatakan solusi/penyelesaian dari permasa. lahan awal sebagai kombinasi dari sub-permasalahan yang lebih kecil. Dalam hal ini, kita dapat membuat argumentasi bahwa nilai jumlah cabai terbanyak yang bisa kita kumpulkan sampai dengan suatu kotak tertentu (di manapun kolomnya) tergantung dari nilai terbaik jumlah cabai sampai dengan kotak di atasnya, atau kotak di sebelah kirinya (jika ada), dan tinggal kita jumlahkan saja dengan nilai banyaknya cabai di kotak akhir tersebut. Hal ini, tentunya karena kita hanya bisa bergerak ke kanan atau ke bawah saja. Misalnya, pada Gambar 2.12 ini:
A
B
C
Gambar 2.12 lustrasi Prinsip Pemrograman Dinamis pada Persoalan Panen Cabal Agria
Nilai terbaik yang bisa kita dapatkan akan berakhir pada kotak berwarna hitam, dapat dihitung dengan cara menghitung nilai terbaik yang didapatkan sampai dengan kotak merah (misalkan nilainya A), dan sampai dengan kotak warna biru (misalkan nilainya B). Maka, untuk mendapatkan nilai terbaik sampai dengan kotak warna hitam, kita hanya mencari, manakah jumlah yang tertinggi antara nilai A dan B, kemudian nilai tersebut dijumlahkan dengan nilai C.
Proses di atas mengubah permasalahan ini menjadi bersifat rekursif, dimana kita bisa menggunakan hasil perhitungan pada kotak-kotak sebelumnya untuk menghitung nilai terbaik pada kotak-kotak selanjutnya (yang berada di posisi
C. Algoritma dan Pemrograman
Pada jenjang sebelumnya dalam materi Informatika Kelas X, kalian telah mempelajari mengenai beberapa bahasa pemrograman, salah satunya adalah bahasa C yang telah dipelajari pada elemen Algoritma dan Pemrograman. Kemampuan bahasa pemrograman terutama bahasa C akan kalian gunakan dalam topik ini. Selanjutnya untuk lebih meningkatkan pemahaman kalian dalam elemen Algoritma dan Pemrograman, kalian akan mempelajari konsep larik serta karakter dan string. Kedua konsep ini sangat penting dalam membuat program dan akan kalian gunakan untuk menyelesaikan berbagai permasalahan yang diberikan pada bagian D dalam bab ini.
Larik (Array)
Saat ini mungkin kalian memiliki pertanyaan seperti "mengapa contoh dan permasalahan yang diberikan selama yang dapat diselesaikan oleh manusia ini adalah hal yar manual atau dengan kalkulator?" Jawabannya adalah karena permasalahan/problem tersebut diberikan untuk mendukung proses kalian menguasai kompetensi dalam algoritma dan pemrograman. secara
Pada praktiknya, program digunakan untuk mengolah data yang berukuran besar dan membutuhkan waktu yang sangat lama jika dikerjakan manual oleh manusia. Misalnya kalian perlu menghitung statistika deskriptif (seperti rata- rata, nilai minimal, nilai maksimal, standar deviasi, dan sebagainya) dari data seluruh penduduk Indonesia. Walaupun masalahnya sederhana, namun dikarenakan jumlah data yang diolah sangat banyak dan berukuran besar mengakibatkan waktu pengerjaan pun menjadi sangat lama bagi manusia untuk menyelesaikannya. Bahkan ada kemungkinan data berukuran besar tersebut tidak dapat diolah menggunakan aplikasi pengolah data (spreadsheet) yang tidak dirancang untuk mengolah data sebesar itu. Untuk solusinya kalian dapat menggunakan program khusus untuk mengolah data berukuran besar atau membuat program sendiri yang mampu menyimpan dan mengolah data berukuran besar.
Kita pun sampai pada pertanyaan besar: "bagaimana caranya membuat program yang mampu menyimpan dan mengolah data berukuran besar?". Sebelumnya kalian telah mengenal konsep variabel yang mampu menyimpan satu buah nilai dengan tipe data tertentu (variabel tunggal). Permasalahan akan muncul ketika program kita harus mengolah sebanyak satu juta data. apakah kita harus membuat satu juta variabel? Bukankah hal tersebut sangat sulit dipraktikkan dalam kode program yang kita tulis? Untuk mengatasi hal tersebut, bahasa pemrograman memiliki suatu alat untuk menyimpan himpunan data ke dalarn satu nama variabel yang diberikan indeks. Salah satunya disebut sebagai larik atau array.
Contoh di dunia nyata yang merepresentasikan larik adalah seperti loker yang diberikan nomor (Gambar 2.13). Ketika kalian menyimpan barang di loker tersebut, kalian akan mengingat nomor loker tersebut. Kalian juga dapat menyimpan barang di loker dengan nomor yang berbeda. Pada analogi tersebut, nomor pada loker adalah indeks yang kita gunakan untuk mengenali tempat kita menyimpan barang kita tadi.
21
22
23
24
25
26
Gambar 2.13 Loker sebagai Ilustrasi Larik dalam Pemrograman
Menggunakan larik pada program mirip dengan membuat variabel tunggal. Perbedaannya adalah kalian perlu memberikan informasi ukuran dari larik yang akan dibuat dan kalian perlu mengaksesnya dengan menggunakan indeks. Ada banyak cara untuk mengimplementasikan konsep larik ke dalam kode program, salah satunya menggunakan vector. Vector ini merupakan pustaka bahasa pemrograman C++ yang juga dapat digunakan pada bahasa C. Vector dapat dibuat untuk menampung himpunan data yang ukurannya dinamis bergantung pada jumlah (atau ukuran) data yang disimpan di dalamnya.
program di bawah ini mengilustrasikan mengakses nilai pada suatu vector. Berbeda dengan buku Kelas X program ini ditulis menggunakan bahasa pemrograman C.. Oleh karena itu, kalian perlu menyimpan kode program dengan ekstensi berkas .cpp dan mengkompilasinya dengan kompilator bahasa C++, misalnya GCC cara
1: /* Demonstrasi larik satu dimensi dengan vektor */
2:
3: #include <stdio.h>
4: #include <vector>
5: using namespace std;
6: void cetaklarik(int ukuran, vector<int> larik)
8:
9:
int i;
for(i=0; i < ukuran; i++)
10:
printf("%d\n", larik[i]);
11:}
12:
13:
int main(){
14:
15:
vector<int> bilangan;
int i;
16: for(i=0; i < 10; i++)
17:
bilangan.push_back(i);
18: cetaklarik(10, bilangan);
19:}
Kalian juga dapat membuat larik yang berukuran dua dimensi, yang memiliki ukuran berupa baris dan kolom (seperti pada matriks di matematika). Pada kasus seperti apa larik dua dimensi digunakan? Misalnya kalian ingin menghitung jarak antara dua kota yang dihubungkan dengan jalan dua arah. Kalian dapat menggunakan matriks dua dimensi untuk merepresentasikan jarak antara dua kota seperti pada Gambar 2.14 berikut. Selain angka, masukan dari program dapat berupa karakter atau rangkaian karakter seperti kata. Hal ini telah lazim kalian temui, misalnya ketika mengetikkan kata kunci untuk melakukan pencarian di mesin pencari atau ketika kalian memasukkan kata sandi saat login. Oleh karena itu, program dilengkapi dengan kemampuan untuk membaca, menyimpan, mengolah, dan mencetak rangkaian karakter tersebut. Rangkaian karakter tersebut dalam pemrograman disebut sebagai string.
Definisi string dalam pemrograman adalah rangkaian karakter. Karakter sendiri merupakan suatu data berupa huruf, angka, simbol, dan karakter lain yang mengikuti suatu standar tertentu seperti "American Standard Code for Information Interchange" (ASCII) atau Unicode. Karakter pada pemrograman pada umumnya diimplementasikan dalam program menggunakan tipe data char. Di sisi lain, ada beberapa cara yang lazim digunakan untuk mengimplementasikan string dalam pemrograman.
Pada bahasa C, string diimplementasikan sebagai larik karakter yang diakhiri oleh karakter '\0. Dengan kata lain, kalian dapat membuat dan memproses suatu string seperti halnya kalian mengolah larik. Bahasa pemrograman lain seperti C++ atau Java memilih sebuah tipe data string sendiri yang menyembunyikan beberapa detail terkait pengelolaan data string yang dilakukan oleh program.
Karena proses pada string berbeda dengan proses pada bilangan, untuk itu bahasa pemrograman telah dilengkapi dengan fungsi-fungsi untuk mengolah karakter dan string. Misalnya untuk melakukan konversi dari huruf kapital ke non kapital, penggabungan string, pencarian substring, dan berbagai fungsi lainnya. Pada bahasa C, kalian dapat akses fungsi-fungsi tersebut pada pustaka <string.h>. Pada contoh
Pelajaran Fisika. Problem akan dibagi menjadi beberapa
subproblem dengan tingkat kesulitan yang meningkat. Ikutilah petunjuk guru kalian dalam memilih tingkat kesulitan subproblem yang akan kalian kerjakan. Apabila kalian berhasil mengerjakan subproblem tersebut, kalian dapat menantang diri kalian untuk mengerjakan subproblem yang lebih sulit. Setelah ditentukan tingkat kesulitan subproblem yang akan dikerjakan, kalian dapat mulai mengerjakan aktivitas Ayo Merancang Program: Merancang Algoritma Simulasi Burung dan Ayo Buat Program: Membuat Program Simulasi Burung berdasarkan deskripsi permasalahan yang sesuai.
Gambar 2.15
Austrasi Boro yang sedang
tidur
Problem. Program Simulasi Burung Boro adalah seekor burung yang terjatuh dari sarangnya di sebuah pohon saat sedang tidur. Saat terjatuh, sayap Boro menghantam tanah dan ia sangat merasa kesakitan. Boro harus kembali ke sarangnya, namun karena sayapnya terluka, ia tidak dapat terbang sebagaimana mestinya. Tak jauh dari tempat Boro jatuh, terdapat ketapel raksasa yang biasa digunakan oleh pemilik lahan untuk kegiatan sirkus. Ketapel tersebut biasa digunakan untuk kegiatan menembak dengan menggunakan buah semangka.
Kebetulan saat itu, pemilik lahan sedang latihan sirkus menembak semangka dengan menggunakan ketapel. Boro meminta tolong kepada pemilik lahan, apakah ia dapat ikut di atas semangka tersebut agar dapat kembali ke rumahnya di atas pohon. Sang pemilik lahan setuju akan membantu dan menanyakan kepada Boro tentang lokasi pohon tempat tinggalnya.
Seberapa paham kalian dengan konsep larik pada pemrograman?
2. Seberapa paham kalian dengan konsep karakter dan string pada pemrograman?
3. Seperti apa pengalaman yang kalian rasakan saat membaca dokumentasi bahasa pemrograman yang disediakan?
4. Pelajaran paling berkesan yang kalian dapatkan dari aktivitas latihan ini?
D. Latihan Strategi Algoritmik dan Pemrograman Lintas Bidang
Pada bagian ini kalian akan membuat berbagai program berdasarkan permasalahan yang tersedia, tiap permasalahan memiliki sub permasalahannya tersendiri yang tingkat kesulitannya meningkat. Kalian akan membuat program dimulai dari perancangan, yaitu merancang algoritma untuk menyelesaikan permasalahan tersebut. Selanjutnya algoritma tersebut kalian terjemahkan ke dalam bahasa pemrograman yang kalian kuasai, misalnya bahasa C, Python, dsb. Permasalahan tersebut akan meningkatkan kemampuan programming kalian dengan mempelajari bagian ini dengan menyelesaikan berbagai sub permasalahan yang tersedia.
1. Problem Simulasi Burung
Pada bagian ini, kalian akan membuat program untuk mensimulasikan gerak burung yang diluncurkan dengan menggunakan alat ketapel. Secara prinsip, gerakan burung yang diluncurkan dengan menggunakan ketapel menggunakan prinsip gerak lurus berubah beraturam (GLBB). Terdapat komponen sudut, gravitasi serta kecepatan dan waktu yang menjadi penentu jauhnya burung tersebut dapat meluncur dengan menggunakan ketapel. Konsep ini menggunakan kaidah gerak parabola yang telah kalian pelajari pada Mata berikut, diberikan dua buah kode program C untuk mengolah karakter dan string.
Program pertama akan membaca sebuah string, mengubahnya
ke dalam huruf non kapital, lalu mencetaknya:
Demonstrasi karakter dan string */ 1:
2:
3:
#include <stdio.h>
4:
#include <iostream>
5:
#include <string.h>
6:
using namespace std;
7:
8:
int main(){
9:
string str;
10:
11:
12:
13:
14:
15: }
cin >> str;
for(int i=0; i < str.length(); i++)
str[1] = tolower(str[i]);
cout << str << "'\n';
Program kedua akan membaca banyak string hingga membaca string "STOP". Setiap string yang dibaca akan diubah ke huruf non kapital dan dicetak.
1: Demonstrasi karakter dan string */
2:
3:
#include <stdio.h>
4:
#include <iostream>
5: #include <string.h>
6:
using namespace std
7:
8:
string lowerCase(string str
9:
10:
str[1] towlower(str[1]);
for(int i=1< str.length(); i++)
11:
return str;
12: }
13:
14:
int main(
15:
string str;
161
17:
18:
19:
cin >> str;
while(str = "STOP") (
cout << lowerCase(str) << "\n';
cin >> str;
20:
}
21:}
E. Proyek Praktik Lintas Bidang (PLB) Pertama-tama, sesuai dengan petunjuk dari guru, buatlah kelompok yang masing-masing terdiri dari 2 orang peserta didik (jika kelas berjumlah ganjil, satu kelompok boleh berisi 3 orang peserta didik). Saat mengerjakan proyek ini, diperlukan kerja sama antar anggota kelompok dengan baik untuk menghasilkan jawaban dan solusi yang tepat.
Tujuan utama dari proyek lintas bidang ini adalah menghasilkan sebuah program (dalam Bahasa C/C++) yang dapat menyelesaikan permasalahan knapsack (baik yang berjenis rational knapsack maupun 0-1 knapsack) dengan menerapkan prinsip-prinsip penyelesaian masalah yang telah dipelajari pada bagian Berpikir Komputasional. Hasil akhir yang diharapkan adalah berupa dua hal:
• Laporan analisis dan perancangan program
• Kode program yang dapat dijalankan dan memberikan solusi dari setiap masukan yang diberikan
Dalam pengerjaan ini, kalian akan dipandu dengan serangkaian langkah-langkah tersebut dan bersama rekan satu tim untuk mendapatkan hasil terbaik.
1. Penjelasan Permasalahan Permasalahan yang akan diselesaikan pada PLB ini adalah
salah contoh dari sebuah permasalahan optimasi. Dalam dunia informatika, optimasi adalah suatu tipe permasalahan dimana kita ingin mencari nilai yang optimal (paling baik) untuk sebuah kasus permasalahan tertentu. Konsep "paling baik" dapat berarti dua hal: paling kecil (minimal) atau paling besar (maksimal), sehingga secara umum ada dua jenis permasalahan optimasi, yaitu optimasi untuk mencari nilai maksimum dan optimasi untuk mencari nilai minimum. Nilai atau besaran yang ingin dioptimalkan (minimal atau maksimal) biasa disebut sebagai fungsi tujuan (fungsi obyektif).
Pada umumnya, ketika mencari suatu nilai yang optimal dalam sebuah permasalahan optimasi, kita harus menghadapi suatu kendala yang mengatur pilihan-pilihan yang dapat kita ambil. Mungkin, tidak semua pilihan dapat kita ambil. Ketika kita melakukan optimasi, kita harus memilih di antara pilihan-pilihan tersebut mana yang memberikan nilai fungsi obyektif yang paling optimal.
Sebagai contoh, kita tinjau kembali permasalahan penukaran uang yang telah kita pelajari pada bagian Berpikir Komputasional. Pada permasalahan tersebut, kita diberikan beberapa pecahan uang (misalnya: 100 Rupiah, 200 Rupiah, 500 Rupiah, 1000 Rupiah, 5000 Rupiah dan 10.000 Rupiah), serta sebuah besaran nilai uang yang ingin kita tukarkan, (misalnya Rp 27.800). Kita diminta untuk menentukan, berapa banyaknya pecahan uang terkecil yang dapat kita tukarkan untuk mencapai besaran tersebut?
Permasalahan ini adalah sebuah permasalahan optimasi dimana jenis optimasi pada permasalahan ini adalah pencarian
nilai minimum (terkecil). Fungsi tujuannya adalah banyaknya pecahan uang yang harus dikumpulkan, sedangkan kendala yang diberikan adalah besaran-besaran pecahan uang yang tersedia, serta jumlah total besaran nilai uang yang harus dikumpulkan.
Pada PLB ini kita akan mempelajari bagaimana menyelesaikan permasalahan yang biasa disebut sebagai knapsack problem. Berikut ini adalah deskripsi umum permasalahan knapsack problem.
Komentar
Posting Komentar