Segitiga Angka dan Bintang (analisis, algoritma, dan program C++)

Beberapa hari yang lalu saya lihat di salah satu grup C++ di Facebook ada yang posting mengenai permasalahan seperti pada gambar.

Baik, langsung kita bahas. Kalau kita lihat pada gambar, kita dapat petunjuk seperti berikut:

• Setiap baris diawali dengan angka 1
• Di akhir karakter tiap baris merupakan angka yang mewakili baris tersebut (baris kedua diakhiri dengan angka 2, baris ketiga diakhiri dengan angka 3, dan seterusnya)
• Diantara angka awal dan angka akhir ada karakter bintang (1 bintang, 3 bintang, dan seterusnya)

Lalu bagaimana membuat algoritma untuk permasalahan tersebut?

Kita tahu bahwa permasalahan pada gambar tersebut membutuhkan perulangan bersarang (bahasa kerennya → nested loop) atau perulangan dalam perulangan. Perulangan yang luar untuk baris dan perulangan yang dalam untuk kolom atau bintangnya.

Kalau ada perulangan bersarang, kita pecahkan dulu masalah perulangan yang dalam atau kolomnya (dalam kasus ini untuk memecahkan masalah bintang).

Dari gambar, kita ambil beberapa baris untuk dianalisa agar ketemu rumus bintangnya. Misal kita ambil baris kedua (1*2) dan baris ketiga (1***3) lalu kita cari hubungannya, jika baris kedua maka bintangnya ada 1, jika baris ketiga maka bintangnya ada 3. Sudah ketemu? Kalau saya (mungkin rekan-rekan beda rumusnya), antara 2 dengan 1, dan 3 dengan 3 adalah 2*2-3 = 1 dan 3*2-3 = 3. Sehingga rumus yang di dapat adalah jumlahBintang = baris * 2 - 3. Sehingga algoritma yang saya dapat adalah:

jumlahBintang ← baris * 2 - 3
write('1')
for bintang ← 1 to jumlahBintang do
    write('*')
endfor
write(baris)

Kemudian kita lakukan tes pada algoritma di atas, kita coba dengan baris keempat:
jumlahBintang = 4 * 2 - 3
jumlahBintang = 5
Sehingga hasil tes algoritma di atas untuk baris keempat adalah 1*****4 (sesuai gambar).

Untuk lebih baiknya, kita lakukan tes dengan data minimal, maksimal, dan data tengah. Data tengah bisa kita pakai yang baris keempat tadi, dan hasilnya sesuai.

Untuk baris kelima:
jumlahBintang = 5 * 2 - 3
jumlahBintang = 7
Hasil tes : 1*******5 (sesuai gambar)

Untuk baris pertama:
jumlahBintang = 1 * 2 - 3
jumlahBintang = -1 (tidak ada bintang, karena perulangan naik dari 1 ke jumlahBintang)
Hasil tes : 11
Kok hasilnya tidak sesuai, pada gambar baris pertama kan hanya angka 1? maka kita bisa siasati dengan barisnya kita mulai dari baris kedua (terkait perulangan yang luar).

Perulangan yang luar (baris) adalah mulai dari baris 1 sampai dengan 5, tetapi karena pada tes algoritma perulangan dalam untuk baris=1 tidak sesuai, maka untuk perulangan luar kita buat mulai dari baris 2, sehingga perulangan luarnya seperti berikut:

for baris ← 2 to banyakBaris do
    ...
endfor

Tinggal kita masukkan algoritma perulangan yang dalam ke dalam perulangan luar, dan hasilnya:

for baris ← 2 to banyakBaris do
    jumlahBintang ← baris * 2 - 3
    write('1')
    for bintang ← 1 to jumlahBintang do
        write('*')
    endfor
    write(baris)
endfor

Ketika kita tes algoritma ini dengan banyakBaris = 5, hasilnya adalah:
1*2
1***3
1*****4
1*******5

Lho kok 1 yang paling atas hilang? Maka kita tambahkan di luar perulangan: write('1'), yang hasil algoritmanya:

write('1')
for baris ← 2 to banyakBaris do
    jumlahBintang ← baris * 2 - 3
    write('1')
    for bintang ← 1 to jumlahBintang do
        write('*')
    endfor
    write(baris)
endfor

Kalau banyakBarisnya mau dibuat dinamis (inputan dari user), maka kita tambah read(banyakBaris):

read(banyakBaris)
write('1')
for baris ← 2 to banyakBaris do
    jumlahBintang ← baris * 2 - 3
    write('1')
    for bintang ← 1 to jumlahBintang do
        write('*')
    endfor
    write(baris)
endfor

Ketika banyakBaris diisi 1, hasilnya:
1

Ketika banyakBaris diisi 3, hasilnya:
1
1*2
1***3

Ketika banyakBaris diisi 0, hasilnya:
1
Lha? Harusnya kan tidak muncul apapun kalau 0 baris? Maka kita beri kondisi setelah baca inputan dari user:

read(banyakBaris)
if(banyakBaris>0) then
    writeln('1')
    for baris ← 2 to banyakBaris do
        jumlahBintang ← baris * 2 - 3
        write('1')
        for bintang ← 1 to jumlahBintang do
            write('*')
        endfor
        writeln(baris)
    endfor
endif

Nah, sekarang kalau user input kurangdari 1 tidak akan muncul apapun.

Untuk program C++ nya seperti di bawah ini, ingat! algoritma yang saya buat ini tidak mesti sama dengan yang dibuat orang lain. Tetapi selama bisa menyelesaikan permasalahan yang ada.. why not?? Yang sudah buat tetapi beda algoritma, bolehlah corat-coret di kolom komentar gan, biar rame.. 

Source code:

#include <iostream>
//develop251.blogspot.com
using namespace std;

int main(){
    int banyakBaris;
    
    cout << "Masukkan banyak baris : "; cin >> banyakBaris;
    
    if(banyakBaris>0){
        cout << '1' << endl;
        
        for(int baris=2; baris<=banyakBaris; baris++){
            int jumlahBintang = baris * 2 - 3;
            
            cout << '1';
            
            for(int bintang=1; bintang<=jumlahBintang; bintang++){
                cout << '*';
            }
            
            cout << baris << endl;
        }
    }
    
    return 0;
}

Hasil: