 |
kişisel web sayfası, yazılar, yorumlar, makaleler, özgeçmiş
her şey hakkında bir şey veya bir şey hakkında hiç bir şey... |
    |
|
MORS kombinasyonlarını bulma algoritması (29 Haziran 2008) Oldum olası severim Mors alfabesini. Eskiden telgraf çekmek için kullanılırmış, hatta telgraf memurları arasında yarışmalar düzenlenirmiş en hızlı kim yazacak diye. Biz unicode da bir karakteri 16 bit le ifade ederken abiler 4 bite dünyaları sığdırmışlar (dezenformasyon yapıyorum). Mors alfabesi aşağıdaki gibi: A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. Mesela ALI yazmak için (Türkçe karakterler Mors alfabesinde yok, ama yerelleştirilmiş Mors alfabelerinde var) .- .-.. .. yazmak gerekiyor, harf aralarında boşluk bırakarak. Ancak düşünün ki, arkadaşın biri, aralarda boşluk bırakmayı unutmuş: .-.-.... Bu basit kodda dahi 96 kombinasyon var. 3-8 harfli 96 kelime yazılabilir. Mesela burada ETLI veya EKSE yazmadığını nereden bileceğiz? Bunu bilmenin bir tek yolu var :) O da kombinasyonları tespit etmek. Hadi başlayalım. Öncelikle mors alfabesini bir HashTable a alalım: MorseCodes.Add("A", ".-") MorseCodes.Add("B", ".---") MorseCodes.Add("C", "-.-.") MorseCodes.Add("D", "-..") MorseCodes.Add("E", ".") MorseCodes.Add("F", "..-.") MorseCodes.Add("G", "--.") MorseCodes.Add("H", "....") MorseCodes.Add("I", "..") MorseCodes.Add("J", ".---") MorseCodes.Add("K", "-.-") MorseCodes.Add("L", ".-..") MorseCodes.Add("M", "--") MorseCodes.Add("N", "-.") MorseCodes.Add("O", "---") MorseCodes.Add("P", ".--.") MorseCodes.Add("Q", "--.-") MorseCodes.Add("R", ".-.") MorseCodes.Add("S", "...") MorseCodes.Add("T", "-") MorseCodes.Add("U", "..-") MorseCodes.Add("V", "...-") MorseCodes.Add("W", ".--") MorseCodes.Add("X", "-..-") MorseCodes.Add("Y", "-.--") MorseCodes.Add("Z", "--..") Bunu Form_Load içerisinde yapabilirsiniz. Daha sonra, esas işimizi yapacak olan fonksiyonumuzu yazalım: Private Function Recurse(ByVal MorseCode As String, Optional ByVal Prefix As String = "") As List(Of String) İki parametre alan bir fonksiyonumuz var. Tahmin ettiğiniz gibi rekürsif olarak çalışacak. Bu nedenle bir Prefix parametresi alıyor. Rekürsif çözümler hakkında bir fikriniz yoksa biraz araştırmanızı öneririm. Özellikle karar ağaçlarında ve ağaç yapılarında çok işlevsel bir yöntem. Rivayete göre, her rekürsif çözümün bir iteratif çözümü varmış, ama kim takar ki :) Call Stack büyümüş-müş banane :) Bu kadar geyik yeter, fonksiyonumuzu yazmaya başlayalım: Öncelikle yapıyı biraz açıklayayım. Şimdi, yukarıdaki Mors kodunu ele aldık diyelim: .-.-.... Bu kodu soldan başlayarak karakterlere çevirmeye çalışıyoruz. Mesela en soldaki karakter E olsun (tabi ki başka bir şey de olabilir ama delikanlı algoritmamız bunu da algılayacak) E -.-.... E’den sonraki kısma yine aynı işi yaptırmak gerekiyor, Bunun da T olduğunu farz edelim, yine kalan kısma aynı işi yaptırmak lazım. Yani tam bir rekürsif yöntemle çözülecek problem tanımı. Ama nereye kadar diyorsanız (ki rekürsif yöntemlerin en önemli noktası budur-aksi takdirde kısır döngüye girersiniz) tabi ki en sağa gelene yani işlenecek hiç bir Mors kodu kalmayana kadar... Bunu da şu şekilde yazıyoruz: If MorseCode = "" Then Results.Add(Prefix) Ee, madem kelimenin sonuna geldik, bari bulduğumuz şeyi çözümlerimiz arasına ekleyelim ki araya gitmesin. Else Diyelim ki hala işlenecek karakterler var, For Each val As String In MorseCodes.Values o zaman soldan başlayarak bunları MorsCodes hashtable ındaki karakterlerle eşleştirmeye çalışalım: If MorseCode.Length >= val.Length AndAlso MorseCode.Substring(0, val.Length) = val Then Yani, Fonksiyona parametre olarak gelen Mors kodunun uzunluğunun Hash tablosundan aldığımız değerden daha kısa olmaması gerekiyor ki karşılaştırma yapalım. AndAlso kullanımına dikkat, bu da VB.NET 2.0 la gelen bir anahtar kelime ve bence çok şık. Results.Concat(Recurse(MorseCode.Substring(val.Length), Prefix & GetCode(val))) İşte, recursion burada. Ne yaptığımızı tahmin edebiliyor musunuz? Results listesine yeni sonuçlar ekliyoruz. Recurse(MorseCode.Substring(val.Length), Prefix & GetCode(val)) Kullanıma dikkat edelim. Birinci parametre, Mors kodunun geri kalan kısmıydı hatırlarsanız. MorseCode.Substring(val.Length) ifadesi val.Length, yani tespit ettiğimiz kodun uzunluğundan itibaren geri kalan mors kodunu al demektir. Recurse ettiğimiz fonksiyonun ikinci parametresine ise, tespit ettiğimiz kodun harf değerini ekliyoruz. Ayrıntıları vereceğim. End If Next End If Return Results End Function Oluşturduğumuz sonuç dizisini bir önceki sonuç listesine eklenmek üzere geri döndürüyoruz, Yukarıda adı geçen GetCode fonksiyonu da şu şekilde tanımlanabilir: Private Function GetCode(ByVal Morse As String) As Char For Each key In MorseCodes.Keys If MorseCodes(key) = Morse Then Return key Next End Function Results dizisini de kod içerisinde herhangi bir yerde class seviyesinde tanımlamayı unutmayın: Dim Results As New List(Of String) Bundan sonrası size kalmış. İsterseniz ListBox da gösterin, isterseniz dosyaya veya web sayfasına yazın: lbxKmb.Items.AddRange(Recurse(tbxMrs.Text).ToArray()) Kafa karıştırıcı mı, tekrar inceleyelim isterseniz: -.-.... kodunu çözmeye çalışıyoruz, fonksiyonu çağıralım, Results=boş 1- Recurse(“.-.-....”, “”) 2- Recurse(“-.-....”, “E”) 3- Recurse(“.-....”, “ET”) 4- Recurse(“-....”, “ETE”) 5- Recurse(“....”, “ETET”) 6- Recurse(“...”, “ETETE”) 7- Recurse(“..”, “ETETEE”) 8- Recurse(“.”, “ETETEEE”) 9- Recurse(“”, “ETETEEEE”) O da ne? Birinci parametrenin uzunluğu sıfır oldu, o zaman ikinci parametreyi sonuçlara ekliyoruz: Results: 1- “ETETEEEE” Ve 7. adımda, .. kodunun E ile başlamadığını farz ederek devam ediyoruz: 7a- Recurse(“..”, “ETETEE”) 8a- Recurse(“”, “ETETEEI”) işte yine oldu, birinci parametrenin boyu yine sıfır, hadi o zaman bunu da ekleyelim : Results: 1- “ETETEEEE” 2- “ETETEEI” Bu sefer 6. adıma giderlim: 6b- Recurse(“...”, “ETETE”) 7b- Recurse(“”, “ETETES”) Sonuçlar yine değişti : Results: 1- “ETETEEEE” 2- “ETETEEI” 3- “ETETES” bu böyle, hiç bir kombinasyon kalmayana kadar devam edecek. Tüm kodu burada bulabilirsiniz : Private MorseCodes As New Hashtable Private Sub frmMorse_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load MorseCodes.Add("A", ".-") MorseCodes.Add("B", ".---") MorseCodes.Add("C", "-.-.") MorseCodes.Add("D", "-..") MorseCodes.Add("E", ".") MorseCodes.Add("F", "..-.") MorseCodes.Add("G", "--.") MorseCodes.Add("H", "....") MorseCodes.Add("I", "..") MorseCodes.Add("J", ".---") MorseCodes.Add("K", "-.-") MorseCodes.Add("L", ".-..") MorseCodes.Add("M", "--") MorseCodes.Add("N", "-.") MorseCodes.Add("O", "---") MorseCodes.Add("P", ".--.") MorseCodes.Add("Q", "--.-") MorseCodes.Add("R", ".-.") MorseCodes.Add("S", "...") MorseCodes.Add("T", "-") MorseCodes.Add("U", "..-") MorseCodes.Add("V", "...-") MorseCodes.Add("W", ".--") MorseCodes.Add("X", "-..-") MorseCodes.Add("Y", "-.--") MorseCodes.Add("Z", "--..") End Sub Private Sub btnDecode_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnDecode.Click lbxKmb.Items.AddRange(Recurse(tbxMrs.Text).ToArray()) End Sub Dim Results As New List(Of String) Private Function Recurse(ByVal MorseCode As String, Optional ByVal Prefix As String = "") As List(Of String) If MorseCode = "" Then Results.Add(Prefix) Else For Each val As String In MorseCodes.Values If MorseCode.Length >= val.Length AndAlso MorseCode.Substring(0, val.Length) = val Then Results.Concat(Recurse(MorseCode.Substring(val.Length), Prefix & GetCode(val))) End If Next End If Return Results End Function Private Function GetCode(ByVal Morse As String) As Char For Each key In MorseCodes.Keys If MorseCodes(key) = Morse Then Return key Next End Function Kolay gelsin. Not: ALI ile aynı Mors kodlarını paylaşan kelimeler şunlar: RTSE RTH RTII RTIEE RTES RTEIE RTEEI RTEEEE RNS RNIE RNEI RNEEE RDI RDEE ARS ARIE AREI AREEE ALI ALEE AASE AAH AAII AAIEE AAES AAEIE AAEEI AAEEEE AETSE AETH AETII AETIEE AETES AETEIE AETEEI AETEEEE AENS AENIE AENEI AENEEE AEDI AEDEE ETRS ETRIE ETREI ETREEE ETLI ETLEE ETASE ETAH ETAII ETAIEE ETAES ETAEIE ETAEEI ETAEEEE ETETSE ETETH ETETII ETETIEE ETETES ETETEIE ETETEEI ETETEEEE ETENS ETENIE ETENEI ETENEEE ETEDI ETEDEE EKSE EKH EKII EKIEE EKES EKEIE EKEEI EKEEEE ENTSE ENTH ENTII ENTIEE ENTES ENTEIE ENTEEI ENTEEEE ENNS ENNIE ENNEI ENNEEE ENDI ENDEE ECS ECIE ECEI ECEEE Geri Dön | Ana Sayfa |
(evet, bildiniz siz bir dahisiniz Windows Vista 'dan arakladim)
|
Son güncelleme:
20 Ağustos 2008 14:08
Bu sayfadaki içeriği izinsiz kopyalayan eşek kulaklıdır.
© Ali AYEN Ankara - 2007
Bu sayfadaki içeriği izinsiz kopyalayan eşek kulaklıdır.
© Ali AYEN Ankara - 2007