{ "cells": [ { "cell_type": "code", "execution_count": 2, "id": "ee0b670d-30e5-49df-891f-d7cb7c7d8216", "metadata": {}, "outputs": [], "source": [ "def max_heapify(lst: list) -> list:\n", " print(\"hola\")" ] }, { "cell_type": "code", "execution_count": 8, "id": "4ef52abf-c4c8-473d-ae00-615248010c86", "metadata": {}, "outputs": [], "source": [ "# void copias::BubbleSort() {\n", "# //este ciclo va desde la primera posicion hasta la penúltima\n", "# //en cada iteracion se asegura que hay un elemento en la posicion correcta (el mas pequeño)\n", "# for (int i = 0; i < size - 1; i++) {\n", "# //empieza desde el penultimo elemento\n", "# for (int j = size - 1; j > i; j--) {\n", "# if (arregloC[j] < arregloC[j - 1]) {\n", "# this->swap(j, j - 1); //se intercambian los elementos \n", "# }\n", "# }\n", "# }\n", "# return;\n", "# }\n", "def BubbleSort(arr: list[int]) -> list[int]:\n", " def swap(i: int, j: int) -> list[int]:\n", " arr[i], arr[j] = arr[j], arr[i]\n", "\n", " for i in range(len(arr) - 1):\n", " for j in range(size - 1, i):\n", " if arr[j] < arr[j - 1]:\n", " swap(j, j - 1)\n", " return arr" ] }, { "cell_type": "code", "execution_count": 9, "id": "fd7cac2f-f8ed-40ed-8d8f-a82cb13f203a", "metadata": {}, "outputs": [], "source": [ "# void copias::MergeSort(int p, int r){\n", "# //caso base\n", "# if(p >= r){\n", "# return;\n", "# }\n", "# //se calcula q como el midpoint (piso)\n", "# int q = (p + r) / 2;\n", "# //recursion con el arreglo \"izquierdo\"\n", "# MergeSort(p, q);\n", "# //recursion con el arreglo \"derecho\"\n", "# MergeSort(q + 1, r);\n", "# //union de todo bajo las llamadas recursivas\n", "# Merge(p, q, r);\n", "\n", "# return;\n", "# }\n", "\n", "def MergeSort(arr: list[int], p = 0, r = None) -> list[int]:\n", " if r == None:\n", " r = len(arr) - 1\n", " if p >= r:\n", " return arr\n", "\n", " q = (p + r) // 2\n", " arr = MergeSort(arr, p, q)\n", " arr = MergeSort(arr, q + 1, r)\n", " arr = Merge(arr, p, q, r)\n", "\n", " return arr" ] }, { "cell_type": "code", "execution_count": 6, "id": "abefcc33-6e81-49e7-9134-b71115f4d029", "metadata": {}, "outputs": [], "source": [ "# void copias::Merge(int p, int q, int r){\n", "# int qty1 = q - p + 1; //cantidad de elementos del arreglo izquierdo\n", "# int qty2 = r - q; //cantidad de elementos del arreglo derecho\n", "# int L[qty1], R[qty2]; //declaración del arreglo izquierdo y derecho\n", "\n", "# //se copian los datos del arreglo a los subarreglos\n", "# for(int i = 0; i < qty1; i++){\n", "# L[i] = arregloC[p + i];\n", "# }\n", "\n", "# for(int j = 0; j < qty2; j++){\n", "# R[j] = arregloC[q + 1 + j];\n", "# }\n", "\n", "# int i = 0;\n", "# int j = 0;\n", "# int k = p;\n", "# //este ciclo sucede siempre que no se hayan evaluado todos los elementos\n", "# //de alguno de los subarreglos\n", "# while(i < qty1 && j < qty2){\n", "\n", "# //se va verificando cual de los \"tops\" de ambos arreglos es el menor, ese se va asignando al indice k\n", "# if( L[i] <= R[j] ){\n", "# arregloC[k] = L[i];\n", "# i++;\n", "# }\n", "\n", "# else{\n", "# arregloC[k] = R[j];\n", "# j++;\n", "# }\n", "# k++;\n", "# }\n", "\n", "# //estos ciclos suceden para meter al arreglo los elementos del subarreglo que faltaron por evaluar\n", "# //porque eran mas grandes que todos los elementos del otro subarreglo\n", "# while(i < qty1){\n", "# arregloC[k] = L[i];\n", "# i++;\n", "# k++;\n", "# }\n", "\n", "# while(j < qty2){\n", "# arregloC[k] = R[j];\n", "# j++;\n", "# k++;\n", "# }\n", "# return;\n", "# }\n", "def Merge(arr: list[int], p: int, q: int, r: int) -> list[int]:\n", " qty1 = q - p + 1\n", " qty2 = r - q\n", " l = arr[0:qty1]\n", " r = arr[0:qty2]\n", "\n", " i = 0\n", " j = 0\n", " k = p\n", " while i < qty1 and j < qty2:\n", " if l[i] < r[j]:\n", " arr[k] = l[i]\n", " i += 1\n", " else:\n", " arr[k] = r[j]\n", " j += 1\n", " k += 1\n", "\n", " while i < qty1:\n", " arr[k] = l[i]\n", " i += 1\n", " k += 1\n", " while k < qty2:\n", " arr[k] = r[j]\n", " j += 1\n", " k += 1\n", " return arr" ] }, { "cell_type": "code", "execution_count": 16, "id": "595d00e7-7d5e-4645-a41e-1560c431e81a", "metadata": {}, "outputs": [], "source": [ "def BubbleMergeSort(arr: list[int]) -> list[int]:\n", " def BubbleSort(lst: list[int]) -> list[int]:\n", " def swap(i: int, j: int) -> list[int]:\n", " lst[i], lst[j] = lst[j], lst[i]\n", " \n", " for i in range(len(lst) - 1):\n", " for j in range(size - 1, i):\n", " if lst[j] < lst[j - 1]:\n", " swap(j, j - 1)\n", " return lst\n", "\n", " def MergeSort(lst: list[int], p = 0, r = None) -> list[int]:\n", " if r == None:\n", " r = len(lst) - 1\n", " if p >= r:\n", " return lst\n", " if len(lst) <= 143:\n", " return BubbleSort(lst)\n", " \n", " q = (p + r) // 2\n", " lst = MergeSort(lst, p, q)\n", " lst = MergeSort(lst, q + 1, r)\n", " lst = Merge(lst, p, q, r)\n", " \n", " return arr\n", "\n", " if len(arr) <= 143:\n", " return BubbleSort(arr)\n", " else:\n", " return MergeSort(arr)" ] }, { "cell_type": "code", "execution_count": 55, "id": "f2c30cc6-0c7d-496f-b940-f047db86e90d", "metadata": {}, "outputs": [], "source": [ "def DC_POSITIVE_PROD(A: list[int], f = 0, l = None) -> tuple[int, int]:\n", " if l == None:\n", " l = len(A)\n", " if l - f == 1:\n", " if A[f] <= 0:\n", " return 0, 1\n", " else:\n", " return 1, A[f]\n", "\n", " n = len(A)\n", " m = (f + l) // 2\n", " x, left = DC_POSITIVE_PROD(A, f, m)\n", " y, right = DC_POSITIVE_PROD(A, m, l)\n", " return x + y, left * right" ] }, { "cell_type": "code", "execution_count": 56, "id": "f4701e84-2f6a-4f77-8987-10fcf64a7b47", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3, 42)" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "DC_POSITIVE_PROD(lst)" ] }, { "cell_type": "code", "execution_count": 54, "id": "3b52dfb5-7f87-48f2-a58e-7a671af08477", "metadata": {}, "outputs": [ { "ename": "SyntaxError", "evalue": "invalid syntax (1079348763.py, line 1)", "output_type": "error", "traceback": [ "\u001b[0;36m Cell \u001b[0;32mIn[54], line 1\u001b[0;36m\u001b[0m\n\u001b[0;31m if x := 0 else elif break;core\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n" ] } ], "source": [ "if x := 0 else elif break;core" ] }, { "cell_type": "code", "execution_count": 50, "id": "1a591d37-fdf5-4058-b680-ace7f34c526f", "metadata": {}, "outputs": [], "source": [ "lst = [2, 0, -1, 7, -9, 0, 3, -20]" ] }, { "cell_type": "code", "execution_count": 26, "id": "95f7f682-f7ea-4cf2-a792-7523763ccc10", "metadata": {}, "outputs": [], "source": [ "memo = {}\n", "def coin_change(amount, coins):\n", " if amount == 0:\n", " return 0\n", " elif amount < 0:\n", " return -1\n", " elif amount not in memo:\n", " amounts = filter(lambda x: x >= 0, [coin_change(amount - coin, coins) for coin in coins])\n", " memo[amount] = min(amounts) + 1\n", " return memo[amount]\n", " else:\n", " return memo[amount]" ] }, { "cell_type": "code", "execution_count": 30, "id": "519b39fe-43aa-4711-8de2-e0a61f26a362", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 1\n", "2 2\n", "3 1\n", "4 2\n", "5 3\n", "6 2\n", "7 1\n", "8 2\n", "9 3\n", "10 2\n", "11 3\n", "12 4\n", "13 3\n", "14 2\n", "15 3\n", "16 4\n", "17 3\n", "18 4\n", "19 5\n", "20 4\n", "21 3\n", "22 4\n", "23 5\n", "24 4\n", "25 5\n", "26 6\n", "27 5\n", "28 4\n", "29 5\n", "30 6\n", "31 5\n", "32 6\n", "33 7\n", "34 6\n", "35 5\n", "36 6\n", "37 7\n", "38 6\n", "39 7\n", "40 8\n", "41 7\n", "42 6\n", "43 7\n", "44 8\n", "45 7\n", "46 8\n", "47 9\n", "48 8\n", "49 7\n", "50 8\n", "51 9\n", "52 8\n", "53 9\n", "54 10\n", "55 9\n", "56 8\n", "57 9\n", "58 10\n", "59 9\n", "60 10\n", "61 11\n", "62 10\n", "63 9\n", "64 10\n", "65 11\n", "66 10\n", "67 11\n", "68 12\n", "69 11\n", "70 10\n", "71 11\n", "72 12\n", "73 11\n", "74 12\n", "75 13\n", "76 12\n", "77 11\n" ] } ], "source": [ "for x in range(1,78):\n", " print(x, coin_change(x, [7, 1, 3]))" ] }, { "cell_type": "code", "execution_count": null, "id": "73bae520-31fb-4c05-bb30-5fc92fc1ea70", "metadata": {}, "outputs": [], "source": [] } ], "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.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }