Penjelasan Array

1. Deklarasi Array: Untuk mendeklarasikan array di C++, Anda perlu menentukan tipe data elemen array dan ukuran array. Contohnya:

   
   int arr[5];
   

   Ini mendeklarasikan sebuah array arr dengan 5 elemen yang bertipe int.

2. Inisialisasi Array: Anda bisa menginisialisasi array saat mendeklarasikannya atau setelah deklarasi. Contohnya:

   
   int arr[5] = {1, 2, 3, 4, 5}; // Inisialisasi saat deklarasi
   int arr[5];
   arr[0] = 1;
   arr[1] = 2;
   arr[2] = 3;
   arr[3] = 4;
   arr[4] = 5; // Inisialisasi setelah deklarasi
   

3. Mengakses Elemen Array: Elemen array diakses menggunakan indeks, yang dimulai dari 0. Contohnya:

   
   int x = arr[0]; // Mengakses elemen pertama
   arr[1] = 10;    // Mengubah nilai elemen kedua
   

4. Ukuran Array: Ukuran array harus ditentukan saat deklarasi dan tidak bisa diubah setelah itu. Anda dapat menggunakan sizeof untuk mengetahui ukuran total array dalam byte:

   
   int size = sizeof(arr) / sizeof(arr[0]); // Menghitung jumlah elemen
   

Contoh Sintaks C++

Berikut adalah contoh program C++ sederhana yang menggunakan array:

#include <iostream>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array
    int numbers[5] = {10, 20, 30, 40, 50};

    // Mengakses dan Menampilkan Elemen Array
    for(int i = 0; i < 5; i++) {
        cout << "Element at index " << i << " is " << numbers[i] << endl;
    }

    // Mengubah Nilai Elemen Array
    numbers[2] = 100;

    // Menampilkan Elemen Array setelah perubahan
    cout << "After modification:" << endl;
    for(int i = 0; i < 5; i++) {
        cout << "Element at index " << i << " is " << numbers[i] << endl;
    }

    return 0;
}

Hasil sintax di atas adalah

Element at index 0 is 10
Element at index 1 is 20
Element at index 2 is 30
Element at index 3 is 40
Element at index 4 is 50
After modification:
Element at index 0 is 10
Element at index 1 is 20
Element at index 2 is 100
Element at index 3 is 40
Element at index 4 is 50

Untuk penjelasan sintak di atas KLIK

Latihan Soal

1. Latihan 1: Buatlah program yang mendeklarasikan array float dengan 4 elemen, inisialisasi dengan nilai-nilai acak, dan cetak setiap elemen serta rata-ratanya.

2. Latihan 2: Tulis program yang mendeklarasikan array int dengan 6 elemen, inisialisasi dengan nilai-nilai dari 1 hingga 6. Buatlah fungsi untuk menghitung jumlah dan rata-rata dari elemen-elemen array tersebut.

3. Latihan 3: Buatlah program yang mendeklarasikan array dua dimensi 3x3 (matriks) dan inisialisasi dengan angka-angka dari 1 hingga 9. Tampilkan matriks tersebut dalam format tabel.

Solusi Latihan

Latihan 1:

#include <iostream>
using namespace std;

int main() {
    float numbers[4] = {5.6, 3.4, 7.8, 1.2};
    float sum = 0;

    for(int i = 0; i < 4; i++) {
        sum += numbers[i];
    }

    cout << "Elements of the array:" << endl;
    for(int i = 0; i < 4; i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    cout << "Average: " << sum / 4 << endl;

    return 0;
}

Latihan 2:

#include <iostream>
using namespace std;

void calculateSumAndAverage(int arr[], int size, int &sum, float &average) {
    sum = 0;
    for(int i = 0; i < size; i++) {
        sum += arr[i];
    }
    average = static_cast<float>(sum) / size;
}

int main() {
    int numbers[6] = {1, 2, 3, 4, 5, 6};
    int sum;
    float average;

    calculateSumAndAverage(numbers, 6, sum, average);

    cout << "Sum: " << sum << endl;
    cout << "Average: " << average << endl;

    return 0;
}

Latihan 3:

#include <iostream>
using namespace std;

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    cout << "Matrix:" << endl;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}



