Marathoncode

Flávio Josephus foi um historiador judeu famoso do primeiro século, no momento da destruição do Segundo Templo. Durante a guerra judaico-romana, ele ficou preso em uma caverna com um grupo de 40 soldados cercados pelos romanos. A lenda diz que eles preferia o suicídio do que serem capturados então os judeus decidiram formar um círculo e, procedendo à sua volta, para matar cada terceira pessoa restante até que ninguém foi deixado. Josephus, não queria de morrer, rapidamente encontrou o local seguro no círculo e assim permaneceu vivo.

Você pode tentar repetir o feito de Flávio no seguinte jogo:

http://www.cut-the-knot.org/recurrence/flavius.shtml

Uma maneira simples de resolver este problema é utilizar a estrutura de dados fila e realizar uma simulação para descobrir qual é a posição do último a morrer no círculo formado.

Resultado

input:

10 3

output:

morreu 3
morreu 6
morreu 9
morreu 2
morreu 7
morreu 1
morreu 8
morreu 5
morreu 10
Sobrevivente 4

Outra maneira é definir a estrutura recursiva do problema:
f(n,k) = sobrevivente em um círculo com n pessoas e salto k começando na pessoa 1.

f(n,k) = ( k-1 + f(n-1,k)) %n + 1
f(1,k) = 1

O valor k-1 é adicionado ao valor de f(n-1,k) justamente para ajustar o círculo na posição k-1, lembrando que f(n-1,k) devolve a posição com relação primeiro, e o valor +1 é para ajustar corretamente na posição k.

segunda-feira, 15 de julho de 2013

Dojo Operações com Árvore Binária de Busca

Operações implementadas:
Altura da árvore
Imprimir em ordem crescente
Inserir elemento na árvore
Menor elemento da árvore
Imprimir a árvore
Remover elemento da árvore
Juntar duas subárvores
Testar se a árvore está balanceada

Saída

0
1
2
3
4
5
6
(4 (2 (1 (0 NULO NULO) NULO) (3 NULO NULO)) (5 NULO (6 NULO NULO)))
(5 (2 (1 (0 NULO NULO) NULO) (3 NULO NULO)) (6 NULO NULO))

sexta-feira, 21 de junho de 2013

Dojo Python Lista Encadeada

No dia 21/06/2013, fizemos um dojo na linguagem Python. O desafio foi implementar uma lista encadeada usando a linguagem Python.
Código fonte

Teste Unitário

sexta-feira, 14 de junho de 2013

Frações contínuas II

Seja um fração contínua x = $[a_1;a_2,a_3,\ldots,a_n]$, chamamos de convergentes ou frações parciais a sequência de números racionais $c_0, c_1, c_2, \ldots$ dados por:

$c_0 = a_0, c_1 = a_0+\frac{1}{a_1}, c_2 = a_0 + \frac{1}{a_1+\frac{1}{a_2}}, \cdots, c_n = a_0 + \frac{1}{a_1+\frac{1}{\cdots +\frac{1}{a_n}}}, \cdots$ ,

ou seja, $c_0 = [a_0], c_1 = [a_0; a_1], c_2 = [a_0; a_1, a_2], \cdots, c_n = [a_0; a_1, a_2, \cdots, a_n], \cdots$

Retirado: http://pt.wikipedia.org/wiki/Fra%C3%A7%C3%A3o_cont%C3%ADnua

Vamos denotar cada $c_i por \dfrac{p_i}{q_i}$

$c_0$ = $a_0$. Logo, $p_0 = a_0$ e $q_0 = 1$

$c_1$ = $a_0 + \dfrac{1}{a_1}$ = $\dfrac{a_0a_1 + 1}{a_1}$. Logo, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$

$c_2$ = $a_0 + \cfrac{1}{ a_1 + \cfrac{1}{a_2}}$ = $\displaystyle \dfrac{a_0a_1a_2 + a_2 + a_0}{a_1a_2 + 1}$ =
$\dfrac{a_2(a_0a_1 + 1) + a_0}{a_1a_2 + 1}$ = $\dfrac{a_2p_1 + p_0}{q_1a_2 + q_0}$

Teorema: Seja $c_i = \dfrac{p_i}{q_i}$ a i-ésima fração parcial da fração contínua $[a_0,a_1,\ldots,a_n]$. Então o numerador $p_i$ e o denominador $q_i$ de $c_i$ satisfazem as seguintes relações: $p_i = a_ip_{i-1} + p_{i-2}$, $q_i = a_iq_{i-1} + q_{i-2}$, para i=2,3,$\ldots$,n sendo que $p_0 = a_0$, $q_0=1$, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$

