Skupne sobe

Za pravilno rešeno nalogo je dovolj oddati, kar je opisano pod "Obvezni del", saj je "Ogrevanje" del tega.

Dodatne naloge ni potrebno reševati, upošteva se le pri končnih ocenah 9 in 10 (glej Pravila predmeta).

Če rešujete dodatno nalogo, napišite oboje v isti program, to je, isto datoteko .py.

Ogrevanje: Zaporedje števil

Ob takem zaporedju bi zavil z očmi celo Collatz: naslednji člen zaporedja izračunamo tako, da trenutni člen pomnožimo s 13, prištejemo 1 in nato izračunamo ostanek po deljenju s 16, se pravi $x_i = (13 x_{i - 1} + 1)\;\%\;16$, pri čemer % pomeni ostanek po deljenju. Začetni člen zaporedja naj bo 0.

  1. Napiši program, ki izračuna in izpiše prvih 16 členov tega zaporedja. Izpisati mora torej

    0
    1
    14
    7
    12
    13
    10
    3
    8
    9
    6
    15
    4
    5
    2
    11
    
  2. Zdaj pa spremeni program tako, da bo izpisal 1000 členov zaporedja. Hitro boš videl(a), da se stalno ponavlja istih 16 členov, kar je dolgčas ...

  3. ... zato spremeni program tako, da uporablja drugačno formulo za izračun naslednjega člena: $x_i = (1664525\,x_{i - 1} + 1013904223)\;\%\;2^{32}$. Zdaj se zaporedje začne z

    0
    1013904223
    1196435762
    3519870697
    2868466484
    1649599747
    ...
    

Glavni del: Zaporedje sob

V nekem hodniku je 10 sob. Ker je lastnik računalnikar, so označene s številkami od 0 do 9 in ne od 1 do 10.

Ana obiskuje sobe v naključnem vrstnem redu, ki ga dobi tako, da računa člene zaporedja iz prejšnje naloge (zadnjega, tistega z velikimi koeficienti). Za vsak člen pogleda skrajno desno števko in gre v sobo s to številko. Pri gornjem zaporedju gre torej v sobe 0, 3, 2, 7, 4, 7, ...

Ker ima preveč časa (najbrž je v samoizolaciji?), to ponovi tisočkrat. Napiši program (oz. spremeni prejšnji program), ki odsimulira njeno početje, pri čemer pa ne izpisuje členov ali sob, temveč izpiše, kolikokrat je bila v sobi številka 6.

(Če se nisem zmotil, je pravilni odgovor 96.)

Dodatna naloga: Srečanja

Tudi Berta je v samoizolaciji in hodi po istih sobah, le drugačno formulo uporablja: $x_i = (22695477\,x_{i - 1} + 1)\;\%\;2^{32}$. Tudi ona gre vedno v sobo, ki jo določi glede na ostanek po deljenju člena z 10. Tudi ona to stori tisočkrat.

Ana in Berta sta sinhronizirani: obe gresta najprej v sobo, ki ustreza prvemu členu, nato obe v istem trenutku v sobo, ki ustreza drugemu členu, tretjemu ...

Napiši program, ki izračuna, kolikokrat se bosta srečali v isti sobi. Ne pozabi, da se prvič srečata že v sobi 0. Tudi to šteje.

(Če se nisem zmotil, je pravilni odgovor 195.)