Peter, John Stephanus (2017) Penyelesaian permasalahan Ulam pada permasalahan SPOJ klasik 17320 Guess The Number With Lies v3. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5113100106-Undergraduate_Theses.pdf - Published Version Download (3MB) | Preview |
Abstract
Permasalahan Ulam adalah permasalahan klasik yang dimulai pada tahun 1976. Permasalahan asli dari Permasalahan Ulam adalah permasalahan mencari banyak pertanyaan minimum untuk mencari sebuah bilangan dari 1 hingga 1.000.000, jika penjawab boleh berbohong paling banyak satu kali selama proses pencarian.
Pada Tugas Akhir ini, akan dirancang penyelesaian permasalahan Ulam dalam pencarian bilangan pada rentang yang diberikan, dengan batasan maksimal rentang adalah 1018. Permasalahan ini dapat diselesaikan dengan menggunakan beberapa teori dan lemma, dan membuat 2 buah set, yaitu truth-set dan lie-set. Beberapa hal yang harus diperhatikan adalah mengenai cara mengatasi overflow dan mengatur elemen-elemen pada truth-set dan lie-set. Tipe data yang banyak digunakan pada permasalahan ini adalah long double dan long long, sedangkan struktur data yang digunakan untuk mengatur elemen pada truth-set maupun lie-set adalah struktur data set dengan tipe pair.
Hasil dari tugas akhir ini telah berhasil menyelesaikan permasalahan di atas dengan cukup efisien, dengan rata-rata waktu penyelesaian 1.000 permainan dalam 0,17 detik dengan penggunaan memori 2,8 MB.
==================================================================
Ulam’s problem is a classic mathematical problem stated on 1976. The original Ulam’s Problem was about to find the minimal number of yes-no questions needed to find an integer between one and one million, if one lie is allowed among the answers.
This undergraduate thesis will design the problem solving of modified Ulam’s problem on searching a number with a given range, with the maximum constraint of the range is 1018. This problem is solved within the help of 2 sets, truth-set and lie-set, and using some lemmas. Some conditions which should be carefully considered during the implementation including how to handle overflow and how to manage the elements of the truth-set and lie-set. Long double and long long data type is frequently used in this undergraduate thesis, with the combination with set and pair data structure.
The result shows that Ulam’s problem is successfully solved efficiently with average time of 0.17 seconds and memory use of 2.8 MB to solve 1,000 games.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Permasalahan Ulam, Set, Pair, Lemma, Bohong |
| Subjects: | Q Science > QA Mathematics > QA269 Game theory |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | John Stephanus Peter |
| Date Deposited: | 02 Feb 2018 01:52 |
| Last Modified: | 08 Mar 2019 02:41 |
| URI: | http://repository.its.ac.id/id/eprint/46264 |
Actions (login required)
 |
View Item |