Factorial
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
- 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! = 479001600olur.
Örnekler
- Girdi
- n = 5
- Çıktı
- 120
- Açıklama
1 × 2 × 3 × 4 × 5iş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üzden0! = 1.
Gönderirken +11 gizli test
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.
4!ve5!ifadelerini çarpım olarak yazın.5!,4!ile nasıl ilişkilidir?5! = 5 × 4!. Genel olarakn! = n × (n-1)!ve zincir0! = 1noktasında durur.1değerinden başlayan bir çarpım değerini güncel tut ve2'denn'ye kadar her sayıyla çarp. 1'den başlamak,0ve1için de doğru sonucu verir.
Çö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
ndeğeri0ise1döndür. Bu, temel durumdur.- Aksi takdirde, işlevi
n-1üzerinde çağır. - Bu sonucu
nile ç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 = 1olarak ayarla.kdeğerini2'denn'e kadar (her ikisi de dahil) döngüye sok.- Her adımda
resultdeğerinikile çarp. resultdeğ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ı
0ile başlatmak. Her çarpma sonucu yine 0 olur. Çarpımın başlangıç değeri1olmalıdır. - Özyinelemeyi yalnızca
n == 1olduğunda durdurmak.0ile ç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 == 0değerini temel durum yap. k ≤ nyerinek < nkoşuluyla döngü kurmak. Böylece son çarpan atlanır ve(n-1)!döndürülür; bu nedenle5iç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 fazla20!değerini tutabilir; daha büyük değerler için büyük tam sayılar gerekir. - Swift'te
for k in 2...nyazmak. Bitiş değeri başlangıç değerinden küçük olan kapalı bir aralık,n0 veya 1 olduğunda çalışma zamanında çöker.
Sıkça sorulan sorular4
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.
Bir tamsayıya sığan en büyük faktöriyel nedir?
12! = 479001600, işaretli 32 bitlik bir tam sayıya sığan en büyük faktöriyeldir. 20! = 2432902008176640000, işaretli 64 bitlik bir tam sayı için en büyük faktöriyeldir. Daha büyük sayılar için Python'ın int türü, Java'nın BigInteger sınıfı veya JavaScript'in BigInt türü gibi sınırsız büyüklükte sayılara ihtiyacınız vardır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def factorial(n):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
n = 5
Beklenen
120