Berikut adalah beberapa contoh penggunaan array 
dalam konteks kehidupan sehari-hari dan sintaks C++ yang sesuai untuk masing-masing contoh:
1. Menyimpan Skor Nilai Siswa
Misalkan Anda ingin menyimpan skor ujian dari beberapa siswa. Anda bisa menggunakan array untuk menyimpan nilai-nilai tersebut.

#include <iostream>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array untuk menyimpan nilai ujian siswa
    int scores[5] = {85, 90, 78, 92, 88};
    int total = 0;
    int numberOfStudents = sizeof(scores) / sizeof(scores[0]);

    // Menampilkan nilai setiap siswa
    cout << "Scores of the students:" << endl;
    for (int i = 0; i < numberOfStudents; i++) {
        cout << "Student " << (i + 1) << ": " << scores[i] << endl;
        total += scores[i];
    }

    // Menghitung rata-rata nilai
    float average = static_cast<float>(total) / numberOfStudents;
    cout << "Average score: " << average << endl;

    return 0;
}
2. Menampilkan Jadwal Mingguan
Jika Anda ingin menyimpan jadwal kegiatan harian untuk seminggu, Anda dapat menggunakan array satu dimensi.

#include <iostream>
#include <string>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array untuk menyimpan jadwal mingguan
    string schedule[7] = {
        "Monday: Meeting with team",
        "Tuesday: Project work",
        "Wednesday: Client call",
        "Thursday: Presentation preparation",
        "Friday: Weekly review",
        "Saturday: Team outing",
        "Sunday: Rest day"
    };

    // Menampilkan jadwal mingguan
    cout << "Weekly Schedule:" << endl;
    for (int i = 0; i < 7; i++) {
        cout << schedule[i] << endl;
    }

    return 0;
}
3. Mengelola Inventaris Barang
Jika Anda memiliki inventaris barang di sebuah toko dan ingin menyimpan jumlah setiap barang yang tersedia, Anda bisa menggunakan array.

#include <iostream>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array untuk menyimpan jumlah inventaris barang
    int inventory[4] = {50, 30, 20, 40}; // Misalnya: barang A, B, C, D
    string itemNames[4] = {"Item A", "Item B", "Item C", "Item D"};

    // Menampilkan jumlah inventaris setiap barang
    cout << "Inventory:" << endl;
    for (int i = 0; i < 4; i++) {
        cout << itemNames[i] << ": " << inventory[i] << " units" << endl;
    }

    return 0;
}
4. Menangani Suhu Harian
Anda bisa menggunakan array untuk menyimpan data suhu harian dalam satu bulan.

#include <iostream>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array untuk suhu harian
    float temperatures[30] = {22.5, 21.0, 23.1, 22.8, 24.0, /* ...data lain... */ 21.5}; // Misalkan ada 30 hari data suhu

    float sum = 0;
    int numberOfDays = sizeof(temperatures) / sizeof(temperatures[0]);

    // Menghitung rata-rata suhu
    for (int i = 0; i < numberOfDays; i++) {
        sum += temperatures[i];
    }
    float averageTemperature = sum / numberOfDays;

    cout << "Average Temperature for the month: " << averageTemperature << " °C" << endl;

    return 0;
}
5. Menyimpan Data Kontak
Jika Anda ingin menyimpan nomor telepon dalam sebuah kontak, array dapat digunakan untuk mengelola data tersebut.

#include <iostream>
#include <string>
using namespace std;

int main() {
    // Deklarasi dan Inisialisasi Array untuk nomor telepon
    string phoneNumbers[3] = {"123-456-7890", "987-654-3210", "555-555-5555"};
    string names[3] = {"Alice", "Bob", "Charlie"};

    // Menampilkan daftar kontak
    cout << "Contact List:" << endl;
    for (int i = 0; i < 3; i++) {
        cout << names[i] << ": " << phoneNumbers[i] << endl;
    }

    return 0;
}
Penjelasan Kode:
Deklarasi Array: int scores[5], string schedule[7], int inventory[4], float temperatures[30], string phoneNumbers[3] digunakan untuk mendeklarasikan array dengan elemen sesuai kebutuhan.
Inisialisasi Array: Data diisi langsung saat deklarasi atau diisi setelah deklarasi.
Mengakses Elemen Array: Menggunakan indeks array seperti scores[i], schedule[i], dll.
Pengulangan Array: Menggunakan loop for untuk iterasi elemen array.

Prinsip Dasar

1. Pilih Langkah Terbaik Saat Ini: Pilih opsi yang tampak terbaik pada saat ini tanpa mempertimbangkan dampaknya pada keputusan di masa depan.
2. Kemajuan Berkelanjutan: Terus pilih langkah terbaik secara lokal sampai solusi lengkap tercapai.
3. Kriteria Akhir: Verifikasi apakah solusi yang diperoleh memenuhi kriteria optimalitas untuk masalah tersebut.

Kapan Menggunakan Algoritma Greedy?

Algoritma greedy tidak selalu memberikan solusi optimal untuk semua jenis masalah. Namun, ia sangat efektif untuk masalah yang memiliki dua sifat penting:

1. Substruktur Optimal: Solusi optimal dari masalah dapat dibangun dari solusi optimal sub-masalahnya.
2. Propertis Greedy: Solusi global dapat dibangun dengan memilih langkah-langkah yang tampaknya terbaik secara lokal.

Contoh Masalah yang Umum dipecahkan dengan Algoritma Greedy

1. Masalah Koin (Coin Change Problem)

Masalah: Diberikan denominasi koin dan jumlah uang yang ingin ditukar, temukan jumlah minimum koin yang dibutuhkan.

Contoh: Denominasi koin: 1, 3, 4 Jumlah yang ingin ditukar: 6

Solusi Greedy:

1. Pilih koin dengan nilai terbesar yang kurang dari atau sama dengan 6. Dalam hal ini, koin 4.
2. Kurangi 6 dengan 4, sisa 2.
3. Pilih koin 1 dua kali untuk sisa 2.
4. Total koin adalah 1 koin 4 dan 2 koin 1, sehingga 3 koin secara keseluruhan.

Implementasi dalam C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCoins(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    std::cout << "Minimum koin yang diperlukan: " << minCoins(coins, amount) << endl;
    return 0;
}

2. Masalah Knapsack 0/1 (Subset Sum)

Masalah: Diberikan kapasitas knapsack dan beberapa item dengan nilai dan berat, pilih item yang akan dimasukkan ke dalam knapsack untuk memaksimalkan nilai total tanpa melebihi kapasitas knapsack.

Solusi Greedy:

1. Hitung rasio nilai terhadap berat untuk setiap item.
2. Urutkan item berdasarkan rasio ini secara menurun.
3. Masukkan item dengan rasio tertinggi ke dalam knapsack sebanyak mungkin sampai kapasitas penuh.

Implementasi dalam C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namacpace std;

struct Item {
    int value;
    int weight;
    double ratio;
};

bool compare(Item a, Item b) {
    return a.ratio > b.ratio;
}

