Armstrong Number

Q: Bir Armstrong sayısını kontrol etmenin zaman karmaşıklığı nedir?

n yaklaşık log n basamağa sahiptir; burada en fazla 10 basamak vardır. Basamakları ayırıp her kuvveti on elemanlı bir tabloda aramak, O(log n) zaman ve O(1) alan gerektirir. Her basamak için d^k değerini bir döngüyle yeniden hesaplamak bunu O(log² n) yapar; bu boyutta yine de hızlıdır.

BaşlangıçMatematik ve simülasyon

+10

Bir pozitif tam sayı, kendi rakamlarının her birinin basamak sayısı kadar kuvvetinin toplamına eşitse Armstrong sayısıdır. 153 üç basamaklıdır ve 1^3 + 5^3 + 3^3 = 153 olduğundan Armstrong sayısıdır. n değerini alan ve Armstrong sayısıysa true, değilse false döndüren bir fonksiyon yaz.

Fonksiyon

isArmstrong(n: integer) → boolean

ninteger: test edilecek pozitif tam sayı
Döndürürboolean: n, rakamlarının her birinin basamak sayısı kuvvetlerinin toplamına eşit olduğunda true

Kısıtlar

1 ≤ n ≤ 10⁹

Örnekler

Girdi: n = 153
Çıktı: true
Açıklama: 153 3 basamaklıdır, bu yüzden her basamağın küpü alınır: 1 + 125 + 27 = 153. Toplam sayıyı verir, bu nedenle yanıt true olur.

Girdi: n = 10
Çıktı: false
Açıklama: 10 2 basamaklıdır, bu yüzden her basamağın karesi alınır: 1 + 0 = 1, bu da 10 değildir. Yanıt false.

Girdi: n = 9474
Çıktı: true
Açıklama: 4 basamakla üs 4'tür: 6561 + 256 + 2401 + 256 = 9474, sayının kendisi; bu nedenle yanıt true.

Gönderirken +31 gizli test

Ek soru

1 ile 10^9 arasında yalnızca 31 Armstrong sayısı vardır. Bir milyar sayıyı tek tek test etmeden hepsini listeleyebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Tanım algoritmanın kendisidir: n'nin kaç basamaklı olduğunu bul, her basamağı bu kuvvete yükselt, sonuçları topla ve n ile karşılaştır. Tuzaklar sayılardadır. Üs, sabit bir 3 değil, bu n'nin basamak sayısıdır ve toplam 32 bitlik bir tam sayının sınırını aşabilir: 999999999 için bu değer 9 × 9^9 = 3486784401 olur.

Dizeleri oku

Sezgi

n sayısının ondalık gösterimi ihtiyacın olan iki şeyi de sağlar. Uzunluğu üs k, karakterleri ise rakamlardır. 9474 için dizgede 4 karakter bulunur; bu nedenle 9^4 + 4^4 + 7^4 + 4^4 işlemini toplarsın.

Her karakteri tekrar rakama dönüştür, k üssünü al ve devam eden bir toplama ekle. Son toplam n'ye eşitse n bir Armstrong sayısıdır.

Toplamı 64 bitlik bir tamsayıda tut. n 32 bite sığar, ancak toplamın sığması gerekmez: 999999999, 32 bitlik 2147483647 sınırını aşan 3486784401 değerini verir. k çarpma işlemi yapan bir döngüyle hesaplanan bir üs, her rakam için k adım gerektirir; dolayısıyla kontrol, k yaklaşık log n olmak üzere O(k²) karmaşıklığındadır. Burada bu en fazla 100 çarpma işlemidir ve dizge bellekte k karakter yer kaplar.

Algoritma

n'yi ondalık dizgeye dönüştür ve k'yi uzunluğu olarak belirle.
64 bitlik bir total değerini 0 olarak ayarla.
Her karakteri d basamağına dönüştür ve kayan noktalı üs alma işlemi çağırmak yerine tam sayıları çarparak d^k değerini total'a ekle.
total'ın n'ye eşit olup olmadığını döndür.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Rakamları ayırın ve kuvvetlerine bakın

Sezgi

Aritmetik, dize kullanmadan da aynı işi yapar. m % 10, m sayısının son basamağıdır ve 10'a göre tam sayı bölmesi bu basamağı atar; bu nedenle, geriye hiçbir şey kalmayana kadar 10'a bölen bir döngü basamakları sayar. 9474, 947, 94, 9, 0 olur: dört adım, yani k = 4.

Yalnızca on basamak bulunduğundan, herhangi bir toplama yapmadan önce 0'dan 9'a kadar her d için powers[d] = d^k tablosunu oluştur. Böylece her basamak için k çarpma yerine tek bir tablo araması gerekir. Kontrol işlemi O(log n) zamana iner ve tablonun sabit boyutu on olduğundan, alan kullanımı O(1)'dir.

