Rekursi dan Algoritma Greedy

HALOO GUYSS KEMBALI LAGI BERSAMA SAYA DI BLOG SAYA YA GUYS YAA!!... 

So kali ini aku bakalan jelasin ke kalian tentang materi yang aku pelajari kemarin yaitu ada Rekursi dan Algoritma Greedy ya guys ya... 

Eee karena saya sibuk di RL saya bakal minta bantuan kepada duo kakak adek yg OP banget ini ya guys ya.. Sebenernya mau anime yg lain tapi pas mau ngerjain seketika malah lupa ingatan, so yaudahlah yang inget aja jadinya.

Takt さん Unmei ちゃん、 頼むよー!!!

'Hmmm.. Disini tugasku hanya menjelaskan saja kan? Baiklah mari kita mulai.'

Rekursi merupakan metode suatu proses memanggil dirinya sendiri yang digunakan untuk mengganti perulangan. Pendekatan ini dapat diterapkan pada berbagai jenis masalah dan rekursi adalah salah satu ide utama dari ilmu komputer.

(Sumber: https://id.m.wikipedia.org/wiki/Rekursi_(Ilmu_komputer)) 

Algoritma Greedy adalah pendekatan dalam pemrograman yang memecahkan persoalan optimasi dengan cara yang tampaknya rakus. Pendekatan ini berfokus pada pengambilan keputusan sekarang dengan harapan bahwa setiap langkah akan membawa kita lebih dekat ke solusi akhir yang optimal.

(Sumber: https://fikti.umsu.ac.id/algoritma-greedy-pengertian-jenis-dan-contoh-program/) 

'Sepertinya hanya ini tugasku, sisanya adalah tugasmu Unmei.'

'Disaat aku istirahat dan baru ingin makan pasti saja selalu begini. Luna てめ!!! これわ難しいです!!!! Dia harus membayarnya dengan pancake nanti!!'

Contoh Soal 1 Rekursi Bilangan Fibonacci

(Sumber: https://youtu.be/1v6TxeNea6o?si=_9TekdV-wm99cP1i ) 

Penjelasan:

1. Barisan Data

Barisan Fibonacci dapat dianggap sebagai barisan data yang didefinisikan sebagai berikut:

- ( F1 = 1 )

- ( F2 = 2 )

- Suku-suku berikutnya dihitung dengan penjumlahan dua suku sebelumnya: ( Fn = F(n1) + F(n2))

Maka, barisan Fibonacci yang dihasilkan adalah:

[ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]

2. Rekursi dan Basis

Rekursi:

Suku ( Fn ) dihitung menggunakan suku-suku sebelumnya dengan rumus:

[ Fn = F(n1) + F(n2) ]

Basis:

Suku pertama dan kedua adalah nilai dasar dari barisan:

- ( F1 = 1 )

- ( F2 = 2 )

Dari sini, setiap suku berikutnya dihitung secara rekursif berdasarkan dua suku sebelumnya.

3. Menggunakan Algoritma Greedy

Algoritma Greedy digunakan untuk memilih bilangan Fibonacci yang berada dalam rentang 10 hingga 100 dengan cara berikut:

- Hitung bilangan Fibonacci satu per satu hingga mencapai nilai yang lebih dari 100.

- Simpan dan pilih bilangan yang berada dalam rentang 10 hingga 100.

Langkah-langkahnya:

1. Hitung suku-suku Fibonacci secara berurutan hingga melebihi 100:

   ( F3 = 3 )

   ( F4 = 5 )

   ( F5 = 8 )

   ( F6 = 13)

   ( F7 = 21)

   ( F8 = 34)

   ( F9 = 55 )

   ( F10 = 89)

   ( F11 = 144) -> (lebih dari 100, berhenti)

2. Pilih suku-suku yang berada dalam rentang 10 hingga 100:

   ( F6 = 13)

   ( F7 = 21)

   ( F8 = 34)

   ( F9 = 55 )

   ( F10 = 89) 

Hasilnya, ada 5 bilangan Fibonacci dalam rentang 10 hingga 100.

Tapii aku juga mau kasih tau nih contoh pemrograman nya hehe, simak selengkapnya yaa!! 

_________________________________________

#include <iostream>

#include <vector>

using namespace std;

// Fungsi untuk menghasilkan deret Fibonacci dan memilih nilai dalam rentang 10 hingga 100

vector<int> generateFibonacci(int maxLimit) {

    vector<int> fibonacci;

    int F1 = 1, F2 = 2;

    

    // Memasukkan suku pertama dan kedua ke dalam barisan Fibonacci

    fibonacci.push_back(F1);

    fibonacci.push_back(F2);

    

    // Menghitung suku-suku Fibonacci berikutnya

    while (true) {

        int Fn = F1 + F2;

        if (Fn > maxLimit) break; // Jika nilai Fibonacci lebih dari 100, berhenti

        fibonacci.push_back(Fn);

        F1 = F2;

        F2 = Fn;

    }

    

    // Pilih bilangan Fibonacci dalam rentang 10 hingga 100

    vector<int> selectedFibonacci;

    for (int num : fibonacci) {

        if (num >= 10 && num <= 100) {

            selectedFibonacci.push_back(num);

        }

    }

    

    return selectedFibonacci;

}

int main() {

    int maxLimit = 100;

    vector<int> result = generateFibonacci(maxLimit);

    

    // Menampilkan hasil bilangan Fibonacci dalam rentang 10 hingga 100

    cout << "Bilangan Fibonacci dalam rentang 10 hingga 100: ";

    for (int num : result) {

        cout << num << " ";

    }

    cout << endl;

    

    return 0;

}

Untuk hasil outputnya gimana sih kak Unmei?? 

_________________________________________

Contoh Soal 2 Activity Selection Problem

Penjelasan

1. Barisan Data

Pertama, buat barisan data berupa waktu mulai dan waktu selesai dari setiap pertunjukan:

- Pinguin: (8:00, 9:30)

- Orang utan: (9:15, 10:30)

- Harimau: (10:00, 12:00)

- Burung pemangsa: (11:00, 12:30)

- Beruang madu: (13:00, 14:30)

- Buaya: (14:00, 15:00)

- Singa: (15:00, 15:30)

- Anjing laut: (15:30, 16:00)

- Panda: (15:30, 16:30)

- Ular piton: (16:00, 17:00)

2. Basis dan Rekursi

Untuk menggunakan pendekatan rekursi, kita harus memecah masalah menjadi sub-masalah yang lebih kecil. Namun, dalam hal ini, kita lebih fokus pada algoritma greedy yang merupakan metode yang paling sesuai untuk masalah ini.

Basis:

Jika tidak ada pertunjukan yang tersisa untuk dipilih, jumlah pertunjukan yang dapat ditonton adalah 0.

Rekursi:

Untuk memilih pertunjukan secara maksimal:

1. Pilih pertunjukan yang selesai paling awal (agar waktu untuk pertunjukan berikutnya lebih banyak).

2. Hapus semua pertunjukan yang tumpang tindih dengan pertunjukan yang telah dipilih.

3. Terapkan rekursi pada sisa pertunjukan.

3. Algoritma Greedy

Langkah-langkah Algoritma Greedy:

1. Urutkan Pertunjukan Berdasarkan Waktu Selesai:

Urutkan semua pertunjukan berdasarkan waktu selesai mereka agar kita bisa memilih pertunjukan yang selesai paling awal.

   Urutan yang dihasilkan setelah pengurutan:

   - Pinguin: (8:00, 9:30)

   - Orang utan: (9:15, 10:30)

   - Harimau: (10:00, 12:00)

   - Burung pemangsa: (11:00, 12:30)

   - Beruang madu: (13:00, 14:30)

   - Buaya: (14:00, 15:00)

   - Singa: (15:00, 15:30)

   - Anjing laut: (15:30, 16:00)

   - Panda: (15:30, 16:30)

   - Ular piton: (16:00, 17:00)

2. Pilih Pertunjukan:

Mulai dari pertunjukan yang selesai paling awal. Tambahkan pertunjukan ke dalam daftar yang dapat ditonton jika waktu mulai pertunjukan berikutnya tidak tumpang tindih dengan waktu selesai pertunjukan terakhir yang dipilih.

Contoh Proses Seleksi:

   - Pilih Pinguin (8:00 - 9:30).

   - Pertunjukan berikutnya yang dapat dipilih setelah Pinguin adalah Harimau (10:00 - 12:00) karena waktunya tidak tumpang tindih.

   - Setelah Harimau, pilih Beruang madu (13:00 - 14:30).

   - Pilih Singa (15:00 - 15:30) setelah Beruang madu.

   - Pilih Anjing laut (15:30 - 16:00) setelah Singa.

   - Terakhir, pilih Ular piton (16:00 - 17:00) setelah Anjing laut.

Hasil:

Dengan algoritma greedy, pertunjukan yang dapat ditonton Dina adalah:

- Pinguin (8:00 - 9:30)

- Harimau (10:00 - 12:00)

- Beruang madu (13:00 - 14:30)

- Singa (15:00 - 15:30)

- Anjing laut (15:30 - 16:00)

- Ular piton (16:00 - 17:00)

Jumlah maksimal pertunjukan yang dapat ditonton Dina adalah 6.

Tapi kalian penasaran ga sihh sama pemrograman nya gimana? Coba cek yukk

_______________________________________

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Struktur untuk menyimpan waktu mulai dan waktu selesai dari setiap pertunjukan

struct Show {

    string name;

    int start;

    int end;

};

// Fungsi untuk mengurutkan pertunjukan berdasarkan waktu selesai

bool compare(Show a, Show b) {

    return a.end < b.end;

}

int main() {

    // Daftar pertunjukan dengan nama, waktu mulai, dan waktu selesai (dalam menit dari jam 00:00)

    vector<Show> shows = {

        {"Pinguin", 480, 570},   // Pinguin: 8:00 - 9:30

        {"Orang utan", 555, 630}, // Orang utan: 9:15 - 10:30

        {"Harimau", 600, 720},   // Harimau: 10:00 - 12:00

        {"Burung pemangsa", 660, 750}, // Burung pemangsa: 11:00 - 12:30

        {"Beruang madu", 780, 870}, // Beruang madu: 13:00 - 14:30

        {"Buaya", 840, 900},     // Buaya: 14:00 - 15:00

        {"Singa", 900, 930},     // Singa: 15:00 - 15:30

        {"Anjing laut", 930, 960}, // Anjing laut: 15:30 - 16:00

        {"Panda", 930, 990},     // Panda: 15:30 - 16:30

        {"Ular piton", 960, 1020} // Ular piton: 16:00 - 17:00

    };

    // Mengurutkan pertunjukan berdasarkan waktu selesai

    sort(shows.begin(), shows.end(), compare);

    // Memulai algoritma greedy untuk memilih pertunjukan

    int count = 0;

    int lastEndTime = 0;

    vector<string> selectedShows;

    // Proses seleksi pertunjukan

    for (int i = 0; i < shows.size(); i++) {

        if (shows[i].start >= lastEndTime) {

            count++;

            lastEndTime = shows[i].end;

            selectedShows.push_back(shows[i].name);

        }

    }

    // Output hasil

    cout << "Jumlah maksimal pertunjukan yang dapat ditonton: " << count << endl;

    cout << "Pertunjukan yang dipilih: ";

    for (string show : selectedShows) {

        cout << show << " ";

    }

    cout << endl;

    return 0;

}

Untuk hasil outputnya akan seperti ini:

_________________________________________

'Gimana guys udah paham kann... Hahhhh 

疲れた一 sepertinya cukup 2 contoh soal saja karena perutku sudah lapar dibuat berfikir terus menerus, 'パンケーキ食べたいなー！,  lunaaa 終わりです !!! '

SELESAI JUGA AKHIRNYA GUYSSS OMG TANPA BANTUAN MEREKA MUNGKIN AKU... Tetep bisa si :3 , walaupun sambil...