Skip to content

Instantly share code, notes, and snippets.

@felipelouza

felipelouza/17.md Secret

Last active October 21, 2020 17:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save felipelouza/7170a912b0e4ad80d66b30e4f491219c to your computer and use it in GitHub Desktop.
Save felipelouza/7170a912b0e4ad80d66b30e4f491219c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
17.md

📘📗📓 Semana 17

Programação dinâmica (parte 1)

Conceitos (Top-Down e Bottom-Down)

Fibonnacci módulo M

O problema 1531 do Uri Online Judge pede para calcular Fib(Fib(10^9)) módulo M. As estratégias Top-Down e Bottom-Down não funcionam para este caso. No editorial abaixo você aprenderá: Sequência de Pisano, Fast Doubling e Exponenciação de Matriz

Os links abaixo lista métodos para calcular o n-ésimo número da sequência de Fibonacci de formas mais rápidas. Passe o olho por todos, pois cada um tem uma forma diferentes de apresentar os métodos.

O número de Pisano é o número de termos no qual a sequência de Fibonacci módulo m leva para voltar a se repetir. Em outras palavras, sabendo que a sequência de Fibonacci módulo m é periódica, o número de Pisano é o tamanho do período. Uma fórma de calcular o número de Pisano para determinado m é:

long long get_pisano_period(long long m) {
    long long a = 0, b = 1, c = a + b;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) return i + 1;
    }
}

Dessa forma, utilizando o número de Pisano, é possível calcular Fibonacci módulo m de um número n muito grande:

long long get_fibonacci_huge(long long n, long long m) {
    long long remainder = n % get_pisano_period(m);

    long long first = 0;
    long long second = 1;

    long long res = remainder;

    for (int i = 1; i < remainder; i++) {
        res = (first + second) % m;
        first = second;
        second = res;
    }

    return res % m;
}

Maior subsequência crescente

Um paralelo muito importante com o problema de maior subsequência cresente e o maior caminho em um grafo é explicado neste post:

Entender essa analogia pode trazer benefícios da teoria dos grafos para resolução de problemas envolvendo maior subsequência crescente.

Princípios combinatórios e Permutações e combinações

Teoria dos jogos

🚶🏃🏃 Exercícios

🏆🏆🏆 Torneio 17 - UFTM/FEELT/UFU

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment