Binary Reflected Gray Code

Kategori: Popular Algorithms , 17 Kasım 2019 , JanFranco


Problem:

Kullanıcıdan aldığımız n sayısı uzunluğunda gray code üreteceğiz. Örneğin 2 girilirse, 00, 01, 11 ve 10. İkili sayı sisteminde her adımda sadece bir değişiklik yaparak ardışık ürettiğimiz sayılara gray kodu denir.

Yaklaşım:

Daha önce yazılmış bir algoritmayı Java'da implemente edelim. İlk olarak pseudo code'u inceleyelim:

ALGORITHM BRGC(n)

if n = 1 make list L containing bit strings 0 and 1 in this order
else generate list L1 of bit strings of size n - 1 by calling BRGC(n - 1)
     copy list L1 to list L2 in reversed order
     add 0 in front of each bit string in list L1
     add 1 in front of each bit string in list L2
     append L2 to L1 to get list L
     return L

n sayısını iki girdiğimizi düşünelim. Bu durumda ilk olarak BRGC(1) fonksiyonu çağırılacak. Bu fonksiyonda n = 1 olduğundan ilk if bloğu çalışacak, else bloğu çalışmayacak. "0" ve "1" stringlerini barındıran L adında bir liste oluşacak. BRGC(2) fonksiyonunu çağırmıştık. BRGC(1) fonksiyonundan bize L listesi döndü. L listesini ters çevirip L2 listesine atıyoruz. L listesindeki her bir stringin başına "0", L2 listesindeki her bir stringin başına "1" ekliyoruz. Daha sonra L2 listesini L listesine ekliyoruz.

Çözüm:




import java.util.ArrayList;

public class BRGC {
	
	public static ArrayList<String> L = new ArrayList<>();
	
	public static void printArrList(ArrayList<String> arrList) {
		for(String s : arrList) {
			System.out.print(s + " ");
		}
	}
	
	public static void BinaryReflectedGC(int n) {
		if(n == 1) {
			L.add("0");
			L.add("1");
		}
		else {
			BinaryReflectedGC(n-1);
			ArrayList<String> L2 = new ArrayList<>();
			for(int i=L.size()-1; i>=0; i--) {
				L2.add(L.get(i));
			}
			for(int i=0; i<L2.size(); i++) {
				L.set(i, "0" + L.get(i));
				L2.set(i, "1" + L2.get(i));
			}
			for(int i=0; i<L2.size(); i++) {
				L.add(L2.get(i));
			}
			printArrList(L);
			System.out.print("\n");
		}
	}
	
	public static void main(String[] args) {
		BinaryReflectedGC(4);
	}

}

>>

00 01 11 10 
000 001 011 010 110 111 101 100 
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000


Sonraki Yazı: Binary Search Algorithm
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın