Pre zadanú hodnotu N nájdite najmenší základ, v ktorom je možné dané číslo vyjadriť ako palindróm.
def prevod(cislo, zaklad):
vysledok = []
while cislo > 0:
#pridavame cislice od konca
vysledok.insert(0, cislo % zaklad)
cislo = cislo // zaklad
return vysledok
prevod(10, 2)
[1, 0, 1, 0]
prevod(12345678901234567890, 1005)
[11, 986, 616, 147, 390, 474, 270]
123*1005**3+123
124854240498
prevod(124854240498, 1005)
[123, 0, 0, 123]
postupnost = [11, 986, 616, 147, 390, 474, 270]
list(reversed(postupnost))
[270, 474, 390, 147, 616, 986, 11]
postupnost == list(reversed(postupnost))
False
postupnost = prevod(124854240498, 1005)
postupnost == list(reversed(postupnost))
True
postupnost = [11, 986, 616, 147, 390, 474, 270]
postupnost[::-1]
[270, 474, 390, 147, 616, 986, 11]
postupnost == postupnost[::-1]
False
postupnost = prevod(124854240498, 1005)
postupnost == postupnost[::-1]
True
def je_palindrom(postupnost):
for index in range(len(postupnost)//2):
#skontrolujeme polovicu, prostredny pri neparnom pocte netreba
# prvy (0) s poslednym (-1)
if postupnost[index] != postupnost[-(index+1)]:
print(index)
return False
return True
je_palindrom([1,2,3])
0
False
je_palindrom([1,3,1])
True
V našom prípade dostaneme palindróm, aj keď prevod končí na nuly
[1,1,0,0] -> [0,0,1,1,0,0]
Teda nuly vpravo môžeme ignorovať pre kontrolu, odstrániť pred kontrolou ... na výsledok treba aj počet cifier, teda musíme si zapamätať počet núl (prirátať k dĺžke postupnosti)
n = 10
for zaklad in range(2, n):
print(prevod(n, zaklad))
[1, 0, 1, 0] [1, 0, 1] [2, 2] [2, 0] [1, 4] [1, 3] [1, 2] [1, 1]
graf $G=(V,E)$ je množina vrcholov vertices
a hrán edges
. Počet vrcholov označujeme $|V|=n$, počet hrán $|E|=m$.
multigraf - viacnásobné hrany, slučky.
orientovaný graf, digraf digraph
.
susedné vrcholy, vrchol+hrana incidentné
Sled Walk
, Ťah Trail
, Cesta Path
- konečná postupnosť striedavo vrchol a incidentná hrana, začínajúca aj končiaca v nejakom vrchole. V ťahu sa nesmú opakovať hrany, na ceste sa nesmú opakovať vrcholy.
hranovo/vrcholovo ohodnotené grafy
prehľadávanie grafu - BreathFirstSearch
(do šírky, rad), DepthFirstSearch
(do hĺbky, zásobník)
komponenty súvislosti
najkratšia cesta
najlacnejšia kostra
stupeň vrchola $d$, $deg_G(v)$
Nakreslite jedným ťahom:
Komponent súvislosti - podgraf, kde sa viem dostať z daného vrcholu (resp. medzi ľubovoľnými dvoma vrcholmi).
hrany = [ ('BA', 'TT'),
('TT', 'NR'),
('TT', 'TN'),
...
]
susedia = { 'BA': ['TT'],
'TT': ['NR', 'TN'],
...
}
mesto | BA | TT | NR | TN | ... |
---|---|---|---|---|---|
BA | - | 1 | 0 | 0 | |
TT | 1 | - | 1 | 1 | |
NR | 0 | 1 | - | 1 | |
TN | 0 | 1 | 1 | - | |
... | - |
vrcholy a hrany, v stĺpci sú dve jednotky (pri mestách, ktoré spája daná cesta)
operácie:
reprezentácia | dva vrcholy spojené | vypísať zoznam susedov |
---|---|---|
zoznam hrán | $O(m)$ | $O(m)$ |
matica susedov | $O(1)$ | $O(n)$ |
zoznam susedov | $O(\deg) \subset O(n)$ | $O(\deg) \subset O(n)$ |
matica incidencie | $O(m)$ | $O(m)$ |
V grafe platí: $0 \leq m \leq \frac{n \cdot (n-1)}{2} = \frac{n^2-n}{2} = \frac{1}{2}n^2-\frac{1}{2}n$, teda $m \in O\left(n^2\right)$