Best Praktis Basic Golang -Part 2
Belajar Dasar Golang dengan Algoritma (Euler Project)
Pada artikel sebelumnya yang berjudul Best Praktis Basic Golang -Part 1 kita telah membahas sekitar lima solusi dari soal-soal yang ada pada Euler Project. Berikut adalah bagian kedua kita belajar basic golang dengan bantuan menyelesaikan beberapa soal algoritma yang ada dalam Euler Project.
Soal Ke Enam, Jumlah Selisih Kuadrat
Soal ke enam pada euler project adalah membahas cara menghitung jumlah selisih kuadrat dari suatu deret angka yang memiliki pola tertentu. Berikut adalah detil dari soalnya tersebut.
Jumlah kuadrat dari sepuluh bilangan asli pertama adalah,
Kuadrat jumlah dari sepuluh bilangan asli pertama adalah,
Oleh karena itu, selisih antara jumlah kuadrat dari sepuluh bilangan asli pertama dan kuadrat dari jumlah tersebut adalah 3025–385=2640.
Temukan selisih antara jumlah kuadrat dari seratus bilangan asli pertama dan kuadrat dari jumlah tersebut!
Solusi soal di atas cukup mudah, kita dapat menyelesaikannya dengan menggunakan iterasi sebanyak seratus kali dan lakukan penjumlahan setiap bilangan serta menjumlahkan hasil kuadrat masing-masing bilangan tersebut.
Solusi untuk soal ke enam ini mungkin lebih mudah dari soal-soal yang sudah kita kerjakan. Akan tetapi, solusi ini merupakan pedekatan yang kurang baik jika banyaknya data yang kita hitung mencapai juataan ! Lamanya waktu prosses pengerjaan adalah linear O(n). Walaupun memang solusi nya termasuk yang terbaik tetapi kita masih dapat menyelesaikannya dengan pendetakan analisis matematik.
Penyelesaian dengan code kita di atas dikenal dengan Numerical Analisis walaupun masih sederhana sedangkan pedekatan analisis simbolis atau rumus adalah sebagai berikut.
Berdasarkan rumus-rumus matematika untuk menyelesaikan penjumlahan angka sampai batas tertentu dikenal dengan Gauss Formula atau Gauss Methode.
Adapun jumlah dari kuadrat suatu deret angka adalah sebagai berikut.
Sehingga solusinya untuk soal ke enam ini jika menggunakan dua rumus di atas adalah,
Apabila kedua code di atas kita gunakan untuk menghitung sampai angka 100.000 maka hasil output soalnya sebagai berikut,
Cara Numerik
Selisis Jumlah Kuadrat Adalah : 6553422590457098384
Waktu eksekusi 81000 nano secondProcess finished with exit code 0
Cara Simbolis
Selisis Jumlah Kuadrat Adalah : 6553422590457098384
Waktu eksekusi 24000 nano secondProcess finished with exit code 0
Jelas cara simbolis lebih cepat dan nilainya akan selalu konstan berapun batas atas bilangan yang kita hitung. Dalam Big O Notation cara simbolis ini memiliki kompleksistas O(1).
Soal Ke Tujuh, Bilangan Prima ke 10001
Soal ke tujuh dari project euler adalah menentukan bilangan prime ke n.
Dengan mendaftar enam bilangan prima pertama: 2, 3, 5, 7, 11, dan 13, kita dapat melihat bahwa bilangan prima ke-6 adalah 13.
Berapakah bilangan prima 10001?
Bilangan prima adalah bilangan spesial yang sangat berguna baik itu dalam ilmu matematika, teknologi, dan ilmu komputer. Banyak algoritma-algoritma yang banyak digunakan dan selalu berhubungan dengan bilangan prima ini.
Contoh adalah RSA Algoritma yang pasti melibatkan bilangan prima. Solusi untuk bilangan prime ini sangat beragam dari mulai algoritma sederhana melalui looping sederhana sampai ke pendekaan algoritma yang cukup kompleks.
Kita coba solusi sederhana dengan pengulanan. Pengertian bilangan prima adalah bilangan yang hanya habis dibagi dengan angka satu dan angkanya sendiri. Contoh umum bilangna prima yang mudah dihafal adalah, 2, 3, 5, 7, 11.
Kode di atas hampir sama dengan solusi soal ke tiga. Kita melakukan modifikasi sedikit yaitu mencari uruan prima ke -n dengan pengulanan yang terjadi terus-menerus sampai kondisi terhenti kita break proses. for ; ; i++salah satu cara melakukan pengulanan terus menerus dan break pada satu kondisi tertentu.
Jika kita eksekusi kode di atas maka outoutnya sebagai berikut.
104743
Waktu eksekusi 28 milli second
Untuk kasus soal ini mungkin waktu pengerjaan cukup cepat, tetapi bila bilangan yang di cari semakin membesar maka solusi ini sangat buruk karena bersipat kuadratik.
Sampai sekarang solusi tercepat yang bisa di gunakan untuk mencari bilangan prima adalah algoritma Lucas–Lehmer. Mungkin pada artikel tententu akan kita coba bahas mengenai algoritma ini.
Soal Ke Delapan, Hasil Perkalian Terbesar dari Deret Angka
Soal ke delapan dari project euler adalah menentukan hasil perkalian terbesar dengan detil soal sebagai berikut.
Empat digit yang berdekatan pada bilangan 1000 digit yang memiliki hasil kali terbesar adalah 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450Temukan tiga belas digit yang berdekatan dalam angka 1000-digit yang memiliki hasil kali terbesar. Berapa nilai produk ini?
Untuk dapat menyelesaikan soal di atas agar lebih mudah deretan angka di atas harus kita pindahkan dahulu ke dalam bentuk string agar memudahkan pengolahan data.
berikut adalah solusi termudah tetapi belum mementingkan performance yang dihasilkan.
Deretan angka dalam bentuk konstanta di atas akan kita bersihkan dari karakter-karater yang tidak dibutuhkan. Di sini kita melakukan pengulangan dua kali. Pertama mengulan dari angka pertama sampai angka terakhir kurang 13. Kedua adalah pengulangan di dalam loop pertama untuk mengalikan semu data sampai ke 13 dan dilakukan pengecekand harsil maksimumnya.
Apabila kita jalankan kode di atas maka hasilnya adalah seperti berikut.
23514624000
Waktu eksekusi 48000 nano second
Soal Ke Sembilan, Segitiga Pytagoras
Soal ke sembilan berbicara mengenai dalil Pytagoras yang berlaku untuk segitiga siku-siku. Berikut adalah soalnya.
Triplet Pythagoras adalah himpunan tiga bilangan asli, a < b < c , yang darinya,
Misalnya, 3 *3 + 4*4 = 9 + 16 = 25 = 5*5.
Terdapat tepat satu triplet pythagoras yang a + b + c = 1000.
Tentukan hasil kali abc .
Soal di atas akan kita coba solusinya dengan pendekatan brute force. Mungkin kedepannnya akan ada algoritnya yang lebih baik untuk menyelesaikan persoalan ini.
Bila kita eksekusi code di atas akan menghasilkan output sebagai berikut.
200 + 375 + 425 = 1000, product = 31875000
Waktu eksekusi 160 milli second
Soal Ke Sepuluh, Penjumlahan Bilangan Prima
Jumlah bilangan prima di bawah 10 adalah 2 + 3 + 5 + 7 = 17.
Temukan jumlah semua bilangan prima di bawah dua juta .
Untuk yang ini, kita perlu menggunakan kembali isPrime()
fungsi kita . Pada dasarnya, kita perlu beralih dari 2 ke 2000000 dan memeriksa setiap nomor. Jika bilangan prima, maka tambahkan ke variabel.
Bila kita eksekusi code di atas akan menghasilkan output sebagai berikut.
142913828922
Waktu eksekusi 294 mili second
Strategi Saya Untuk Mempelajari Dasar-dasar Bahasa Pemrograman
Misalnya saya ingin belajar Ruby, Java, Clojure, atau Haskell, saya akan membuat akun di Project Euler atau menyelesaikan beberapa soal algoritma yang ada secara langsung serta mencoba menyelesaikan 10 masalah pertama.
Setelah saya selesai, saya kembali ke masalah pertama dan mencoba mengubah kode berdasarkan teknik refactoring yang saya ketahui dari bahasa pemrograman lain dengan tujan untuk meningatkan performance dan kode lebih mudah terbaca. Dengan begitu kita akan semakin memahami dasar-dasar pemograman pada bahasa yang sedang kita pelajari.
Untuk selanjutnya soal-soal algoritma memang bagus utuk memperlajari hal-hal dasar dan logical tetapi pemograman tidak selamanya mengenai logical, selanjutnya kita akan mempelajari konsep Concurrency pada Golang salah satunya Go Routine dan best praktisnya.
References
- https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
- https://en.wikipedia.org/wiki/RSA_(cryptosystem)
- https://nrich.maths.org/2478
- https://en.wikipedia.org/wiki/Numerical_analysis
Sponsor
Membutuhkan kaos dengan tema pemrograman :
Dapat menghubungi The Legend.