double knapsackGreedy(std::vector<Item>& items, int capacity) {
    sort(items.begin(), items.end(), compare);
    double totalValue = 0.0;
    int currentWeight = 0;

    for (const auto& item : items) {
        if (currentWeight + item.weight <= capacity) {
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            int remainingWeight = capacity - currentWeight;
            totalValue += item.value * (static_cast<double>(remainingWeight) / item.weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10, 6.0}, {100, 20, 5.0}, {120, 30, 4.0}};
    int capacity = 50;
    cout << "Nilai maksimum yang dapat dicapai: " << knapsackGreedy(items, capacity) << endl;
    return 0;
}

Kelebihan dan Kekurangan

Kelebihan:

• Sederhana dan cepat untuk diterapkan.
• Dapat memberikan solusi yang baik dalam waktu yang singkat untuk beberapa masalah.

Kekurangan:

• Tidak selalu memberikan solusi optimal untuk semua masalah.
• Hasil bisa sangat bergantung pada urutan langkah yang diambil.

Beberapa contoh algoritma greedy yang sering diterapkan dalam konteks lingkungan sekolah atau pembelajaran. 

1. Masalah Penjadwalan Kelas

Masalah: Diberikan sejumlah kelas dengan waktu mulai dan waktu selesai, buatlah jadwal kelas yang memaksimalkan jumlah kelas yang dapat diambil tanpa adanya tabrakan waktu.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih kelas yang selesai lebih awal dan tidak tumpang tindih dengan kelas yang sudah dijadwalkan.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Class {
    int start;
    int end;
};

bool compare(Class a, Class b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

void scheduleClasses(std::vector<Class>& classes) {
    sort(classes.begin(), classes.end(), compare); // Urutkan kelas berdasarkan waktu selesai
    cout << "Jadwal Kelas yang dipilih:" << endl;

    int n = classes.size();
    int i = 0; // Pilih kelas pertama
    cout << "Kelas (" << classes[i].start << ", " << classes[i].end << ")" << endl;

    for (int j = 1; j < n; ++j) {
        if (classes[j].start >= classes[i].end) {
            cout << "Kelas (" << classes[j].start << ", " << classes[j].end << ")" << endl;
            i = j;
        }
    }
}

int main() {
    vector<Class> classes = {{9, 10}, {11, 12}, {10, 11}, {13, 14}, {12, 13}};
    scheduleClasses(classes);
    return 0;
}

2. Masalah Pemilihan Buku (Book Selection Problem)

Masalah: Diberikan sejumlah buku dengan waktu mulai dan waktu selesai untuk setiap buku dan waktu total yang tersedia. Pilih buku-buku yang memaksimalkan jumlah buku yang dibaca tanpa melebihi waktu yang tersedia.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih buku yang memerlukan waktu paling sedikit sehingga kita dapat membaca lebih banyak buku.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Book {
    int time;
};

bool compare(Book a, Book b) {
    return a.time < b.time; // Urutkan berdasarkan waktu yang dibutuhkan untuk membaca
}

int selectBooks(std::vector<Book>& books, int availableTime) {
    ort(books.begin(), books.end(), compare); // Urutkan buku berdasarkan waktu yang dibutuhkan
    int totalBooks = 0;
    int totalTime = 0;

    for (const auto& book : books) {
        if (totalTime + book.time <= availableTime) {
            totalTime += book.time;
            totalBooks++;
        } else {
            break;
        }
    }

    return totalBooks;
}

int main() {
    vector<Book> books = {{3}, {2}, {1}, {4}, {2}};
    int availableTime = 6; // Waktu total yang tersedia
    std::cout << "Jumlah buku yang dapat dibaca: " << selectBooks(books, availableTime) << std::endl;
    return 0;
}

3. Masalah Penjadwalan Ujian

Masalah: Diberikan sejumlah ujian dengan waktu mulai dan waktu selesai, pilih ujian-ujian yang dapat diambil tanpa saling bertabrakan.

Contoh Solusi: Menggunakan algoritma greedy yang memilih ujian yang selesai lebih awal untuk memaksimalkan jumlah ujian yang dapat diambil.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Exam {
    int start;
    int end;
};

bool compare(Exam a, Exam b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

void scheduleExams(std::vector<Exam>& exams) {
    sort(exams.begin(), exams.end(), compare); // Urutkan ujian berdasarkan waktu selesai
    cout << "Jadwal Ujian yang dipilih:" << endl;

    int n = exams.size();
    int i = 0; // Pilih ujian pertama
    cout << "Ujian (" << exams[i].start << ", " << exams[i].end << ")" << endl;

    for (int j = 1; j < n; ++j) {
        if (exams[j].start >= exams[i].end) {
            cout << "Ujian (" << exams[j].start << ", " << exams[j].end << ")" << endl;
            i = j;
        }
    }
}

int main() {
    vector<Exam> exams = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
    scheduleExams(exams);
    return 0;
}

4. Masalah Pembagian Waktu Belajar

Masalah: Diberikan sejumlah kegiatan dengan waktu mulai dan selesai, bagi waktu belajar Anda sehingga memaksimalkan jumlah kegiatan yang dapat diselesaikan.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih kegiatan yang memerlukan waktu paling sedikit untuk memaksimalkan jumlah kegiatan.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Activity {
    int start;
    int end;
};

bool compare(Activity a, Activity b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

int maximizeActivities(std::vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare); // Urutkan kegiatan berdasarkan waktu selesai
    int count = 0;
    int lastEndTime = -1;

    for (const auto& activity : activities) {
        if (activity.start >= lastEndTime) {
            lastEndTime = activity.end;
            count++;
        }
    }

    return count;
}

int main() {
    vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
    cout << "Jumlah kegiatan yang bisa diselesaikan: " << maximizeActivities(activities) << std::endl;
    return 0;
}

Contoh Dasar Rekursi dalam C++

Berikut adalah beberapa contoh untuk menunjukkan cara kerja rekursi dalam C++.

1. Faktorial

Faktorial dari sebuah bilangan bulat non-negatif $n$ adalah produk dari semua bilangan bulat positif kurang dari atau sama dengan $n$. Misalnya, faktorial dari 5 (ditulis sebagai 5!) adalah $5 \times 4 \times 3 \times 2 \times 1$.

#include <iostream>
using namaspace std;

int factorial(int n) {
    if (n <= 1)  // Kasus dasar: faktorial dari 0 atau 1 adalah 1
        return 1;
    else
        return n * factorial(n - 1);  // Panggilan rekursif
}

int main() {
    int number = 5;
    cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
    return 0;
}

2. Deret Fibonacci

Deret Fibonacci adalah deret di mana setiap bilangan adalah jumlah dari dua bilangan sebelumnya, dimulai dari 0 dan 1. Jadi, deretnya adalah 0, 1, 1, 2, 3, 5, 8, 13, dan seterusnya.

#include <iostream>
using namaespace std;

int fibonacci(int n) {
    if (n <= 1)  // Kasus dasar: deret Fibonacci dari 0 adalah 0, dan dari 1 adalah 1
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);  // Panggilan rekursif
}

int main() {
    int number = 10;
    cout << "Fibonacci dari " << number << " adalah " << fibonacci(number) << endl;
    return 0;
}

3. Pencarian Binari

Pencarian binari adalah metode efisien untuk mencari elemen dalam array yang terurut. Algoritma ini membagi array menjadi dua bagian secara berulang-ulang sampai elemen yang dicari ditemukan atau sampai array tidak bisa dibagi lagi.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right)
        return -1;  // Elemen tidak ditemukan
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target)
        return mid;  // Elemen ditemukan
    else if (arr[mid] > target)
        return binarySearch(arr, left, mid - 1, target);  // Pencarian di sebelah kiri
    else
        return binarySearch(arr, mid + 1, right, target);  // Pencarian di sebelah kanan
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result != -1)
        cout << "Elemen ditemukan di indeks " << result << endl;
    else
        cout << "Elemen tidak ditemukan" << endl;
    
    return 0;
}

