Sesión 3-4

Clases del 25 y 27 de febrero de 2020.

Temas

• Recursión con memorización.

• Aritmética modular.

• Exponenciación rápida.

Extra. Puedes consultar el material de este link para ampliar los temas de recursión y exponenciación rápida.

Recursión con memorización

Demostración de por qué es conveniente guardar los resultados en memoria.

// Funcion recursiva 4
#include <iostream>
#include <vector>

using namespace std;

vector<int> memo(41);

int f(int n) {
    // Caso base
    if (n <= 3) {
        return  1;
    }
    // Verificar si no lo hemos calculado antes
    if(memo[n] != 0) {
        return memo[n];
    }
    // Calcular el resultado y guardarlo en la memoria
    memo[n] = f(n-1) + f(n-2) + f(n-3);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    cout << f(n);

    return 0;
}

Exponenciación rápida

Consulta la explicación en este link: https://github.com/omioaxaca/ooi-2020/blob/master/curso-avanzado/sesion-3/exponenciacion_rapida.md

Aritmética modular

// Demostracion de las operaciones basicas de aritmetica modular
#include <iostream>

using namespace std;

int main() {
    // Variable para guardar el modulo;
    int m = 7;
    // Variables de ejemplo
    int a = 8;
    int b = 5;
    int c;

    // Suma
    c = a + b; // 13
    // Suma modular
    // Es lo mismo sumar todos los elementos y al final obtener el modulo m
    // que obtener el modulo de cada elemento y sumarlo y obtener el modulo al final.
    int d;
    d = (a % m + b % m) % m; // 5 + 1 = 6
    if (c % m == d) {
        cout << "La aritmetica modular funciona en sumas!\n";
    }
    // 5 + 8 = 13
    // 13 % 7 = 6

    // 10 + 15 + 22 = 47
    // 47 % 7 = 5

    // 10 % 7 = 3
    // 15 % 7 = 1
    // 22 % 7 = 1
    // 3 + 1 + 1 = 5
    // 5 % 7 = 5

    // Resta
    c = a - b;
    // Resta modular
    // Es lo mismo restar todos los elementos y al final obtener el modulo m
    // que obtener el modulo de cada elemento y restarlos y obtener el modulo al final.
    // Nota: Si en algun momento el resultado parcial se hace negativo, es necesario sumar
    // el modulo (m).                                Ejemplo
    //                                                 |
    //                                                 ↓              
    // Regla general: (a - b) % m = ((a % m - b % m) + m) % m;
    d = ((a % m - b % m) + m) % m;
    if (c % m == d) {
        cout << "La aritmetica modular funciona en restas!\n";
    }
    // 5 - 8 = (-3+7) % 7 = 4
    // 5 % 7 = 5
    // -8 % 7 = 1
    // 5 - 1 = 4
    // 4 % 7 = 4

    // Multiplicacion
    c = a * b;
    // Multiplicacion modular
    d = (a % m * b % m) % m;
    if (c % m == d) {
        cout << "La aritmetica modular funciona en multiplicaciones!\n";
    }

    // Division
    // NO SE PUEDE! Nota: En realidad si se puede, pero haciendo cosas muy raras. :(





    return 0;
}

Códigos vistos en clase

ooi-2020/curso-avanzado/sesion-3 at master · omioaxaca/ooi-2020GitHub

Clase 3

ooi-2020/curso-avanzado/sesion-4 at master · omioaxaca/ooi-2020GitHub

Clase 4

Video: https://youtu.be/4ex-wyPhBc4