Factorial

Q: Faktöriyel hesaplamanın zaman karmaşıklığı nedir?

Hem döngü hem de özyineleme, n değerine kadar her sayı için bir çarpma işlemi yapar; bu nedenle zaman karmaşıklığı O(n) olur. Döngü O(1) ek alan gerektirir. Özyineleme, temel durum dönene kadar her çağrı için bir yığın çerçevesi tutar; bu nedenle O(n) alan kullanır.

Q: 0! neden 1'e eşittir?

0! hiçbir sayının çarpımıdır ve çarpanı olmayan bir çarpım 1 'dir; tıpkı terimi olmayan bir toplamın 0 olması gibi. Bu, n! = n × (n-1)! kuralının n = 1 için de doğru olmasını sağlar: 1! = 1 × 0! = 1 . Sayma da bunu doğrular: sıfır öğeyi sıralamanın tam olarak bir yolu vardır.

Q: Faktöriyel hesaplamak için özyineleme mi yoksa döngü mü daha iyidir?

Aynı çarpma işlemlerini yapar ve aynı sonucu döndürürler. Özyinelemeli sürüm, matematiksel tanım gibi okunur; bu nedenle özyineleme konusundaki klasik ilk alıştırmadır. Döngü sabit bellek kullanır ve çağrı yığınını taşırmaz; bu yüzden gerçek kodlarda daha iyi bir seçimdir.

BaşlangıçMatematik ve simülasyon Özyineleme

+10

n tam sayısının, n! şeklinde yazılan faktöriyeli, 1'den n'ye kadar olan tüm tam sayıların çarpımıdır. Örneğin, 4! = 1 × 2 × 3 × 4 = 24. Tanım gereği 0! = 1. Fonksiyonun n değerini alır ve n! değerini döndürür.

Fonksiyon

factorial(n: integer) → integer

ninteger: Faktöriyelini hesapladığınız tam sayı
Döndürürinteger: 1’den n’ye kadar olan tüm tam sayıların çarpımıdır; n 0 olduğunda bu değer 1’dir.

Kısıtlar

0 ≤ n ≤ 12
Yanıt, işaretli 32 bitlik bir tam sayıya sığar: en büyüğü 12! = 479001600 olur.

Örnekler

Girdi: n = 5
Çıktı: 120
Açıklama: 1 × 2 × 3 × 4 × 5 işlemini çarpın. Ara çarpımlar 1, 2, 6, 24 şeklinde ilerler ve sonuç 120 olur.

Girdi: n = 0
Çıktı: 1
Açıklama: Çarpılacak hiçbir şey yoktur ve çarpanı olmayan bir çarpım 1’dir. İşte bu yüzden 0! = 1.

Ek soru

100! sayısı 158 basamaklıdır. Hesaplamadan, sonunda kaç sıfır olduğunu sayabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Faktöriyel iki eşdeğer tanıma sahiptir ve her biri koda dönüştürülebilir. Bir çarpım olarak, n! = 1 × 2 × ... × n; bu bir döngüdür. Özyinelemeli bir tanım olarak, 0! = 1 ve n! = n × (n-1)!; bu da kendisini çağıran bir işlevdir. Her ikisi de yaklaşık n çarpma işlemi yapar. Sonunda kullanılması gereken döngüdür, çünkü çağrı yığını gerektirmez.

Tanımdan özyineleme

Sezgi

Faktöriyel, daha küçük bir faktöriyel üzerinden tanımlanır: n! = n × (n-1)!. 4! = 24 olduğunu zaten biliyorsan, 5! = 5 × 24 = 120 olur. Özyinelemeli bir işlev, bu cümleyi kod olarak yazar. factorial(n) sonucunu bulmak için factorial(n-1) değerini ister ve yanıtı n ile çarpar.

Çağrıların duracağı bir yere, yani temel duruma ihtiyaç vardır: factorial(0), hiçbir şeyi çağırmadan 1 döndürür. Her çağrı n değerini bir azaltır; bu nedenle 5 için çağrılar 5, 4, 3, 2, 1, 0 şeklinde ilerler. Ardından yanıtlar zincir boyunca geri döner: 1, 1, 2, 6, 24, 120.

n + 1 çağrı ve n çarpma vardır; bu yüzden çalışma süresi O(n) olur. Her çağrı, altındaki çağrı dönene kadar yığında bekler; bu nedenle yığın n + 1 çerçeve tutar ve bu da O(n) alan demektir. n ≤ 12 olduğunda bu çok azdır; ancak aynı kalıp büyük bir girdi üzerinde yığın taşmasına yol açar.

