Square Root (Integer)
Fungsi kamu menerima bilangan bulat nonnegatif x dan mengembalikan akar kuadrat bilangan bulatnya: bilangan bulat terbesar r dengan r × r ≤ x. Artinya, akar kuadratnya dibulatkan ke bawah, sehingga bilangan yang bukan kuadrat sempurna mendapatkan akar dari kuadrat sempurna di bawahnya. Hitung sendiri, tanpa fungsi akar kuadrat atau pangkat bawaan.
Fungsi
- xinteger
- bilangan bulat nonnegatif yang akan dicari akar kuadratnya
- Mengembalikaninteger
- akar kuadrat dari x yang dibulatkan ke bawah menjadi bilangan bulat
Batasan
0 ≤ x ≤ 231 - 1- Jangan panggil fungsi akar kuadrat, pangkat, atau eksponen bawaan.
Contoh
- Input
- x = 17
- Output
- 4
- Penjelasan
4 × 4 = 16paling besar 17, tetapi5 × 5 = 25lebih besar, jadi akar dari 17 dibulatkan ke bawah menjadi 4.
- Input
- x = 49
- Output
- 7
- Penjelasan
- 49 adalah kuadrat sempurna,
7 × 7 = 49, jadi tidak ada yang dibulatkan dan jawabannya tepat 7.
Pertanyaan lanjutan
Bagaimana kamu mencari akar pangkat tiga bilangan bulat, yaitu r terbesar dengan r × r × r ≤ x, jika x juga bisa negatif?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Jawabannya adalah bilangan bulat terbesar yang kuadratnya paling banyak
x. Jika kamu menguadratkan kandidatmdan membandingkannya denganx, apa yang kamu ketahui tentang kandidat yang lebih kecil dan lebih besar darim?Kuadrat bertambah besar seiring bertambahnya
m. Jikam × m ≤ x, semua kandidat yang lebih kecil juga muat; jikam × m > x, semua kandidat yang lebih besar tidak muat. Kandidat membentuk urutan yang terurut, dimulai dari yang muat lalu diikuti yang tidak muat, dan pencarian biner menemukan titik peralihannya.Cari
mdi antara 0 danx. Saatm × m ≤ x, ingatmdan cari ke arah kanan; jika tidak, cari ke arah kiri. Kuadratkanmdengan bilangan bulat 64-bit, karenampertama bisa mencapai sekitar10^9.
Solusi
Bilangan kuadrat 0, 1, 4, 9, 16, dan seterusnya tersusun berurutan, jadi kamu bisa melakukan pencarian biner untuk menemukan bilangan terakhir yang kuadratnya paling besar x dalam sekitar 31 langkah. Jebakannya adalah overflow: kuadrat suatu kandidat tidak selalu muat dalam 32 bit.
Hitung naik mulai dari nol
Intuisi
Mulai dari r = 0 dan lanjutkan ke r + 1 selama kuadrat bilangan berikutnya masih kurang dari atau sama dengan x. Perulangan berhenti pada r pertama yang nilai berikutnya terlalu besar, yaitu akar. Untuk x = 17, kuadrat 1, 4, 9, dan 16 memenuhi, sedangkan 25 tidak, jadi perulangan berhenti di 4.
Akar terbesar di sini adalah 46340, jadi perulangan berjalan paling banyak 46340 kali. Namun, biayanya bertambah seiring ukuran input: x 64-bit dapat membutuhkan sekitar 3 × 10^9 langkah.
Algoritma
- Atur
root = 0. - Selama
(root + 1) × (root + 1) ≤ x(dalam 64 bit), naikkanrootsebanyak 1. - Kembalikan
root.
def mySqrt(x):
root = 0
while (root + 1) * (root + 1) <= x:
root += 1
return rootPencarian biner untuk menemukan jawaban
Intuisi
Tanyakan kepada setiap kandidat dari 0 hingga x apakah kuadratnya paling besar x. Nilai kuadrat hanya bertambah, jadi jawabannya ya hingga akar, lalu tidak setelahnya. Akar tersebut adalah nilai terakhir yang jawabannya ya, yang ditemukan oleh pencarian biner dengan membagi dua rentang kandidat yang belum diputuskan. Simpan nilai ya terbesar yang ditemukan sejauh ini di best.
Untuk x = 17, pencarian menguji 8 (64, terlalu besar), 3 (9, cukup), 5 (25, terlalu besar), dan 4 (16, cukup). Rentangnya kemudian kosong dan best bernilai 4. Untuk x = 2^31 - 1, pencarian memerlukan 31 langkah.
Algoritma
- Tetapkan
lo = 0,hi = x, danbest = 0. - Selama
lo ≤ hi, ambilmid = lo + (hi - lo) / 2. - Jika
mid × mid ≤ x(dalam 64 bit), tetapkanbest = middanlo = mid + 1. - Jika tidak, tetapkan
hi = mid - 1. - Kembalikan
best.
def mySqrt(x):
lo, hi = 0, x
best = 0 # largest candidate seen so far whose square fits
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
best = mid # mid fits, so try a larger root
lo = mid + 1
else:
hi = mid - 1 # mid is too big
return best
Jebakan dan kasus tepi
- Pengkuadratan dalam 32 bit. Untuk
x = 2147483647, nilaimidpertama adalah 1073741823, kuadratnya sekitar1.15 × 10^18dan meluap menjadi nilai yang salah. Kalikan dalam 64 bit, atau bandingkanm ≤ x / m. - Luapan yang sama terjadi dalam perulangan penghitung: pemeriksaan terakhirnya menguadratkan 46341, yang menghasilkan 2147488281, melebihi batas 32 bit.
- Menggunakan batas eksklusif
hi = x + 1. Untuk nilaixterbesar, yaitu 2147483648, nilainya satu lebih besar dari batas 32 bit. - Mengembalikan
midterakhir yang diuji. Untukx = 17, pencarian berakhir setelah menguji 5; jawabannya adalah 4 yang telah disimpan. - Memulai pencarian dengan
lo = 1, sehinggax = 0terlewat. Pemeriksaanm ≤ x / mjuga membagi dengan nol saatm = 0.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu pencarian biner untuk akar kuadrat?
Waktu O(log x) dan ruang O(1): setiap langkah membagi dua rentang, jadi x = 2^31 - 1 memerlukan 31 langkah. Menghitung naik dari 0 memerlukan O(√x) langkah, yaitu 46340 untuk x yang sama.
Bagaimana cara metode Newton menghitung akar kuadrat bilangan bulat?
Mulai dengan r = x. Selama r × r > x, ganti r dengan (r + x / r) / 2 menggunakan pembagian bilangan bulat. Setiap langkah menurunkan r menuju akar tanpa melewatinya, dan perulangan berhenti pada nilai lantai dari akar kuadrat. Untuk x = 2^31 - 1, dibutuhkan 19 langkah.
Mengapa solusi memerlukan bilangan bulat 64-bit ketika jawabannya muat dalam 32 bit?
Jawabannya paling banyak 46340, tetapi kandidat yang kamu uji tidak demikian. Pencarian biner antara 0 dan x pertama-tama mencoba kandidat sekitar 10^9, yang kuadratnya sekitar 10^18, jauh melampaui batas 32-bit sekitar 2.1 × 10^9.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def mySqrt(x):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
x = 17
Output yang diharapkan
4