1/1
1.000000000000000000
3/2
1.500000000000000000
7/5
1.399999999999999911
17/12
1.416666666666666741
41/29
1.413793103448275801
99/70
1.414285714285714368
239/169
1.414201183431952558
577/408
1.414215686274509887
1393/985
1.414213197969543145
3363/2378
1.414213624894869570
8119/5741
1.414213551646054778
19601/13860
1.414213564213564256
47321/33461
1.414213562057320406
114243/80782
1.414213562427273363
275807/195025
1.414213562363799470
665857/470832
1.414213562374689870
1607521/1136689
1.414213562372821364
3880899/2744210
1.414213562373141997
9369319/6625109
1.414213562373086930
22619537/15994428
1.414213562373096478
54608393/38613965
1.414213562373094701
131836323/93222358
1.414213562373095145
318281039/225058681
1.414213562373095145
768398401/543339720
1.414213562373095145
1855077841/1311738121
1.414213562373095145
4478554083/3166815962
1.414213562373095145
10812186007/7645370045
1.414213562373095145
26102926097/18457556052
1.414213562373095145
63018038201/44560482149
1.414213562373095145
152139002499/107578520350
1.414213562373095145
367296043199/259717522849
1.414213562373095145
886731088897/627013566048
1.414213562373095145
2140758220993/1513744654945
1.414213562373095145
5168247530883/3654502875938
1.414213562373095145
12477253282759/8822750406821
1.414213562373095145
30122754096401/21300003689580
1.414213562373095145
72722761475561/51422757785981
1.414213562373095145
175568277047523/124145519261542
1.414213562373095145
423859315570607/299713796309065
1.414213562373095145
1023286908188737/723573111879672
1.414213562373095145
2470433131948081/1746860020068409
1.414213562373095145
5964153172084899/4217293152016490
1.414213562373095145
14398739476117879/10181446324101389
1.414213562373095145
34761632124320657/24580185800219268
1.414213562373095145
83922003724759193/59341817924539925
1.414213562373095145
202605639573839043/143263821649299118
1.414213562373095145
489133282872437279/345869461223138161
1.414213562373095145
1180872205318713601/835002744095575440
1.414213562373095145
2850877693509864481/2015874949414289041
1.414213562373095145
6882627592338442563/4866752642924153522
1.414213562373095145

quinta-feira, 6 de junho de 2013

Frações contínuas

Uma fração contínua é uma expressão obtida a partir de um processo iterativo para representação de um número como a soma de sua parte inteira mais o inverso da sua parte fracionária. O processo termina quando o número não tem uma parte fracionária. Note que este processo pode ser utilizado para representação dos números racionais e irracionais.

Considere o seguinte exemplo:
$\dfrac{415}{93}$ = 4 + $\dfrac{43}{93}$ = 4 + $\dfrac{1}{\frac{93}{43}}$
$\dfrac{93}{43}$ = 2 + $\dfrac{7}{43}$ = 2 + $\dfrac{1}{\frac{43}{7}}$
$\dfrac{43}{7}$ = 6 + $\dfrac{1}{7}$ = 6 + $\dfrac{1}{\frac{7}{1}}$
$\dfrac{7}{1}$ = 7 + 0

Este processo produz a seguinte expressão:
$4+\cfrac{1}{2+\cfrac{1}{6+\cfrac{1}{7}}}$

Esta expressão pode ser abreviada usando a seguinte notação
[4;2,6,7]

Saída

[4;[2;[6;[7;]]]]

A representação usando frações contínuas tem várias propriedades desejáveis:

1. A representação usando frações contínuas para um número racional é finita e somente os números racionais tem representação finita. Usando a representação decimal, alguns números tem representação finita e outros são representados por dízimas periódicas. Por exemplo,
Representação decimal
$\dfrac{4}{27} $ = 0.148148148148….
Representação usando frações contínuas:
$\dfrac{4}{27} $ = [0;6,1,3]

Sobre os problemas da representação decimal leia:
0,999... OU “COMO COLOCAR UM BLOCO QUADRADO EM UM BURACO REDONDO”

O mesmo problema acontece na representação de números reais na base 2:
http://marathoncode.blogspot.com.br/2013/01/representacao-do-ponto-flutuante-em.html

2. A representação usando frações contínuas reduzidas, ou seja, com todos os numeradores iguais a 1, é sempre única.
3. A representação usando frações contínuas de números irracionais é única.
4. A representação usando frações contínuas de alguns números irracionais parece ser menos randômica que a representação decimal. Por exemplo,