Pentingnya Kasus Dasar

Dalam setiap fungsi rekursif, penting untuk memiliki kasus dasar (base case) yang menghentikan rekursi. Tanpa kasus dasar, fungsi akan terus memanggil dirinya sendiri tanpa henti, yang dapat menyebabkan stack overflow dan crash program.

Berikut adalah beberapa contoh penerapan prinsip rekursi dalam kehidupan sehari-hari:

1. Resep Masakan (Pembuatan Makanan dengan Bahan Bertumpuk)

Masalah: Menghasilkan hidangan yang memerlukan beberapa langkah pengolahan dengan bahan yang harus diproses secara berulang. Misalnya, membuat lasagna yang memerlukan beberapa lapisan saus dan pasta.

Contoh Rekursi:

• Langkah 1: Siapkan bahan dasar (saus, daging, keju).
• Langkah 2: Tambahkan lapisan saus, pasta, dan keju.
• Langkah 3: Untuk setiap lapisan, panggil kembali langkah 2 hingga bahan habis.
• Kasus Dasar: Jika semua bahan sudah habis, susun lasagna dan panggang.

2. Pembersihan Rumah (Pembersihan Berulang)

Masalah: Pembersihan rumah yang membutuhkan pembersihan berbagai area dengan metode yang sama.

Contoh Rekursi:

• Langkah 1: Pilih satu area untuk dibersihkan (misalnya, satu ruangan).
• Langkah 2: Bersihkan area tersebut (sapu, lap, vakum).
• Langkah 3: Setelah selesai, pilih area berikutnya dan ulangi langkah 2 hingga semua area dibersihkan.
• Kasus Dasar: Jika semua ruangan sudah dibersihkan, proses selesai.

