Steps to Reduce a Number to Zero

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

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

Q: Adım sayısının formülü nedir?

n > 0 için cevap, n sayısının ikilik sistemdeki uzunluğundan bir çıkarıp 1 bitlerinin sayısını eklemektir. Her 1 biti bir çıkarma, baştaki 1'in altındaki her basamak ise bir yarıya bölme işlemi gerektirir. n = 0 için cevap 0 'dır.

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

İkilik sistemde otuz bir tane 1 olan 2^31 - 1 . Toplamda 61 adım olmak üzere 31 çıkarma ve 30 yarıya bölme işlemi gerekir. Daha küçük hiçbir sayı aynı anda bu kadar çok basamağa ve bu kadar çok 1’e sahip değildir.

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

+10

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

Fonksiyon

numberOfSteps(n: integer) → integer

ninteger: başlangıç sayısı
Döndürürinteger: sayının 0'a ulaşmasına kadar geçen 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: üçe 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 gerektirir, 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 gerektirir ve baştaki 1'in altındaki altı basamak altı yarıya bölme işlemi gerektirir; toplam 12 adım.

Gönderirken +12 gizli test

Ek soru

Tek bir sayı aşağı gitmek yerine 1 artabilir de. 0'a ulaşmak için gereken en az adım sayısı nedir 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

Kuralı çalıştırmak zaten hızlıdır: her yarıya indirme sayıyı ikiye böler, bu yüzden 2^31 - 1 bile yalnızca 61 adım gerektirir. İşin ilginç yanı, kuralın ikilik basamaklara ne yaptığını görmektir. Sayıyı yarıya indirmek son basamağı siler ve tek bir sayıdan 1 çıkarmak, sondaki 1'i 0'a dönüştürür. Dolayısıyla yanıt, basamak sayısı ile 1'lerin sayısının toplamından bir çıkarılmasıdır.

Süreci çalıştır

Sezgi

İfadenin söylediğini yap. n değeri 0'dan büyükken, çiftse yarıya böl, tekse 1 çıkar ve adımı say. 14 için döngü 7, 6, 3, 2, 1 ve 0 değerlerini ziyaret eder; toplam altı adım.

Döngü kısadır; çünkü çıkarma işlemi tek bir sayıyı her zaman çift yapar, dolayısıyla en az iki adımda bir yarıya bölme işlemi yapılır. 2^31'den küçük bir sayı 1'e ulaşmadan önce en fazla 30 kez yarıya bölünür ve her yarıya bölme işleminden önce bir çıkarma, sonunda da bir çıkarma yapıldığında döngü en fazla 61 kez çalışır.

0 girdisi için özel bir duruma gerek yoktur: döngü koşulu hemen başarısız olur 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, 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 rakamları say

Sezgi

Süreci ikilik sistemde izleyin. 14, 1110'dur. İkiye bölmek son basamağı düşürür: 111. Tek bir sayıdan 1 çıkarmak son basamağını, yani bir 1'i temizler: 110. Dolayısıyla her adım ya son basamağı kaldırır ya da sondaki bir 1'i 0'a dönüştürür.

Şimdi sayalım. Sayıdaki her 1 bir kez temizlenmelidir; her 1 için bir çıkarma işlemi gerekir. Her basamak da kaldırılmalıdır; bu da baştaki basamak dışında her basamak için bir ikiye bölme işlemi gerektirir: geriye yalnızca 1 kaldığında, onu temizleyen çıkarma işlemi zaten 0'ı verir. Dolayısıyla yanıt length - 1 + ones olur. 14 = 1110 için bu, 4 - 1 + 3 = 6 eder.

Java, C, C++, Go, Rust ve Swift'de her iki sayım için de yerleşik işlevler (baştaki sıfır sayısı ve 1 bitlerinin sayısı) vardır; bunlar çoğu işlemcide tek bir komuta derlenir. Diğer dillerde n ikilik sistemde yazılır ve karakterler sayılır ya da basamaklar % 2 ile okunur; bu, en fazla 31 tur süren bir döngüdür. Önce n = 0 için 0 döndürün: formülü uygulamak için dayanak olacak 1 biti yoktur.

Algoritma

Eğer n == 0 ise 0 döndür.
length değerini, yani n sayısının ikili basamak sayısını bul.
ones değerini, yani 1 bitlerinin sayısını bul.
length - 1 + ones 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

Kural iki satırdan oluşur. Hatalar, sınır durumlarında ve formüldeki bir eksik hesaplamasında ortaya çıkar.

Bit formülünde n = 0 durumunu unutmak. Hiç basamak ve hiç 1 olmadığında, length - 1 + ones ifadesi -1 verir ve baştaki sıfırların sayısı 0 tanımsız olabilir (C'de __builtin_clz(0)).
Önde gelen basamak için bir yarıya indirme işlemi saymak. 1, çıkarma işlemiyle 0 olur; bu nedenle 8 = 1000 sayısı 5 değil, 4 - 1 + 1 = 4 adım sürer.
İki adımı tek adımda birleştirmek. Tek bir sayı için n = (n-1) / 2 yazmak, çıkarma ve yarıya indirme işlemlerini aynı anda yapar; bu yüzden sayaca 1 değil, 2 eklenmelidir. Aksi takdirde 14, 6 yerine 4 olarak hesaplanır.
n > 1 iken döngüyü çalıştırmak. Bu, son adım 1'i 0'a dönüştürdüğü için bir adım erken durur. Döngü, n değeri 0 olana kadar çalışmalıdır.

Sıkça sorulan sorular4

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

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

Adım sayısının formülü nedir?

n > 0 için cevap, n sayısının ikilik sistemdeki uzunluğundan bir çıkarıp 1 bitlerinin sayısını eklemektir. Her 1 biti bir çıkarma, baştaki 1'in altındaki her basamak ise bir yarıya bölme işlemi gerektirir. n = 0 için cevap 0'dır.

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

İkilik sistemde otuz bir tane 1 olan 2^31 - 1. Toplamda 61 adım olmak üzere 31 çıkarma ve 30 yarıya bölme işlemi gerekir. Daha küçük hiçbir sayı aynı anda bu kadar çok basamağa ve bu kadar çok 1’e sahip değildir.

İkiye bölmek neden 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 sağa kaydırır ve sondaki 0'ı düşürür. n >> 1 tam olarak bunu yapar; dolayısıyla yarıya indirmeyi her iki şekilde de yazabilirsin.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 14

Beklenen