Representação decimal $\sqrt{2}$ = 1,4142135623730950488016887242097...
Representação usando frações contínuas $\sqrt{2}$ = [1;2,2,2,…]

5. A representação usando frações contínuas pode ser usada para obter aproximações bastando interromper o processo a qualquer momento.

Considere o seguinte exemplo:

Note que as seguintes propriedades são válidas:
$(\sqrt{2}+1)(\sqrt{2}-1)=1$
$(\sqrt{2}+1) = \dfrac{1}{(\sqrt{2}-1)}$

A fração contínua de $\sqrt{2}$:

$\sqrt{2}$ = 1 + ($\sqrt{2}$-1) = 1 + $\dfrac{1}{\sqrt{2}-1}$
$(\sqrt{2}+1)$ = 2 + ($\sqrt{2}$-1) = 2 + $\dfrac{1}{\sqrt{2}-1}$

O processo repete-se indefinidamente. Logo,

$\sqrt{2}$ = [1;2,2,...]

Podemos usar essa ideia para encontrar uma aproximação para $\sqrt{2}$

Saída:

1.000000000000000000
1.500000000000000000
1.399999999999999911
1.416666666666666741
1.413793103448275801
1.414285714285714368
1.414201183431952558
1.414215686274509887
1.414213197969543145
1.414213624894869570
1.414213551646054778
1.414213564213564256
1.414213562057320406
1.414213562427273363
1.414213562363799470
1.414213562374689870
1.414213562372821364
1.414213562373141997
1.414213562373086930
1.414213562373096478
1.414213562373094923
1.414213562373095145
Numero de iteracoes: 21

Alguns exemplos de representação de números irracionais usando frações contínuas:

$\sqrt{19} = [4;2,1,3,1,2,8,2,1,3,1,2,8,…]$. O padrão repete-se com período 6.
e = [2;1,2,1,1,4,1,1,6,1,1,8,…]
$\pi$ = [3;7,15,1,292,1,1,1,2,1,3,1,…].

Fonte:
http://en.wikipedia.org/wiki/Continued_fraction
http://pt.wikipedia.org/wiki/Fra%C3%A7%C3%A3o_cont%C3%ADnua

Leia também:
O uso das Frações Contínuas como tema articulador no Ensino Médio

Quem quiser se aprofundar:
http://www.sbm.org.br/docs/coloquios/SE-1.06.pdf

Você gostou da postagem? Deixe seu comentário!!

quinta-feira, 9 de maio de 2013

Torneio de Boxe

Um torneio eliminatório de boxe foi organizada. Temos 114 participantes e por isso temos 57 partidas na primeira rodada do torneio. Na segunda rodada, os 57 lutadores restantes foram emparelhado, resultando em 28 jogos, um lutador ganhou por WO (isto é, não tem que lutar nessa rodada). Os 29 lutadores restantes foram então emparelhado, e assim por diante.

(a) Quantos jogos ao todo foram necessários para determinar um vencedor do torneio?

(b) Quantos jogos seria necessário se n pessoas participaram no torneio (onde n representa um inteiro fixo, mas não especificado número)?

Vamos definir uma função F(n) que devolve o número de lutas necessárias para descobrir o vencedor do torneio com n participantes:

F(n) : número de lutas necessárias para descobrir o vencedor do torneio com n participantes.

Observe que quando o n é par então podemos realizar n/2 lutas e restaram n/2 lutadores. Quando n é impar, então podemos realizar n/2 lutas e restaram n/2 + 1 lutadores. Logo, podemos obter a seguinte recursão:

$$F(1) = 0$$
$$F(n) =
\begin{cases}
F(\frac{n}{2}) + \frac{n}{2} & \mbox{se n é par}\\
F(\frac{n}{2}+1) + \frac{n}{2} & \mbox{se n é ímpar}\\
\end{cases}
$$

Testando alguns casos da recursão acima, podemos notar que F(n) = n-1, uma vez que, cada luta elimina um lutador e precisamos eliminar n-1 lutadores para encontrar o vencedor do torneio.

Podemos provar este fato resolvendo a recorrência acima:

Suponha n = $2^k$. Logo, podemos escrever a recorrência da seguinte maneira: $$F(2^0) = 0$$
$$F(2^k) = F(2^{k-1}) + 2^{k-1}$$
Utilizando o método da substituição: $$ F(2^k) = F(2^{k-1}) + 2^{k-1} \\ F(2^{k-1}) = F(2^{k-2}) + 2^{k-2} \\ F(2^{k-2}) = F(2^{k-3}) + 2^{k-3} \\ \vdots \\ F(2^{1}) = F(2^{0}) + 2^{0} \\ $$ Somando tudo temos: $$ F(2^k) = F(2^{0}) + 2^{0} + 2^{1} + 2^{2} + \ldots + 2^{k-1} \\ F(2^k) = 2^{k} - 1\\ $$ Desfazendo a substituição, temos: $$ F(n) = n - 1\\ $$

