p1/domace-naloge/2020/02 skupne sobe/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ogrevanje: Zaporedje števil\n",
    "\n",
    "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.\n",
    "\n",
    "Napiši program, ki izračuna in izpiše prvih 16 členov tega zaporedja. Izpisati mora torej\n",
    "\n",
    "```\n",
    "0\n",
    "1\n",
    "14\n",
    "7\n",
    "12\n",
    "13\n",
    "10\n",
    "3\n",
    "8\n",
    "9\n",
    "6\n",
    "15\n",
    "4\n",
    "5\n",
    "2\n",
    "11\n",
    "```\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Običajni vzorec za štetje je\n",
    "\n",
    "```python\n",
    "i = 0\n",
    "while i < 16:\n",
    "    print(i)\n",
    "    i += 1\n",
    "```\n",
    "\n",
    "le da tu ne bomo izpisovali števca, `i`-ja, ker nas ne zanima, potrebujemo ga le za štetje. Pač pa bomo imeli še eno spremenljivko, ki bo vsebovala vrednost člena: `x`. Ta bo v začetku 0; v vsakem koraku ga bomo izpisali in irzačunali naslednjega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "14\n",
      "7\n",
      "12\n",
      "13\n",
      "10\n",
      "3\n",
      "8\n",
      "9\n",
      "6\n",
      "15\n",
      "4\n",
      "5\n",
      "2\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "x = 0\n",
    "while i < 16:\n",
    "    print(x)\n",
    "    x = (13 * x + 1) % 16\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Naloga (nadaljevanje)\n",
    "\n",
    "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, zato ga 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\n",
    "\n",
    "```\n",
    "0\n",
    "1013904223\n",
    "1196435762\n",
    "3519870697\n",
    "2868466484\n",
    "1649599747\n",
    "2670642822\n",
    "1476291629\n",
    "2748932008\n",
    "2180890343\n",
    "```\n",
    "\n",
    "### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1013904223\n",
      "1196435762\n",
      "3519870697\n",
      "2868466484\n",
      "1649599747\n",
      "2670642822\n",
      "1476291629\n",
      "2748932008\n",
      "2180890343\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "x = 0\n",
    "while i < 10:  # V teh zapiskih bomo izpisali samo prvih 10 členov...\n",
    "    print(x)\n",
    "    x = (1664525 * x + 1013904223) % 2 ** 32\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Glavni del: Zaporedje sob\n",
    "\n",
    "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.\n",
    "\n",
    "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, 1, 6, 1, 8, 9, ...\n",
    "\n",
    "Ker ima preveč časa (najbrž je v samoizolaciji?), to ponovi tisočkrat. Program naj ne izpisuje členov ali sob, temveč naj izpiše, kolikokrat je bila Ana v sobi številka 6.\n",
    "\n",
    "(Če se nisem zmotil, je pravilni odgovor 96.)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Dodamo še novo spremenljivko (rekli ji bomo `soba6`), v kateri bomo šteli, kolikokrat je zadnja števka `x` enaka 6. Kako pa dobimo zadnjo števko `x`? Ostanek po deljenju z 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "96\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "x = 0\n",
    "soba6 = 0\n",
    "while i < 1000:\n",
    "    x = (1664525 * x + 1013904223) % 2 ** 32\n",
    "    if x % 10 == 6:\n",
    "        soba6 += 1\n",
    "    i += 1\n",
    "print(soba6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najbrž se nisem motil. :)\n",
    "\n",
    "\n",
    "### Dodatna naloga: Srečanja\n",
    "\n",
    "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.\n",
    "\n",
    "Obe računata enako hitro, se pravi, obe gresta najprej v sobo, ki ustreza prvemu členu, nato obe v istem trenutku v sobo, ki ustreza drugemu členu, tretjemu ...\n",
    "\n",
    "Napiši program, ki izračuna, kolikokrat se bosta srečali.\n",
    "\n",
    "(Če se nisem zmotil, je pravilni odgovor 195.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "195\n"
     ]
    }
   ],
   "source": [
    "skupaj = 0\n",
    "x1 = 0\n",
    "x2 = 0\n",
    "for i in range(1000):\n",
    "    if x1 % 10 == x2 % 10:\n",
    "        skupaj += 1\n",
    "    x1 = (1664525 * x1 + 1013904223) % 2 ** 32\n",
    "    x2 = (22695477 * x2 + 1) % 2 ** 32\n",
    "print(skupaj)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ker nekatere študente take stvari zanimajo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "195\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "print(\n",
    "    sum(\n",
    "        map(lambda x: 2 - len(set(map(lambda t: t % 10, x))),\n",
    "            zip(reduce(lambda s, _: s + [(1664525 * s[-1] + 1013904223) % (2 ** 32)], range(1000), [0]),\n",
    "                reduce(lambda s, _: s + [(22695477 * s[-1] + 1) % (2 ** 32)], range(1000), [0])))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ampak ni prav lepo. So tudi lepši onelinerji. Ampak ne za ta problem.\n",
    "\n",
    "## Ozadje naloge\n",
    "\n",
    "Na ta način so dolgo delale funkcije, ki vračajo naključna števila. Začetna vrednost ni 0, temveč jo izberemo na nek dovolj \"naključen\" način, na primer na podlagi trenutnega časa ali pa na podlagi natančnega merjenja razmikov med uporabnikovimi akcijami (npr. pritiski na tipke). Od tam naprej pa vsako naslednje \"naključno\" število izračunamo iz prejšnjega s pomočjo formule v obliki $(ax + c) % m$. Vrnjeno naključno število je pri tem del tega, naračunanega števila. Konstante morajo biti $a$, $c$ in $m$ izbrane tako, da se števila ne začnejo prehitro ponavljati. Prej ko slej pa se morajo: ker računamo ostanek po deljenju z $m$, teh ostankov pa je le $m$, se bo člen po največ $m$ korakih ponovil. Ko se ponovi en člen, pa se seveda tudi vsi za njim.\n",
    "\n",
    "Ker so ta števila izračunana z neko formulo, seveda niso naključna, čeprav se zdijo takšna. Rečemo jim psevdo-naključna števila. Resnično naključnih števil računalnik tako ali tako ne more proizvajati, saj v njem ni ničesar naključnega (brez kakšne dodatne opreme, seveda).\n",
    "\n",
    "Več o tem si lahko preberete na strani Wikipedije o [linearnih kongruenčnih generatorjih](https://en.wikipedia.org/wiki/Linear_congruential_generator).\n",
    "\n",
    "Moderni generatorji naključnih števil temeljijo na drugačni, malo bolj zapleteni matematiki [Mersennovega vrtinca](https://en.wikipedia.org/wiki/Mersenne_Twister). "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}