Soal Pengenalan Algoritma dan Pemrograman (8)

Soal 8/8

Tugas AO Computer Science

Dari delapan soal yang diberikan, semuanya meminta kita untuk mencetak output angka atau karakter lainnya dengan susunan/pola menyerupai bangun datar.

Soal Pengenalan Algoritma dan Pemrograman #8

Format masukan berupa sebuah bilangan N.
Format keluaran berupa N baris dengan pola sesuai gambar di bawah.

8

Berikut ini solusi untuk soal di atas :

#include <stdio.h>
#include <vector>
#include <bitset>

std::vector<int> primes;
std::bitset<10000000> bs;

void sieve(long long x){
	bs.set();
	for(long long a = 2; a <= x; a++) if(bs[a]){
		for(long long b = a * a; b <= x; b += a) bs[b] = 0;
		primes.push_back((int) a);
	}
}

int main(){
	int N;

	sieve(1000000);
	scanf("%d", &N);
	for(int a = 0; a < N; a++){
		for(int b = 1; b < N-a; b++) printf("%-3c", ' ');
		for(int b = a; b >= 0; b--) printf("%-3d", primes[b]);
		printf("\n");
	}
}

Penjelasan :

Soal ini meminta kita untuk mencetak bilangan prima sesuai dengan pola pada contoh gambar di atas. Kali ini kita menggunakan teknik yang bernama Sieve of Eratosthenes.

Saya mempelajari bentuk optimisasi fungsi Sieve of Eratosthenes tersebut dari buku Competitive Programming 3 (by Steven Halim & Felix Halim), jadi bila diperhatikan potongan fungsi di atas memang mirip.

Pada baris 22 dan 23, for-loop yang berindeks mewakili buah baris dan yang berindeks b pertama mewakili banyaknya karakter spasi yang perlu dicetak pada setiap baris ke-yaitu N-a buah, sedangkan for-loop berindeks kedua mewakili banyaknya bilangan prima yang perlu dicetak agar sesuai dengan pola dari soal yaitu a+1 buah untuk setiap baris ke-a.

Leave a Reply

Your email address will not be published. Required fields are marked *