3. Pengurutan Tugas (To-Do List)

Masalah: Mengelola dan menyelesaikan daftar tugas yang harus diselesaikan.

Contoh Rekursi:

• Langkah 1: Pilih satu tugas dari daftar.
• Langkah 2: Selesaikan tugas tersebut atau bagilah menjadi sub-tugas lebih kecil.
• Langkah 3: Untuk setiap sub-tugas, ulangi langkah 1 dan 2 hingga sub-tugas selesai.
• Kasus Dasar: Jika tidak ada lagi sub-tugas yang tersisa, tugas selesai.

4. Pembuatan Keputusan (Mengambil Keputusan Berlapis)

Masalah: Mengambil keputusan yang melibatkan beberapa langkah yang bergantung pada keputusan sebelumnya.

Contoh Rekursi:

• Langkah 1: Buat keputusan pertama berdasarkan kondisi saat ini.
• Langkah 2: Jika keputusan tersebut mempengaruhi langkah berikutnya, panggil kembali langkah 1 dengan kondisi baru.
• Langkah 3: Terus ulangi hingga semua keputusan selesai diambil.
• Kasus Dasar: Jika semua keputusan sudah dibuat, proses selesai.

5. Penyelesaian Masalah (Menangani Permasalahan Berlapis)

Masalah: Menangani masalah besar dengan memecahnya menjadi masalah-masalah kecil.

Contoh Rekursi:

• Langkah 1: Identifikasi masalah utama yang harus diselesaikan.
• Langkah 2: Pecah masalah tersebut menjadi sub-masalah yang lebih kecil.
• Langkah 3: Untuk setiap sub-masalah, terapkan langkah-langkah penyelesaian hingga mencapai solusi.
• Kasus Dasar: Jika tidak ada sub-masalah yang tersisa, masalah utama selesai.

Implementasi Rekursi dalam C++: Contoh Masalah Faktorial

Untuk memberikan gambaran yang lebih jelas tentang bagaimana rekursi bekerja, mari kita lihat contoh implementasi fungsi faktorial menggunakan C++.

#include <iostream>

using namespace std;

// Fungsi rekursif untuk menghitung faktorial dari n
int factorial(int n) {
    if (n <= 1) // Kasus dasar
        return 1;
    else
        return n * factorial(n - 1); // Panggilan rekursif
}

int main() {
    int number = 5;
    cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
    return 0;
}

Penjelasan:

• Kasus Dasar: Jika n kurang dari atau sama dengan 1, faktorialnya adalah 1.
• Panggilan Rekursif: Untuk nilai n yang lebih besar dari 1, fungsi factorial memanggil dirinya sendiri dengan parameter n - 1.

Komponen Utama Informatika:

Algoritma dan Struktur Data: 

Metode sistematis untuk memecahkan masalah dan cara-cara untuk menyimpan dan mengelola data secara efisien.

Pemrograman: 

Pembuatan perangkat lunak melalui bahasa pemrograman, seperti Python, Java, atau C++.

Basis Data: 

Penyimpanan, pengelolaan, dan pengambilan data dari sistem basis data menggunakan DBMS (Database Management System) seperti MySQL, Oracle, atau MongoDB.

Sistem Operasi: 

Pengelolaan sumber daya perangkat keras komputer dan menyediakan layanan untuk perangkat lunak aplikasi.

Jaringan Komputer: 

Pengaturan dan pengelolaan komunikasi antara komputer dan perangkat lainnya melalui jaringan lokal (LAN) atau jaringan luas (WAN).

Keamanan Siber: 

Perlindungan data dan sistem dari ancaman, termasuk enkripsi, firewall, dan teknik keamanan lainnya.

Contoh Aplikatif Informatika:

Pengembangan Aplikasi Mobile: 

Membuat aplikasi seperti Instagram atau WhatsApp yang memanfaatkan teknik pemrograman untuk interaksi pengguna dan pengelolaan data.

Sistem Manajemen Basis Data:

Sistem manajemen basis data di rumah sakit yang menyimpan informasi pasien, rekam medis, dan jadwal dokter dengan menggunakan sistem seperti Oracle atau SQL Server.

E-commerce: 

Platform belanja online seperti Amazon atau Tokopedia yang memerlukan sistem untuk pengelolaan inventaris, transaksi, dan rekomendasi produk menggunakan algoritma dan basis data.

Jaringan Perusahaan: 

Infrastruktur jaringan untuk perusahaan besar yang memungkinkan komunikasi antara kantor yang berbeda dan akses ke sumber daya bersama, seperti file server atau aplikasi berbasis cloud.

Sistem Keamanan Digital: 

Penggunaan teknologi enkripsi untuk melindungi data sensitif dalam transaksi perbankan online atau sistem login dengan autentikasi dua faktor untuk meningkatkan keamanan akses.

1. Pengurutan Bubble (Bubble Sort)

Deskripsi: Mengulang melalui daftar dan membandingkan pasangan elemen yang berdekatan, menukar mereka jika mereka berada dalam urutan yang salah. Proses ini diulang hingga daftar terurut.

Kompleksitas Waktu: O(n^2)

Contoh Implementasi:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Tukar arr[j] dan arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

2. Pengurutan Seleksi (Selection Sort)

Deskripsi: Mencari elemen terkecil (atau terbesar) dari bagian yang belum terurut dan menukarnya dengan elemen pertama dari bagian tersebut.

Kompleksitas Waktu: O(n^2)

Contoh Implementasi:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // Tukar arr[i] dan arr[minIdx]
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

3. Pengurutan Sisip (Insertion Sort)

Deskripsi: Mengambil elemen satu per satu dan menyisipkannya pada posisi yang tepat di bagian yang sudah terurut dari daftar.

Kompleksitas Waktu: O(n^2)

Contoh Implementasi:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

4. Pengurutan Merge (Merge Sort)

Deskripsi: Metode pengurutan berbasis pembagian dan penaklukan yang membagi daftar menjadi dua bagian, mengurutkan masing-masing bagian, dan kemudian menggabungkannya.

Kompleksitas Waktu: O(n log n)

Contoh Implementasi:

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0;
    int j = 0;
    int k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

5. Pengurutan Quick (Quick Sort)

Deskripsi: Metode pengurutan berbasis pembagian dan penaklukan yang memilih elemen pivot, mengurutkan elemen yang lebih kecil dan lebih besar dari pivot, dan kemudian menggabungkannya.

Kompleksitas Waktu: O(n log n) rata-rata, O(n^2) terburuk

Contoh Implementasi:

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

6. Pengurutan Heap (Heap Sort)

Deskripsi: Menggunakan struktur data heap untuk mengurutkan data dengan membangun heap dari data, lalu mengeluarkan elemen dari heap satu per satu.

Kompleksitas Waktu: O(n log n)

Contoh Implementasi:

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    cout << "Array terurut: ";
    printArray(arr, n);
    return 0;
}

Dalam informatika, pencarian (searching) adalah proses menemukan data atau informasi tertentu dalam struktur data atau sistem informasi. Berbagai teknik pencarian digunakan untuk menangani berbagai jenis data dan kebutuhan aplikasi. Berikut adalah penjelasan mengenai pencarian dalam informatika beserta beberapa jenis teknik pencarian yang umum:

1. Pencarian Linier (Linear Search)

• Deskripsi: Metode pencarian ini memeriksa setiap elemen dalam struktur data satu per satu dari awal hingga akhir hingga elemen yang dicari ditemukan atau semua elemen telah diperiksa.
• Kelebihan: Sederhana dan mudah diimplementasikan.
• Kekurangan: Tidak efisien untuk dataset besar karena waktu pencarian bisa linear terhadap ukuran dataset.
• Contoh Penggunaan: Pencarian dalam array atau list yang tidak terurut.

  
  def linear_search(arr, target):
      for index, value in enumerate(arr):
          if value == target:
              return index
      return -1
  

2. Pencarian Biner (Binary Search)

• Deskripsi: Metode pencarian yang efisien untuk dataset terurut dengan membagi dataset menjadi dua bagian dan membandingkan nilai tengah dengan elemen yang dicari. Jika tidak cocok, pencarian dilanjutkan pada bagian yang relevan.
• Kelebihan: Efisien dengan kompleksitas waktu O(log n).
• Kekurangan: Memerlukan data yang terurut.
• Contoh Penggunaan: Pencarian dalam array terurut.

  
  def binary_search(arr, target):
      low, high = 0, len(arr) - 1
      while low <= high:
          mid = (low + high) // 2
          if arr[mid] == target:
              return mid
          elif arr[mid] < target:
              low = mid + 1
          else:
              high = mid - 1
      return -1
  

