{ "cells": [ { "cell_type": "markdown", "id": "36cee816", "metadata": {}, "source": [ "# Řešení 1. série" ] }, { "cell_type": "code", "execution_count": 1, "id": "efe16561", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
Manim Community v0.12.0\n",
       "\n",
       "
\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from manim import *" ] }, { "cell_type": "markdown", "id": "24037488", "metadata": {}, "source": [ "## Míchání" ] }, { "cell_type": "code", "execution_count": 2, "id": "252d64a3", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " \r" ] }, { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%manim -v WARNING -qh Shuffle\n", "\n", "from random import *\n", "\n", "\n", "class Shuffle(Scene):\n", " def construct(self):\n", " seed(0xdeadbeef)\n", " \n", " # počet hodnot k míchání\n", " n = 5\n", "\n", " circles = [\n", " Circle(color=WHITE, fill_opacity=0.8, fill_color=WHITE).scale(0.6)\n", " for _ in range(n)\n", " ]\n", "\n", " # mezery mezi kruhy\n", " spacing = 2\n", " for i, circle in enumerate(circles):\n", " circle.shift(RIGHT * (i - (len(circles) - 1) / 2) * spacing)\n", "\n", " self.play(*[Write(circle) for circle in circles])\n", "\n", " # vybraný kruh\n", " selected = randint(0, n - 1)\n", " self.play(circles[selected].animate.set_color(RED))\n", " self.play(circles[selected].animate.set_color(WHITE))\n", "\n", " # postupné zrychlování při navazujících prohozeních\n", " swaps = 13\n", " speed_start = 1\n", " speed_end = 0.2\n", "\n", " for i in range(swaps):\n", " speed = speed_start - abs(speed_start - speed_end) / swaps * i\n", " \n", " # vybrání dvou různých náhodných kruhů\n", " a, b = sample(range(n), 2)\n", " \n", " # prohození s o trochu větším úhlem, jinak přes sebe kruhy procházejí, což není hezké\n", " self.play(\n", " Swap(circles[a], circles[b]), run_time=speed, path_arc=135 * DEGREES\n", " )\n", "\n", " # zvýraznění původních kruhů\n", " self.play(circles[selected].animate.set_color(RED))\n", " self.play(circles[selected].animate.set_color(WHITE))" ] }, { "cell_type": "markdown", "id": "c5b2a96d", "metadata": {}, "source": [ "## Třízení" ] }, { "cell_type": "code", "execution_count": 3, "id": "72c49f8f", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " \r" ] }, { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%manim -v WARNING -qh Sort\n", "\n", "from random import *\n", "\n", "\n", "class Sort(Scene):\n", " def construct(self):\n", " seed(0xdeadbeef)\n", " \n", " # počet hodnot ke třízení\n", " n = 20\n", "\n", " # nejmenší a největší hodnta\n", " value_min, value_max = 1, 20\n", "\n", " # hodnoty v poli\n", " values = [randint(value_min, value_max) for _ in range(n)]\n", "\n", " # šířka čtverce a výška jedné hodnoty (tzn. číslo 5 má výšku 5 * unit_height)\n", " rectangle_width = 0.2\n", " unit_height = 0.2\n", "\n", " # mezera mezi obdélníky\n", " rectangle_spacing = 2.5\n", " \n", " rectangles = [\n", " Rectangle(\n", " width=rectangle_width,\n", " height=unit_height * v,\n", " fill_color=WHITE,\n", " fill_opacity=1,\n", " )\n", " for v in values\n", " ]\n", " \n", " # bod, podle kterého budeme rovnat spodek přes funkci align_to\n", " # aby byly čtverce vycentrované, bude odpovídat spodku nejvyšší hodnoty\n", " alignment_point = None\n", " max_value = 0\n", " for i, v in enumerate(values):\n", " if max_value < v:\n", " max_value = v\n", " alignment_point = Point().shift(DOWN * rectangles[i].height / 2)\n", "\n", " # posun obdélníků tak, aby byly rovnoměrně rozprostřené a zarovnané dolů\n", " for i, rect in enumerate(rectangles):\n", " rect.shift(\n", " RIGHT\n", " * (i - (len(rectangles) - 1) / 2)\n", " * rectangle_width\n", " * rectangle_spacing\n", " ).align_to(alignment_point, DOWN)\n", "\n", " self.play(*[Write(r) for r in rectangles])\n", "\n", " def animate_at(a, b, duration):\n", " \"\"\"Animace toho, že se aktuálně díváme na pozice a a b.\"\"\"\n", " self.play(\n", " *[\n", " r.animate.set_color(WHITE if i not in (a, b) else YELLOW)\n", " for i, r in enumerate(rectangles)\n", " ],\n", " run_time=duration,\n", " )\n", "\n", " def animate_swap(a, b, duration):\n", " \"\"\"Animace prohození a a b (s tím, že v poli values už jsou prohozené).\"\"\"\n", " self.play(\n", " # jelikož stretch_to_fit_height stretchuje z prostředku, musíme alignnout na bod\n", " rectangles[a]\n", " .animate.stretch_to_fit_height(values[a] * unit_height)\n", " .align_to(alignment_point, DOWN),\n", " rectangles[b]\n", " .animate.stretch_to_fit_height(values[b] * unit_height)\n", " .align_to(alignment_point, DOWN),\n", " run_time=duration,\n", " )\n", "\n", " # při prvním průchodu jsou animace pomalejší\n", " speed_slow = 0.6\n", " speed_fast = 0.07\n", "\n", " for i in range(n):\n", " speed = speed_slow if i == 0 else speed_fast\n", " swapped = False\n", " for j in range(n - i - 1):\n", " animate_at(j, j + 1, speed)\n", "\n", " if values[j] > values[j + 1]:\n", " values[j], values[j + 1] = values[j + 1], values[j]\n", "\n", " animate_swap(j, j + 1, speed)\n", " swapped = True\n", "\n", " # pokud jsme při průchodu nic neprohodili, tak už není co třídit\n", " if not swapped:\n", " break\n", "\n", " self.play(*[FadeOut(r) for r in rectangles])" ] }, { "cell_type": "markdown", "id": "7a4c30a9", "metadata": {}, "source": [ "## Vyhledávání" ] }, { "cell_type": "code", "execution_count": 4, "id": "07983bb0", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " \r" ] }, { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%manim -v WARNING -qh Search\n", "\n", "from random import *\n", "\n", "\n", "class Search(Scene):\n", " def construct(self):\n", " seed(0xdeadbeef4) # hezčí vstup :)\n", " \n", " # počet hodnot ke třízení\n", " n = 10\n", "\n", " # nejmenší a největší hodnta\n", " value_min, value_max = 1, n\n", "\n", " # hodnoty v poli\n", " values = sorted([randint(value_min, value_max) for _ in range(n)])\n", "\n", " square_side_length = 0.75\n", " square_spacing = 1.3\n", "\n", " squares = [Square(side_length=square_side_length) for v in values]\n", " numbers = [Tex(f\"${v}$\") for v in values]\n", "\n", " # posun čtverců tak, aby byly uprostřed obrazovky\n", " for i, rect in enumerate(squares):\n", " rect.shift(\n", " RIGHT\n", " * (i - (len(squares) - 1) / 2)\n", " * square_side_length\n", " * square_spacing\n", " )\n", "\n", " # posun textu tak, aby byly uvnitř čtverců\n", " for i, number in enumerate(numbers):\n", " number.move_to(squares[i])\n", "\n", " # pointery na to, kde aktuálně jsme\n", " pointer_length = 0.4\n", " l_arrow = Arrow(start=DOWN * pointer_length, end=UP).next_to(squares[0], DOWN)\n", " r_arrow = Arrow(start=DOWN * pointer_length, end=UP).next_to(squares[-1], DOWN)\n", "\n", " self.play(*[Write(s) for s in squares], *[Write(n) for n in numbers])\n", "\n", " # vypsání čísla, které hledáme\n", " target = randint(value_min, value_max)\n", " text = Tex(f\"Hledáme: ${target}$\").shift(UP * 1.5)\n", "\n", " self.play(Write(text))\n", "\n", " self.play(Write(l_arrow), Write(r_arrow))\n", "\n", " lo, hi = 0, len(values) - 1\n", "\n", " def color_in_range(objects, color, range):\n", " \"\"\"Vrátí seznam animací vybarvení daných objektů v daném rozmezí.\"\"\"\n", " return [\n", " o.animate.set_color(color) for i, o in enumerate(objects) if i in range\n", " ]\n", "\n", " # samotný algoritmus\n", " while lo < hi:\n", " avg = (lo + hi) // 2\n", " \n", " # vykreslení pointeru u aktuálního prvku\n", " current_arrow = Arrow(start=DOWN * pointer_length, end=UP) \\\n", " .next_to(squares[avg], DOWN) \\\n", " .set_color(ORANGE)\n", " \n", " self.play(Write(current_arrow))\n", "\n", " if values[avg] < target:\n", " # posunutí levého pointeru\n", " self.play(\n", " FadeOut(current_arrow),\n", " l_arrow.animate.next_to(squares[avg + 1], DOWN),\n", " *color_in_range(squares, DARK_GRAY, range(lo, avg + 1)),\n", " *color_in_range(numbers, DARK_GRAY, range(lo, avg + 1)),\n", " )\n", "\n", " lo = avg + 1\n", " elif values[avg] >= target:\n", " # posunutí pravého pointeru\n", " self.play(\n", " FadeOut(current_arrow),\n", " r_arrow.animate.next_to(squares[avg], DOWN),\n", " *color_in_range(squares, DARK_GRAY, range(avg + 1, hi + 1)),\n", " *color_in_range(numbers, DARK_GRAY, range(avg + 1, hi + 1)),\n", " )\n", "\n", " hi = avg\n", "\n", " # nalezení hledané hodnoty\n", " if values[hi] == target:\n", " self.play(\n", " *color_in_range(squares, DARK_GRAY, range(hi)),\n", " *color_in_range(squares, DARK_GRAY, range(hi+1, n)),\n", " *color_in_range(numbers, DARK_GRAY, range(hi)),\n", " *color_in_range(numbers, DARK_GRAY, range(hi+1, n)),\n", " numbers[hi].animate.set_color(GREEN),\n", " squares[hi].animate.set_color(GREEN),\n", " FadeOut(l_arrow),\n", " )\n", " break\n", " \n", " \n", " self.play(*[FadeOut(r) for r in numbers + squares + [r_arrow, text]])" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.7" } }, "nbformat": 4, "nbformat_minor": 5 }