Samoopisna števila

Število 1210 je samoopisno, saj vsebuje 1 ničlo, 2 enici, 1 dvojko in 0 trojk. Tudi število 3211000 je samoopisno, saj vsebuje 3 ničle, 2 enici, 1 dvojko, 1 trojko, 0 štiric, 0 petic, 0 štestic.

Testi

testi-samoopisna-stevila.py

Obvezna naloga

Napiši funkcijo samoopisno(n), ki vrne True, če je število n samoopisno, in False, če ni.

Napiši funkcijo vsa_samoopisna(d), ki vrne vsa d-mestna samoopisna števila. Predpostaviti smeš, da je d največ 7.

Funkcije morajo biti napisane tako, da v resnici računajo, ne pa tako, da vračajo števila, ki si jih domislil ročno.

Rešitev

Da bomo lahko opazovali števke števila n, ga bo potrebno spremeniti v niz. Nato gremo prek števk - očitno torej z zanko. V vsakem koraku nas bo zanimalo, kakšna je števka, pa tudi na katerem mestu v nizu smo, torej, ali opazujemo ničto števko, prvo, drugo... Če potrebujemo tako element kot indeks, bomo uporabili enumerate. Naša funkcija bo torej nekako takšna:

def samoopisno(n):
    s = str(n)
    for i, c in enumerate(s):
        if stevka-na-item-mestu-ni-v-redu:
            return False
    return True

Potrebno je le še razmisliti pogoj. Kaj mora veljati za števko na i-tem mestu? Prešteti moramo, koliko števk i je v nizu. Če se ukvarjamo z, recimo, drugim mestom, nas zanima, koliko dvojk je v nizu. Dobimo ga z s.count(i) ... ampak ne čisto. s.count kot argument zahteva niz, i pa je število. No, ga pač pretvorimo v niz tako, da uporabimo str. Število števk i v nizu s je torej s.count(str(i)). Čemu pa mora to število biti enako? Števki na i-tem mestu, torej c. Pogoj bi torej lahko bil if s.count(str(i)) != c, vendar spet ne čisto, ker je c niz (se pravi, znak, števka, element niza s), tisto na levi strani != pa je število. To bomo rešili tako, da bomo c pretvorili iz niza v število.

def samoopisno(n):
    s = str(n)
    for i, c in enumerate(s):
        if s.count(str(i)) != int(c):
            return False
    return True

Bistvo te naloge je, da

• znamo napisati vzorec, kjer v zanki for nekaj iščemo in jo, če najdemo, prekinemo z return, če ne, pa nadaljujemo (brez kakega else in return!), po zanki pa pride return z drugo vrednostjo, v našem primeru return True,
• se spomnimo na metodo count, saj so bile metode tema predavanj,
• se znajdemo v igri str-jev in int-ov, se pravi, razumemo, kdaj potrebujemo število in kdaj niz, ter kdaj dobimo število in kdaj niz.

Tisti, ki so reševali dodatno nalogo, so funkcijo samoopisno seveda lahko napisali tako, da so poklicali kar samoopisno_b:

def samoopisno(n):
    return samoopisno_b(n, 10)

Funkcija vsa_samoopisna je primer kar običajne funkcije, kjer v nek seznam naberemo vse elemente nekega drugega seznama, ki ustrezajo določenemu pogoju.

def vsa_samoopisna(d):
    samoopisna = []
    for i in range(10 ** (d - 1), 10 ** d):
        if samoopisno(i):
            samoopisna.append(i)
    return samoopisna

Zabavni del te naloge je bil, seveda, določiti meje intervala. A to za nekoga z dvanajstletno matematično izobrazbo ne bi smelo biti pretežko: d-mestna števila so vsa števila med 10^d-1 in 10^d-1. Ker range ne vključuje zgornje meje, tam ne odštevamo -1, temveč pišemo kar range(10 ** (d - 1), 10 ** d)

Dodatna naloga

Napiši funkcijo pretvori(n, b), ki vrne niz s številom n, zapisanim v številskem sistemu z osnovo b.

Napiši funkcijo samoopisno_b(n, b), ki vrne True, če je podano število n samoopisno, če ga zapišemo v številskem sistemu z osnovo b.

Rešitev

O pretvarjanju med številskimi zapisi ste se učili v šoli. V b-iški zapis pretvorimo tako, da pogledamo ostanek po deljenju z b; to je naša zadnja števka. Celo število pa celoštevilsko delimo z b. Ostanek količnika po deljenju z b je predzadnja števka... in tako naprej.

def pretvori(n, b):
    if n == 0:
        return "0"

    s = ""
    while n != 0:
        s = str(n % b) + s
        n //= b
    return s

Funkcija, ki pove ali je število samoopisno v b-iškem zapisu je popolnoma podobna (točneje: enaka) funkciji, ki pove, ali je število samoopisno v desetiškem zapisu, le da namesto str(n) pokličemo pretvori(n, b). Tako ali tako je str(b) natančno isto kot pretvori(n, 10).

def samoopisno_b(n, b):
    s = pretvori(n, b)
    for i, c in enumerate(s):
        if s.count(str(i)) != int(c):
            return False
    return True