Square Root (Integer)

Q: Karekökü yerleşik bir işlev kullanmadan nasıl bulursunuz?

Tamsayı karekökü için yanıtı ikili aramayla bul. 0 ile x arasındaki adaylar, kareleri x 'ten küçük veya eşit olan bir diziye ve kareleri daha büyük olan bir diziye ayrılır; ikili arama ilk dizinin son adayını bulur. Newton yöntemi diğer yaygın yanıttır: bir r tahminini, kare uygun olana kadar (r + x / r) / 2 ile iyileştirir.

Q: İkili aramayla karekök bulmanın zaman karmaşıklığı nedir?

O(log x) zaman ve O(1) alan. Her adım aday aralığını yarıya indirir; bu nedenle x = 2^31 - 1 için 31 adım gerekir. 0'dan başlayarak saymak O(√x) adım alır; aynı x için bu sayı 46340'tır. Burada bu uygundur, ancak 64 bitlik girdilerde hızla artar.

Q: Newton yöntemi tam sayı karekökü nasıl hesaplar?

r = x ile başlayın. r × r > x olduğu sürece, tam sayı bölmesi kullanarak r değerini (r + x / r) / 2 ile değiştirin. Her adım, kökü geçmeden r değerini aşağı doğru köke yaklaştırır ve döngü karekökün tabanında durur. x = 2^31 - 1 için 19 adım gerekir ve yaklaştıkça doğru basamak sayısı her adımda yaklaşık iki katına çıkar.

Kolayİkili arama Matematik ve simülasyon

+10

Fonksiyonunuz negatif olmayan bir tam sayı x alır ve tam sayı karekökünü döndürür: r × r ≤ x koşulunu sağlayan en büyük tam sayı r. Yani aşağı yuvarlanmış kareköktür; tam kare olmayan bir sayı için kendisinden küçük en yakın tam karenin karekökünü verir. Yerleşik bir karekök veya üs alma fonksiyonu kullanmadan kendiniz hesaplayın.

Fonksiyon

mySqrt(x: integer) → integer

xinteger: karekökü alınacak negatif olmayan tam sayı
Döndürürinteger: x'in karekökünün aşağı yuvarlanarak tam sayıya dönüştürülmüş hâli

Kısıtlar

0 ≤ x ≤ 2³¹ - 1
Yerleşik karekök, kuvvet veya üs alma işlevini çağırmayın.

Örnekler

Girdi: x = 17
Çıktı: 4
Açıklama: 4 × 4 = 16 en fazla 17'dir, ancak 5 × 5 = 25 daha büyüktür; bu nedenle 17'nin karekökü aşağı yuvarlanarak 4 olur.

Girdi: x = 49
Çıktı: 7
Açıklama: 49 bir tam karedir, 7 × 7 = 49, bu nedenle hiçbir şey yuvarlanmaz ve cevap tam olarak 7'dir.

Gönderirken +17 gizli test

Ek soru

Bunun yerine, x negatif de olabilseydi, r × r × r ≤ x koşulunu sağlayan en büyük r olan tam sayı küp kökünü nasıl bulurdun?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

x değerinden büyük bir sonraki kareye ulaşana kadar 0'dan başlayarak saymak doğru sonucu verir, ancak kökün birimi başına bir adım gerektirir; aralığın üst sınırına yakın değerlerde bu yaklaşık 46000 adımdır. 0, 1, 4, 9, 16 ve devamı sıralı olduğundan, karesi x değerinden küçük veya ona eşit olan son adayı bulmak için ikili arama yapabilir ve yaklaşık 31 adımda bitirebilirsiniz. Her iki yöntemdeki tuzak taşmadır: bir adayın karesi her zaman 32 bitlik alana sığmaz.

Sıfırdan başlayarak say

Sezgi

Karekök, r × r ≤ x koşulunu sağlayan en büyük r değeridir. Her zaman sığan karesiyle r = 0 noktasından başla ve sonraki sayının karesi hâlâ sığdığı sürece r + 1 adımlarıyla ilerle. Döngü, ardılının fazla büyük olduğu ilk r değerinde durur; bu da tam olarak kareköktür. x = 17 için 1, 4, 9 ve 16 kareleri sığar, 25 sığmaz; dolayısıyla döngü 4'te durur.

Döngü, sonucun her bir birimi için bir kez çalışır. Buradaki en büyük sonuç 46340'tır; yani en fazla 46340 adım sürer ve bu da hızlıca tamamlanır. Ancak maliyet O(√x) değerindedir ve girdiyle birlikte artar: 64 bitlik bir x yaklaşık 3 × 10^9 adım gerektirebilir.

Son kontrole dikkat et. x = 2^31 - 1 için döngü, fazla büyük olduğunu anlamak üzere 46341'in karesini alır ve 46341 × 46341 = 2147488281 değeri 32 bitlik bir tamsayıya sığmaz. Kareyi 64 bitte hesapla.

Algoritma

root = 0 olarak ayarla.
(root + 1) × (root + 1) ≤ x olduğu sürece root değerini 1 artır.
root değerini döndür.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Yanıt üzerinde ikili arama

Sezgi

Adayları 0, 1, 2'den x'e kadar sırala ve her birine aynı soruyu sor: karesi x'ten küçük veya eşit mi? Yanıtlar evet, evet, evet diye devam eder; kökten sonraki her aday içinse hayır olur, çünkü kareler yalnızca büyür. Karekök, son evettir. Ardından hayır gelen sıralı bir evet dizisi, ikili aramanın işe yaradığı şeydir.