İkinci döngü basamakları yeniden ayırır ve toplama powers[m % 10] değerini ekler. Her terim sıfır veya pozitiftir; dolayısıyla toplam hiçbir zaman azalmaz ve n değerini geçtiğinde yanıt false olur. 999999999 için bu, üç basamaktan sonra, 3 × 387420489 = 1162261467 değerinde gerçekleşir. Tablo için yine de 64 bit gerekir; çünkü n = 10^9 on basamaklıdır ve 9^10 = 3486784401.

Algoritma

n değerinin rakamlarını, bir kopyasını 0'a ulaşana kadar 10'a bölerek say; bu sayıya k de.
0'dan 9'a kadar her d rakamı için, 64 bitlik tamsayılarda powers[d] = d^k değerini hesapla.
n değerinin yeni bir kopyasını tekrar 10'a böl ve her adımda powers[m % 10] değerini total değerine ekle.
total değeri n değerini aşarsa hemen false döndür.
Son rakamdan sonra, total değerinin n değerine eşit olup olmadığını döndür.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

Tuzaklar ve uç durumlar

Formül kısa olduğu için hatalar, çevresindeki sayılardan kaynaklanır.

Sabit bir 3 üssü. 153 ve 370 sayılarını kabul eder ama 9474 sayısını reddeder; ayrıca 7^3 = 343 olduğundan 1'den büyük tek basamaklı her sayıyı reddeder.
32 bitlik bir toplam. 999999999 sayısının rakamları toplamı 3486784401 olur ve tablodaki 9^10 girdisi de aynı sayıdır. C'de bu taşma tanımsız davranıştır; Java ve C# negatif bir sayıya sarar, Rust'ın hata ayıklama derlemesi ise panikler. long, long long veya i64 kullanın.
Kayan noktalı üs alma. C'deki pow ve Java'daki Math.pow bir double döndürür. Bazı C çalışma zamanları, 5^2 için 24.999... gibi tam sayıdan biraz küçük bir değer döndürmüştür; bu değer tür dönüştürmeyle 24 sayısına kesilir. Bunun yerine bir döngüde tam sayıları çarpın.
Yanlış değerle karşılaştırma. Rakam döngüleri n değerini 0'a kadar böler; bu nedenle bir kopya üzerinde çalışın ve toplamı özgün değerle karşılaştırın.
Bilimsel gösterim. R'de as.character(1e9), beş karakterden oluşan "1e+09" değerini verir; bu nedenle dizge tabanlı bir R çözümü sprintf("%.0f", n) ile biçimlendirme yapar.

Sıkça sorulan sorular4

Armstrong sayısı nedir?

Narsistik sayı olarak da adlandırılan bir Armstrong sayısı, kendi rakamlarının her birinin rakam sayısı kuvvetine yükseltilmiş hâllerinin toplamına eşittir. 153 bir Armstrong sayısıdır çünkü 1^3 + 5^3 + 3^3 = 153 ve 9474 bir Armstrong sayısıdır çünkü 9^4 + 4^4 + 7^4 + 4^4 = 9474. Tek basamaklı her sayı bu koşulu sağlar; çünkü d^1 = d.

Kaç Armstrong sayısı vardır?

10 tabanında tam olarak 88 pozitif sayı vardır ve en büyüğü 39 basamaklıdır. Liste sonludur; çünkü k basamaklı bir sayı en az 10^(k-1) değerindeyken basamaklarının kuvvetleri toplamı en fazla k × 9^k olabilir ve 61 basamaktan itibaren toplam sayıya asla yetişemez. 1 ile 10^9 arasında 31 tane vardır.

Armstrong sayısı denetimi neden 64 bitlik bir tamsayı gerektirir?

Girdi 32 bite sığar, ancak basamakların üslerinin toplamı sayıdan birkaç kat daha büyük olabilir. 999999999, 9 × 9^9 = 3486784401 değerini verir; bu da 2^31-1 = 2147483647 değerinden büyüktür. Burada 32 bitlik toplam taşar; bu nedenle toplamı ve üsleri 64 bitlik bir türde tut.

Bir Armstrong sayısını kontrol etmenin zaman karmaşıklığı nedir?

n yaklaşık log n basamağa sahiptir; burada en fazla 10 basamak vardır. Basamakları ayırıp her kuvveti on elemanlı bir tabloda aramak, O(log n) zaman ve O(1) alan gerektirir. Her basamak için d^k değerini bir döngüyle yeniden hesaplamak bunu O(log² n) yapar; bu boyutta yine de hızlıdır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 153

Beklenen

true