9 4
6 3
5 8
Yukarıdaki yapıda birbiriyle doğrudan komşu olanlar için 6x6 bir matriste karşılık gelen indekse 1, olmayanlar için 0 yazılacak.
9 4 6 3 5 8
9 0 1 1 0 0 0
4 1 0 0 1 0 0
6 1 0 0 1 1 0
3 0 1 1 0 0 1
5 0 0 1 0 0 1
8 0 0 0 1 1 0
Bu sorun için iki farklı sürüm yazıldı. Bunlar:
- gridKomsularibulV1
- gridKomsularibulV2
Çözüm koduna buradan ulaşılabilir.
- Matris boyutu kadar döngüde kal.
- Herbir grid elemanı indeksi (sıradaki) için tüm grid elemanlarının indekslerini gez.
- Sıradaki satır indeksi ile bakılan elemanın satır indeksi farkı mutlak(1) ise matriste yatay ve dikey indekse denk gelen hücre değerine 1 yükle.
- Veya sıradaki sütun indeksi ile bakılan elemanın sütun indeksi farkı mutlak(1) ise matriste yatay ve dikey indekse denk gelen hücre değerine 1 yükle.
- Kalan her şey için matriste yatay ve dikey indekse denk gelen hücre değerine 0 yükle.
- Bakılan her eleman için matris yatay indeksini 1 artır.
- Sıradaki her elemana bakıldıktan sonra matris indeksini 1 artır.
- Gridin satır sayısı kadar dön.
- Gridin herbir sütunü için:
- Gridin satır ve sütun indeksini Matrisin satır indeksine dönüştür: (
matrixstr = a * (GRIDSTR - 1) + b
) - Matrisin herbir sütunu için:
- Taranacak grid sütun indeksi (
stnind
) sona ulaştıysa sıfırla ve taranacak gridin bir sonraki satırına geç; satır indeksini (strind
) 1 artır. - Satır komşuluğunu yokla. Satır komşuluğu için gereken koşullar:
- Taranan gridin sütun indeksi ile ana döngünün sütun indeksi aynı ve taranan gridin satır indeksi ile ana döngünün satır indeksi arasındaki fark mutlak(1) olmalı.
- Sütun komşuluğunu yokla. Sütun komşuluğu için gereken koşullar:
- Taranan gridin satır indeksi ile ana döngünün satır indeksi aynı ve taranan gridin sütun indeksi ile ana döngünün sütun indeksi arasındaki fark mutlak(1) olmalı.
- Yoklamaların sonuçlarını XOR (^) işleminden geçirerek matriste hesaplanan indekslere denk gelen yere kaydet.
- Taranan gridin sonraki sütununa geç (sütun indeksini 1 artır).
- Taranacak grid sütun indeksi (
- Gridin satır ve sütun indeksini Matrisin satır indeksine dönüştür: (
Benchmark işlemi doğrudan kod içerisinde olup yalnızca algoritmaların ölçümü yapılmıştır. Benchmark sonuçları donanımdan donanıma ve sistemden (OS) sisteme değişiklik gösterebilir. Hatta aynı sistemde arka arkaya çalıştırılınca herbir çalışma için bile farklı sonuçlar verebilir.
Benchmark ölçmü yalnızca algoritmalara uygulanmış olup ilgisiz yerler hariç tutulmuştur. Kendi sistemimde yaptığım testlerin sonuçları şöyle:
Çözüm sürümü | Benchmark (ns) |
---|---|
gridCozum_v1 | 1779 |
gridCozum_v2 | 1651 |
İşletim sistemi: openSUSE Tumbleweed 20240502
KDE Plasma sürümü:* 6.0.4
KDE Frameworks sürümü: 6.1.0
Qt sürümü: 6.7.0
Çekirdek sürümü: 6.8.8-1-default (64 bit)
Grafik platformu: X11
İşlemciler: 12 × 11th Gen Intel® Core™ i5-11400H @ 2.70GHz
Bellek: 7,5 GiB RAM
Grafik işlemcisi: Mesa Intel® UHD Graphics
Üretici: ASUSTeK COMPUTER INC.
Ürün adı: ASUS TUF Gaming F15 FX506HF_FX506HF
0 1
0 9 4
1 6 3
2 5 8
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 0 0
Algoritma v1 sonuç:
0 1 2 3 4 5
0 0 1 1 0 0 0
1 1 0 0 1 0 0
2 1 0 0 1 1 0
3 0 1 1 0 0 1
4 0 0 1 0 0 1
5 0 0 0 1 1 0
Algoritma v1 sonuçları temizleniyor...
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 0 0
V1 Algoritması çalışma süresi (nanosaniye): 1812.000000
V2 Algoritması çalışma süresi (nanosaniye): 1704.000000
Algoritma v2 sonuç:
0 1 2 3 4 5
0 0 1 1 0 0 0
1 1 0 0 1 0 0
2 1 0 0 1 1 0
3 0 1 1 0 0 1
4 0 0 1 0 0 1
5 0 0 0 1 1 0