{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MAF gyakorlat 2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jó tanácsok\n",
    "- **Kommentelés** A feladatok megoldása során kommenteld a munkádat!\n",
    "- **Haszonsítás** A feladatok megoldásához használd fel a korábban megírt függvényeket!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Egy kis számelmélet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Euklideszi algoritmus\n",
    "Írd meg az euklideszi algoritmust végrehajtó függvényt. Példa:   \n",
    "`Euclidean_algorithm(32,12)`\n",
    "\n",
    "Ami a következőt jelenti:\n",
    "\n",
    "`32 = 2 (12) + 8\n",
    "12 = 1 (8) + 4\n",
    "8 = 2 (4) + 0`\n",
    "\n",
    "\n",
    "Ezt a képernyőre a következőképpen legyen kiírva:\n",
    "\n",
    "`\n",
    "[32,2,12,8]\n",
    "[12,1,8,4]\n",
    "[8,2,4,0]\n",
    "`\n",
    "\n",
    "\n",
    "Aki bátor, nyugodtan írja ki az egyenleteket stringként."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Euclidean_algorithm(a,b):\n",
    "    #TODO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Euclidean_algorithm(32,12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Írd meg a legnagyobb közös osztót kiszámoló függvényt!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GCD(a,b):\n",
    "    #TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Írj egy függvényt, ami a megadott egész számot felírja a lehető legkevesebb négyzetszám összegeként, majd visszatér a négyzetszámokat tartalmazó listával.\n",
    "Pl:\n",
    "\n",
    "`sum_of_squares(5) [1,4]\n",
    "sum_of_squares(6) [1,1,4]\n",
    "sum_of_squares(7) [1,1,1,4]\n",
    "sum_of_squares(8) [4,4]\n",
    "sum_of_squares(9) [9]`\n",
    "\n",
    "Hint: Bármely egész szám felírható legfeljebb 4 négyzetszám összegeként. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_of_squares(n):\n",
    "    #TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4 (Collatz-sorozat) A sorozatot a következő rekurzióval definiáljuk: \n",
    "$$a_n = \\frac{a_{n-1}}{2} \\text{, ha } a_{n-1} \\text{páros,}$$\n",
    "$$a_n = a_{n-1} \\cdot 3 + 1 \\text{, ha } a_{n-1} \\text{ páratlan.}$$\n",
    "\n",
    "#### Ha a sorozat eléri az 1-et, akkor végtelen ciklusba kerül (1-4-2-1), ezért ezt a sorozat végének tekinthetjük. Írj függvényt, ami tetszőleges pozitív egész számra kiszámolja annak Collatz sorozatát!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def collatz(n):\n",
    "    #TODO\n",
    "\n",
    "assert(collatz(13)==[13, 40, 20, 10, 5, 16, 8, 4, 2, 1])\n",
    "assert(collatz(17)==[17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Írj egy függvényt, ami adott $n,k$ eseten visszatér az ${n\\choose k}$ értékkel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binom(n,k):\n",
    "    #TODO\n",
    "    \n",
    "assert(binom(5,2)==10)\n",
    "assert(binom(4,3)==4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 Irj egy fuggvenyt, ami egy adott $K$ es egy lista eseten visszater azon resz-intervallumok szamaval, amikben a szamok osszege oszthato $K$-val. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def div_intervals(l,K):\n",
    "    #TODO\n",
    "    \n",
    "assert(div_interval([1,2,3,4],2)==4)\n",
    "assert(div_interval([1,2,3,4,5,6],3)==11) #0,1,0,0,1,0,0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Alapértelmezett (default) argumentumok.\n",
    "\n",
    "### 2.1 Írj egy függvényet, amely kiszámolja egy listában lévő számok összegét, egy opcionális kezdőértékből kiindulva. Ha a kezdőérték nincs megadva, az összegzés kezdődjön 0-tól."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO def sum_list...\n",
    "\n",
    "assert(sum_list([1, 2, 3]) == 6)\n",
    "assert(sum_list([1, 2, 3], 5) == 11)\n",
    "assert(sum_list([1, 2, 3], 7) == 13)\n",
    "assert(sum_list([1, 2, 3, 6], 5) == 17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Írj egy függvényt, amely elfogad két számot és egy aritmetikai műveletet string alakban (\"+\", \"-\", \"\\*\" vagy \"/\") és visszatér a művelet eredményével. Az alapértelmezett művelet legyen az összeadás."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO def arithmetic...\n",
    "\n",
    "assert(arithmetic(2, 3) == 5)\n",
    "assert(arithmetic(2, 3, \"-\") == -1)\n",
    "assert(arithmetic(2, 3, \"*\") == 6)\n",
    "assert(arithmetic(2, 3, \"/\") == 2/3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. `listák` \n",
    "\n",
    "* lista konstrukció `l=[2,3,4]`\n",
    "* lista elem elérese `l[2]`\n",
    "* lista hossza `len(l)`\n",
    "* lista bővítése egy elemmel `l.append(4)`\n",
    "* listák fűzése `l+k`\n",
    "* lista szeletelese egy range(a,b,c) menten `l[a:b:c]`\n",
    "* lista `i`-edik elemének törlése `del l[i]`\n",
    "* lista egy darab `a` értékű elemének törlése `l.remove(a)`\n",
    "\n",
    "### 3.1 Tegyük fel, hogy adott számok egy _l_ listája és egy egész szám *i < len(l)*. Add vissza az *i*-ik legnagyobb elemet a listából!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ith(l,i):\n",
    "    \n",
    "assert(ith([1,4,2,7],2)==4)\n",
    "assert(ith([1,4,2,7],3)==2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Adott két lista. Döntsd el, hogy van-e közös elemük!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def common(l,k):\n",
    "\n",
    "assert( common([1,2,3],[6,5,3])==True)\n",
    "assert( common([1,2,3],[6,5,4])==False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Adott két lista. Döntsd el, hogy egymás cirkuláris permutációi-e!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm(l,k):\n",
    "\n",
    "assert( perm([1,2,3],[2,3,1])==True)\n",
    "assert( perm([1,2,3],[3,2,1])==False)\n",
    "assert( perm([1,1,2,3],[1,2,1,3])==False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Az `enumerate()` függvény egy lista (vagy mas iterálható objektumból) elemeiből párokat csinál, ahol az pár egyik eleme az eredeti elem, a másik pedig a sorszáma:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i,k in enumerate([3,1,4,1,5,9,2]):\n",
    "    print(i,k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adott egy permutáció lista formájában. Pl: [1,0,2,3] Írd ki a lista fixpontjainak a számát!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fixpont(l):\n",
    "    #todo\n",
    "    \n",
    "assert(fixpont([0,1,2])==3)\n",
    "assert(fixpont([0,2,1])==1)\n",
    "assert(fixpont([4,1,2,0])==2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Az `import numpy as np` parancs lefuttatás után a `list(np.random.permutation(n))` parancsot használhatjuk arra, hogy egy véletlen permutációt kapjunk. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "list(np.random.permutation(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Végezzünk kíséretet! Egy véletlen permutációnak várhatóan hány fixpontja van? Vegyél 10000 véletlen permutációt és számold ki az átlagos fixpontszámot! Próbáld ki többféle n-re is!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# todo kísérlet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6 Írj egy függvényt, amely visszatér egy megadott lista másolatával!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def copylist(l):\n",
    "    #todo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.7 Írj egy függvényt, amely helyben megfordítja egy lista sorrendjét. (Tehát nincs visszatérési érték, csupán megváltozik a beadott lista.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(l):\n",
    "    #todo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}