Hamming sayıları
Hamming sayıları ilk kez Richard Hamming tarafından tanımlanmış bir sayı dizisidir. Bunlar pozitif tam sayılar olup çarpanları sadece 2, 3 ve 5'in kuvvetleridir. İlk birkaç Hamming sayısı şunlardır: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ... Hamming sayıları k-düzgün sayıları denen sayılar kategorisinin bir özel halidir. Bu tür sayıların kdan büyük asal çarpanı yoktur. Dolayısı ile Hamming sayıları da 5-düzgün sayılardır. Hamming sayılarını artan sırada hesaplama algoritmaları Edsger Dijkstra tarafından yaygınlaştırılmıştır.
Dijkstra'ya göre Hamming sayılarını hesaplamak 1'den büyük ve 2, 3 veya 5 haricinde asal çarpanı olmayan, yani 2^i x 3^j x 5^k (i, j, k ≥ 0) şeklindeki, sonsuz sayı dizisini kurmak demektir. Bunu hesaplamak için aşağıdaki adımlar takip edilir.
- h bir Hamming sayısı ise 2h, 3h ve 5h de Hamming sayılarıdır.
- 1 bir Hamming sayısıdır ve hesaplamayı başlatmak için kullanılır.
- Dizinin sıralı olması için 2, 3 ve 5 ile çarpmadan gelecek ve henüz kullanılmamış olan sayıları kıyaslamak yeterlidir. Diğer çarpımlar bunların bir kısmından daha büyük olacaktır, dolayısı ile sıralı listedeki ilk eleman olamazlar.
Bu algoritma sık sık tembel fonksiyonel programlama dillerinin gücünü göstermek için kullanılır çünkü böyle bir dilde yukarıdaki adımları doğrudan uygulamak mümkün iken bir katı fonksiyonel programlama dili ile ya da bir imperatif programlama dili ile bunu gerçekleştirmek basit bir iş değildir.
Dış bağlantılar
[değiştir | kaynağı değiştir]- Tam sayı Dizileri Ansiklopedisi A051037
- Mathworld'deki Düzgün Sayılar Sayfası [1][ölü/kırık bağlantı]
- Dijkstra algoritmasının temel fonksiyonel dillerden biri olan Haskell ile 5 satırlık uygulaması [2]12 Mart 2007 tarihinde Wayback Machine sitesinde arşivlendi.
- Dijkstra algoritmasının C# programlama dili ile uygulaması [3]16 Şubat 2007 tarihinde Wayback Machine sitesinde arşivlendi.