Array adalah struktur data yang digunakan untuk menyimpan sekumpulan elemen yang memiliki tipe data yang sama dalam satu variabel. Dalam C++, array memungkinkan kita untuk mengakses dan memanipulasi data dengan lebih efisien menggunakan indeks. Berikut adalah penjelasan mendalam tentang array, beserta contoh sintaks dan latihan soal:

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.

Merupakan metode pemecahan masalah yang mengandalkan strategi "memilih yang terbaik pada saat ini" dengan harapan bahwa pilihan lokal terbaik akan mengarah ke solusi global yang optimal. Prinsip dasarnya adalah membuat keputusan yang paling baik (optimum) pada setiap langkah dari algoritma, tanpa memperhatikan konsekuensi keputusan tersebut di masa depan.

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;
}

Dalam C++ Rekursi  adalah teknik di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah. Teknik ini sering digunakan untuk memecahkan masalah yang dapat dibagi menjadi sub-masalah yang lebih kecil dan serupa. Misalnya, masalah seperti pencarian dalam struktur data berbentuk pohon atau penyelesaian masalah matematika seperti faktorial atau deret Fibonacci sering diselesaikan menggunakan rekursi.

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.

Proses menyusun data dalam urutan tertentu, biasanya berdasarkan nilai atau kriteria tertentu. Pengurutan adalah operasi fundamental dalam ilmu komputer dan banyak digunakan dalam berbagai aplikasi, seperti penyimpanan data, pencarian, dan analisis.

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;
}

fungsi printf() adalah bagian dari pustaka C standar, yaitu <cstdio>. Meskipun C++ memiliki fitur lebih modern seperti std::cout, printf() masih sering digunakan terutama oleh mereka yang familiar dengan C atau ketika format output yang spesifik diperlukan.

Berikut adalah sintaks dasar printf() dan beberapa contoh penggunaannya.

Sintaks Dasar

#include <cstdio>  // Header untuk printf()

int main() {
    printf(format, arg1, arg2, ...);
    return 0;
}

• format: String format yang berisi teks dan spesifikasi format untuk argumen berikutnya.
• arg1, arg2, ...: Argumen yang akan digantikan dalam format string.

Contoh Penggunaan printf()

1. Mencetak Teks Sederhana

#include <cstdio>

int main() {
    printf("Hello, World!\n");
    return 0;
}

Output:

Hello, World!

2. Mencetak Teks dengan Format

#include <cstdio>

int main() {
    int age = 25;
    double height = 1.75;

    printf("Age: %d years\n", age);
    printf("Height: %.2f meters\n", height);
    return 0;
}

Output:

makefile

Age: 25 years
Height: 1.75 meters

• %d: Format untuk integer.
• %.2f: Format untuk floating-point number dengan dua tempat desimal.

3. Mencetak Lebih Banyak Argumen

#include <cstdio>

int main() {
    int quantity = 10;
    double price = 9.99;
    double total = quantity * price;

    printf("Quantity: %d\n", quantity);
    printf("Price per item: Rp%.2f\n", price);
    printf("Total: Rp%.2f\n", total);
    return 0;
}

Output:

yaml

Quantity: 10
Price per item: Rp9.99
Total: Rp99.90

4. Mencetak Teks dengan Lebar Kolom dan Padding

#include <cstdio>

int main() {
    printf("|%10s|%5d|\n", "Item", 123);
    printf("|%10s|%5d|\n", "Total", 456);
    return 0;
}

Output:

mathematica

|      Item|  123|
|     Total|  456|

• %10s: Format string dengan lebar minimum 10 karakter, di-pad dengan spasi di sebelah kiri jika diperlukan.
• %5d: Format integer dengan lebar minimum 5 karakter, di-pad dengan spasi di sebelah kiri jika diperlukan.

5. Mencetak dengan Format Hexadecimal dan Oktal

#include <cstdio>

int main() {
    int number = 255;

    printf("Decimal: %d\n", number);
    printf("Hexadecimal: %X\n", number);  // %X untuk huruf kapital
    printf("Octal: %o\n", number);
    return 0;
}

Output:

makefile

Decimal: 255
Hexadecimal: FF
Octal: 377

• %X: Format hexadecimal (huruf kapital).
• %o: Format oktal.

Catatan

• printf() tidak mendukung tipe data C++ modern seperti std::string secara langsung. Untuk itu, Anda biasanya harus menggunakan std::cout.
• Format string di printf() harus sesuai dengan tipe argumen yang diberikan. Jika tidak, Anda mungkin akan mendapatkan hasil yang tidak terduga atau kesalahan runtime.