Feeds:
Posts
Comentários

Cormen – Programação Dinâmica – Linha de Montagem

Uma DSL que fornece os dados para o algoritmo de linha de montagem (o objetivo maior foi praticar ruby e implementação de DSL’s)

Cormen - Programação Dinâmica

Cormen – Programação Dinâmica
(mude de doc para rtf ou rb qdo for abrir)

[]’s,
Vinicius AC

Busca soma num conjunto ( Cormen Exercício 2.3.7 (Outra implementação)

Implementação que usa dois índices para percorrer o arranjo ordenado. Um índice percorre o arranho em ordem crescente e o outro em ordem decrescente. Os pares com a soma desejada vão sendo armazenados até que os índices se cruzem.

Caso existam pares adequados, estes serão retornados num array de pares(array com dois elementos(uma imitação de tupla(vou dormir :)))). Fornece também a quantidade de pares encontrados.

Cormen Exerc�cio 2.3.7 - Verifica se existe ao menos dois elementos cuja soma é S (v.2)

Cormen Exercício 2.3.7 – Verifica se existem elementos cuja soma é S (v.2) (mude de doc para .rb ou .rtf qdo for abrir)

Busca soma num conjunto ( Cormen Exercício 2.3.7

Só por causa de Maurício, vou copiar o enunciado. O coitado deve tá sofrendo muito no IMPA com blibliotecas gigantes e firefox’s velhos (a propósito, não me odeie por isto, mas…. parabéns pelo dez, fiquei feliz em saber). Bom…. chega de papo furado.

2.3-7 – Descreva um algoritmo de tempo O (n lg n) que, dado um conjunto S de n inteiros e outro inteiro x, determine se existem ou não dois elementos em S cuja soma seja exatamente x.

Cormen Exerc�cio 2.3.7 - Verifica se existe ao menos dois elementos cuja soma é X (versão com erros)

Versão corrigida com a ajuda dos comentários de Mauricio (comento logo abaixo)

Cormen Exerc�cio 2.3.7 - Verifica se existe ao menos dois elementos cuja soma é S

Respostas aos comentários de Mauricio

(Parte 1 do comentário) Vc está certo. Foi pq antes eu tava colocando um s2 = GeraS2(s1).sort! porque o merge precisa de dois arrays ordenados. Aí tirei o .sort! e deixei o (n log n). Realmente, deveria ordenar no GeraS2, como estou fazendo agora.

(Parte 2 do comentário) Vc tb está certo. (droga) 🙂
Teoricamente não precisa de nenhum uniq, já que as entradas devem ser conjuntos de números, não arranjos.

(Parte 3 do comentário)
“3) A descrição do título faz ele parecer … números. É isso?” >> Essa o enunciado respondeu.
(continuando … )
Vou *tentar* implementar do jeito que vc sugeriu(opção dois ponteiros). Realmente é bem mais simples. Vou fazer de forma que verifique num *arranjo*, se existe a soma procurada, quantas vezes ela ocorre e através de que elementos. (vai ser o próximo POST do blog)

(Parte 4 do comentário)
Interessante mesmo, porque toda vez que coloquei antes índices de arrays fora da faixa nos loops deu erro. Também tava com muito sono, quando fiz. 🙂
O resultado de uma análise sem tanto sono é:
arr[x] == nil , para todo x > arr.length-1 (olha eu aprendendo ruby :))
então a última comparação tava dando sempre false, por isso não prejudicava o resultado. Mas vou consertar assim mesmo, claro.
Eu verifico length >= 2 pra saber se tem dois ou mais elementos repetidos. Se sim, existe a soma procurada.

Cormen Exercício 2.3.7 – Verifica se existe ao menos dois elementos cuja soma é S (mude de doc para rtf ou rb qdo for abrir)

Merge-Sort ( Cormen Exercício 2.3.2)

Cormen Exerccio 2.3.2

Selection-Sort ( Cormen Exercício 2.2.2 )

Selection-Sort ( Cormen Exerc�cio 2.2.2 )

Cormen Merge-Sort

Merge-Sort com Sentinelas ( Cormen )

Merge-Sort com Sentinelas ( Cormen Exerc�cio)

Merge-Sort (Cormen Exercício 2.3.1)

Merge-Sort (Cormen Exerc�cio 2.3.1)

:(P