inf-abi2027/01 Einführung/07 Rekursion/03 Fibonacci.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0609fa9a-6337-43c0-a8d2-f947558066ac",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import { assertEquals } from \"jsr:@std/assert\"\n",
    "import \"https://git.amgdhg.de/kg/tslib/raw/branch/main/logger.ts\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2253715-005d-4a31-b577-4ba32a314da6",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# Aufgabe 01.07.2 - Fibonacci\n",
    "\n",
    "Die Fibonacci Folge $F$\n",
    "$$0,1,1,2,3,5,8,13,21,34,55,\\dots$$\n",
    "ist folgendermaßen definiert:\n",
    "* $F(0)=0$\n",
    "* $F(1)=1$\n",
    "* $F(2)=F(0)+F(1)$\n",
    "* $F(3)=F(1)+F(2)$\n",
    "* bzw. allgemein: $F(n)=F(n-2)+F(n-1)$\n",
    "\n",
    "Diese soll nun mit einer Funktion `fibo` programmiert werden, die einen Parameter $n$ übergeben bekommt und dann die $n$-te Fibonacci-Zahl berechnet.\n",
    "\n",
    "### Hinweis:\n",
    "$0$ ist die \"nullte\" Zahl, 1 die erste."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81e736ba-89cd-4d1a-9b98-8475de6820bd",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Teil 1\n",
    "Notiere zunächst die rekursiven Funktionsaufrufe für das konkrete Zahlenbeispiel $n=5$:"
   ]
  },
  {
   "cell_type": "raw",
   "id": "58f5ec36-ae74-4ff0-9e47-4f0f83adbd7b",
   "metadata": {
    "editable": true,
    "raw_mimetype": "",
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ba4b1f2a-51cc-47ff-8b1f-f8444cddd7b9",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Teil 2\n",
    "Wann bricht die Rekursion ab, d.h. wann wird nicht mehr erneut die Funktion `fibo` aufgerufen?"
   ]
  },
  {
   "cell_type": "raw",
   "id": "261e0c80-0169-424f-840a-47c774029ced",
   "metadata": {
    "editable": true,
    "raw_mimetype": "",
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "37316573-632d-440f-9674-1dddbd5039f3",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Teil 3\n",
    "Programmiere die Funtion `fibo`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8c40034-1b97-458a-9e30-648c41cb3d7c",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e114cca7-8b8a-4f7e-8861-1a507a679d3d",
   "metadata": {
    "editable": true,
    "jupyter": {
     "source_hidden": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "let _nr = \"01.07.2\"\n",
    "Deno.test(`${_nr}: function`, () => {\n",
    "    assertEquals(typeof fibo, 'function')\n",
    "})\n",
    "Deno.test(`${_nr}: Parameter`, () => {\n",
    "    assertEquals(fibo.length, 1)\n",
    "})\n",
    "Deno.test(`${_nr}: fibo(1)=1`, () => {\n",
    "    assertEquals(fibo(1), 1)\n",
    "})\n",
    "Deno.test(`${_nr}: fibo(3)=2`, () => {\n",
    "    assertEquals(fibo(3), 2)\n",
    "})\n",
    "Deno.test(`${_nr}: fibo(5)=5`, () => {\n",
    "    assertEquals(fibo(5), 5)\n",
    "})\n",
    "Deno.test(`${_nr}: fibo(11)=89`, () => {\n",
    "    assertEquals(fibo(11), 89)\n",
    "})\n",
    "Deno.test(`${_nr}: fibo(23)=28657`, () => {\n",
    "    assertEquals(fibo(23), 28657)\n",
    "})"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Deno",
   "language": "typescript",
   "name": "deno"
  },
  "language_info": {
   "codemirror_mode": "typescript",
   "file_extension": ".ts",
   "mimetype": "text/x.typescript",
   "name": "typescript",
   "nbconvert_exporter": "script",
   "pygments_lexer": "typescript",
   "version": "5.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}