quarta-feira, 8 de maio de 2013

Desafio Semanal

Professor Ricardo tem n chips supostamente idênticos que, em princípio, são capazes de testar uns aos outros. Um testador do professor acomoda dois chips ao mesmo tempo. Quando os chips são carregados, cada chip testa o outro e relata se é bom ou ruim. Um bom chip de sempre relata com precisão se o outro chip é bom ou ruim, mas a resposta de um mau chip não pode ser confiável. Assim, os quatro possíveis resultados de um teste são como se segue:

Chip A	Chip B	Conclusão
B é bom	A é bom	ambos são bons, ou ambos são ruins
B é bom	A é ruim	pelo menos um é ruim
B é ruim	A é bom	pelo menos um é ruim
B é ruim	A é ruim	pelo menos um é ruim

a. Mostre que, se mais de n / 2 chips são ruins, o professor pode não determina necessariamente quem são os bons chips usando qualquer estratégia com base neste tipo de teste emparelhado. Suponha que os maus chips podem conspirar para enganar o professor.

b. Considere o problema de encontrar um único chip de bom entre n chips, supondo que o mais que n / 2 dos chips são bons. Mostre que ⎣ n / 2 ⎦ testes de pares são suficientes para reduzir o problema para aproximadamente a metade do tamanho.

c. Mostre que os bons chips podem ser identificados com Θ (n) testes emparelhados, assumindo que mais que n / 2 dos chips são bons. Dê e resolva a recorrência que descreve o número de testes.

segunda-feira, 29 de abril de 2013

Problemas legais resolvidos usando recursão

Not so mobile

http://uva.onlinejudge.org/external/8/839.html

Chocolate

http://uva.onlinejudge.org/external/109/10970.html

Investimento em ações

http://br.spoj.com/problems/ACOES1MG/

Coconut

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=557%7C

Brick Wall Patterns

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=841

Cola

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2091

Tri Triling

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1859

The Coco-Cola Store

http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=226&page=show_problem&problem=2999

Moliu Number Generator

http://uva.onlinejudge.org/external/115/11567.html

segunda-feira, 22 de abril de 2013

Funções recursivas

O entendimento e a utilização de funções recursivas é uma grande arma para resolver vários tipos de problemas. Entre os problemas que são mais fáceis serem resolvidos usando métodos recursivos estão os problemas de contagem. Em alguns casos, o próprio processo que precisamos contar é descrito de maneira recursiva.

Em geral, os algoritmos recursivos são mais fáceis de serem entendidos e mais fáceis de provar a corretude dos mesmos.

Considere o seguinte problema Cola:

A cada três garrafas devolvidas vazias de Choco Cola, ganhe um nova garrafa de Choco Cola.

Se você comprar N garrafas de Choco Cola na loja, quantos refrigerantes você vai conseguir realizando todas as trocas possíveis?

Seja T(n) o número de refrigerante que você pode conseguir realizando todas as trocas possíveis.

Recorrência dada pelo professor Fábio Carlos.

$$T(n) = \begin{cases}n & n < 3 \\ 3 + T(n-3+1) & \text{caso contrário,} \end{cases}$$

Observe que a cada três refrigerantes, ele ganha um novo refrigerante. Teste

Podemos acelerar a recorrência acima da seguinte maneira:

$$T(n) = \begin{cases}n & n < 3 \\ 3* \lfloor n/3 \rfloor + T(n - 3 \lfloor n/3 \rfloor + \lfloor n/3 \rfloor) & \text{caso contrário,} \end{cases}$$

Esta solução é equivalente a solução dada pelo aluno Alexsandro Oliveira.

$$T(n) = \begin{cases}n & n < 3 \\ n - n \text{ mod } 3 + T(n \text{ mod } 3 + \lfloor n/3 \rfloor ) & \text{caso contrário,} \end{cases}$$

Esta outra recorrência também resolve o mesmo problema:

$$T(n,m) = \begin{cases}n & n+m < 3 \\ n + T( \lfloor (n+m)/3 \rfloor , (n+m) \text{ mod } 3 ) & \text{caso contrário,} \end{cases}$$

segunda-feira, 26 de agosto de 2013

17 equations that changed the course of humanity http://www.thejournal.ie/equations-changed-course-of-humanity-764429-Jan2013/?utm_source=shortlink

segunda-feira, 5 de agosto de 2013