NAVODILO NALOGE:

Consider the number 45656.

It can be seen that each pair of consecutive digits of 45656 has a difference of one.

A number for which every pair of consecutive digits has a difference of one is called a step number.

A pandigital number contains every decimal digit from 0 to 9 at least once. How many pandigital step numbers less than 10^40 are there?

OPIS PROBLEMA:

Naloga zahteva, da spišemo program, ki vrne True, če je podano število »Step number«. Da je število »Step number«, mora veljati, da se vsak par po absolutni vrednosti sosednjih števk danega števila razlikuje za 1.

Enomestna števila načeloma niso »Step number«, izjema je število 1. Število 1 si lahko predstavljamo kot število 01, kjer je razlika sosednjih števk enaka 1 in zato je število 1 »Step number«. Ostala enomestna števila pa niso »Step number«, saj je pri 02, 03, itd. razlika sosednjih števk večja od 1.

Naloga na koncu še sprašuje, koliko je takih števil med 1 in 10^40, ki ustrezajo pogojem števila »Step number«.

IDEJA REŠITVE:

• Nalogo rešimo tako, da najprej podano število x razbijemo na števke in jih damo v pravilnem vrstnem redu v seznam.

• Nato ustvarimo nov seznam, v katerega bomo dodajali absolutne vrednosti razlik sosednjih števk danega števila x, ki jih imamo v seznamu.

• Iz seznama razlik naredimo množico. Bistvo množice je, da so v njej števila zapisana v naraščajočem vrstnem redu (t.j. od najmanjšega do največjega) in v njej je le po en predstavnik nekega števila (t.j. števila se ne ponavljajo).

• Tako vidimo, za koliko se razlikujejo sosednje števke po absolutni vrednosti.

• Če je množica razlik singleton in je ta edini element enak »1«, potem je podano število x »Step number«.

def step_number(x):

--->if x == 1:

------->return True

--->sez = []

--->while x > 0:

------->e = x%10

------->sez.insert(0, e)

------->x = x / 10

--->razlike = []

--->i = 1

--->while i < len(sez):

------->razlika = abs(sez[i] - sez[i-1])

------->razlike.extend(str(razlika))

------->i += 1

--->mnozicaRazlik = set(razlike)

--->if len(mnozicaRazlik) == 1 and mnozicaRazlik == {'1'}:

------->return True

--->else:

------->return False

Poglejmo si še primere uporabe te funkcije:

V okno Shell vnesemo »step_number(45656)« in Python nam vrne rezultat »True«.

>>> step_number(45656)

True

>>> step_number(45658)

False

>>> step_number(12345)

True

Tako lahko tudi preverimo, da funkcija »step_number« deluje pravilno.

Poglejmo si še rešitev drugega dela naloge:

Sprogramirati moramo še metodo, ki vrne število števil od 1 do 10^40, ki so »step number«.

def step_numbers_od_1_do_10na40 ():

Metoda vrne število takih števil od 1 do 10na40, ki zadoščajo pogoju "step number".

--->sez = []

--->for i in range(1,10^40):

-------->if step_number(i) == True:

------------>sez.append(i)

--->return len(sez)

Vrnemo število elementov seznama sez in tako vidimo, koliko je takih števil od 1 do 10^40, ki so »step number«.

Poglejmo si še primer uporabe funkcije »step_numbers_od_1_do_10na40«:

>>> step_numbers_od_1_do_10na40()

Klikni za ogled