Steps to Reduce a Number to Zero

Q: Bir sayıyı sıfıra indirmenin zaman karmaşıklığı nedir?

Sürecin çalıştırılması O(log n) zaman alır, çünkü en azından her ikinci adımda sayı yarıya iner: n = 2^31 - 1 için 61 adım. Yerleşik bit talimatlarıyla ikili basamakları saymak O(1) sürer.

Q: 2^31'den küçük hangi sayı en çok adım alır?

2^31 - 1 ; ikilik sistemde otuz bir tane 1'den oluşur. Toplamda 61 adım için 31 çıkarma ve 30 ikiye bölme işlemi gerekir. Bundan daha küçük hiçbir sayı aynı anda bu kadar basamağa ve bu kadar 1'e sahip değildir.

BaşlangıçBit işlemleri Matematik ve simülasyon

+10

Negatif olmayan bir n tam sayısından başlayın ve 0'a ulaşana kadar bir kuralı tekrarlayın: sayı çiftse 2'ye bölün; tekse 1 çıkarın. Kuralın her uygulanışı bir adımdır. Kaç adım sürdüğünü döndürün.

Fonksiyon

numberOfSteps(n: integer) → integer

ninteger: başlangıç sayısı
Döndürürinteger: sayı 0'a ulaşana kadar atılacak adım sayısı

Kısıtlar

0 ≤ n ≤ 2³¹ - 1

Örnekler

Girdi: n = 14
Çıktı: 6
Açıklama: Sayı 14 → 7 → 6 → 3 → 2 → 1 → 0 şeklinde ilerler: üç yarıya bölme ve üç çıkarma, 6 adım.

Girdi: n = 8
Çıktı: 4
Açıklama: 8 → 4 → 2 → 1 → 0. İkinin kuvveti üç kez yarıya iner ve sonunda bir çıkarma işlemi gerekir; 4 adım.

Girdi: n = 123
Çıktı: 12
Açıklama: 123, ikilik sistemde 1111011 şeklindedir: yedi basamak ve altı tane 1. Altı tane 1, altı çıkarma işlemi; baştaki birin altındaki altı basamak ise altı yarıya bölme işlemi gerektirir: toplam 12 adım.

Ek soru

Tek sayının da 1 artırılabileceğini varsayalım. 0'a ulaşmak için gereken en az adım sayısı kaçtır ve 15 için hangi seçim doğrudur?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

İkilik sistemde yarıya bölmek son basamağı düşürür ve tek bir sayıdan 1 çıkarmak, son 1 basamağını 0 yapar. Bu nedenle n > 0 için yanıt, ikilik basamak sayısı ile 1'lerin sayısının toplamından bir çıkarılmasıdır. Kuralı doğrudan uygulamak da hızlıdır: en fazla 61 adım.

Süreci çalıştır

Sezgi

Kuralı uygula ve adımları say. 14 için döngü 7, 6, 3, 2, 1 ve 0 değerlerini ziyaret eder: altı adım.

Bir çıkarma işlemi tek sayıyı her zaman çift sayıya dönüştürür; bu nedenle en azından her ikinci adımda sayı yarıya iner. 2^31 değerinden küçük bir sayı, 1 değerine ulaşmadan önce en fazla 30 kez yarıya iner. Her yarıya indirme işleminden önce bir çıkarma ve sonunda bir çıkarma yapıldığında döngü en fazla 61 kez çalışır. n = 0 için döngü hiç çalışmaz ve yanıt 0 olur.

Algoritma

steps değerini 0 olarak ayarla.
n > 0 olduğu sürece: n çiftse n değerini n / 2 olarak ayarla, değilse n-1 olarak ayarla.
Her seferinde steps değerine 1 ekle.
steps değerini döndür.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

İkili basamakları say

Sezgi

Her adım ya son ikilik basamağı düşürür ya da sondaki 1'i 0'a dönüştürür. 14, 1110'dır: ikiye bölmek 111'i verir ve 111'den çıkarmak 110'u verir. Her 1 bir kez temizlenmelidir; bu da her 1 için bir çıkarma işlemi gerektirir. Baştaki bir hariç her basamak düşürülmelidir; bunun için her basamakta bir kez ikiye bölme gerekir: geriye yalnızca 1 kaldığında, bu sayıyı çıkarmak zaten 0'ı verir. Dolayısıyla yanıt length - 1 + ones'tır ve 14 için bu 4 - 1 + 3 = 6 eder.

Java, C, C++, Go, Rust ve Swift'de her iki sayım için de (baştaki sıfırlar ve ayarlanmış bitler) çoğu işlemcide tek bir komut olarak derlenen yerleşik işlevler bulunur. Diğer diller, en fazla 31 tur süren bir döngüde basamakları % 2 ile okur. Önce n = 0 durumunu ele alın: formüle dayanak olacak 1 bit'i yoktur.

Algoritma

Eğer n == 0 ise 0 döndür.
n'nin ikili basamak sayısı olan length'i bul.
1 bitlerinin sayısı olan ones'ı bul.
length - 1 + ones değerini döndür.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Tuzaklar ve uç durumlar

Bit formülünde n = 0 durumunu unutmak. length - 1 + ones sonucu -1 verir ve baştaki sıfırların sayısı 0 olduğunda tanımsız olabilir (C'de __builtin_clz(0)).
Baştaki rakam için bir yarılama adımı saymak. 1, çıkarma işlemiyle 0 olur; bu nedenle 8 = 1000 sayısı 5 değil, 4 - 1 + 1 = 4 adımda dönüşür.
Tek bir sayı için n = (n-1) / 2 yazıp bir adım saymak. Bu satır iki adım uygular; bu nedenle 14 için sonuç 6 yerine 4 olur.
n > 1 koşuluyla döngü kurmak. Bu, 1 değerini 0 yapan son adımdan önce durur.

Sıkça sorulan sorular3

Bir sayıyı sıfıra indirmenin zaman karmaşıklığı nedir?

Sürecin çalıştırılması O(log n) zaman alır, çünkü en azından her ikinci adımda sayı yarıya iner: n = 2^31 - 1 için 61 adım. Yerleşik bit talimatlarıyla ikili basamakları saymak O(1) sürer.

2^31'den küçük hangi sayı en çok adım alır?

2^31 - 1; ikilik sistemde otuz bir tane 1'den oluşur. Toplamda 61 adım için 31 çıkarma ve 30 ikiye bölme işlemi gerekir. Bundan daha küçük hiçbir sayı aynı anda bu kadar basamağa ve bu kadar 1'e sahip değildir.

Neden ikiye bölmek sağa kaydırmayla aynıdır?

İkili sayı, ikinin kuvvetlerinin toplamıdır. Çift bir sayıyı 2'ye bölmek her kuvveti bir azaltır; bu da her basamağı bir basamak sağa kaydırır ve sondaki 0'ı düşürür. n >> 1 bunu yapar; dolayısıyla yarıya indirmeyi iki şekilde de yazabilirsin.

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

Test #1

Test #2

Test #3

Argüman

n = 14

Beklenen Çıktı