3. Pencarian Hash (Hash Search)

• Deskripsi: Menggunakan tabel hash untuk melakukan pencarian yang sangat cepat dengan memetakan kunci ke posisi dalam tabel berdasarkan fungsi hash.
• Kelebihan: Waktu pencarian yang sangat cepat, rata-rata O(1).
• Kekurangan: Memerlukan fungsi hash yang baik dan dapat menghadapi masalah seperti tabrakan (collision).
• Contoh Penggunaan: Pencarian dalam struktur data seperti hash table.

  
  hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
  def hash_search(key):
      return hash_table.get(key, 'Not found')
  

4. Pencarian Teks (Text Search)

• Deskripsi: Mencari kata, frasa, atau pola dalam teks dokumen atau string.
• Kelebihan: Berguna untuk pengolahan teks dan pencarian konten.
• Kekurangan: Kompleksitas dapat meningkat dengan ukuran teks dan pola pencarian.
• Contoh Penggunaan: Pencarian substring dalam string atau dokumen.

  
  def text_search(text, pattern):
      return pattern in text
  

5. Pencarian dalam Graf (Graph Search)

• Deskripsi: Pencarian dalam struktur graf, biasanya menggunakan algoritma seperti Depth-First Search (DFS) dan Breadth-First Search (BFS).
• Kelebihan: Dapat digunakan untuk berbagai aplikasi graf seperti pencarian jalur atau konektivitas.
• Kekurangan: Kompleksitas tergantung pada struktur graf.
• Contoh Penggunaan: Menemukan jalur antara dua node dalam graf.

  
  from collections import deque
  
  def bfs(graph, start, goal):
      queue = deque([start])
      visited = set()
      while queue:
          vertex = queue.popleft()
          if vertex == goal:
              return True
          visited.add(vertex)
          queue.extend(set(graph[vertex]) - visited)
      return False
  

6. Pencarian Semantik (Semantic Search)

• Deskripsi: Mencari informasi berdasarkan makna dan konteks daripada hanya kata kunci. Menggunakan teknik NLP (Natural Language Processing) untuk memahami konteks pencarian.
• Kelebihan: Memberikan hasil yang lebih relevan dan sesuai konteks.
• Kekurangan: Memerlukan pemrosesan bahasa alami dan model yang kompleks.
• Contoh Penggunaan: Mesin pencari modern seperti Google yang memahami makna di balik query pencarian.

7. Pencarian Multidimensi (Multidimensional Search)

• Deskripsi: Pencarian dalam data yang memiliki lebih dari satu dimensi, sering digunakan dalam aplikasi seperti sistem rekomendasi atau database spasial.
• Kelebihan: Dapat menangani data kompleks dengan banyak atribut.
• Kekurangan: Memerlukan struktur data khusus seperti pohon KD atau indeks ruang.
• Contoh Penggunaan: Pencarian dalam database spasial untuk menemukan objek dalam area geografis tertentu.

8. Pencarian Fuzzy (Fuzzy Search)

• Deskripsi: Pencarian yang memperbolehkan kesalahan ketik atau variasi dalam pencarian. Berguna ketika data yang dicari mungkin tidak cocok persis.
• Kelebihan: Menangani ketidakakuratan dalam pencarian.
• Kekurangan: Dapat memberikan hasil yang lebih luas dari yang diinginkan.
• Contoh Penggunaan: Pencarian dengan kesalahan ketik di mesin pencari atau aplikasi e-commerce.

9. Pencarian dalam Database (Database Search)

• Deskripsi: Menggunakan query untuk mencari data dalam database relasional atau non-relasional.
• Kelebihan: Dapat menggunakan SQL atau NoSQL untuk pencarian yang terstruktur atau tidak terstruktur.
• Kekurangan: Kompleksitas tergantung pada jenis database dan struktur data.
• Contoh Penggunaan: Menggunakan SQL untuk mencari data dalam database relasional.