2 Kontrol Yapıları ve Fonksiyonlar
Python ile İlk Adımlar bölümünde Python’u güçlü bir hesap makinesi gibi kullandık: her satır bir kez ve yukarıdan aşağıya çalıştı. Oysa matematikteki hesapların çoğu böyle düz bir çizgi izlemez. “Diskriminant pozitifse iki gerçel kök vardır” bir karardır. \(\sum_{k=1}^{n} k^2\) aynı işlemin \(n\) kez tekrarıdır. Öklid algoritması ise “kalan sıfır olana dek böl” der ve kaç adım süreceğini önceden söylemez.
Bu bölümde bu üç kalıbın Python karşılıklarını öğreneceğiz: karar için if, sayısı belli tekrar için for, koşula bağlı tekrar için while. Ardından bir hesabı bir ad altında toplayan fonksiyonlara ve kendini çağıran fonksiyonlara, yani özyinelemeye geçeceğiz. Her aracı tanıdık bir matematik problemi üzerinde göreceğiz: ebob, Collatz dizisi, karekökün Newton yöntemiyle hesabı, asallık testi ve Fibonacci sayıları.
Bölümdeki her kod parçası kendi başına çalışır. Bir .py dosyasına ya da bir Jupyter hücresine yapıştırıp çalıştırdığınızda altındaki çıktının aynısını alırsınız.
2.1 Koşullar ve if Deyimi
Bir program, bir koşulun doğru olup olmamasına göre farklı yollar izleyebilmelidir. Python ile İlk Adımlar bölümünde 7 > 2 karşılaştırmasının değerinin True olduğunu görmüştük; şimdi bu tür ifadeleri, yani koşulları yakından tanıyalım.
Tanım 2.1 (Mantıksal Değer ve Koşul) Python’da mantıksal değer (Boolean) tipi bool’dur ve yalnız iki değeri vardır: True (doğru) ve False (yanlış). == (eşit), != (eşit değil), <, <=, >, >= karşılaştırma işleçleri iki değeri karşılaştırıp bir bool üretir. Mantıksal değerler and (ve), or (veya), not (değil) işleçleriyle birleştirilir. Değeri True ya da False olan her ifadeye koşul denir.
Yani bir koşul, Python’a sorulmuş bir evet-hayır sorusudur. Matematikteki \(p \wedge q\), \(p \vee q\) ve \(\neg p\) burada p and q, p or q ve not p olarak yazılır. \(1 < x \le 10\) gibi zincirleme bir eşitsizlik de matematikteki gibi tek parça yazılabilir.
x = 7
print(x > 5) # 7, 5'ten büyük mü?
print(x % 2 == 0) # 7 çift mi?
print(x != 7) # 7, 7'den farklı mı?
print(1 < x <= 10) # zincirleme karşılaştırma: 1 < x ve x <= 10
print(x > 5 and x % 2 == 0)
print(x > 5 or x % 2 == 0)
print(not x > 5)
print(type(x > 5))Çıktı:
True
False
False
True
False
True
False
<class 'bool'>Son satır, karşılaştırmanın sonucunun gerçekten bool tipinde olduğunu gösteriyor. Karşılaştırmalar aritmetik işlemlerden sonra yapılır: x % 2 == 0 önce x % 2’yi hesaplar, sonra sonucu 0 ile karşılaştırır. Mantıksal işleçlerde öncelik sırası not, and, or biçimindedir; emin olmadığınızda parantez kullanın.
Tanım 2.2 (if, elif ve else Deyimi) Bir if deyiminin genel biçimi şudur:
if koşul_1:
blok_1
elif koşul_2:
blok_2
else:
blok_3Python koşulları yukarıdan aşağıya sırayla sınar ve doğru çıkan ilk koşulun bloğunu çalıştırır; diğer bloklar atlanır. Hiçbir koşul doğru değilse else bloğu çalışır. elif kısmı istenildiği kadar tekrarlanabilir; elif ve else kısımları hiç yazılmayabilir de. Her if, elif ve else satırı iki nokta (:) ile biter. Ona bağlı blok, aynı miktarda (gelenek olarak dört boşluk) girintili satırlardan oluşur.
Yani if deyimi, parçalı tanımlı bir fonksiyon gibi okunur: ilk uyan durum geçerlidir. Python’da blokların nerede başlayıp bittiğini süslü parantezler değil girinti belirler. Girintisi bozuk bir program ya hata verir ya da beklenmedik bir iş yapar.
if/elif/else deyiminin akışı. Koşullar yazıldıkları sırayla sınanır; doğru çıkan ilk koşulun bloğu çalışır ve geri kalanlar atlanır. Hiçbir koşul doğru değilse else bloğu çalışır. Hangi yoldan gidilirse gidilsin, sonunda deyimden sonraki satıra geçilir.Örnek 2.1 (İkinci Dereceden Denklemin Kökleri) \(x^2 - 2x + 5 = 0\) denkleminin köklerini, diskriminantın işaretine göre üç durumu ayıran bir programla bulunuz.
Çözüm
\(a \ne 0\) olmak üzere \(ax^2 + bx + c = 0\) denkleminin diskriminantı \(\Delta = b^2 - 4ac\)’dir. \(\Delta > 0\) ise iki farklı gerçel kök, \(\Delta = 0\) ise çift katlı bir kök vardır. \(\Delta < 0\) ise kökler, birbirinin karmaşık eşleniği olan
\[x_{1,2} = -\frac{b}{2a} \pm \frac{\sqrt{-\Delta}}{2a}\, i\]
sayılarıdır. Bu üç durum, bir if-elif-else deyiminin üç dalına karşılık gelir.
import math
a, b, c = 1, -2, 5
delta = b**2 - 4*a*c
if delta > 0:
x1 = (-b + math.sqrt(delta)) / (2*a)
x2 = (-b - math.sqrt(delta)) / (2*a)
print(f"İki farklı gerçel kök: {x1} ve {x2}")
elif delta == 0:
print(f"Çift katlı kök: {-b / (2*a)}")
else:
re = -b / (2*a)
im = math.sqrt(-delta) / (2*a)
print(f"Gerçel kök yok; karmaşık kökler {re} ± {im}i")
print("Diskriminant:", delta)Çıktı:
Gerçel kök yok; karmaşık kökler 1.0 ± 2.0i
Diskriminant: -16a, b, c = 1, -2, 5 eşzamanlı ataması üç katsayıyı birden verir. Burada \(\Delta = 4 - 20 = -16 < 0\) olduğundan ilk iki koşul yanlış çıktı ve else bloğu çalıştı: kökler \(1 \pm 2i\)’dir. Katsayıları değiştirip programı yeniden çalıştırırsanız diğer dallara da girersiniz. Bunu bölümün ilerleyen kısmında bir fonksiyonla daha rahat yapacağız. \(\blacksquare\)
İki değerden birini seçmek için if deyiminin tek satırlık bir kısaltması da vardır. a if koşul else b koşullu ifadesi, koşul doğruysa a’nın, yanlışsa b’nin değerini alır. Örneğin
\[|x| = \begin{cases} x, & x \ge 0 \\ -x, & \text{diğer durumlarda} \end{cases}\]
tanımı bu biçimde tek satıra sığar:
x = -3.5
abs_x = x if x >= 0 else -x
n = 17
parity = "çift" if n % 2 == 0 else "tek"
print(abs_x, parity)Çıktı:
3.5 tek= atama, == karşılaştırmadır; if x = 3: yazmak sözdizimi hatası verir. Daha sinsi tuzak float sayıların eşitliğidir. Python ile İlk Adımlar bölümünde gördüğümüz gibi \(0{,}1\) ve \(0{,}2\) ikili sistemde tam gösterilemez, bu yüzden toplamları 0.3 ile tam eşit çıkmaz. Ondalık sonuçları math.isclose ile ya da abs(a - b) < tol biçiminde bir toleransla karşılaştırın.
import math
s = 0.1 + 0.2
if s == 0.3:
print("eşit")
else:
print("eşit değil, s =", s)
if math.isclose(s, 0.3):
print("math.isclose: yeterince yakın")Çıktı:
eşit değil, s = 0.30000000000000004
math.isclose: yeterince yakın2.2 for Döngüsü ve range
Bir işlemi önceden bilinen sayıda tekrarlamak için for döngüsünü kullanırız. Döngünün dolaşacağı tam sayıları çoğunlukla range üretir; önce onu tanıyalım.
Tanım 2.3 (range Nesnesi) \(a\), \(b\) ve \(s \ne 0\) tam sayılar olsun. range(a, b, s) nesnesi \(a, a + s, a + 2s, \dots\) tam sayılarını sırayla verir; \(s > 0\) ise \(b\)’ye ulaşmadan, \(s < 0\) ise \(b\)’ye inmeden durur. Örneğin \(s > 0\) için verilen sayılar
\[\{\, a + ks \;:\; k = 0, 1, 2, \dots \text{ ve } a + ks < b \,\}\]
kümesinin küçükten büyüğe sıralanmış elemanlarıdır. range(a, b) yazımında adım \(s = 1\) alınır; range(b) ise range(0, b) demektir.
Yani range(a, b), \([a, b)\) yarı açık aralığındaki tam sayıları verir: başlangıç dahil, bitiş hariç. Bu yüzden \(1, 2, \dots, n\) için range(1, n + 1) yazılır; range(n) ise \(0, 1, \dots, n - 1\) olmak üzere tam \(n\) sayı verir. Bir range’in elemanlarını görmek için onu list(...) ile listeye çeviriyoruz. Listeleri Veri Yapıları ve Comprehension bölümünde ayrıntılı göreceğiz.
print(list(range(5)))
print(list(range(2, 11, 3)))
print(list(range(10, 0, -2)))
print(list(range(3, 3)))
print(len(range(1, 101)))Çıktı:
[0, 1, 2, 3, 4]
[2, 5, 8]
[10, 8, 6, 4, 2]
[]
100range(3, 3) boştur, çünkü \([3, 3)\) aralığında tam sayı yoktur. len ise bir range’in kaç sayı verdiğini söyler.
Tanım 2.4 (for Döngüsü)
for değişken in nesne:
blokbiçimindeki for döngüsü, nesne’nin (örneğin bir range’in ya da sonraki bölümde göreceğimiz bir listenin) elemanlarını sırayla değişken’e atar ve her atamadan sonra girintili bloğu bir kez çalıştırır. Bloğun her çalışmasına döngünün bir adımı (iterasyon) denir.
Yani for k in range(1, n + 1): satırı, matematikteki “\(k = 1, 2, \dots, n\) için” ifadesinin birebir karşılığıdır. Döngü değişkeni sıradan bir değişkendir ve döngü bittiğinde son aldığı değeri korur.
for k in range(1, 6):
print(f"{k:2} {k**2:4} {k**3:5}")
print("döngü bitti, k =", k)Çıktı:
1 1 1
2 4 8
3 9 27
4 16 64
5 25 125
döngü bitti, k = 5f-dizgisindeki {k**2:4} gibi biçim belirteçleri sayıyı 4 karakterlik bir alana sağa yaslar, böylece tablo hizalı çıkar.
Döngülerin en sık kullanımı bir toplam ya da çarpım biriktirmektir. \(\sum\) ve \(\prod\) sembollerinin özyineli tanımı (bkz. Analiz 1) tam olarak bu kalıbı anlatır: \(S_0 = 0\) ve \(S_k = S_{k-1} + a_k\).
- Biriktirici değişkeni işlemin etkisiz elemanıyla başlatın: toplam için
s = 0, çarpım içinp = 1. - Döngünün her adımında terimi ekleyin (
s += terim) ya da terimle çarpın (p *= terim). - Sonucu döngü bittikten sonra kullanın; biriktiriciyi döngünün içinde yeniden başlatmayın.
Örnek 2.2 (Karelerin Toplamı) \(\sum_{k=1}^{100} k^2\) toplamını bir döngüyle hesaplayıp
\[\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\]
formülünün verdiği değerle karşılaştırınız.
Çözüm
Tarifin üç adımı kodda yorum olarak işaretli. s += k**2, s = s + k**2 atamasının kısa yazılışıdır.
n = 100
s = 0 # 1. adım: toplamın etkisiz elemanı
for k in range(1, n + 1):
s += k**2 # 2. adım: terimi biriktiriciye ekle
print("döngüyle:", s) # 3. adım: sonucu döngüden sonra kullan
print("formülle:", n * (n + 1) * (2*n + 1) // 6)Çıktı:
döngüyle: 338350
formülle: 338350İki değer aynıdır:
\[\frac{100 \cdot 101 \cdot 201}{6} = \frac{2030100}{6} = 338350.\]
Formülde / yerine // kullandık. \(n(n+1)(2n+1)\) her zaman \(6\)’ya bölündüğünden tam bölme kesin sonucu int olarak verir; / ise 338350.0 gibi bir float döndürürdü. \(\blacksquare\)
Bir döngünün bloğu başka bir döngü içerebilir; buna iç içe döngü denir. İç döngü, dış döngünün her adımında baştan sona bir kez çalışır.
Örnek 2.3 (Kareler Tersleri Serisinin Kısmi Toplamları) \(S_n = \sum_{k=1}^{n} \dfrac{1}{k^2}\) kısmi toplamlarını \(n = 10, 10^2, \dots, 10^5\) için hesaplayıp serinin toplamı olan \(\pi^2/6\) ile farklarını bulunuz.
Çözüm
Serinin yakınsadığını \(p\)-serisi ölçütü (bkz. Analiz 2), toplamının \(\pi^2/6\) olduğunu ise Fourier serileri (bkz. Analiz 3) verir. Dış döngü \(j = 1, \dots, 5\) için \(n = 10^j\)’yi seçer, iç döngü \(S_n\)’yi tarifteki gibi biriktirir. s = 0.0 satırı dış döngünün içinde ama iç döngünün dışında durur: her \(n\) için yeni bir toplam başlar, toplamın kendisi ise iç döngü boyunca birikir.
import math
limit = math.pi**2 / 6
for j in range(1, 6):
n = 10**j
s = 0.0
for k in range(1, n + 1):
s += 1 / k**2
print(f"n = {n:6} S_n = {s:.10f} fark = {limit - s:.4e}")Çıktı:
n = 10 S_n = 1.5497677312 fark = 9.5166e-02
n = 100 S_n = 1.6349839002 fark = 9.9502e-03
n = 1000 S_n = 1.6439345667 fark = 9.9950e-04
n = 10000 S_n = 1.6448340718 fark = 9.9995e-05
n = 100000 S_n = 1.6449240669 fark = 9.9999e-06Fark her seferinde yaklaşık on kat küçülüyor; \(n\) ile farkın çarpımı hep \(1\)’e yakın. Gerçekten de fark
\[\frac{\pi^2}{6} - S_n = \sum_{k=n+1}^{\infty} \frac{1}{k^2} \approx \int_n^{\infty} \frac{dx}{x^2} = \frac{1}{n}\]
kuyruğudur. Yani bu seriyle \(d\) ondalık basamak doğruluk için kabaca \(10^d\) terim toplamak gerekir: seri yavaş yakınsar. \(\blacksquare\)
Örnek 2.4 (Bir Dairedeki Kafes Noktaları) \(N(r)\), \(x^2 + y^2 \le r^2\) eşitsizliğini sağlayan \((x, y)\) tam sayı çiftlerinin sayısı olsun. \(r = 5, 10, 15, 20\) için \(N(r)\)’yi hesaplayıp dairenin alanı \(\pi r^2\) ile karşılaştırınız.
Çözüm
Böyle bir çiftte \(|x| \le r\) ve \(|y| \le r\) olmalıdır, bu yüzden \(x\) ve \(y\)’yi \(-r, \dots, r\) arasında dolaştırmak yeter. İki iç döngü karedeki \((2r + 1)^2\) noktanın hepsini dener; en dıştaki üçüncü döngü ise \(r\)’yi değiştirir.
import math
for r in range(5, 21, 5):
count = 0
for x in range(-r, r + 1):
for y in range(-r, r + 1):
if x*x + y*y <= r*r:
count += 1
area = math.pi * r**2
print(f"r = {r:2} N(r) = {count:4} pi r^2 = {area:8.2f}")Çıktı:
r = 5 N(r) = 81 pi r^2 = 78.54
r = 10 N(r) = 317 pi r^2 = 314.16
r = 15 N(r) = 709 pi r^2 = 706.86
r = 20 N(r) = 1257 pi r^2 = 1256.64\(N(r)\) ile \(\pi r^2\) arasındaki fark, alanın yanında çok küçüktür. Her kafes noktasının merkezde durduğu birim kareler düşünülürse bu karelerin toplam alanı \(N(r)\)’dir ve daireyi neredeyse tam kaplar. \(r = 20\) için iki iç döngü \(41^2 = 1681\) çift dener; toplam iş, karedeki nokta sayısıyla, yani yaklaşık \(4r^2\) ile orantılıdır. \(\blacksquare\)
2.3 while Döngüsü
for döngüsü, tekrar sayısı baştan belli olduğunda kullanışlıdır. Öklid algoritmasında ya da bir iterasyonu belirli bir hassasiyete ulaşana dek sürdürürken ise kaç adım gerektiğini önceden bilmeyiz; o zaman while kullanılır.
Tanım 2.5 (while Döngüsü)
while koşul:
blokbiçimindeki while döngüsü önce koşulu sınar. Koşul doğruysa bloğu bir kez çalıştırır ve koşulu yeniden sınar. Koşul yanlış çıktığı anda döngü biter ve program döngüden sonraki satırdan devam eder.
Yani while, “koşul sağlandığı sürece tekrarla” demektir. Koşul ilk sınamada yanlışsa blok hiç çalışmaz; koşul hiç yanlış olmazsa döngü sonsuza dek sürer. Bu yüzden blok, koşuldaki değişkenleri eninde sonunda koşulu bozacak biçimde değiştirmelidir.
Öklid algoritmasının dayandığı olgu şudur.
Önerme 2.1 (EBOB ve Bölme Kalanı) \(a, b\) tam sayılar ve \(b \ne 0\) olsun. \(a = qb + r\) olacak biçimde \(q, r\) tam sayıları için \(\gcd(a, b) = \gcd(b, r)\)’dir. Ayrıca \(\gcd(a, 0) = |a|\)’dır.
\(r = a - qb\) olduğundan \((a, b)\) ile \((b, r)\) çiftlerinin ortak bölenleri aynıdır; ispat için bkz. Sayılar Teorisi. \(r\) olarak bölme kalanını seçip önermeyi tekrar tekrar uygulamak Öklid algoritmasıdır. Kalanlar kesin azalan doğal sayılar olduğundan bir gün sıfır olur ve son sıfırdan farklı kalan ebob’dur.
Örnek 2.5 (Öklid Algoritması) \(\gcd(1071, 462)\)’yi Öklid algoritmasıyla, her bölmeyi yazdırarak hesaplayınız.
Çözüm
Önerme 2.1’a göre \((a, b)\) çiftini \((b,\ a \bmod b)\) ile değiştirmek ebob’u korur. Bunu \(b\) sıfır olana dek yaparız. Kaç bölme gerektiğini önceden bilmediğimiz için döngüyü while ile yazarız. divmod(a, b) bölümü ve kalanı birlikte verir.
a, b = 1071, 462
while b != 0:
q, r = divmod(a, b)
print(f"{a} = {q} * {b} + {r}")
a, b = b, r
print("ebob =", a)Çıktı:
1071 = 2 * 462 + 147
462 = 3 * 147 + 21
147 = 7 * 21 + 0
ebob = 21Son sıfırdan farklı kalan \(21\)’dir ve döngü bittiğinde bu değer a’dadır. Gerçekten \(1071 = 3^2 \cdot 7 \cdot 17\) ve \(462 = 2 \cdot 3 \cdot 7 \cdot 11\) olduğundan ebob \(3 \cdot 7 = 21\)’dir. Şekilde kare sayıları (\(2\), \(3\), \(7\)) bölümlere, karelerin kenarları (\(462\), \(147\), \(21\)) bölenlere karşılık gelir. \(\blacksquare\)
a, b = b, r satırı, Python ile İlk Adımlar bölümünde gördüğümüz eşzamanlı atamadır: önce sağ taraftaki bütün değerler hesaplanır, sonra sola atanır. Aynı işi iki ayrı satırla yapmaya çalışmak yanlış sonuç verir, çünkü ikinci satır a’nın yeni değerini görür:
a, b = 1071, 462
a = b # a artık 462
b = a % b # yanlış: 462 % 462 hesaplanır
print(a, b)Çıktı:
462 0Bu durumda döngü ilk adımda biter ve ebob yanlışlıkla \(462\) çıkar.
while döngüsünün en ünlü örneklerinden biri, her başlangıç değeri için durup durmadığını bugün bile kimsenin bilmediği bir döngüdür.
Tanım 2.6 (Collatz Dizisi) Bir \(n_0\) pozitif tam sayısından başlayan Collatz dizisi
\[n_{k+1} = \begin{cases} n_k / 2, & n_k \text{ çift ise} \\ 3n_k + 1, & n_k \text{ tek ise} \end{cases}\]
kuralıyla tanımlanır. Dizinin \(1\)’e ilk ulaştığı \(k\) indisine \(n_0\)’ın adım sayısı denir.
Yani çift sayılar yarıya iner, tek sayılar ise \(3n + 1\)’e sıçrar; \(1\)’e ulaşan dizi bundan sonra \(1, 4, 2, 1, \dots\) döngüsünde döner. Collatz sanısı, her başlangıç değerinden sonlu sayıda adımda \(1\)’e ulaşıldığını söyler. Sanı çok büyük sayılara kadar bilgisayarla doğrulanmıştır ama ispatı yoktur. Adım sayısı için bir formül bilmediğimizden dizi ancak while ile izlenebilir.
Örnek 2.6 (Collatz Dizisi: Başlangıç Değeri 27) \(n_0 = 27\) için Collatz dizisinin adım sayısını ve dizinin en büyük terimini bulunuz.
while ile yazılır.Çözüm
Döngü \(n \ne 1\) olduğu sürece döner. Her adımda \(n\)’yi kurala göre günceller, adım sayacını bir artırır ve o ana kadarki en büyük terimi Python’un hazır max fonksiyonuyla saklar. n // 2 tam bölmedir; \(n\) çift olduğundan sonuç kesin bir int’tir.
n = 27
steps = 0
peak = n
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3*n + 1
steps += 1
peak = max(peak, n)
print("adım sayısı:", steps)
print("en büyük terim:", peak)Çıktı:
adım sayısı: 111
en büyük terim: 9232Küçük bir başlangıç değeri \(111\) adım sürer ve yolda \(9232\)’ye kadar tırmanır. \(\blacksquare\)
Koşulu hiç bozulmayan bir while döngüsü durmaz. Örneğin Collatz döngüsünde n’yi güncellemeyi unutursanız program sonsuza dek çalışır. Böyle bir programı terminalde Ctrl+C ile, Jupyter’de ise çekirdeği durdurarak kesebilirsiniz. Güvenlik için iterasyon sayısına bir üst sınır koymak iyi bir alışkanlıktır; bölümün Newton örneklerinde max_iter bunu yapar. Ayrıca n / 2 yazmak n’yi float’a çevirir. \(2^{53}\)’ten büyük tam sayıların hepsi float olarak tam tutulamadığından dizi bozulabilir. Tam sayı dizilerinde // kullanın.
2.4 break, continue ve else
Bazen döngüyü koşulun belirlediği yerden önce bitirmek ya da bir adımın geri kalanını atlamak isteriz. Bunun için iki deyim vardır.
Tanım 2.7 (break ve continue) Bir döngünün bloğunda break çalıştığında döngü hemen sona erer ve program döngüden sonraki satırdan devam eder. continue çalıştığında ise o adımın geri kalanı atlanır ve döngü bir sonraki adıma geçer. İç içe döngülerde ikisi de yalnız içinde bulundukları en içteki döngüyü etkiler.
Yani break “aradığımı buldum, dur”, continue ise “bu adım beni ilgilendirmiyor, sıradakine geç” demektir. Çıkış koşulu ancak bloğun ortasında hesaplanabiliyorsa while True: ile sonu olmayan bir döngü kurup çıkışı içerideki bir break ile yapmak yaygın bir kalıptır.
Örnek 2.7 (Faktöriyelin Bir Gugolü Aştığı Yer) \(10^{100}\) sayısına gugol (googol) denir. \(n! > 10^{100}\) eşitsizliğini sağlayan en küçük \(n\) doğal sayısını bulunuz.
Çözüm
\(n!\)’i f değişkeninde biriktirip \(n\)’yi birer artırırız; f ilk kez \(10^{100}\)’ü aştığında break ile döngüden çıkarız. Python’un tam sayıları istenildiği kadar büyük olabildiğinden f kesin olarak hesaplanır.
import math
n = 1
f = 1 # f = n!
while True:
n += 1
f *= n
if f > 10**100:
break # ilk kez 10^100'ü aştı: döngüden çık
print("n =", n)
print("log10(n!) =", round(math.log10(f), 3))
print("log10((n-1)!) =", round(math.log10(f // n), 3))Çıktı:
n = 70
log10(n!) = 100.078
log10((n-1)!) = 98.233\(\log_{10}(70!) \approx 100{,}078 > 100\) ve \(\log_{10}(69!) \approx 98{,}233 < 100\) olduğundan aranan sayı \(n = 70\)’tir. Son satırda \(69! = 70!/70\) eşitliğini f // n ile kullandık. \(\blacksquare\)
Örnek 2.8 (Bin ile Aralarında Asal Sayılar) \(1 \le k \le 1000\) ve \(\gcd(k, 1000) = 1\) koşullarını sağlayan \(k\) sayılarının kaç tane olduğunu ve toplamlarını bulunuz.
Çözüm
Döngü \(k = 1, \dots, 1000\) sayılarını dolaşır. \(1000\) ile ortak böleni olan bir \(k\) geldiğinde continue adımın geri kalanını atlar; böylece sayaç ve toplam yalnız aralarında asal sayılarla güncellenir. Ebob için Python’un hazır math.gcd fonksiyonunu kullanıyoruz.
import math
n = 1000
count = 0
total = 0
for k in range(1, n + 1):
if math.gcd(k, n) != 1:
continue # n ile ortak böleni var: bu k'yı atla
count += 1
total += k
print("n ile aralarında asal olanların sayısı:", count)
print("bunların toplamı:", total)
print("n * phi(n) / 2 =", n * count // 2)Çıktı:
n ile aralarında asal olanların sayısı: 400
bunların toplamı: 200000
n * phi(n) / 2 = 200000Sayı, Euler fonksiyonunun değeridir (bkz. Sayılar Teorisi):
\[\phi(1000) = 1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400.\]
Toplamın \(1000 \cdot 400 / 2\) çıkması tesadüf değildir. \(\gcd(k, n) = 1\) ise \(\gcd(n - k, n) = 1\)’dir, yani bu sayılar toplamı \(n\) olan \(\phi(n)/2\) çifte ayrılır. \(\blacksquare\)
Döngülerin az bilinen bir parçası da else kısmıdır. Bir for ya da while döngüsünün sonuna yazılan else bloğu, döngü break ile kesilmeden kendiliğinden bittiğinde çalışır. Bu, “aradığımı bulamadım” durumunu yakalamanın temiz bir yoludur. Asallık testinde aradığımız şey bir bölendir; aramayı nerede bitirebileceğimizi aşağıdaki önerme söyler.
Önerme 2.2 (Bölen Aramak İçin Karekök Yeter) \(n > 1\) asal olmayan bir tam sayı ise \(n\)’nin \(2 \le d \le \sqrt{n}\) koşulunu sağlayan bir \(d\) böleni vardır. Dolayısıyla \(2, 3, \dots, \lfloor \sqrt{n} \rfloor\) sayılarından hiçbiri \(n\)’yi bölmüyorsa \(n\) asaldır.
\(n = d \cdot e\) ise \(d\) ile \(e\)’nin ikisi birden \(\sqrt{n}\)’den büyük olamaz, yoksa çarpımları \(n\)’yi aşardı; ispatın ayrıntısı için bkz. Sayılar Teorisi.
Örnek 2.9 (Deneme Bölmesiyle Asallık) \(1001\), \(1005\) ve \(1009\) sayılarının asal olup olmadığını deneme bölmesiyle belirleyiniz.
Çözüm
Önerme 2.2’e göre \(d = 2, 3, \dots, \lfloor \sqrt{n} \rfloor\) bölenlerini denemek yeter. math.isqrt(n), \(\lfloor \sqrt{n} \rfloor\) tam sayı karekökünü kesin olarak verir. Bir bölen bulunduğunda break iç döngüyü keser ve else bloğu atlanır. Hiçbir bölen bulunamazsa iç döngü kendiliğinden biter ve else bloğu “asal” yazar. else’in if ile değil iç for ile aynı hizada olduğuna dikkat edin.
import math
for n in range(1001, 1010, 4):
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
print(f"{n} = {d} * {n // d}, asal değil")
break
else:
print(f"{n} asal")Çıktı:
1001 = 7 * 143, asal değil
1005 = 3 * 335, asal değil
1009 asal\(\lfloor \sqrt{1009} \rfloor = 31\) olduğundan \(1009\) için yalnız \(30\) aday bölen denendi. \(1001 = 7 \cdot 11 \cdot 13\)’tür; kod ilk bulduğu bölen olan \(7\)’de durdu. \(\blacksquare\)
2.5 Fonksiyonlar
Öklid algoritmasını her ebob gerektiğinde yeniden yazmak istemeyiz. Fonksiyon, bir hesabı bir ad altında paketler: bir kez tanımlanır, istenildiği kadar çağrılır.
Tanım 2.8 (Fonksiyon Tanımı ve Çağrısı)
def ad(parametre_1, parametre_2):
blokbiçimindeki def deyimi ad adlı bir fonksiyon tanımlar; parametre sayısı herhangi bir doğal sayı olabilir. ad(argüman_1, argüman_2) biçimindeki bir çağrı, parametrelere sırasıyla argümanların değerlerini atar ve bloğu çalıştırır. Blokta bir return ifade satırına gelindiğinde fonksiyon hemen sona erer ve çağrının değeri ifade’nin değeri olur. Blok bir return’e rastlamadan biterse çağrının değeri özel None değeridir.
Yani \(f(x) = x^2 - 2x + 5\) gibi bir matematiksel fonksiyon Python’da def f(x): satırı ve altındaki return x**2 - 2*x + 5 satırıyla yazılır. Ama bir Python fonksiyonu bundan fazlasıdır: içinde döngüler, kararlar ve başka fonksiyon çağrıları olan bir hesap yordamıdır.
def f(x):
return x**2 - 2*x + 5
print(f(0), f(1), f(3))
print(f(1 + 2j))
y = f(2) + f(-2)
print(y)Çıktı:
5 4 8
0j
18Aynı fonksiyon karmaşık sayılarla da çalışır. \(f(1 + 2i) = 0\) çıkması, Örnek 2.1’de bulduğumuz kökün sağlamasıdır. Bir çağrı, değeri olan bir ifadedir; f(2) + f(-2) gibi başka ifadelerin içinde kullanılabilir.
Tanım 2.9 (Belge Dizgisi) Bir fonksiyon bloğunun ilk satırına yazılan dizgiye o fonksiyonun belge dizgisi (docstring) denir. Belge dizgisi fonksiyonun ne yaptığını, parametrelerini ve döndürdüğü değeri anlatır; help(ad) çağrısı onu ekrana yazar.
Yani belge dizgisi, fonksiyonun kodla birlikte taşınan kullanım kılavuzudur. Gelenek, onu üç tırnak arasında ("""...""") yazmak, ilk satırda tek cümlelik bir özet vermek ve gerekiyorsa bir boş satırdan sonra ayrıntıya girmektir.
Örnek 2.10 (Ebob Fonksiyonu) Öklid algoritmasını belge dizgisi olan bir gcd(a, b) fonksiyonuna çeviriniz.
Çözüm
Örnek 2.5’deki döngüyü fonksiyonun bloğuna taşırız, yazdırma satırını atar ve sonucu return ile döndürürüz. Negatif girdilerde de pozitif bir ebob vermek için sonucu abs ile döndürüyoruz.
def gcd(a, b):
"""a ile b'nin en büyük ortak bölenini döndürür.
Öklid algoritması: b sıfır olana dek (a, b) çiftini
(b, a % b) ile değiştirir.
"""
while b != 0:
a, b = b, a % b
return abs(a)
help(gcd)
print(gcd(1071, 462), gcd(-12, 18), gcd(7, 0))Çıktı:
Help on function gcd in module __main__:
gcd(a, b)
a ile b'nin en büyük ortak bölenini döndürür.
Öklid algoritması: b sıfır olana dek (a, b) çiftini
(b, a % b) ile değiştirir.
21 6 7gcd(-12, 18) çağrısında Python’un % işlemi kalanı bölenin işaretiyle verir: -12 % 18 işleminin sonucu \(6\)’dır. Ardından \((18, 6)\) çifti \((6, 0)\)’a döner ve sonuç \(6\) olur. gcd(7, 0) ise döngüye hiç girmeden \(7\) döndürür; bu, \(\gcd(a, 0) = |a|\) kuralıdır. Python’un math modülünde aynı işi yapan hazır bir math.gcd fonksiyonu da vardır. \(\blacksquare\)
Bir fonksiyon birden çok değeri virgülle ayırarak döndürebilir; çağıran taraf bunları x1, x2 = ... biçiminde ayrı değişkenlere açabilir. Python bu değerleri bir demet (tuple) içinde paketler. Demetleri de Veri Yapıları ve Comprehension bölümünde göreceğiz.
Örnek 2.11 (Kökleri Döndüren Bir Fonksiyon) Örnek 2.1’deki hesabı, \(ax^2 + bx + c = 0\) denkleminin iki kökünü döndüren bir roots(a, b, c) fonksiyonuna çeviriniz ve üç durumu da deneyiniz.
Çözüm
\(\Delta \ge 0\) ise \(\sqrt{\Delta}\) gerçeldir. \(\Delta < 0\) ise \(\sqrt{\Delta}\) yerine \(i\sqrt{-\Delta}\) alırız ve bunu sanal birim 1j ile 1j * math.sqrt(-delta) olarak kurarız. Böylece kök formülü üç durumda da aynı satırla yazılır.
import math
def roots(a, b, c):
"""ax^2 + bx + c = 0 denkleminin köklerini döndürür (a != 0)."""
delta = b**2 - 4*a*c
if delta >= 0:
r = math.sqrt(delta)
else:
r = 1j * math.sqrt(-delta)
return (-b + r) / (2*a), (-b - r) / (2*a)
x1, x2 = roots(1, -3, 2)
print(x1, x2)
print(roots(1, -2, 1))
print(roots(1, -2, 5))Çıktı:
2.0 1.0
(1.0, 1.0)
((1+2j), (1-2j))\(x^2 - 3x + 2 = (x - 1)(x - 2)\) denkleminin kökleri \(2\) ve \(1\)’dir. \(x^2 - 2x + 1 = (x - 1)^2\) çift katlı \(1\) kökünü iki kez verir. \(x^2 - 2x + 5\) için yine \(1 \pm 2i\) bulunur. İlk çağrıda sonuçları iki değişkene açtık, diğerlerinde ise çağrının kendisini yazdırdık; Python iki değeri parantez içinde gösterdi. \(\blacksquare\)
Fonksiyonun içinde sonucu print ile yazdırmak onu döndürmek demek değildir. return içermeyen bir fonksiyonun çağrısı None değerini alır ve bu değerle hesap yapmaya çalışmak hata verir:
def square_print(x):
print(x**2) # ekrana yazar ama değer döndürmez
def square(x):
return x**2
a = square_print(3)
b = square(3)
print(a, b)Çıktı:
9
None 9Hesapta kullanılacak sonuçları return ile döndürün; print’i yalnız ekrana bilgi vermek için kullanın.
Fonksiyonun içindeki değişkenlerle dışarıdakiler arasındaki ilişki de net olmalıdır.
Tanım 2.10 (Yerel ve Global Değişken) Bir fonksiyonun bloğunda değer atanan değişkenler o fonksiyonun yerel değişkenleridir: yalnız çağrı süresince var olurlar ve fonksiyonun dışındaki aynı adlı değişkenleri etkilemezler. Parametreler de yereldir. Programın en üst düzeyinde, fonksiyonların dışında tanımlanan değişkenlere global değişken denir. Bir fonksiyon bir global değişkeni okuyabilir; ona yeni bir değer atayabilmesi için ise bloğun başında global ad bildirimi gerekir.
Yani her çağrı kendi küçük çalışma alanında çalışır; fonksiyonun içindeki x, dışarıdaki x’in yalnız adaşıdır.
x = 10
def g(t):
x = 2 * t # bu x, g'nin yerel değişkenidir
return x + 1
print(g(5))
print(x) # dışarıdaki x değişmediÇıktı:
11
10Fonksiyonların yalnız parametreler ve return üzerinden haberleşmesi onları güvenilir yapı taşları yapar. global bildirimini bu bölümde yalnız bir fonksiyonun kaç kez çağrıldığını ya da kaç işlem yaptığını saymak için kullanacağız.
Sayısal yöntemlerde bir fonksiyonun asıl girdisinin yanında tolerans, en fazla adım sayısı gibi ayarları da olur. Bunları her çağrıda yazmak zorunda kalmamak için varsayılan değerler kullanılır.
Tanım 2.11 (Varsayılan Değer ve Anahtar Sözcüklü Argüman) Bir parametreye tanımda ad=değer biçiminde bir varsayılan değer verilebilir; çağrıda bu parametreye argüman yazılmazsa varsayılan değer kullanılır. Varsayılan değerli parametreler, varsayılanı olmayanlardan sonra gelir. Çağrıda bir argüman ad=değer biçiminde parametresinin adıyla da verilebilir; böyle bir anahtar sözcüklü argüman, sıraya bakılmaksızın adıyla eşleşir.
Yani sık değiştirilmeyen ayarlar varsayılan değerlerle tanımlanır, çağıran yalnız değiştirmek istediğini adıyla yazar. Bu, uzun parametre listelerini okunur kılar: sqrt_newton(10, tol=1e-6) çağrısı, aynı işi yapan sqrt_newton(10, 1.0, 1e-6) çağrısından çok daha açıktır.
Bu araçları sayısal analizin klasik bir algoritmasında birleştirelim. \(a > 0\) için \(\sqrt{a}\), \(f(x) = x^2 - a\) fonksiyonunun pozitif köküdür. Newton yönteminin \(x_{k+1} = x_k - f(x_k)/f'(x_k)\) adımı (bkz. Nümerik Analiz) bu fonksiyon için
\[x_{k+1} = x_k - \frac{x_k^2 - a}{2x_k} = \frac{1}{2}\left(x_k + \frac{a}{x_k}\right)\]
olur. Bu, Babillilerden beri bilinen karekök iterasyonudur (bkz. Analiz 1).
- Bir başlangıç değeri seçin: \(x_0 > 0\), örneğin \(x_0 = 1\).
- Yeni terimi \(x_{k+1} = \frac{1}{2}\left(x_k + a/x_k\right)\) ile hesaplayın.
- \(|x_{k+1} - x_k|\) bir
toltoleransından küçükse durun ve \(x_{k+1}\)’i döndürün; değilse ikinci adıma dönün. Yakınsamama ihtimaline karşı adım sayısınımax_iterile sınırlayın.
Örnek 2.12 (Newton Yöntemiyle Karekök) Tarifi varsayılan değerli parametreleri olan bir sqrt_newton fonksiyonu olarak yazıp \(\sqrt{2}\)’yi hesaplayınız; ara adımları da yazdırınız.
Çözüm
Fonksiyon \(a\)’yı zorunlu, x0, tol, max_iter ve verbose parametrelerini varsayılan değerli alır. Döngü en fazla max_iter adım süren bir for döngüsüdür. Durma koşulu sağlanınca return hem döngüyü hem de fonksiyonu bitirir. Fonksiyon kök ile adım sayısını birlikte döndürür.
def sqrt_newton(a, x0=1.0, tol=1e-12, max_iter=50, verbose=False):
"""a > 0 sayısının karekökünü Newton yöntemiyle hesaplar.
x_{k+1} = (x_k + a / x_k) / 2 iterasyonu, ardışık iki terimin
farkı tol'dan küçük olunca durur. (kök, adım sayısı) döndürür.
"""
x = x0
for k in range(1, max_iter + 1):
x_new = (x + a / x) / 2
if verbose:
print(f"k = {k} x = {x_new:.16f}")
if abs(x_new - x) < tol:
return x_new, k
x = x_new
return x, max_iter
root, steps = sqrt_newton(2, verbose=True)
print("sonuç:", root, "adım:", steps)
print(sqrt_newton(10, tol=1e-6))
print(sqrt_newton(10, 3.0, 1e-6))Çıktı:
k = 1 x = 1.5000000000000000
k = 2 x = 1.4166666666666665
k = 3 x = 1.4142156862745097
k = 4 x = 1.4142135623746899
k = 5 x = 1.4142135623730949
k = 6 x = 1.4142135623730949
sonuç: 1.414213562373095 adım: 6
(3.162277660168379, 6)
(3.162277660168379, 4)İlk çağrıda yalnız verbose’u adıyla değiştirdik, diğer parametreler varsayılan değerlerini aldı. Doğru ondalık basamak sayısı her adımda kabaca ikiye katlanıyor: \(x_2\)’de \(2\), \(x_3\)’te \(5\), \(x_4\)’te \(11\) basamak doğru. Bu, Newton yönteminin karesel yakınsamasının izidir. Aynı davranış \(\cos x - x = 0\) denkleminde de görülür (bkz. Nümerik Analiz); hızın kesin ifadesine Kök Bulma ve Optimizasyon bölümünde döneceğiz. Beşinci adımdan sonra terim değişmez; altıncı adımda fark sıfır olduğundan döngü durur. Sonuç, math.sqrt(2) değerinden yalnız son basamakta, yaklaşık \(2{,}2 \cdot 10^{-16}\) kadar ayrılır; bu, makine duyarlığı düzeyinde bir farktır.
Son iki çağrının ikisi de \(\sqrt{10}\) sayısını aynı \(10^{-6}\) toleransıyla hesaplar, ama farklı başlangıç değerlerinden. tol=1e-6 adıyla verildiğinde x0 varsayılan \(1\) değerinde kalır ve altı adım gerekir. sqrt_newton(10, 3.0, 1e-6) çağrısında ise argümanlar sırayla eşleştiği için x0 = 3.0 ve tol = 1e-6 olur. \(x_0 = 3\) köke yakın bir başlangıç olduğundan dört adım yeter. \(\blacksquare\)
Python’da fonksiyonlar da birer değerdir: bir değişkene atanabilir, başka bir fonksiyona argüman olarak verilebilir. Bu sayede \(\sum\) sembolü gibi bir fonksiyonu girdi olarak alan kavramları doğrudan yazabiliriz. Argüman olarak verilecek kısa fonksiyonlar için ayrıca def yazmak da gerekmez.
Tanım 2.12 (lambda İfadesi) lambda parametreler: ifade biçimindeki bir lambda ifadesi adsız bir fonksiyon üretir; bu fonksiyon çağrıldığında ifade’nin değerini döndürür. Gövdesi tek bir ifadeden oluşur; içinde if deyimi, döngü ya da return bulunmaz.
Yani lambda x: x**2, matematikteki \(x \mapsto x^2\) gösteriminin Python yazımıdır. Aşağıdaki sigma fonksiyonu terimi bir fonksiyon olarak alır ve \(\sum_{k=m}^{n} \mathrm{term}(k)\) toplamını hesaplar.
def sigma(term, m, n):
"""term(m) + term(m+1) + ... + term(n) toplamını döndürür."""
s = 0
for k in range(m, n + 1):
s += term(k)
return s
print(sigma(lambda k: k**2, 1, 100))
print(sigma(lambda k: 1 / 2**k, 0, 30))
print(sigma(lambda k: k**3, 1, 10))
print(sigma(abs, -3, 3)) # hazır bir fonksiyon da verilebilirÇıktı:
338350
1.9999999990686774
3025
12İkinci satır \(\sum_{k=0}^{30} 2^{-k} = 2 - 2^{-30}\) geometrik toplamıdır, üçüncüsü \(1^3 + \dots + 10^3 = 55^2 = 3025\)’tir. Son satırdaki abs gibi def ile ya da hazır tanımlı her fonksiyon da argüman olabilir. Bir lambda’yı bir ada atamak mümkündür, ama adı olacak bir fonksiyon için def yazmak daha okunurdur. Lambda en çok, burada olduğu gibi, tek kullanımlık argüman fonksiyonlarında işe yarar.
Örnek 2.13 (Genel Newton Fonksiyonu) \(f\) ile türevi \(f'\)’yi argüman olarak alan bir newton(f, df, x0) fonksiyonu yazıp \(\cos x = x\) denkleminin kökünü bulunuz.
Çözüm
Örnek 2.12’teki döngü, \(f\) ve \(f'\) için yer tutan iki parametreyle her denkleme genelleşir. \(f(x) = \cos x - x\) ve \(f'(x) = -\sin x - 1\) fonksiyonlarını lambda ile verir, \(x_0 = \pi/4\)’ten başlarız. Döngü değişkenini blokta kullanmadığımız için ona gelenekteki gibi _ adını verdik.
import math
def newton(f, df, x0, tol=1e-12, max_iter=50):
"""f(x) = 0 denkleminin x0 yakınındaki kökünü döndürür."""
x = x0
for _ in range(max_iter):
x_new = x - f(x) / df(x)
if abs(x_new - x) < tol:
return x_new
x = x_new
return x
p = newton(lambda x: math.cos(x) - x,
lambda x: -math.sin(x) - 1, math.pi / 4)
print(p, math.cos(p) - p)
print(newton(lambda x: x**3 - 2*x - 5, lambda x: 3*x**2 - 2, 2.0))Çıktı:
0.7390851332151606 1.1102230246251565e-16
2.0945514815423265Kök \(p \approx 0{,}7390851332\)’dir (bkz. Nümerik Analiz). \(f(p)\)’nin yaklaşık \(1{,}1 \cdot 10^{-16}\) çıkması, sonucun makine duyarlığı düzeyinde doğru olduğunu gösterir. Aynı fonksiyon, Newton’un kendi örneği olan \(x^3 - 2x - 5 = 0\) denkleminin \(2{,}0945514815\) kökünü de verir. \(\blacksquare\)
2.6 Özyineleme
Matematikte pek çok nesne kendisi cinsinden tanımlanır: \(0! = 1\) ve \(n! = n \cdot (n-1)!\); Fibonacci sayıları için \(F_0 = 0\), \(F_1 = 1\) ve \(F_n = F_{n-1} + F_{n-2}\). Python’da bir fonksiyon kendini çağırabildiğinden bu tanımlar neredeyse kelimesi kelimesine koda dönüşür.
Tanım 2.13 (Özyinelemeli Fonksiyon) Bloğunda kendisini çağıran fonksiyona özyinelemeli (recursive) fonksiyon denir. Böyle bir fonksiyonun en az bir taban durumu, yani kendini çağırmadan doğrudan sonuç döndürdüğü girdileri vardır. Diğer girdilerde fonksiyon, taban durumuna daha yakın girdilerle kendini çağırır ve bu çağrıların sonuçlarından kendi sonucunu kurar.
Yani özyineleme, tümevarımın hesaptaki karşılığıdır (bkz. Analiz 1): taban durumu başlangıç adımına, özyineli çağrı tümevarım adımına karşılık gelir. Taban durumu unutulursa ya da çağrılar tabana yaklaşmazsa fonksiyon kendini durmadan çağırır.
Örnek 2.14 (Özyinelemeli Faktöriyel) \(n!\)’i özyinelemeyle hesaplayan bir fonksiyon yazınız ve \(20!\) için sonucu döngüyle bulunan değerle karşılaştırınız.
Çözüm
Tanım doğrudan koda dönüşür: taban durumu \(0! = 1\), özyineli adım \(n! = n \cdot (n-1)!\). Karşılaştırma için tarifteki çarpım kalıbıyla yazılmış bir döngü sürümü ile Python’un math.factorial fonksiyonunu kullanıyoruz.
import math
def fact(n):
"""n! değerini özyinelemeyle hesaplar (n >= 0 tam sayı)."""
if n == 0:
return 1 # taban durumu
return n * fact(n - 1) # özyineli adım
def fact_loop(n):
p = 1
for k in range(2, n + 1):
p *= k
return p
print(fact(5), fact(20))
print(fact(20) == fact_loop(20) == math.factorial(20))Çıktı:
120 2432902008176640000
Truefact(5) çağrısı 5 * fact(4) değerini, o da 4 * fact(3) değerini bekler. Zincir fact(0)’a ulaşınca geri dönüşte \(1, 1, 2, 6, 24, 120\) değerleri sırayla oluşur. Üç yöntem de \(20! = 2432902008176640000\) verir; zincirleme == üçünün eşitliğini tek satırda sınar. \(\blacksquare\)
Örnek 2.15 (Saf Özyinelemeli Fibonacci) \(F_n\)’yi tanımı doğrudan izleyen özyinelemeli bir fonksiyonla hesaplayınız ve \(n = 5, 10, \dots, 30\) için fonksiyonun kaç kez çağrıldığını sayınız.
fib(5) çağrısının ağacı: toplam 15 çağrı. fib(3) (turuncu) iki kez, fib(2) (yeşil) üç kez baştan hesaplanır. n büyüdükçe aynı alt ağaçlar katlanarak tekrarlanır; fib(30) için çağrı sayısı 2692537'dir.Çözüm
Çağrıları saymak için global bir calls sayacı kullanırız. Fonksiyon bu sayaca değer atadığından blokta global calls bildirimi gerekir (Tanım 2.10). Her \(n\) için sayacı sıfırlayıp fonksiyonu çağırırız.
calls = 0
def fib(n):
"""n. Fibonacci sayısı: saf özyineleme."""
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in range(5, 31, 5):
calls = 0
value = fib(n)
print(f"fib({n:2}) = {value:6} çağrı sayısı: {calls:7}")Çıktı:
fib( 5) = 5 çağrı sayısı: 15
fib(10) = 55 çağrı sayısı: 177
fib(15) = 610 çağrı sayısı: 1973
fib(20) = 6765 çağrı sayısı: 21891
fib(25) = 75025 çağrı sayısı: 242785
fib(30) = 832040 çağrı sayısı: 2692537Çağrı sayısı \(C(n)\) için \(C(0) = C(1) = 1\) ve \(C(n) = 1 + C(n-1) + C(n-2)\) olduğundan tümevarımla \(C(n) = 2F_{n+1} - 1\) bulunur; örneğin
\[C(30) = 2 \cdot 1346269 - 1 = 2692537.\]
\(F_n\), yaklaşık \(1{,}618^n/\sqrt{5}\) hızıyla büyür (\(1{,}618 \approx (1 + \sqrt{5})/2\) altın orandır). Bu yüzden çağrı sayısı \(n\) ile üstel olarak artar: \(n\)’yi \(5\) artırmak işi yaklaşık \(1{,}618^5 \approx 11\) katına çıkarır. Şekildeki ağaç sorunun kaynağını gösteriyor: aynı değerler tekrar tekrar baştan hesaplanıyor. \(\blacksquare\)
Tanım 2.14 (Hafızalama) Bir fonksiyonun hesapladığı her sonucu girdisiyle birlikte bir depoya kaydetmesine ve aynı girdiyle yeniden çağrıldığında hesabı tekrarlamadan kayıtlı sonucu döndürmesine hafızalama (memoization) denir.
Yani hafızalama, hesap süresini bellekle takas eder: Fibonacci ağacında her \(F_k\) yalnız bir kez hesaplanır, sonraki istekler depodan karşılanır. Depo olarak Python’un sözlük (dict) yapısını kullanacağız. Sözlükleri Veri Yapıları ve Comprehension bölümünde ayrıntılı göreceğiz; burada üç işlem yeter. memo = {0: 0, 1: 1} iki başlangıç kaydıyla bir sözlük kurar, n in memo \(n\) için kayıt olup olmadığını sorar, memo[n] = değer kaydı yazar ve memo[n] onu okur.
Örnek 2.16 (Hafızalı Fibonacci) Fibonacci fonksiyonunu hafızalı yazarak \(F_{30}\) ve \(F_{100}\) sayılarını hesaplayınız; çağrı sayılarını Örnek 2.15 ile karşılaştırınız.
Çözüm
Taban durumları sözlüğün başlangıç kayıtlarıdır. Fonksiyon önce depoya bakar; kayıt yoksa değeri iki özyineli çağrıyla hesaplayıp kaydeder. calls += 1 satırı calls adına yeni bir değer atadığı için yine global calls bildirimi gerekir. memo[n] = ... satırı ise memo adına yeni bir değer atamaz, yalnız bu adın gösterdiği sözlüğün içeriğini değiştirir; bu yüzden memo için bildirim gerekmez.
memo = {0: 0, 1: 1} # hesaplanan değerlerin deposu (sözlük)
calls = 0
def fib(n):
"""n. Fibonacci sayısı: hafızalı özyineleme."""
global calls
calls += 1
if n in memo:
return memo[n] # daha önce hesaplandı: hazır değer
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(30), "çağrı sayısı:", calls)
calls = 0
print(fib(100), "çağrı sayısı:", calls)Çıktı:
832040 çağrı sayısı: 59
354224848179261915075 çağrı sayısı: 141\(F_{30}\) için çağrı sayısı \(2692537\)’den \(59 = 2 \cdot 30 - 1\)’e indi, çünkü her \(F_k\) bir kez hesaplanıyor. \(F_{100}\) yalnız \(141\) çağrı tuttu, çünkü \(F_0, \dots, F_{30}\) önceki hesaptan depoda duruyordu. Saf sürümle \(F_{100}\) için \(2F_{101} - 1 \approx 1{,}1 \cdot 10^{21}\) çağrı gerekirdi.
Python’un standart kütüphanesi bu kalıbı hazır sunar. functools modülündeki cache, fonksiyon tanımının üstüne @cache satırı olarak yazıldığında fonksiyonu kendi deposuyla hafızalı hâle getirir. Bir fonksiyonu böyle saran @ satırlarına dekoratör denir.
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100))
print(fib.cache_info())Çıktı:
354224848179261915075
CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)cache_info() deponun durumunu bildirir: \(F_0, \dots, F_{100}\) olmak üzere \(101\) değer birer kez hesaplandı (misses), \(98\) istek depodan karşılandı (hits). \(\blacksquare\)
Her özyineli çağrı, geri dönülecek yeri saklamak için bellek harcar. Python bu yüzden iç içe çağrıların derinliğini sınırlar; sınır aşılınca program RecursionError hatasıyla durur. Sınırı sys modülü söyler:
import sys
print(sys.getrecursionlimit())Çıktı:
1000Bu yüzden fact(5000) gibi binlerce düzey inen bir özyineleme hata verir; hafızalı fib(5000) çağrısı da aynı nedenle başarısız olur. Derinliği girdiyle doğrusal büyüyen hesaplarda döngü kullanın. Özyinelemeyi, ebob ya da hızlı üs alma gibi derinliği logaritmik kalan hesaplara ve doğal olarak ağaç biçimli problemlere saklayın.
2.7 Alıştırmalar
Aşağıdaki alıştırmalarda bölümdeki kalıpları kendi başınıza uygulayacaksınız. Her çözümdeki kod kendi başına çalışır.
Alıştırma 2.1 (Artık Yıl Kuralı) Gregoryen takvimde \(4\)’e bölünen yıllar artık yıldır; ancak \(100\)’e bölünen yıllar, \(400\)’e de bölünmedikçe artık yıl değildir. Bu kuralı bir is_leap(year) fonksiyonuyla yazıp \(1901\) ile \(2000\) arasındaki (ikisi de dahil) artık yılları sayınız.
Çözüm
Kuralda en özel durum en önce sınanmalıdır: önce \(400\), sonra \(100\), en son \(4\). return fonksiyonu hemen bitirdiğinden elif yazmaya gerek kalmaz; bir return’e ulaşan çağrı alttaki satırları hiç görmez. Son satırdaki year % 4 == 0 zaten bir bool olduğundan doğrudan döndürülür.
def is_leap(year):
"""Gregoryen takvimde artık yıl mı?"""
if year % 400 == 0:
return True
if year % 100 == 0:
return False
return year % 4 == 0
print(is_leap(1900), is_leap(2000), is_leap(2024), is_leap(2026))
count = 0
for y in range(1901, 2001):
if is_leap(y):
count += 1
print("1901-2000 arası artık yıl:", count)Çıktı:
False True True False
1901-2000 arası artık yıl: 25\(1900\), \(100\)’e bölünüp \(400\)’e bölünmediğinden artık yıl değildir; \(2000\) ise \(400\)’e bölündüğünden artık yıldır. \(1901\) ile \(2000\) arasında \(1904, 1908, \dots, 2000\) olmak üzere \(25\) artık yıl vardır. \(\blacksquare\)
Alıştırma 2.2 (Rakamlar Toplamı) Bir doğal sayının onluk tabandaki rakamlarının toplamını while döngüsüyle hesaplayan bir digit_sum(n) fonksiyonu yazınız ve \(2^{100}\) sayısının rakamları toplamını bulunuz.
Çözüm
\(n\)’nin son rakamı \(n \bmod 10\)’dur, \(\lfloor n/10 \rfloor\) ise son rakamı silinmiş sayıdır. divmod(n, 10) ikisini birlikte verir. \(n\) sıfır olana dek son rakamı ayırıp toplama ekleriz.
def digit_sum(n):
"""n >= 0 tam sayısının onluk tabandaki rakamlarının toplamı."""
s = 0
while n > 0:
n, d = divmod(n, 10) # son rakamı ayır
s += d
return s
print(digit_sum(2026), digit_sum(9**9))
print(2**100)
print(digit_sum(2**100))Çıktı:
10 45
1267650600228229401496703205376
115\(9^9 = 387420489\) sayısının rakamları toplamı \(45\)’tir. Python’un sınırsız tam sayıları sayesinde \(31\) basamaklı \(2^{100}\) de kesin hesaplanır ve rakamları toplamı \(115\) çıkar. \(\blacksquare\)
Alıştırma 2.3 (Mükemmel Sayılar) Kendisinden küçük pozitif bölenlerinin toplamına eşit olan sayılara mükemmel sayı denir; örneğin \(6 = 1 + 2 + 3\). \(10000\)’den küçük mükemmel sayıları bulunuz.
Çözüm
Önerme 2.2’deki fikir bölen toplamını da hızlandırır: \(d \le \sqrt{n}\) bir bölense eşi \(n/d\) de bir bölendir. Bu yüzden \(d\)’yi yalnız \(2, \dots, \lfloor \sqrt{n} \rfloor\) arasında dolaştırıp her bölende hem \(d\)’yi hem \(n/d\)’yi ekleriz. \(d = n/d\) ise, yani \(n\) tam kareyse bu bölen bir kez eklenir. \(1\) her zaman bölen olduğundan toplam \(1\)’den başlar.
import math
def divisor_sum(n):
"""n'nin kendisinden küçük pozitif bölenlerinin toplamı (n > 1)."""
s = 1
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
s += d
if d != n // d:
s += n // d # eş bölen n/d de sayılır
return s
for n in range(2, 10001):
if divisor_sum(n) == n:
print(n, "mükemmel")Çıktı:
6 mükemmel
28 mükemmel
496 mükemmel
8128 mükemmelDört mükemmel sayı bulunur: \(6\), \(28\), \(496\) ve \(8128\). Bunlar \(p = 2, 3, 5, 7\) için \(2^{p-1}(2^p - 1)\) biçimindedir. Öklid, \(2^p - 1\) asal olduğunda bu sayının mükemmel olduğunu göstermişti; Euler de her çift mükemmel sayının bu biçimde olduğunu kanıtladı. \(\blacksquare\)
Alıştırma 2.4 (Yüzü İki Asalın Toplamı Olarak Yazmak) \(100\) sayısının, \(p \le q\) olmak üzere iki asalın \(p + q\) toplamı olarak bütün yazılışlarını bulunuz.
Çözüm
Önce deneme bölmesini bir is_prime fonksiyonuna çeviririz. Bölen bulunduğu anda return False fonksiyonu bitirir; bu, Örnek 2.9’deki break ile else ikilisinin fonksiyon içindeki karşılığıdır. Sonra \(p\)’yi \(2, \dots, 50\) arasında dolaştırıp hem \(p\)’nin hem \(100 - p\)’nin asal olduğu durumları yazdırırız. \(p \le 50\) koşulu \(p \le q\) demektir.
import math
def is_prime(n):
"""n asal mı? (deneme bölmesi)"""
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False
return True
n = 100
count = 0
for p in range(2, n // 2 + 1):
if is_prime(p) and is_prime(n - p):
print(f"{n} = {p} + {n - p}")
count += 1
print("yazılış sayısı:", count)Çıktı:
100 = 3 + 97
100 = 11 + 89
100 = 17 + 83
100 = 29 + 71
100 = 41 + 59
100 = 47 + 53
yazılış sayısı: 6Altı yazılış vardır. Goldbach sanısı, \(2\)’den büyük her çift sayının en az bir yazılışı olduğunu söyler. Sanı çok büyük sayılara kadar bilgisayarla doğrulanmıştır ama ispatlanmamıştır. \(\blacksquare\)
Alıştırma 2.5 (Genişletilmiş Öklid Algoritması) \(a, b\) doğal sayıları için \(\gcd(a, b)\) ile birlikte \(ax + by = \gcd(a, b)\) eşitliğini sağlayan \(x, y\) tam sayılarını da bulan özyinelemeli bir ext_gcd(a, b) fonksiyonu yazınız ve \(a = 240\), \(b = 46\) için çalıştırınız.
Çözüm
\(b = 0\) ise \(\gcd(a, 0) = a\) ve \(a \cdot 1 + b \cdot 0 = a\)’dır; taban durumu budur. \(b \ne 0\) ise \(q = \lfloor a/b \rfloor\) ve \(r = a - qb\) olsun. Önerme 2.1 gereği \(\gcd(a, b) = \gcd(b, r) = g\)’dir. Özyineli çağrı \(bx' + ry' = g\) eşitliğini sağlayan \(x', y'\) sayılarını verirse
\[g = bx' + (a - qb)y' = ay' + b(x' - qy')\]
olduğundan \(x = y'\) ve \(y = x' - qy'\) alınır.
def ext_gcd(a, b):
"""(g, x, y) döndürür: g = ebob(a, b) ve a*x + b*y = g."""
if b == 0:
return a, 1, 0
g, x, y = ext_gcd(b, a % b)
return g, y, x - (a // b) * y
g, x, y = ext_gcd(240, 46)
print(g, x, y)
print(240 * x + 46 * y)
g, x, y = ext_gcd(1071, 462)
print(g, x, y, 1071 * x + 462 * y)Çıktı:
2 -9 47
2
21 -3 7 21Sağlamalar:
\[\begin{aligned} 240 \cdot (-9) + 46 \cdot 47 &= -2160 + 2162 = 2, \\ 1071 \cdot (-3) + 462 \cdot 7 &= -3213 + 3234 = 21. \end{aligned}\]
Böyle \(x, y\) sayılarının varlığı Bézout teoremidir (bkz. Sayılar Teorisi); bu fonksiyon onları açıkça kurar. Özyinelemenin derinliği Öklid algoritmasının adım sayısı kadardır ve Lamé teoremine göre bu sayı en fazla \(\log b\) ile orantılı büyür. \(\blacksquare\)
Alıştırma 2.6 (Hızlı Üs Alma) \(n\) çiftse \(a^n = (a^{n/2})^2\), tekse \(a^n = (a^{\lfloor n/2 \rfloor})^2 \cdot a\) eşitliklerini kullanarak \(a^n\)’yi hesaplayan özyinelemeli bir power(a, n) fonksiyonu yazınız. \(n = 100, 400, 700, 1000\) için \(3^n\) hesabında kaç çarpma yapıldığını sayınız.
Çözüm
Taban durumu \(a^0 = 1\)’dir. Her özyineli adım \(n\)’yi yarıya indirir; yarım kuvvet bir kez hesaplanıp kendisiyle çarpılır, \(n\) tekse bir çarpma daha yapılır. Çarpmaları global bir sayaçla sayarız.
mults = 0
def power(a, n):
"""a**n değerini n'yi ikiye bölerek hesaplar (n >= 0 tam sayı)."""
global mults
if n == 0:
return 1
half = power(a, n // 2)
mults += 1
result = half * half
if n % 2 == 1:
mults += 1
result *= a
return result
print(power(3, 13), 3**13)
for n in range(100, 1001, 300):
mults = 0
ok = power(3, n) == 3**n
print(f"n = {n:4} çarpma sayısı: {mults:2} doğru mu: {ok}")Çıktı:
1594323 1594323
n = 100 çarpma sayısı: 10 doğru mu: True
n = 400 çarpma sayısı: 12 doğru mu: True
n = 700 çarpma sayısı: 16 doğru mu: True
n = 1000 çarpma sayısı: 16 doğru mu: TrueDoğrudan \(a \cdot a \cdots a\) çarpımı \(n - 1\) çarpma ister; \(n = 1000\) için bu \(999\) demektir. Bu yöntem ise en fazla \(2(\lfloor \log_2 n \rfloor + 1)\) çarpma yapar ve \(n = 1000\) için \(16\) çarpmayla yetinir. Python’un ** işleci de tam sayı kuvvetlerini aynı fikre dayanan bir yöntemle hesaplar. \(\blacksquare\)
Alıştırma 2.7 (Euler Sayısının Serisi) \(e = \sum_{k=0}^{\infty} \dfrac{1}{k!}\) serisini, sıradaki terim \(10^{-17}\)’den küçük olana dek toplayınız ve sonucu math.e ile karşılaştırınız.
Çözüm
Her terimi faktöriyeli baştan hesaplayarak bulmak gereksizdir. \(\dfrac{1}{k!} = \dfrac{1}{(k-1)!} \cdot \dfrac{1}{k}\) olduğundan terimi her adımda \(k\)’ya bölmek yeter. Kaç terim gerektiğini bilmediğimiz için while kullanırız.
import math
total = 0.0
term = 1.0 # 1/0! = 1
k = 0
while term > 1e-17:
total += term
k += 1
term /= k # 1/k! = (1/(k-1)!) / k
print("toplanan terim sayısı:", k)
print("seri :", total)
print("math.e :", math.e)
print("fark :", total - math.e)Çıktı:
toplanan terim sayısı: 19
seri : 2.7182818284590455
math.e : 2.718281828459045
fark : 4.440892098500626e-16\(k = 0, \dots, 18\) olmak üzere \(19\) terim toplandı; \(1/19! \approx 8{,}2 \cdot 10^{-18}\) eşiğin altında kaldığından eklenmedi. Fark yaklaşık \(4{,}4 \cdot 10^{-16}\), yani son basamakta birkaç birimdir: terimler toplanırken yapılan yuvarlamalar birikir. \(e\) sayısının tanımı için bkz. Analiz 1. \(\blacksquare\)
Alıştırma 2.8 (Newton Yöntemiyle Küp Kök) \(f(x) = x^3 - a\) fonksiyonuna Newton yöntemini uygulayarak \(\sqrt[3]{a}\) değerini hesaplayan bir fonksiyon yazınız; başlangıç değeri, tolerans ve en fazla adım sayısı varsayılan değerli parametreler olsun. \(\sqrt[3]{10}\)’u hesaplayınız.
Çözüm
\(f'(x) = 3x^2\) olduğundan Newton adımı
\[x_{k+1} = x_k - \frac{x_k^3 - a}{3x_k^2} = \frac{1}{3}\left(2x_k + \frac{a}{x_k^2}\right)\]
olur. Fonksiyonun yapısı Örnek 2.12’tekiyle aynıdır.
def cbrt_newton(a, x0=1.0, tol=1e-14, max_iter=100):
"""a sayısının küp kökü: x <- (2x + a/x^2) / 3."""
x = x0
for k in range(1, max_iter + 1):
x_new = (2*x + a / x**2) / 3
if abs(x_new - x) < tol:
return x_new, k
x = x_new
return x, max_iter
root, steps = cbrt_newton(10)
print(root, steps)
print(root**3)
print(cbrt_newton(10, x0=2.0))
print(cbrt_newton(-27))Çıktı:
2.154434690031884 8
10.000000000000002
(2.154434690031884, 5)
(-3.0, 9)\(\sqrt[3]{10} \approx 2{,}154434690031884\) sekiz adımda bulundu; küpü \(10\)’a son basamaktaki yuvarlama farkıyla eşittir. Başlangıç değeri x0=2.0 ile köke yaklaştırılınca beş adım yetti. Fonksiyon negatif \(a\) için de çalışır: \(\sqrt[3]{-27} = -3\). \(\blacksquare\)
Alıştırma 2.9 (En Uzun Collatz Yolu) \(10000\)’den küçük başlangıç değerleri arasında Collatz dizisi \(1\)’e en çok adımda ulaşanı bulunuz.
Çözüm
Örnek 2.6’daki döngüyü, adım sayısını döndüren bir fonksiyona çeviririz; güncellemeyi koşullu ifadeyle tek satırda yazıyoruz. Sonra \(n = 1, \dots, 9999\) için en büyük adım sayısını ve onu veren \(n\)’yi saklarız.
def collatz_steps(n):
"""n'den 1'e ulaşana dek atılan Collatz adımlarının sayısı."""
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3*n + 1
steps += 1
return steps
best_n, best_steps = 1, 0
for n in range(1, 10000):
s = collatz_steps(n)
if s > best_steps:
best_n, best_steps = n, s
print("en uzun yol:", best_n, "başlangıcından", best_steps, "adım")
print("27 için:", collatz_steps(27))Çıktı:
en uzun yol: 6171 başlangıcından 261 adım
27 için: 111\(6171\) başlangıcı \(261\) adımla en uzun yoldur. Fonksiyonun \(27\) için örnekteki \(111\) adımı yeniden vermesi, iki yazımın tutarlı olduğunu gösteren bir sağlamadır. \(\blacksquare\)
Alıştırma 2.10 (Hanoi Kuleleri) A, B, C adlı üç çubuktan A’da, en büyüğü en altta olmak üzere \(n\) disk dizilidir. Her hamlede bir çubuğun en üstündeki disk başka bir çubuğa taşınır ve hiçbir disk kendisinden küçük bir diskin üstüne konmaz. \(n = 3\) için diskleri A’dan C’ye taşıyan hamleleri özyinelemeyle yazdırınız; hamle sayısının \(2^n - 1\) olduğunu birkaç \(n\) için doğrulayınız.
Çözüm
\(n\) diski A’dan C’ye taşımak için önce üstteki \(n - 1\) diski C’yi yardımcı kullanarak B’ye taşırız. Sonra en büyük diski A’dan C’ye götürür, en son \(n - 1\) diski A’yı yardımcı kullanarak B’den C’ye taşırız. Taban durumu \(n = 0\)’dır: yapılacak hamle yoktur. Hamle sayısı \(H_n\) için \(H_0 = 0\) ve \(H_n = 2H_{n-1} + 1\) olduğundan tümevarımla \(H_n = 2^n - 1\) bulunur.
moves = 0
def hanoi(n, source, target, spare, show=True):
"""n diski source'tan target'a, spare'i yardımcı kullanarak taşır."""
global moves
if n == 0:
return
hanoi(n - 1, source, spare, target, show)
moves += 1
if show:
print(f"disk {n}: {source} -> {target}")
hanoi(n - 1, spare, target, source, show)
hanoi(3, "A", "C", "B")
print("hamle sayısı:", moves)
for n in range(1, 11, 3):
moves = 0
hanoi(n, "A", "C", "B", show=False)
print(f"n = {n:2} hamle: {moves:4} 2^n - 1 = {2**n - 1}")Çıktı:
disk 1: A -> C
disk 2: A -> B
disk 1: C -> B
disk 3: A -> C
disk 1: B -> A
disk 2: B -> C
disk 1: A -> C
hamle sayısı: 7
n = 1 hamle: 1 2^n - 1 = 1
n = 4 hamle: 15 2^n - 1 = 15
n = 7 hamle: 127 2^n - 1 = 127
n = 10 hamle: 1023 2^n - 1 = 1023Fonksiyonun show parametresinin varsayılan değeri True’dur. Büyük \(n\)’lerde hamleleri yazdırmamak için show=False veriyoruz; sayaç yine her hamlede artar. \(\blacksquare\)
Alıştırma 2.11 (Pascal Kuralıyla Binom Katsayısı) \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) ve \(\binom{n}{0} = \binom{n}{n} = 1\) kurallarıyla binom katsayısını hafızalı özyinelemeyle hesaplayıp \(\binom{30}{15}\) değerini bulunuz.
Çözüm
Kural doğrudan özyinelemeli bir fonksiyon verir. Hafızasız sürümde her taban durumu sonuca \(1\) katkı verir; bu yüzden \(\binom{30}{15}\) için en az \(\binom{30}{15}\) kez taban durumuna inilirdi. @cache her \((n, k)\) çiftini bir kez hesaplatır.
import math
from functools import cache
@cache
def binom(n, k):
"""C(n, k): Pascal kuralıyla özyineli hesap."""
if k == 0 or k == n:
return 1
return binom(n - 1, k - 1) + binom(n - 1, k)
print(binom(30, 15), math.comb(30, 15))
print(binom.cache_info())Çıktı:
155117520 155117520
CacheInfo(hits=196, misses=255, maxsize=None, currsize=255)Sonuç math.comb ile aynıdır. Depoda \(255\) farklı \((n, k)\) çifti var; hafızasız sürümdeki çağrı sayısı ise \(2\binom{30}{15} - 1 = 310235039\), yani yaklaşık \(3 \cdot 10^8\) olurdu. \(\blacksquare\)
Bu bölümde programın akışını yöneten üç yapıyı (karar, sayısı belli tekrar ve koşula bağlı tekrar) ve hesapları adlandırıp yeniden kullanmamızı sağlayan fonksiyonları gördük. Şimdiye dek hep tek tek sayılarla çalıştık; Collatz dizisinin terimlerini ya da bulduğumuz asalları bir yerde saklamadık. Bir sonraki bölüm Veri Yapıları ve Comprehension, sayı topluluklarını tutan listeleri, demetleri, sözlükleri ve kümeleri ele alıyor.