You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
429 lines
15 KiB
429 lines
15 KiB
{
|
|
"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": [
|
|
"<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\">Manim Community <span style=\"color: #008000\">v0.12.0</span>\n",
|
|
"\n",
|
|
"</pre>\n"
|
|
],
|
|
"text/plain": [
|
|
"<rich.jupyter.JupyterRenderable at 0x7f2157da0e80>"
|
|
]
|
|
},
|
|
"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": [
|
|
"<video src=\"media/jupyter/Shuffle@2021-12-03@16-30-04.mp4\" controls autoplay loop style=\"max-width: 60%;\" >\n",
|
|
" Your browser does not support the <code>video</code> element.\n",
|
|
" </video>"
|
|
],
|
|
"text/plain": [
|
|
"<IPython.core.display.Video object>"
|
|
]
|
|
},
|
|
"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": [
|
|
"<video src=\"media/jupyter/Sort@2021-12-03@16-32-06.mp4\" controls autoplay loop style=\"max-width: 60%;\" >\n",
|
|
" Your browser does not support the <code>video</code> element.\n",
|
|
" </video>"
|
|
],
|
|
"text/plain": [
|
|
"<IPython.core.display.Video object>"
|
|
]
|
|
},
|
|
"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": [
|
|
"<video src=\"media/jupyter/Search@2021-12-03@16-32-19.mp4\" controls autoplay loop style=\"max-width: 60%;\" >\n",
|
|
" Your browser does not support the <code>video</code> element.\n",
|
|
" </video>"
|
|
],
|
|
"text/plain": [
|
|
"<IPython.core.display.Video object>"
|
|
]
|
|
},
|
|
"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
|
|
}
|
|
|