Programar é uma atividade cheia de desafios. Neste artigo vamos explorar problemas clássicos e programação dinâmica, utilizando exemplos práticos em JavaScript. 

Quais os problemas que serão abordados neste artigo?

• Torre de Hanói
• Dois Números com Soma Alvo
• Elemento Mais Frequente de um Array
• O Problema da Mochila
• Maior Subsequência Crescente
• Fibonacci Otimizado

A Torre de Hanói

A Torre de Hanói é um quebra-cabeça matemático que foi criado em 1883 pelo matemático francês Édouard Lucas. Ele apresentou o problema sob o nome "Torre de Brâmanes" e o associou a uma lenda fascinante para torná-lo mais intrigante.

Segundo a lenda, havia um templo em Benares (atualmente Varanasi, na Índia), onde sacerdotes realizavam um ritual envolvendo três pinos e 64 discos de ouro de tamanhos diferentes. A tarefa dos sacerdotes era mover todos os discos de um pino para outro, seguindo as mesmas regras do quebra-cabeça moderno:

- Apenas um disco pode ser movido por vez.

- Um disco maior não pode ser colocado sobre um menor.

- Todos os discos devem ser transferidos de uma torre para outra.

Dizia-se que quando os sacerdotes completassem a tarefa, o universo chegaria ao fim. No entanto, a matemática por trás do problema mostra que isso levaria uma quantidade de tempo extraordinária para acontecer. Mesmo que os sacerdotes trabalhassem a uma velocidade de um movimento por segundo, levariam cerca de 585 bilhões de anos para concluir a tarefa — muito mais do que a idade atual do universo!

Este problema é excelente para entender conceitos de recursão.

function hanoi(n, from, to, aux) {

    if (n === 1) {

        console.log(`Move o disco 1 de ${from} para ${to}`);

        return;

    }

    hanoi(n - 1, from, aux, to);

    console.log(`Move o disco ${n} de ${from} para ${to}`);

    hanoi(n - 1, aux, to, from);

}

hanoi(3, \'A\', \'C\', \'B\'); // Exemplo com 3 discos

Esse problema ajuda a entender como dividir uma tarefa complexa em subtarefas menores, um conceito crucial em algoritmos.

Dois Números com Soma Alvo

Dado um array de números e um valor alvo, o objetivo é encontrar dois números cuja soma seja igual ao valor alvo.

function twoSum(nums, target) {

    const map = new Map();

    for (let i = 0; i < nums.length; i++) {

        const complement = target - nums[i];

        if (map.has(complement)) {

            return [map.get(complement), i];

        }

        map.set(nums[i], i);

    }

    return [];

}

console.log(twoSum([2, 7, 11, 15], 9)); // Saída: [0, 1]

Esse é um problema comum em entrevistas e destaca a eficiência de usar estruturas de dados como Map para resolver problemas em tempo linear.

Elemento Mais Frequente

O desafio é encontrar o elemento que aparece mais vezes em um array.

function mostFrequent(nums) {

    const freqMap = {};

    let maxCount = 0, mostFrequentNum = null;

    for (let num of nums) {

        freqMap[num] = (freqMap[num] || 0) + 1;

        if (freqMap[num] > maxCount) {

            maxCount = freqMap[num];

            mostFrequentNum = num;

        }

    }

    return mostFrequentNum;

}

console.log(mostFrequent([1, 3, 2, 3, 3, 1, 2, 1, 1])); // Saída: 1

Esse problema introduz o uso de mapas de frequência, uma técnica comum para analisar conjuntos de dados.

O problema da mochila

O problema da mochila foi formalizado no campo da teoria da computação e da pesquisa operacional. Ele apareceu inicialmente em estudos matemáticos sobre programação linear e teoria dos grafos no início do século XX, mas se popularizou no século XX com a crescente demanda por algoritmos eficientes para resolver problemas reais.

A primeira referência clara ao problema como o conhecemos hoje é encontrada nos trabalhos de pesquisadores como George Dantzig, que também é famoso por desenvolver o método Simplex.

A ideia básica é simples: você é um aventureiro com uma mochila de capacidade limitada. Diante de você estão vários itens, cada um com um peso e um valor. O desafio é escolher quais itens levar para maximizar o valor total sem ultrapassar o peso máximo que a mochila pode suportar.

Este problema é um clássico para aprender sobre otimização e ele é uma metáfora para muitas decisões práticas, como Gestão de Recursos, Planejamento de Investimentos, Logística e Jogos e Simulações.

function knapsack(values, weights, capacity) {

    const n = values.length;

    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {

        for (let w = 1; w <= capacity; w++) {

            if (weights[i - 1] <= w) {

                dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);

            } else {

                dp[i][w] = dp[i - 1][w];

            }

        }

    }

    return dp[n][capacity];

}

console.log(knapsack([60, 100, 120], [10, 20, 30], 50)); // Saída: 220

Este problema ensina como usar tabelas para armazenar soluções intermediárias, um conceito essencial na programação dinâmica.

Maior Subsequência Crescente

O objetivo deste problema é encontrar a maior subsequência crescente dentro de um array de números.

function longestIncreasingSubsequence(nums) {

    const dp = Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {

        for (let j = 0; j < i; j++) {

            if (nums[i] > nums[j]) {

                dp[i] = Math.max(dp[i], dp[j] + 1);

            }

        }

    }

    return Math.max(...dp);

}

console.log(longestIncreasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18])); // Saída: 4

Esse problema mostra como identificar relações entre elementos e usar técnicas iterativas para resolvê-lo eficientemente.

Fibonacci Otimizado

A sequência de Fibonacci foi introduzida ao mundo ocidental pelo matemático italiano Leonardo de Pisa, conhecido como Fibonacci, em seu livro Liber Abaci (1202). No livro, ele usou a sequência para resolver um problema sobre o crescimento de uma população de coelhos em condições ideais.

Imagine que:

- Você começa com um par de coelhos.

- Cada par de coelhos atinge a maturidade em um mês.

- Após o primeiro mês, cada par maduro gera um novo par de coelhos a cada mês.

- Nenhum coelho morre.

- Quantos pares de coelhos existirão após um determinado número de meses?

Ao modelar o crescimento, Fibonacci descobriu a sequência que leva seu nome.

O desafio é calcular o n-ésimo número de Fibonacci de forma eficiente, evitando a recursão simples.

function fibonacci(n) {

    if (n <= 1) return n;

    let prev = 0, curr = 1;

    for (let i = 2; i <= n; i++) {

        [prev, curr] = [curr, prev + curr];

    }

    return curr;

}

console.log(fibonacci(10)); // Saída: 55

O problema de Fibonacci demonstra como otimizar soluções ao reduzir o uso de memória sem comprometer a eficiência.