Algoritma

n değeri 0 ise 1 döndür. Bu, temel durumdur.
Aksi takdirde, işlevi n-1 üzerinde çağır.
Bu sonucu n ile çarp ve döndür.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Döngüde çarpma

Sezgi

Özyinelemeyi açtığınızda bir birikimli çarpım elde edersiniz. result = 1 ile başlayın ve önce 2 ile, sonra 3 ile ve bu şekilde n'ye kadar çarpın. n = 5 için sonuç 1, 2, 6, 24, 120 olur.

1'den başlamak en küçük girdileri de kapsar. n = 0 ve n = 1 için 2'den n'ye kadar olan döngü sıfır kez çalışır ve fonksiyon başlangıç değeri olan 1'i döndürür; bu her iki durum için de doğru yanıttır.

Döngü n-1 çarpma işlemi yapar; zaman karmaşıklığı O(n)'dir ve tek bir sayı tutar; alan karmaşıklığı O(1)'dir. Taşabilecek bir çağrı yığını yoktur; bu nedenle, özyinelemeli sürümü gösterdikten sonra görüşmeciler bu sürümü bekler.

Algoritma

result = 1 olarak ayarla.
k değerini 2'den n'e kadar (her ikisi de dahil) döngüye sok.
Her adımda result değerini k ile çarp.
result değerini döndür.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Tuzaklar ve uç durumlar

Faktöriyel kodu kısadır, bu yüzden hatalar uç durumlarda ortaya çıkar.

Çarpımı 0 ile başlatmak. Her çarpma sonucu yine 0 olur. Çarpımın başlangıç değeri 1 olmalıdır.
Özyinelemeyi yalnızca n == 1 olduğunda durdurmak. 0 ile çağrıldığında bu işlev temel durumuna asla ulaşmaz: yığın taşana kadar -1, -2 ve benzeri değerlerle devam eder. n == 0 değerini temel durum yap.
k ≤ n yerine k < n koşuluyla döngü kurmak. Böylece son çarpan atlanır ve (n-1)! döndürülür; bu nedenle 5 için 120 yerine 24 elde edilir.
Taşmayı yok saymak. 13! = 6227020800, işaretli 32 bitlik bir tam sayıya sığmaz. Java ve C# dillerinde çarpım sessizce yanlış bir sayıya sarılır; C dilinde işaretli taşma tanımsız davranıştır ve Rust'ta hata ayıklama derlemesi paniğe yol açar. 64 bitlik bir tam sayı en fazla 20! değerini tutabilir; daha büyük değerler için büyük tam sayılar gerekir.
Swift'te for k in 2...n yazmak. Bitiş değeri başlangıç değerinden küçük olan kapalı bir aralık, n 0 veya 1 olduğunda çalışma zamanında çöker.

Sıkça sorulan sorular3

Faktöriyel hesaplamanın zaman karmaşıklığı nedir?

Hem döngü hem de özyineleme, n değerine kadar her sayı için bir çarpma işlemi yapar; bu nedenle zaman karmaşıklığı O(n) olur. Döngü O(1) ek alan gerektirir. Özyineleme, temel durum dönene kadar her çağrı için bir yığın çerçevesi tutar; bu nedenle O(n) alan kullanır.

0! neden 1'e eşittir?

0! hiçbir sayının çarpımıdır ve çarpanı olmayan bir çarpım 1'dir; tıpkı terimi olmayan bir toplamın 0 olması gibi. Bu, n! = n × (n-1)! kuralının n = 1 için de doğru olmasını sağlar: 1! = 1 × 0! = 1. Sayma da bunu doğrular: sıfır öğeyi sıralamanın tam olarak bir yolu vardır.

Faktöriyel hesaplamak için özyineleme mi yoksa döngü mü daha iyidir?

Aynı çarpma işlemlerini yapar ve aynı sonucu döndürürler. Özyinelemeli sürüm, matematiksel tanım gibi okunur; bu nedenle özyineleme konusundaki klasik ilk alıştırmadır. Döngü sabit bellek kullanır ve çağrı yığınını taşırmaz; bu yüzden gerçek kodlarda daha iyi bir seçimdir.

def factorial(n):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

n = 5

Beklenen Çıktı