--- title: 'Hızlı ve Yavaş İşaretçi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/hizli-ve-yavas-isaretci' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:29+00:00' license: 'CC BY-SA 4.0' --- # Hızlı ve Yavaş İşaretçi Farklı hızda ilerleyen iki işaretçiyle döngü tespiti ve orta eleman; ikinci kenarın görünmez kıldığı 14 döngü ve durmama bedeli. Önceki iki kalıp bir dizide çalıştı: uzunluk biliniyordu, her konuma dizin üzerinden erişilebiliyordu. Bu dersin yapısı farklıdır. Elde bir **başlangıç düğümü** ve her düğüm için bir **ardıl** vardır; uzunluk bilinmez, geriye gidilemez, yapının bir sonu olup olmadığı önceden bilinmez. Kalıp iki işaretçiyi aynı yönde ilerletir ama **farklı hızlarda**: yavaş olan bir adım, hızlı olan iki adım atar. Ön koşulu tek cümledir: **ilerleme tek yönlü olmalı**, yani her düğümün tam bir ardılı bulunmalıdır. Bu ders o ön koşulun bozulduğu girdileri sayar ve kalıbın asıl kazancının adımda değil **tutulan düğüm sayısında** olduğunu gösterir. ## Döngü Tespiti İlk problem şudur: başlangıçtan ilerleyen bir gezinme sonsuza kadar sürer mi. Kâhin, Veri Yapıları kursunun derine aramasıyla döngü arar; oradaki "ziyaret edildi" ile "hâlâ açık" ayrımı **tekrarlanmaz, doğrudan kullanılır**. Kalıp hiçbir küme tutmaz: iki işaretçi farklı hızda ilerler ve döngü varsa er geç aynı düğümde buluşurlar. **PK18.** Yapı 12 düğümlüdür; düğümler bir yol üzerinde dizilir ve yolun sonu ya biter ya geriye bağlanır. Tohum `20260218`. **PK19.** Ön koşulu bozan tek şey bazı düğümlere eklenen **ikinci bir geri kenardır**. Ön koşulu sağlayan öbek, aynı yapıların ikinci kenarları atılmış biçimidir. **PK20.** Kalıp her zaman **ilk ardılı** izler; ikinci kenarın varlığını göremez, çünkü gördüğü tek şey `ardil[d][0]` değeridir. **PK21.** Adımın yanında ikinci bir ölçü tutulur: **aynı anda tutulan düğüm sayısı**. Kâhin için ziyaret kümesinin en büyük boyu, kalıp için iki işaretçidir. ```python TOHUM, DUGUM, DAGARCIK = 20260218, 12, 40 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def zincir_dagarcik(tohum=TOHUM, n=DAGARCIK, dugum=DUGUM): """Her yapida bir yol var. Yolun sonu ya biter ya geriye baglanir; ayrica bazi dugumlere IKINCI bir geri kenar eklenir.""" r = uretec(tohum) kume = [] for i in range(n): yol = list(range(dugum)) for j in range(dugum - 1, 0, -1): k = r(j + 1) yol[j], yol[k] = yol[k], yol[j] ardil = {yol[j]: [yol[j + 1]] for j in range(dugum - 1)} ardil[yol[-1]] = [yol[r(dugum)]] if r(100) < 40 else [-1] if r(100) < 60: p = 2 + r(dugum - 3) ardil[yol[p]].append(yol[r(p)]) kume.append({"no": i + 1, "bas": yol[0], "ardil": ardil}) return kume def tek_yonlu(ardil): """Ikinci kenarlar atilir: her dugumun tam bir ardili kalir.""" return {d: [a[0]] for d, a in ardil.items()} class Sayac: def __init__(self): self.adim, self.tutulan = 0, 0 def say(self, tutulan=0): self.adim += 1 self.tutulan = max(self.tutulan, tutulan) def kahin_dongu(bas, ardil, s): """Butun kenarlari gezer. Derine aramanin dongu tespiti dogrudan kullanilir.""" ziyaret, acik = set(), set() def gez(d): ziyaret.add(d) acik.add(d) s.say(len(ziyaret)) for k in ardil.get(d, []): if k == -1: continue if k in acik: return True if k not in ziyaret and gez(k): return True acik.discard(d) return False return gez(bas) def kalip_hizli_yavas(bas, ardil, s): """ONKOSUL: her dugumun TAM BIR ardili olmali. Kalip ilk ardili izler.""" yavas = hizli = bas while True: s.say(2) for _ in range(2): hizli = ardil[hizli][0] if hizli == -1: return False yavas = ardil[yavas][0] if yavas == hizli: return True def olc(kume, tek): ayrilan, ak, ah, tk, th = [], 0, 0, 0, 0 for k in kume: ardil = tek_yonlu(k["ardil"]) if tek else k["ardil"] s1, s2 = Sayac(), Sayac() a = kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"]), s1) b = kahin_dongu(k["bas"], ardil, s2) ak, ah = ak + s1.adim, ah + s2.adim tk, th = max(tk, s1.tutulan), max(th, s2.tutulan) if a != b: ayrilan.append(k["no"]) return {"ayrilan": len(ayrilan), "ilk_ayrilan": ayrilan[:6], "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2), "kalip_tutulan": tk, "kahin_tutulan": th} K = zincir_dagarcik() print("dagarcik:", len(K), "yapi x", DUGUM, "dugum | ikinci kenari olan:", sum(1 for k in K if any(len(a) > 1 for a in k["ardil"].values()))) for ad, tek in (("on_kosul saglaniyor", True), ("on_kosul bozuk ", False)): print(f" {ad}", olc(K, tek)) ``` ``` dagarcik: 40 yapi x 12 dugum | ikinci kenari olan: 23 on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 299, 'kahin_adim': 480, 'oran': 1.61, 'kalip_tutulan': 2, 'kahin_tutulan': 12} on_kosul bozuk {'ayrilan': 14, 'ilk_ayrilan': [2, 8, 11, 12, 16, 19], 'kalip_adim': 299, 'kahin_adim': 480, 'oran': 1.61, 'kalip_tutulan': 2, 'kahin_tutulan': 12} ``` İki satırın adım sütunları **birebir aynı**: kalıp 299, kâhin 480, oran 1,61. Tutulan düğüm sütunları da aynı: kalıp **2**, kâhin **12**. Değişen tek sütun ayrılan girdidir — 0'dan **14'e** çıkıyor. Adım oranı 1,61 zaten mütevazıdır ve kalıbın satış noktası da orası değildir. Kalıp **tutulan düğüm sayısında** kazanır: kâhin yapının bütün düğümlerini bir kümede tutmak zorundadır, kalıp iki işaretçiden başka hiçbir şey tutmaz. Düğüm sayısı büyüdükçe kâhinin tuttuğu şey büyür, kalıbınki **2'de kalır**. Ölçülen kazanç budur ve ön koşul bozulduğunda bu kazanç **hiç değişmez** — yalnız yanıt bozulur. Buluşmanın neden güvenceli olduğu da tek ardıl varsayımına dayanır. İki işaretçi döngüye girdikten sonra aralarındaki uzaklık her turda **tam bir azalır**, çünkü hızlı olan iki, yavaş olan bir adım atar. Uzaklık bir tam sayıdır ve döngü uzunluğu kadar değerden birini alır; her turda bir azaldığı için sonlu sayıda turda sıfıra iner. Uzaklığın bir azalması, her düğümden **tek bir yol** çıkması demektir. İkinci bir ardıl varken "aralarındaki uzaklık" diye tek bir sayı yoktur ve gerekçe düşer. ## İkinci Kenar Neden Görünmüyor Kalıbın tek bilgi kaynağı `ardil[d][0]` değeridir. Bir düğümün ikinci bir ardılı varsa kalıp onu sorgulamaz; sorgulayamaz da, çünkü kalıbın tanımı "tek ardıl" varsayımı üzerine kuruludur. Yapıda yalnız ikinci kenar üzerinden kapanan bir döngü varsa, kalıp o döngüye hiç girmez ve `False` döndürür. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def zincir_dagarcik(tohum, n=40, dugum=12): r = uretec(tohum) kume = [] for i in range(n): yol = list(range(dugum)) for j in range(dugum - 1, 0, -1): k = r(j + 1) yol[j], yol[k] = yol[k], yol[j] ardil = {yol[j]: [yol[j + 1]] for j in range(dugum - 1)} ardil[yol[-1]] = [yol[r(dugum)]] if r(100) < 40 else [-1] if r(100) < 60: p = 2 + r(dugum - 3) ardil[yol[p]].append(yol[r(p)]) kume.append({"no": i + 1, "bas": yol[0], "ardil": ardil}) return kume def tek_yonlu(ardil): return {d: [a[0]] for d, a in ardil.items()} def kahin_dongu(bas, ardil): ziyaret, acik = set(), set() def gez(d): ziyaret.add(d) acik.add(d) for k in ardil.get(d, []): if k == -1: continue if k in acik: return True if k not in ziyaret and gez(k): return True acik.discard(d) return False return gez(bas) def kalip_hizli_yavas(bas, ardil): yavas = hizli = bas while True: for _ in range(2): hizli = ardil[hizli][0] if hizli == -1: return False yavas = ardil[yavas][0] if yavas == hizli: return True K = zincir_dagarcik(20260218) ornek = next(k for k in K if kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"])) != kahin_dongu(k["bas"], k["ardil"])) print("ayrilan ilk girdi no:", ornek["no"], "| baslangic:", ornek["bas"]) print(" ardil:", {d: a for d, a in sorted(ornek["ardil"].items())}) print(" kalip (ilk ardil):", kalip_hizli_yavas(ornek["bas"], tek_yonlu(ornek["ardil"]))) print(" kahin (butun kenarlar):", kahin_dongu(ornek["bas"], ornek["ardil"])) print() print("tohum on_kosul dongulu (kahin) ayrilan/40 oran") for tohum in (20260218, 20260219): K = zincir_dagarcik(tohum) for ad, tek in (("saglaniyor", True), ("bozuk ", False)): dongulu = ayrilan = 0 for k in K: ardil = tek_yonlu(k["ardil"]) if tek else k["ardil"] b = kahin_dongu(k["bas"], ardil) dongulu += b ayrilan += (kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"])) != b) print(f"{tohum} {ad} {dongulu:15d} {ayrilan:8d} {ayrilan / 40:.4f}") ``` ``` ayrilan ilk girdi no: 2 | baslangic: 0 ardil: {0: [8], 1: [2], 2: [7], 3: [-1], 4: [1, 8], 5: [10], 6: [5], 7: [6], 8: [9], 9: [11], 10: [3], 11: [4]} kalip (ilk ardil): False kahin (butun kenarlar): True tohum on_kosul dongulu (kahin) ayrilan/40 oran 20260218 saglaniyor 16 0 0.0000 20260218 bozuk 30 14 0.3500 20260219 saglaniyor 18 0 0.0000 20260219 bozuk 32 14 0.3500 ``` İkinci girdide düğüm 4'ün iki ardılı var: `1` ve `8`. Kalıp yalnız `1`'i görüyor ve `0 → 8 → 9 → 11 → 4 → 1 → 2 → 7 → 6 → 5 → 10 → 3 → son` yolunu izleyip `False` diyor. Kâhin `4 → 8` kenarını da deniyor ve `8 → 9 → 11 → 4` döngüsünü buluyor. **PK22.** İkinci dağarcık `20260219` tohumundan gelir. İki dağarcıkta da ayrılan girdi **14/40**, oran **0,3500**; sonuç dağarcığa bağlı değildir. ## Orta Eleman ve Durmama İkinci problem, aynı kalıbın en sık kullanılan ikinci biçimidir: yapının **orta düğümünü** bulmak. Kâhin düğümleri sırayla toplar, sonra ortadakini seçer — iki geçiş ve bir küme. Kalıp tek geçişte biter: hızlı işaretçi sona ulaştığında yavaş işaretçi ortadadır. Burada ön koşul değişir. Orta eleman ancak yapının bir **sonu** varsa tanımlıdır; döngü varsa "orta" diye bir düğüm yoktur. Kâhin bunu görür ve `tanimsiz` döndürür. Kalıbın göreceği bir şey yoktur: hızlı işaretçi döngü içinde sonsuza kadar döner. **PK23.** Bu ölçümde ikinci kenarlar yoktur; yapılar tek ardıllıdır. Bozulan ön koşul **döngüsüzlüktür**. **PK24.** Kalıba bir **adım sınırı** konur (48 adım). Sınıra dayanan koşum `durmadi` döndürür ve kâhinden ayrılmış sayılır. Sınır olmasaydı ölçüm hiç bitmezdi. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def yol_dagarcik(tohum=20260218, n=40, dugum=12): """`son` yolun son dugumu; oradan geriye baglanti varsa yapida dongu var.""" r = uretec(tohum) kume = [] for i in range(n): yol = list(range(dugum)) for j in range(dugum - 1, 0, -1): k = r(j + 1) yol[j], yol[k] = yol[k], yol[j] ardil = {yol[j]: yol[j + 1] for j in range(dugum - 1)} ardil[yol[-1]] = yol[r(dugum)] if r(100) < 40 else -1 r(100) kume.append({"no": i + 1, "bas": yol[0], "son": yol[-1], "ardil": ardil}) return kume class Sayac: def __init__(self): self.adim, self.tutulan = 0, 0 def say(self, tutulan=0): self.adim += 1 self.tutulan = max(self.tutulan, tutulan) def kahin_orta(bas, ardil, s): """Once butun dugumleri toplar, sonra ortadakini secer. Ziyaret kumesi tutar.""" ziyaret, sira, d = set(), [], bas while d != -1 and d not in ziyaret: ziyaret.add(d) sira.append(d) s.say(len(ziyaret)) d = ardil[d] if d != -1: return "tanimsiz" for _ in range(len(sira) // 2 + 1): s.say(len(ziyaret)) return sira[len(sira) // 2] def kalip_orta(bas, ardil, s, sinir=48): """ONKOSUL: yapida dongu olmamali. Tek gecis, yalniz iki isaretci tutulur.""" yavas = hizli = bas while True: s.say(2) if s.adim > sinir: return "durmadi" if hizli == -1 or ardil[hizli] == -1: return yavas hizli = ardil[ardil[hizli]] yavas = ardil[yavas] K = yol_dagarcik() A = [dict(k, ardil={**k["ardil"], k["son"]: -1}) for k in K] print("dagarcik:", len(K), "yapi | dongulu olan:", sum(1 for k in K if k["ardil"][k["son"]] != -1)) print("on_kosul ayrilan/40 kalip kahin oran kalip tutulan kahin tutulan") for ad, kume in (("saglaniyor", A), ("bozuk ", K)): ayrilan, ak, ah, tk, th = 0, 0, 0, 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() a = kalip_orta(k["bas"], k["ardil"], s1) b = kahin_orta(k["bas"], k["ardil"], s2) ak, ah = ak + s1.adim, ah + s2.adim tk, th = max(tk, s1.tutulan), max(th, s2.tutulan) ayrilan += (a != b) print(f"{ad} {ayrilan:8d} {ak:5d} {ah:5d} {ah / ak:5.2f}" f" {tk:13d} {th:13d}") ``` ``` dagarcik: 40 yapi | dongulu olan: 14 on_kosul ayrilan/40 kalip kahin oran kalip tutulan kahin tutulan saglaniyor 0 280 760 2.71 2 12 bozuk 14 868 662 0.76 2 12 ``` Ön koşul sağlandığında kalıp **280** adımda 40 girdinin 40'ında kâhinle aynı düğümü buluyor; kâhin **760** adım harcıyor, oran **2,71**. Döngülü yapılar geldiğinde ayrılan girdi **14** oluyor ve oran **0,76'ya** düşüyor — kalıp kâhinden **pahalı** hâle geliyor. Bu satır, önceki iki dersin göstermediği bir şeyi gösteriyor. Orada ön koşul bozulunca kalıp yanlış bir yanıt veriyor ve normal adım sayısında bitiyordu. Burada kalıp **bitmiyor**: 868 adımın büyük bölümü, on dört yapının her birinde sınıra dayanana kadar dönen işaretçilerdir. Sınır konmasaydı ölçüm hiç tamamlanmayacaktı. **Ön koşulun bedeli her zaman yanlış yanıt değildir; bazen yanıtın hiç gelmemesidir.** ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Döngü tespiti, ön koşul sağlanıyor | 480 adım / 12 düğüm | 299 adım / 2 düğüm | **0/40** | | Döngü tespiti, ikinci kenarlı | 480 adım / 12 düğüm | 299 adım / 2 düğüm | **14/40** | | Orta eleman, ön koşul sağlanıyor | 760 adım / 12 düğüm | 280 adım / 2 düğüm | **0/40** | | Orta eleman, döngülü yapı | 662 adım / 12 düğüm | 868 adım / 2 düğüm | **14/40** | Dört satırın hepsinde kalıbın tuttuğu düğüm sayısı **2**, kâhinin tuttuğu **12**. Bu sütun kalıbın neden var olduğunu açıklar ve dört satırda da değişmez. Ayrılan girdi sütunu ise iki kez sıfır, iki kez on dörttür — ve o sütunu okumadan diğerlerine bakmak, kalıbın on dört girdide yanlış yanıt verdiğini görmemek demektir. ## Özet - Hızlı ve yavaş işaretçi, uzunluğu bilinmeyen tek yönlü bir yapıda döngüyü ve orta düğümü hiçbir küme tutmadan bulur. - Ön koşul her düğümün **tam bir ardılı** olmasıdır; ikinci bir kenar eklendiğinde kalıp o kenarı hiç sorgulamaz ve **14 girdide** kâhinden ayrılır. - Ayrılma adım sayısına yansımaz: iki öbekte de kalıp 299, kâhin 480 adım harcar. - Kalıbın ölçülen kazancı adımda değil tutulan düğüm sayısındadır: **2'ye karşı 12**, ve bu oran ön koşul bozulsa da değişmez. - Orta eleman probleminde ön koşul döngüsüzlüktür; döngülü yapıda kalıp yanlış yanıt vermekle kalmaz, adım sınırına dayanır ve oran 2,71'den 0,76'ya düşer. ## Sonraki Adım Buraya kadarki üç kalıp tek bir geçişte, tek bir yapı üzerinde çalıştı. Sonraki kalıp girdiyi önce **yeniden düzenler**: örtüşen aralıkları birleştirmek, aralıkları bir ölçüte göre sıralamakla başlar. Ön koşul artık verinin bir özelliği değil, **seçilen ölçütün kendisidir** — ve yanlış ölçütle sıralamak kalıbı bozar. Sonraki ders üç ayrı sıralama ölçütünü aynı kâhinle karşılaştırıp hangisinin kaç girdide yanlış birleştirdiğini sayacak.