Factorial

Q: Apa kompleksitas waktu untuk menghitung faktorial?

Perulangan dan rekursi sama-sama melakukan satu perkalian untuk setiap angka hingga n : waktu O(n) . Perulangan membutuhkan ruang tambahan O(1) . Rekursi menyimpan satu frame stack untuk setiap pemanggilan hingga kasus dasar mengembalikan nilai, jadi rekursi menggunakan ruang O(n) .

Q: Mengapa 0! sama dengan 1?

0! adalah hasil kali dari tidak ada angka, dan hasil kali tanpa faktor adalah 1 , sama seperti jumlah tanpa suku adalah 0 . Ini juga membuat n! = n × (n-1)! tetap benar saat n = 1 . Selain itu, hanya ada satu cara untuk menyusun nol item.

Q: Berapa faktorial terbesar yang muat dalam sebuah bilangan bulat?

12! = 479001600 adalah faktorial terbesar yang dapat ditampung dalam bilangan bulat bertanda 32-bit. 20! = 2432902008176640000 adalah yang terbesar untuk bilangan bulat bertanda 64-bit. Di atas itu, kamu memerlukan bilangan dengan ukuran tak terbatas, seperti int di Python, BigInteger di Java, atau BigInt di JavaScript.

PemulaMatematika dan simulasi Rekursi

+10

Faktorial dari bilangan bulat nonnegatif n, yang ditulis n!, adalah hasil kali setiap bilangan bulat dari 1 hingga n. Contohnya, 4! = 1 × 2 × 3 × 4 = 24. Berdasarkan definisi, 0! = 1. Fungsi kamu menerima n dan mengembalikan n!.

Fungsi

factorial(n: integer) → integer

ninteger: bilangan bulat yang faktorialnya kamu hitung
Mengembalikaninteger: hasil perkalian semua bilangan bulat dari 1 hingga n, yang bernilai 1 jika n adalah 0

Batasan

0 ≤ n ≤ 12
Jawabannya muat dalam integer bertanda 32-bit: nilai terbesarnya adalah 12! = 479001600.

Contoh

Input: n = 5
Output: 120
Penjelasan: Kalikan 1 × 2 × 3 × 4 × 5. Hasil perkalian berturut-turut adalah 1, 2, 6, 24 dan berakhir di 120.

Input: n = 0
Output: 1
Penjelasan: Tidak ada yang dikalikan, dan hasil kali tanpa faktor adalah 1. Itulah sebabnya 0! = 1.

Pertanyaan lanjutan

100! memiliki 158 digit. Bisakah kamu menghitung berapa banyak nol di bagian akhirnya tanpa menghitung hasilnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Faktorial memiliki dua deskripsi yang setara, dan masing-masing dapat menjadi kode. Sebagai hasil kali, n! = 1 × 2 × ... × n adalah perulangan. Sebagai definisi rekursif, 0! = 1 dan n! = n × (n-1)! adalah fungsi yang memanggil dirinya sendiri. Keduanya melakukan sekitar n perkalian; perulangan tidak memerlukan tumpukan pemanggilan.

Rekursi berdasarkan definisinya

Intuisi

Jika kamu tahu 4! = 24, maka 5! = 5 × 24 = 120. Jadi, factorial(n) meminta factorial(n-1) lalu mengalikan jawabannya dengan n. Kasus dasar factorial(0) mengembalikan 1 tanpa pemanggilan. Dari 5, pemanggilan berjalan turun: 5, 4, 3, 2, 1, 0, lalu jawabannya kembali naik: 1, 1, 2, 6, 24, 120.

Ada n + 1 pemanggilan dan n perkalian: waktu O(n). Setiap pemanggilan menunggu di stack hingga pemanggilan di bawahnya selesai, jadi stack menampung n + 1 frame, ruang O(n).

Algoritma

Jika n adalah 0, kembalikan 1. Ini adalah kasus dasar.
Jika tidak, panggil fungsi dengan n-1.
Kalikan hasil tersebut dengan n, lalu kembalikan hasilnya.

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

Kalikan dalam perulangan

Intuisi

Uraikan rekursi menjadi hasil kali yang terus diperbarui: mulai dari result = 1 lalu kalikan dengan 2, kemudian 3, dan seterusnya hingga n. Memulai dari 1 juga mencakup n = 0 dan n = 1: perulangan dari 2 hingga n berjalan nol kali dan mengembalikan 1, jawaban yang tepat untuk keduanya.

Artinya ada n-1 perkalian, waktu O(n), dan satu angka, ruang O(1), tanpa call stack yang bisa meluap.

Algoritma

Tetapkan result = 1.
Ulangi k dari 2 hingga n, termasuk keduanya.
Kalikan result dengan k pada setiap langkah.
Kembalikan result.

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

Jebakan dan kasus tepi

Memulai hasil kali dengan 0. Setiap perkalian membuatnya tetap 0, jadi mulailah dengan 1.
Menghentikan rekursi hanya pada n == 1. Jika dipanggil dengan 0, fungsi akan terus berlanjut ke -1, -2, dan seterusnya hingga stack overflow. Jadikan n == 0 sebagai kasus dasar.
Melakukan perulangan dengan k < n, bukan k ≤ n. Faktor terakhir jadi tidak disertakan, sehingga 5 menghasilkan 24, bukan 120.
Di Swift, menulis for k in 2...n. Rentang tertutup yang nilai akhirnya lebih kecil daripada nilai awalnya akan menyebabkan crash saat program dijalankan jika n bernilai 0 atau 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menghitung faktorial?

Perulangan dan rekursi sama-sama melakukan satu perkalian untuk setiap angka hingga n: waktu O(n). Perulangan membutuhkan ruang tambahan O(1). Rekursi menyimpan satu frame stack untuk setiap pemanggilan hingga kasus dasar mengembalikan nilai, jadi rekursi menggunakan ruang O(n).

Mengapa 0! sama dengan 1?

0! adalah hasil kali dari tidak ada angka, dan hasil kali tanpa faktor adalah 1, sama seperti jumlah tanpa suku adalah 0. Ini juga membuat n! = n × (n-1)! tetap benar saat n = 1. Selain itu, hanya ada satu cara untuk menyusun nol item.

Berapa faktorial terbesar yang muat dalam sebuah bilangan bulat?

12! = 479001600 adalah faktorial terbesar yang dapat ditampung dalam bilangan bulat bertanda 32-bit. 20! = 2432902008176640000 adalah yang terbesar untuk bilangan bulat bertanda 64-bit. Di atas itu, kamu memerlukan bilangan dengan ukuran tak terbatas, seperti int di Python, BigInteger di Java, atau BigInt di JavaScript.

def factorial(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 5

Output yang diharapkan