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 a‰¥ 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.
Harici bağlantılar
- Tamsayı Dizileri Ansiklopedisi A051037
- Mathworld`deki Düzgün Sayılar Sayfası [1]
- Dijkstra algoritmasının temel fonksiyonel dillerden biri olan Haskell ile 5 satırlık uygulaması [2]
- Dijkstra algoritmasının C# programlama dili ile uygulaması [3]