Archive for 2018
PENGERTIAN TREE
Kumpulan node yang saling terhubung satu sama lain dalam
suatu kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon
adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara
grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai
kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier
yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara
elemen-elmennya.
ISTILAH DALAM TREE
Gambar 1.1 Istilah dalam Tree
Ilustrasi alogaritma tree
Gambar 1.2 Ilustrasi Algoritma Tree
Keterangan :
Ancesor (F) = C, A
Descendant(C) = F,G
Parent (D) = B
Child (A) = B, C
Sibbling (F) = G
Size = 7
Height = 3
Root = A
Leaf = D,E,F,G
Degree = 2
JENIS-JENIS TREE
BINARY TREE
Tree dengan syarat bahwa tiap node hanya boleh memiliki
maksimal dua sub pohon dan kedua subpohon harus terpisah.
Kelebihan struktur Binary Tree :
- Mudah
dalam penyusunan algoritma sorting
- Searching
data relatif cepat
- Fleksibel
dalam penambahan dan penghapusan data
Gambar 1.4 Binary Tree
FULL BINARY TREE
Semua node, kecuali leaf pasti memiliki 2 anak dan tiap
subpohon memiliki panjang path yang sama.
Gambar 1.5 Full Binary Tree
COMPLETE BINARY TREE
Tree yang mirip dengan full binary tree, tapi tiap
subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf)
memiliki 2 anak.
Gambar 1.6 Complete Binary Tree
SKEWED BINARY TREE
Binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak.
Gambar 1.7 Skewed Binary Tree
Berikut adalah contoh progam :
//header file
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//pendeklarasian struct sebuah tree awal
struct Node{
int data;
Node *kiri;
Node *kanan;
};
//fungsi untuk menambahkan node baru
void tambah(Node **root, int databaru)
{
//jika root masih kosong
if((*root) == NULL)
{
//pembuatan node baru
Node *baru;
//pengalokasian memori dari node yang telah dibuat
baru = new Node;
//inisialisasi awal node yang baru dibuat
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf("Data bertambah!");
}
//jika data yang akan dimasukkan lebih kecil daripada elemen root, maka akan diletakkan di node sebelah kiri.
else if(databaru<(*root)->data)
tambah(&(*root)->kiri, databaru);
//jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan
else if(databaru>(*root)->data)
tambah(&(*root)->kanan, databaru);
//jika saat dicek data yang akan dimasukkan memiliki nilai yang sama dengan data pada root
else if(databaru == (*root)->data)
printf("Data sudah ada!");
}
//fungsi yang digunakan untuk mencetak tree secara preOrder
void preOrder(Node *root)
{
if(root != NULL){
printf("%d ", root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
//fungsi yang digunakan untuk mencetak tree secara inOrder
void inOrder(Node *root)
{
if(root != NULL){
inOrder(root->kiri);
printf("%d ", root->data);
inOrder(root->kanan);
}
}
//fungsi yang digunakan untuk mencetak tree secara postOrder
void postOrder(Node *root)
{
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d ", root->data);
}
}
//fungsi utama
int main()
{
//deklarasikan variabel
int pil, data;// c;
Node *pohon; //*t;
pohon = NULL; //inisialisasi node pohon
//perulangan do-while
do
{
system("cls"); //bersihkan layar
printf("\t#PROGRAM TREE C++#");
printf("\n\t==================");
printf("\nMENU");
printf("\n----\n");
printf("1. Tambah\n");
printf("2. Lihat pre-order\n");
printf("3. Lihat in-order\n");
printf("4. Lihat post-order\n");
printf("5. Exit\n");
printf("Pilihan : ");
scanf("%d", &pil);
switch(pil)
{
//jika pil bernilai 1
case 1 :
printf("\nINPUT : ");
printf("\n-------");
printf("\nData baru : ");
scanf("%d", &data);
//panggil fungsi untuk menambah node yang berisi data pada tree
tambah(&pohon, data);
break;
//jika pil bernilai 2
case 2 :
printf("\nOUTPUT PRE ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara preOrder
preOrder(pohon);
else
printf("Masih kosong!");
break;
//jika pil bernilai 3
case 3 :
printf("\nOUTPUT IN ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara inOrder
inOrder(pohon);
else
printf("Masih kosong!");
break;
//jika pil bernilai 4
case 4 :
printf("\nOUTPUT POST ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara postOrder
postOrder(pohon);
else
printf("Masih kosong!");
break;
}
_getch();
}while(pil != 5); //akan diulang jika input tidak samadengan 5
return EXIT_FAILURE;
}
Hasil Eksekusi Progam
Gambar 1.8 Tampilan Awal
Gambar 1.9 Tambah data
Gambar 2.0 Jika ditekan Menu 2
Gambar 2.1 Jika ditekan menu 3
Gambar 2.2 Jika ditekan menu 4
Gambar 2.3 Jika ditekan menu 5
Post By :
Tri Atmojo Sulaiman
Pend. Teknik Informatika
Referensi :
http://www.nblognlife.com/2014/12/tree-pada-c-tree-awal.html
Queue atau antrian merupakan suatu kumpulan data yang memiliki head/front dimana data dikeluarkan (dequeue) dan tail/rear dimana data dimasukkan (enqueue) ke antrian.
Proses QUEUE
Seperti halnya pada antrian yang biasa kita lakukan sehari-hari, di manapun. Antrian dimulai dari depan ke belakang, jika didepan belum pergi meninggalkan antrian maka antrian terus bertambah dari belakang dan antrian paling belakang disini dinamakan rear/tail.
Jadi selama antrian terus bertambah (enqueue) maka antrian yang paling akhir adalah tail/rear.
| front | ||||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| rear |
Jika ada yang keluar dari antrian (dequeue) maka data tersebut adalah yang paling depan (head/front), dan data berikutnya setelah data yang keluar berubah menjadi yang paling depan (head/front).
| front | |||||
|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | 7 |
| rear |
Queue menggunakan metode FIFO, dimana yang masuk pertama kali akan keluar pertama kali juga.
Berikut adalah contoh progam nya :
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
using namespace std;
const int MAX_ANTRIAN = 5;
struct orang
{
string nama;
int umur;
};
void buatAntrian(); // mengisi antrian kosong sebanyak MAX_ANTRIAN dengan variabel kontrol
void tampilkanMenu(); // menampilkan menu yang ada
void eksekusiPilihan(); // mengambil pilihan dari user dan eksekusi pilihan tersebut
void tambahAntrian(); // menambah antrian paling belakang
void kurangiAntrian(); // mengurangi antrian paling depan dan menampilkan orang yang keluar dari antrian
void printAntrian(); // menampilkan seluruh antrian yang ada
void printOrang(); // menampilkan data satu orang saja
//inisisalisasi variabel yang akan dipakai
orang antrian[MAX_ANTRIAN];
int pil, pripil, antri;
bool isEmpty = true; // penanda apakah antrian sedang kosong
bool isFull = false; // penanda apakah antrian sudah penuh
bool isOver = false; // penanda bahwa program selesai atau tidak
/**
* ================== MAIN PROGRAM ===================
*/
int main()
{
buatAntrian();
while(!isOver)
{
tampilkanMenu();
eksekusiPilihan();
}
system("pause");
return 0;
}
/**
* ============== END OF MAIN PROGRAM ================
*/
//mengisi data awal dari antrian
void buatAntrian()
{
int i;
for(i=0; i<MAX_ANTRIAN; i++)
{
antrian[i].nama = "null"; // antrian dikatakan kosong apabila nama = null
antrian[i].umur = -1; // dan umur = -1
}
}
//menampilkan menu utama
void tampilkanMenu()
{
system("cls");
cout << "(1) tambah antrian" << endl;
cout << "(2) kurangi antrian" << endl;
cout << "(3) print antrian" << endl;
cout << "(4) keluar dari program" << endl;
cout << "masukkan pilihan anda: ";
cin >> pil; //kesatu
}
//pemrosesan pilihan dari menu utama
void eksekusiPilihan()
{
if (pil == 1)
{
tambahAntrian();
}
else if (pil == 2)
{
kurangiAntrian();
}
else if (pil == 3)
{
//pada pilihan ini ditambahkan submenu print semua atau satu saja
cout << "(1) print semua antrian" << endl;
cout << "(2) print satu antrian" << endl;
cout << "pilihan : ";
cin >> pripil;
if (pripil == 1)
{
printAntrian();
}
else if (pripil == 2)
{
printOrang();
}
}
else if (pil == 4)
{
isOver = true;
}
}
//prosedur untuk penambahan data antrian
void tambahAntrian()
{
//diatur perulangan untuk memeriksa apakah ada antrian yang kosong
int i;
for(i=0; i<MAX_ANTRIAN; i++)
{
//jika ada antrian yang kosong, maka data bisa dimasukkan
if(antrian[i].nama == "null" && antrian[i].umur == -1)
{
cout << "antrian ke-" << i+1 << " > " << endl;
cout << "masukkan nama: ";
cin >> antrian[i].nama;
cout << "masukkan umur: ";
cin >> antrian[i].umur;
break;
}
//jika tidak ada yang kosong, maka tampilkan antrian penuh
else
{
if (i == MAX_ANTRIAN-1)
{
cout << "antrian penuh" << endl;
}
}
}
system("pause");
}
//prosedur untuk mengurangi pengantri pertama, lalu antrian setelahnya maju.
void kurangiAntrian()
{
int i;
//tampilkan data yang akan dihapus
cout << "antrian ke-1 telah dihapus" << endl;
cout << "nama: " << antrian[0].nama << endl;
cout << "umur: " << antrian[0].umur << endl;
//hapus data dengan mengisi "null" dan -1
antrian[0].nama = "null";
antrian[0].umur = -1;
//menggeser antrian ke atas
for(i=0; i<MAX_ANTRIAN-1; i++)
{
antrian[i].nama = antrian[i+1].nama;
antrian[i].umur = antrian[i+1].umur;
}
//mengisi antrian terakhir dengan data kosong
antrian[MAX_ANTRIAN-1].nama = "null";
antrian[MAX_ANTRIAN-1].umur = -1;
system("pause");
}
//prosedur menampilkan data semua antrian
void printAntrian()
{
int i;
for(i=0; i<MAX_ANTRIAN; i++)
{
cout << "antrian ke-" << i+1 << " > " << endl;
if(antrian[i].nama == "null" && antrian[i].umur == -1)
{
cout << "KOSONG" << endl;
}
else
{
cout << "nama: " << antrian[i].nama << endl;
cout << "umur: " << antrian[i].umur << endl;
}
}
system("pause");
}
//prosedur untuk menampilkan data antrian perorang
void printOrang()
{
cout << "antrian ke: ";
cin >> antri;
if(antrian[antri].nama == "null" && antrian[antri].umur == -1)
{
cout << "KOSONG" << endl;
}
else
{
cout << "nama: " << antrian[antri-1].nama << endl;
cout << "umur: " << antrian[antri-1].umur << endl;
}
system("pause");
}
Ketika Progam dijalankan:
Gambar 1.1 Tampilan Awal Progam
Gambar 1.2 Tampilan Eksekusi Pertama
Gambar 1.3 Hasil Eksekusi Penambahan daftar antarian
Gambar 1.4 Penambahan antrian ke tiga
Gambar 1.5 ketika daftar semua antrian di tampilkan
Gambar 1.6 Ketika Progam di tutup
Post by :
Tri Atmojo Sulaiman
Pend. Teknik Informatika
Referensi :
http://blogg.ing.web.id/posts/program-antrian-dengan-cpp-tanpa-linked-list/
https://bekti.net/blog/implementasi-queue-di-cpp
Saya akan memberikan penjelasan singkat tentang Finite State
Machine (FSM) pada game beserta contohnya dan Pseudocode. Pertama apakah itu
FSM, Finite State Machine (FSM) adalah sebuah metodologi perancangan sistem
kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan
menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan action
(aksi). Sebagai sebuah metodologi perancangan sistem kontrol, penerapan FSM
telah banyak diterapkan pada perangkat lunak, khususnya pada game.
PSEUDOCODE
using UnityEngine;
using System.Collections;
public class GameFSM : MonoBehaviour {
public enum
{LevelAwal, diam, melompat, benda, soal, kunci, menembak, menghindar, musuh,
nyawa, GameOver, NextLevel}
public TurnStates state;
public bool gameInProgress = true;
void Start () {
state =
GameFSM.Mulai.Init;
StartCoroutine
("TurnFSM");
}
private IEnumerator TurnFSM (){
while(gameInProgress){
switch(state){
case
TurnStates.LevelAwal:
if( Permainan
Awal()) {* state = diam:}
break;
case
TurnStates.diam:
if(Mulai()) {*
state = jump;}
break;
case
TurnStates.melompat:
if( Melompat()) {*
state = benda;}
break;
case
TurnStates.benda:
if( mencari
benda()) {* state = soal;}
if (menghindar ()) {*
state = Musuh;}
break;
case
TurnStates.benda:
if( mencari Benda
()) {* state = soa;}
if(Menembak()) {*
state = Musuh;}
break;
case
TurnStates.musuh:
if( Terkena Enemy
()) {* state = nyawa;}
Break;
case
TurnStates.soal:
if( benar ()) {*
state = kunci;}
else (salah ()) {*
state = nyawa;}
break;
case
TurnStates.nyawa:
if(nyawa masih
tersedia ()) {* state = diam;}
else (nyawa masih
habis ()) {* state = GameOver;}
Break;
case TurnStates.Kunci:
if( berhasil
menjawab()) {*state = NextGame;}
break;
case
TurnState.NextGame :
if (DoneLevel ()) {*
state = LevelBaru;}
break;
}
yield return null;
}
}
Tri Atmojo Sulaiman
Pend. Teknik Informatika
Referensi :
http://gamedevelopertips.com/finite-state-machine-game-developers/
https://forum.unity.com/threads/implementing-finite-state-machine-ai-c.287401/
