Re: [obm-l] Um Algoritmo Legal
Olá Paulo, O melhor algoritmo que se pode obter para esse problema é O(NxP), já que se gasta isso só para ler a matriz e procurar a minhoca (cuja posição inicial não é dada diretamente). Dessa forma descreverei um algoritmo com tal complexidade. Podemos visualizar o tabuleiro como um grafo onde há um nó para cada casa com valor 1 ou 2. Há arestas entre dois nós se e somente se um nó é adjacente ao outro, o que significa que podemos alcançar um a partir do outro por um único movimento da minhoca. Temos então um problema de caminho mínimo em grafo não direcionado com arestas de peso 1. Podemos então usar uma busca em largura que, em um grafo, o tempo é O(n+m), onde n é o número de nós e m o número de arestas. Como n é O(NxP) e m é (8n)/2, portanto tb O(NxP), temos que a busca em largura funciona em O(NxP). Como funciona? Marcamos todos os nós como não visitados, exceto onde está a minhoca, cuja distância a ela mesma é zero: .#.#.#.#.#.###..##..###.0.#..#...##...#..#### : casa com brasa . casa não visitada Número : distância à minhoca Colocamos a posição inicial em uma lista L . Repetimos então, até visitarmos uma casa da borda, os seguintes passos: início Se a lista L é vazia, termina o programa sem solução Para cada elemento p da lista L: Para cada vizinho f de p não brasa e não visitado Marque f com1 maiso valor de p Coloque f em uma nova lista NL Substitua a lista L pela nova lista NL fim Se terminarmos alcançando uma casa da borda, o valor dessa casa será a solução. Por exemplo: Na primeira execução teremos: .#.#.#.#.#.###.1##..###101#..#...##111#..### Nasegunda execução teremos: .#2#2#.#.#.###21##2.###...2101#..#...##1112...#...222### E o programa terminará com a solução 2. Um abraço Vinicius Fortuna - Original Message - From: "Paulo Santa Rita" [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, July 04, 2002 5:10 PM Subject: [obm-l] Um Algoritmo Legal Ola Pessoal, Segue abaixo a traducao de um problema de computacao que recebi de outra lista e que achei interessante e digno de figurar nesta nostra lista OBM-L. O Algoritmo e de IA. Uma minhoca esta em uma celula de um labirinto quadriculado NxP ( N linhas, P colunas ). Ela almeja sair do labirinto. Todavia, sabe-se que nalgumas celulas ha brasa, noutras, terra. A minhoca se movimenta como o rei em um tabuleiro de xadrex. Os dados de entrada sao : N ,P e LAB(N,P). LAB(N,P) uma matriz da forma : 0 (zero) - casa com brasa 1 (um) - casa com terra 2 (dois) - a minhoca Exemplo : 101010101010 001100110001 21011011 10011101 1000 O programa ( function ) deve devolver : 1) 0 ( zero ) se nao houver um caminho de saida 2) N ( numero inteiro positivo ) se houver. Neste caso N e o menor numero de passos que a minhoca deve dar para sair do labirinto sem se queimar. O programa pode estar em qualquer linguagem padrao ou em pseudo-codigo. OBS : O tempo de resposta ( inteligencia do algoritmo ) sera o principal fator na classifucacao final dos algoritmos. Um Abraco a Todos Paulo Santa Rita 5,1709,040702
Re: [obm-l] Um Algoritmo Legal
Ola Duda, Tudo Legal ? A sua solucao e um otimo PRANAYAMA. Todavia, antes do otimo PRANAYAMA e necessario que se faca corretamente o ASANA ... Quero dizer que quanto voce diz : Construa uma outra matriz X NxP com um 1 na mesma posição onde a minhoca está e 0 em todas as outras posições, e uma matriz Y NxP toda zerada. Voce esta implicitamente pressupondo que a posicao da minhoca e um dos dados de entrada, o que nao esta correto. Em verdade, na lista italiana onde o problema foi originalmente proposto, o enfoque era justamente descobrir uma forma diferente e inteligente de encontrar a minhoca, pois partindo-se da posicao dela ha algoritmos inteligentes e otimos de se encontrar o menor caminho de saida. Assim, a parte de maior interesse e justamente o que voce nao fez : Encontre uma forma inteligente - tao rapida quanto possivel - de encontrar a posicao inicial da minhoca. A imensa maioria das solucoes usavam grafos e pesquisa em largura, dando pouca atencao ao problema de se encontrar a posicao da minhoca. Era previsivel. Todavia, o autor do problema escreve claramente : O algoritmo e de IA. Pelo pouco que conheco de IA, nao ha uma unica padronizacao nesta area ... vigoram aqui a criatividade e a imaginacao. Essa area e a Teoria da Computacao sao realmente bonitas e acredito que devem despertar o interesse de qualquer Matematico. Um abraco Paulo Santa Rita 6,1239,050702 From: Eduardo Casagrande Stabel [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] Um Algoritmo Legal Date: Thu, 4 Jul 2002 19:57:14 -0300 Oi Paulo, talvez não seja o melhor algoritmo, mas uma idéia simples é a seguinte: * Construa uma outra matriz X NxP com um 1 na mesma posição onde a minhoca está e 0 em todas as outras posições, e uma matriz Y NxP toda zerada. INICIO Para cada 1 presente na matriz X verifique na vizinhança dos elementos de LAB onde existe 1 e marque esses elementos na matriz Y (NxP). (A matriz Y marca todos os movimentos possíveis, sem morte, da minhoca nesta rodada) Acrescente à X os elementos de Y que são 1 e que em X eram 0. Se as matrizes X e Y forem iguais o programa terminha e devolve 0. Se a matriz X tiver algum elemento em sua borda igual a 1 então o programa termina e devolve o número de vezes que executou INICIO. Zere a matriz Y e repita o procedimento desde INICIO. * Por que o programa funciona? No caso de Y e X serem iguais, é claro que todo movimento a partir das casas com 1 em X só levam a casas que já eram 1 em X, portanto não se pode fugir das casas de X, e portanto se está preso no labirinto. No caso de haver uma saída do labirinto, na vez K que passamos em INICIO Y mostra todas as possibilidades de a minhoca estar após o K movimentos, TODAS as possibilidades, inclusive os K primeiros movimentos do caminho ideal (que faz sair do labirinto na quantidade mínima de movimentos). Segue que se for possível sair do labirinto em K movimentos, na K-ésima vez que passamos por INICIO a matriz vai incluir um 1 na borda. Está bom? Eduardo Casagrande Stabel. Porto Alegre, RS. From: Paulo Santa Rita [EMAIL PROTECTED] Ola Pessoal, Segue abaixo a traducao de um problema de computacao que recebi de outra lista e que achei interessante e digno de figurar nesta nostra lista OBM-L. O Algoritmo e de IA. Uma minhoca esta em uma celula de um labirinto quadriculado NxP ( N linhas, P colunas ). Ela almeja sair do labirinto. Todavia, sabe-se que nalgumas celulas ha brasa, noutras, terra. A minhoca se movimenta como o rei em um tabuleiro de xadrex. Os dados de entrada sao : N ,P e LAB(N,P). LAB(N,P) uma matriz da forma : 0 (zero) - casa com brasa 1 (um) - casa com terra 2 (dois) - a minhoca Exemplo : 101010101010 001100110001 21011011 10011101 1000 O programa ( function ) deve devolver : 1) 0 ( zero ) se nao houver um caminho de saida 2) N ( numero inteiro positivo ) se houver. Neste caso N e o menor numero de passos que a minhoca deve dar para sair do labirinto sem se queimar. O programa pode estar em qualquer linguagem padrao ou em pseudo-codigo. OBS : O tempo de resposta ( inteligencia do algoritmo ) sera o principal fator na classifucacao final dos algoritmos. Um Abraco a Todos Paulo Santa Rita 5,1709,040702 = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED]
Re: [obm-l] Re: [obm-l] Racionalização
Ah,essa historia de poder usar o fato (a+b)(a-b)=(a^2-b^2) vale sim.A ideia e racionalizar um por vez. E essa de radical duplo,voce precisa de novas regras para fazer isso. Fui claro? [],Peterdirichlet --- [EMAIL PROTECTED] escreveu: -- Mensagem original -- --- [EMAIL PROTECTED] escreveu: Estava resolvendo algumas questões do selecionados, e me deparei com algumas dúvidas de teoria. *Como faço para racionalizar denominadores com mais de 3 raízes ? Exemplo simples : 1/[sqrt(2) + sqrt(3) + sqrt(5)] *Como faço para racionalizar denominadores com mais de uma raiz , do tipo : 1/[raiz4(2) + 1 ] Será que a relação 1/[raiz n (a^p)] = raiz n (a^p - 1)/raiz n (a^p - 1) é válida ? *A relação do radical duplo , serve para raízes que não sejam quadradas ? Ex: raiz 5 [2 + raiz 3(3)] Obrigado. Pelo que eu saiba,a maioria das questoes de racionalizaçao se relaciona com o fato de que os denominadores sao algebricos(RAIZES DE EQUACOES POLINOMIAIS DE COEFICIENTES INTEIROS). Vou exemplificar:2^1/2+5^1/2=x.Veja que x^2=7+2*(10)^1/2,e (x^2-7)^2=40, x^4-14*x^2+9=0.Assim sendo,x(x^3-14*x)=-9 Logo x^3-14*x e racionalizante de x. Te mais!Peter Gustav = Obrigado pela correção , mais eu estou com dúvidas com racionalização de denominadores ,foi o que eu exemplifiquei logo na primeira dúvida que eu tive. será que você poderia me ajudar , ou alguém da lista , eu queria saber , se eu posso fazer uma coisa tipo isso . 1/[sqrt(2) + sqrt(3) + sqrt(5)]= 1/[sqrt(2) + sqrt(3) + sqrt(5)]x [sqrt(2) - sqrt(3) - sqrt(5)]/[sqrt(2) - sqrt(3) - sqrt(5)] Será que me inteudeu ? E queria saber também , se a relação do radical duplo , vale para raízes que não sejam quadradas?? Agradeço qualquer ajuda . Abraço. Rick. |-=Rick-C.R.B.=- | |ICQ 124805654 | |e-mail [EMAIL PROTECTED] | -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = ___ Yahoo! Encontros O lugar certo para encontrar a sua alma gêmea. http://br.encontros.yahoo.com/ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Racionalização
E essa de radical duplo,voce precisa de novas regras para fazer isso. Fui claro? = Foi sim peter , me ajudo bastante , muito obrigado . Mais já tentei de tudo quanto foi forma chegar a essas novas regras ... Como faço para obtê-las ? Se não fosse tomar muito seu tempo , poderia me ajudar ? Um abraço! Rick. |-=Rick-C.R.B.=- | |ICQ 124805654 | |e-mail [EMAIL PROTECTED] | -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] dois problemas
Sauda, c~oes,
Não verifiquei mas considero o problema 1
resolvido. Obrigado.
Quanto ao 2o, como ninguém se manifestou
e já desconfiado desde o começo, enviei-o
pro prof. Rousseau. Vejam sua resposta:
===
Dear Luis:
I just sent a solution of the Knuth problem via telescoping sums.
As for the other question, I would be exceedingly surprised if
the series in question has closed form sum. Of course, one can
re-express the series sum as an integral; a quick calculation gives
\int_0^1 x^{x+1} dx,
and I am confident that one prove (using the Risch algorithm) that
x^{x+1} has no antiderivative in elementary terms. While this
doesn't completely settle the issue, it comes close.
===
Para registrar, o problema 2 era
2) Calcule S = 1 / (1+n)^n =
= 1 + 1/2 + 1/3^2 + 1/4^3 +
Agora uma pergunta: alguém conhece esse algoritmo
de Risch? Nunca ouvi falar disso. E então aquela outra
soma que apareceu por aqui - S = \sum 1 / n^n -
recentemente deve ter o mesmo tratamento e conclusão:
nada de forma fechada.
[]'s
Luis
-Mensagem Original-
De: Johann Dirichlet [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: quarta-feira, 3 de julho de 2002 14:18
Assunto: Re: [obm-l] dois problemas
Este problema 1 ja e famoso.Eu resolvo com
trigonometria.Seja x=anguloCQT.SLS no QCT,
2*sen 60=TQ*sen .No PAT,PT=2/cos x.Pela
equilateralidade,tg x=sen 60.E como
x=anguloPTA(prove!),PT e facil de ser calculado e
vale 7^1/2.Com isso voce finaliza a questao.
Te mais
--- Luis Lopes [EMAIL PROTECTED] escreveu:
Sauda,c~oes,
Acabo de receber estes dois problemas
por fax. Alguém saberia resolvê-los?
1) No triângulo ABC desenhado abaixo,
A=90, C=60,AC=4.
B
PQ
ATC
T é ponto médio de AC
O triângulo PQT é equilátero. Calcule a área
do círculo circunscrito ao triângulo PQT.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] trabalho
Oi Pessoal! Trabalho num site tirando dúvidas de matemática das pessoas que pagam por esse serviço. Para quem responde as dúvidas dessa lista não é nenhum serviço muito difícil. Infelizmente vou ter que me desligar desse trabalho e queria saber se tem alguém da lista que estaria interessado em ficar no meu lugar. Se alguém estiver interessado, por favor escreva diretamente para mim para eu explicar exatamente como funciona, qual o site, pagamento, etc. Um abraço, Rafael. = Rafael Werneck Cinoto ICQ# 107011599 [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.rwcinoto.hpg.com.br/ __ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Algoritmo de Risch
Luis,
Entre em http://mathworld.wolfram.com/ e procure por risch. A definição é a
mínima, mas a bibliografia indicada talvez ajude.
JF
-Mensagem Original-
De: Luis Lopes [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Sexta-feira, 5 de Julho de 2002 15:44
Assunto: Re: [obm-l] dois problemas
Sauda, c~oes,
Não verifiquei mas considero o problema 1
resolvido. Obrigado.
Quanto ao 2o, como ninguém se manifestou
e já desconfiado desde o começo, enviei-o
pro prof. Rousseau. Vejam sua resposta:
===
Dear Luis:
I just sent a solution of the Knuth problem via telescoping sums.
As for the other question, I would be exceedingly surprised if
the series in question has closed form sum. Of course, one can
re-express the series sum as an integral; a quick calculation gives
\int_0^1 x^{x+1} dx,
and I am confident that one prove (using the Risch algorithm) that
x^{x+1} has no antiderivative in elementary terms. While this
doesn't completely settle the issue, it comes close.
===
Para registrar, o problema 2 era
2) Calcule S = 1 / (1+n)^n =
= 1 + 1/2 + 1/3^2 + 1/4^3 +
Agora uma pergunta: alguém conhece esse algoritmo
de Risch? Nunca ouvi falar disso. E então aquela outra
soma que apareceu por aqui - S = \sum 1 / n^n -
recentemente deve ter o mesmo tratamento e conclusão:
nada de forma fechada.
[]'s
Luis
-Mensagem Original-
De: Johann Dirichlet [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: quarta-feira, 3 de julho de 2002 14:18
Assunto: Re: [obm-l] dois problemas
Este problema 1 ja e famoso.Eu resolvo com
trigonometria.Seja x=anguloCQT.SLS no QCT,
2*sen 60=TQ*sen .No PAT,PT=2/cos x.Pela
equilateralidade,tg x=sen 60.E como
x=anguloPTA(prove!),PT e facil de ser calculado e
vale 7^1/2.Com isso voce finaliza a questao.
Te mais
--- Luis Lopes [EMAIL PROTECTED] escreveu:
Sauda,c~oes,
Acabo de receber estes dois problemas
por fax. Alguém saberia resolvê-los?
1) No triângulo ABC desenhado abaixo,
A=90, C=60,AC=4.
B
PQ
ATC
T é ponto médio de AC
O triângulo PQT é equilátero. Calcule a área
do círculo circunscrito ao triângulo PQT.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Risch algorithm
Sauda, c~oes, Acabo de receber a seguinte resposta do prof. Rousseau: === Dear Luis: The work by Risch in question dates from 1969 (Trans. AMS 139 (1969), 167-189 and Bull. AMS 76 (1970), 605-608). What little I know about the subject comes from a a Monthly article by Rosenlicht (Integration in Finite Terms, AMM 79 (1972), 964-972). My belief (perhaps wrong) is that the integration routines of Maple and Mathematica basically implement some form of the Risch algorithm - which, given a function in elementary form (computable by a finite number steps from algebraic, exponential, logarithmic, trigonometric functions) decides in a finite number of steps whether or nor the antiderivative is elementary. Of course, Maple goes beyond this, so it can also represent certain antiderivatives in terms of higher transcendental functions (e.g. erf(x)). But if I give Maple an indefinite integral of an elementary function and it gives no result, I take it to mean that there is no such function in elementary terms. Perhaps I am giving Maple more credit than it deserves, but that is my assumption. Now definite integrals and sums of infinite series are a whole new ball game. In any case, I would be interested in learning what you find out about this series. Have a good weekend. Cheers, Cecil === []'s Luís = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
RES: [obm-l] trabalho
Title: RES: [obm-l] trabalho Olá, Rafael! Vc poderia me passar os detalhes a respeito? [], Sérgio - Mensagem original - De: Rafael WC [SMTP:[EMAIL PROTECTED]] Enviada em: sexta-feira, 5 de julho de 2002 16:30 Para: OBM Assunto: [obm-l] trabalho Oi Pessoal! Trabalho num site tirando dúvidas de matemática das pessoas que pagam por esse serviço. Para quem responde as dúvidas dessa lista não é nenhum serviço muito difícil. Infelizmente vou ter que me desligar desse trabalho e queria saber se tem alguém da lista que estaria interessado em ficar no meu lugar. Se alguém estiver interessado, por favor escreva diretamente para mim para eu explicar exatamente como funciona, qual o site, pagamento, etc. Um abraço, Rafael. = Rafael Werneck Cinoto ICQ# 107011599 [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.rwcinoto.hpg.com.br/ __ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Geo Plana..
Laurito, Deduzi que, de acordo com o enunciado, sendo AM a metade de MB, então AM teria o comprimento igual a 1/2 * BM. Se imaginarmos um ponto X entre B e M que fizesse o segmento BX igual à metade de XA, teríamos uma outra reta (CX) que dividiria o ângulo C em 15 graus e outro em 30 graus, assim como CM faz ao ângulo C. Acertei? Alexandre - Original Message - From: Laurito Alves [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, July 04, 2002 4:03 PM Subject: Re: [obm-l] Geo Plana.. Quer ter seu próprio endereço na Internet? Garanta já o seu e ainda ganhe cinco e-mails personalizados. DomíniosBOL - http://dominios.bol.com.br Alexandre, Por que voce afirma que: o segmento CM trisecciona o lado BA em três partes iguais. Sendo assim, o ângulo C também é triseccionado em três partes iguais. Isso não tornaria possível a resolução do problema da trissecção do angulo ? Laurito _ Join the world's largest e-mail service with MSN Hotmail. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] dois problemas
Caro Luis: O seu problema 1 so tem solucao se M coincide com A. Neste caso, se BC = a, o raio da circunferencia circunscrita ao triangulo ATN eh a/4. -- From: Luis Lopes [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] dois problemas Date: Wed, Jul 3, 2002, 12:20 PM Sauda,c~oes, Acabo de receber estes dois problemas por fax. Alguém saberia resolvê-los? 1) No triângulo ABC desenhado abaixo, A=90, B=60. B MN ATC T é ponto médio de AC O triângulo MNT é equilátero. Calcule a área do círculo circunscrito ao triângulo MNT. 2) Calcule S = 1 / (1+n)^n = = 1 + 1/2 + 1/3^2 + 1/4^3 + []'s Luís = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] RE!:Re: [obm-l] Geo Plana..
Na verdade, o que você esta errando , não é bem o modo como o segmento esta cortando o outro lado. Está errado em dizer que o angulo também e dividido em três partes iguais , isto é ERRADO... Vou tentar provar isso algebricamente aqui em casa , e mando para a lista assim que tiver tempo. Abraço para o triseccionado Alexandre! Rick. |-=Rick-C.R.B.=- | |ICQ 124805654 | |e-mail [EMAIL PROTECTED] | -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