Henüz karara bağlanmamış adayların aralığını lo ile hi arasında tut; başlangıçta bu aralık 0 ile x arasındadır. Şimdiye kadarki en büyük evet için de best değişkenini kullan. Ortadaki mid değerini test et. mid × mid ≤ x ise karekök mid veya daha büyüktür: değeri best'e kaydet ve lo'yu mid + 1 yap. Aksi hâlde karekök daha küçüktür: hi'yi mid - 1 yap. Aralık boşaldığında karekök best'tir.

x = 17 değerinin izini sürelim. 0 ile 17 arasındaki aralıkta önce 8 test edilir (64, çok büyük); sonra 0 ile 7 arasındaki aralıkta 3 test edilir (9, sığıyor, best = 3); ardından 4 ile 7 arasındaki aralıkta 5 test edilir (25, çok büyük); son olarak 4 ile 4 arasındaki aralıkta 4 test edilir (16, sığıyor, best = 4). Aralık boşalır ve yanıt 4'tür. Her adım aralığı yarıya indirir, bu nedenle x = 2^31 - 1 31 adım sürer. Kare alma işlemini 64 bitte yap: oradaki ilk mid değeri 1073741823'tür.

Algoritma

lo = 0, hi = x ve best = 0 olarak ayarla.
lo ≤ hi olduğu sürece, aralığın ortası olan mid değerini hesapla.
mid × mid ≤ x ise (64 bitte), best = mid ve lo = mid + 1 olarak ayarla.
Aksi takdirde hi = mid - 1 olarak ayarla.
best değerini döndür.

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

Tuzaklar ve uç durumlar

Aramanın kendisi kısadır; hatalar aritmetikte ve sınır durumlarında gizlidir.

32 bitte kare alma. x = 2147483647 için ilk orta aday 1073741823'tür ve karesi yaklaşık 1.15 × 10^18 eder. 32 bitlik bir int içinde bu değer taşarak yanlış bir sonuca dönüşür; hatta sığacak kadar küçük bile görünebilir. Çarpma işlemini 64 bitte yapın veya bunun yerine m ≤ x / m karşılaştırmasını kullanın.
Sayma döngüsünde sonraki adayın karesini 32 bitte alma. 2^31 - 1 sayısının karekökü 46340'tır ve döngünün son kontrolünde 46341'in karesi alınır; bu da 2147488281 eder ve 32 bitlik sınırı aşar.
Aralığı 32 bitin ötesine taşırma. hi = x + 1 şeklindeki özel üst sınır, en büyük x değeri için 2147483648 olur; bu, 32 bitlik sınırın bir ötesidir. hi = x şeklindeki dahil üst sınırda lo + hi ilk adımda tam olarak 2147483647 değerine ulaşır, dolayısıyla ucu ucuna sığar. 64 bitlik indeksler veya lo + (hi - lo) / 2 kullanın.
Son sığan değer yerine, baktığınız son mid değerini döndürme. x = 17 için arama, fazla büyük olan 5'i test ettikten sonra sona erer; yanıt, akılda tutulan 4'tür.
Küçük durumları bozma. lo = 1 ile başlayan bir arama x = 0 değerini gözden kaçırır ve m ≤ x / m bölme kontrolünde m = 0 olduğunda sıfıra bölme hatası oluşur. 0 ve 1 değerlerini ayrı ayrı test edin.

Sıkça sorulan sorular4

Karekökü yerleşik bir işlev kullanmadan nasıl bulursunuz?

Tamsayı karekökü için yanıtı ikili aramayla bul. 0 ile x arasındaki adaylar, kareleri x'ten küçük veya eşit olan bir diziye ve kareleri daha büyük olan bir diziye ayrılır; ikili arama ilk dizinin son adayını bulur. Newton yöntemi diğer yaygın yanıttır: bir r tahminini, kare uygun olana kadar (r + x / r) / 2 ile iyileştirir.

İkili aramayla karekök bulmanın zaman karmaşıklığı nedir?

O(log x) zaman ve O(1) alan. Her adım aday aralığını yarıya indirir; bu nedenle x = 2^31 - 1 için 31 adım gerekir. 0'dan başlayarak saymak O(√x) adım alır; aynı x için bu sayı 46340'tır. Burada bu uygundur, ancak 64 bitlik girdilerde hızla artar.

Newton yöntemi tam sayı karekökü nasıl hesaplar?

r = x ile başlayın. r × r > x olduğu sürece, tam sayı bölmesi kullanarak r değerini (r + x / r) / 2 ile değiştirin. Her adım, kökü geçmeden r değerini aşağı doğru köke yaklaştırır ve döngü karekökün tabanında durur. x = 2^31 - 1 için 19 adım gerekir ve yaklaştıkça doğru basamak sayısı her adımda yaklaşık iki katına çıkar.

Yanıt 32 bite sığarken çözüm neden 64 bit tamsayılar gerektiriyor?

Yanıt en fazla 46340'tır, ancak denediğin adaylar bu sınırın üzerinde olabilir. 0 ile x arasında ikili arama yaparken önce 10^9 civarında bir aday denenir ve bunun karesi 10^18 civarındadır; bu, yaklaşık 2.1 × 10^9 olan 32 bitlik sınırın çok üzerindedir. Karesini 64 bitte almak karşılaştırmanın kesinliğini korur. m ≤ x / m karşılaştırması büyük çarpımı tamamen önler.