none
DESAFIO DE DICIONÁRIO EM C# RRS feed

  • Pergunta

  • Escrever um programa do tipo console application em que possamos pesquisar a posição em que uma determinada palavra se encontra em um dado dicionário.

    Para deixar as coisas mais divertidas, a única maneira de se interagir com este dicionário é através de um webservice no endereço: http://dicionario.com.br/dic/api/words/{posição}

    Sendo assim, uma chamada para:

    http://dicionario.com.br/dic/api/words/0 retorna “AARÃO”

    http://dicionario.com.br/dic/api/words/1 retorna “ABEL”

    http://dicionario.com.br/dic/api/words/1000 retorna “ABRANGEREIS”

    http://dicionario.com.br/dic/api/words/40000000000000 retorna 400 Bad Request

    É importante saber também que cada vez que você chama este webservice, morre um gatinho.

    Seu algoritmo não deve considerar o tamanho do dicionário mesmo se você o descubra por tentativa e erro. Isto se deve ao fato que você não sabe quando este dicionário vai mudar (aumentar ou diminuir) e seu algoritmo não pode quebrar por isso.

    Seu programa deve receber uma palavra como parâmetro de entrada e retornar a posição da palavra informada, alguma mensagem caso a palavra não exista e o número de gatinhos mortos.

    PREMISSAS DO PROJETO

    - ser escrito em c#, console application

    - utilizar c# 4.0 ou superior

    - solução no VS2012 ou superior

    - deve estar pronto para rodar apenas apertando F5 no Visual Studio e nada mais.


    sexta-feira, 28 de agosto de 2015 01:27

Respostas

  • Seu professor(a) é muito legal.... Vamos ser legais com ele também e deixar que voce resolva o desafio e matar o menor numero possiveis de gatos.

    Só algumas dicas:

    1- Busca sequencial voce vai matar muitos gatos. Por exemplo se a palavra for zebra, vc vai ter que começar no "AARÃO" e até chegar na Zebra, muitos gatos serao mortos.

    2- Como voce nao sabe qual é o numero da ultima palavra (e seu indice) fica um pouco complicado, pois saber qual é o meio do dicionario é essencial para aplicar uma busca binaria, pois esta exige que voce saiba qual é o meio da lista e funciona assim: pegue a palavra do meio da lista, e compare com a palavra alvo; verifique se ela é maior ou menor que sua palavra; se for maior vá para o meio da sublista superior e compare novamente e assim até achar... com isso voce mata somente log2 n, onde n é numero de itens da lista. Por exemplo, se a lista total tiver 10000 palavras, com esse metodo somente 14 gatos morreriam. Mas seu professor odeia gatos! Voce nao sabe e nem pode saber qual é o tamanho da lista.

    3- Como busca binaria nao é possivel, entao outro tipo de busca deve ser aplicada, e ela se chama busca exponencial e funciona assim: voce pega a primeira palavra e salta para o dobro: voce sai do 1 e vai para o 2. Verifica se a palavra do indice dois é maior ou menor (ou igual) qu o alvo.  se for menor va para o dobro, ou seja palava do indice 4 e vai indo em sequencia, 8, 16, 32.... quando vc achar uma palavra menor, voce volta para a metade da lista conhecida e começa a repetir a sequncia imaginando que o novo ponto de partida como 1...

    4- Voce pode usar o passeio aleatorio (random walk) e esse é o mais simples e com certeza vai matar bem menos gatos que o metodo sequencial (somente a metade da lista) e é assim: selecione um numero aletorio, veja qual é a palavra associada. é igual? bingo !!! somente um gato morreu. Nao... traga outro gato... sorteie outro numero e veja se acertou.. Faça isso de uma maneira a nao repetir numeros ja sorteados.

    Voce pode usar uma combinaçao de metodos, random walk com pesquisa binaria (creio que seja lá que voce vai matar menos gatos)

    Em todos os casos: denuncie seu professor(a) à sociedade protetora de animais. Mesmo que voce nao passe nessa materia ele sera preso e nunca mais vai porpor desafios como esse. :P

    Att


    William John Adam Trindade
    Analyste-programmeur
    ----------------------------------------------------------




    sexta-feira, 28 de agosto de 2015 16:34
    Moderador

Todas as Respostas

  • @Luciano Weber

    E trabalho de casa?

    Queres que alguem faca pra ti ?


    A flower cannot blossom without sunshine, and man cannot live without love.

    sexta-feira, 28 de agosto de 2015 15:12
    Moderador
  • Bom dia Luciano Weber,

    Tudo bem?

    Dentro do contexto publicado, qual seria a sua dúvida?

    Atenciosamente


    Marcos Roberto de Souza Junior

    Esse conteúdo e fornecido sem garantias de qualquer tipo, seja expressa ou implícita

    MSDN Community Support

    Por favor, lembre-se de Marcar como Resposta as respostas que resolveram o seu problema. Essa e uma maneira comum de reconhecer aqueles que o ajudaram e fazer com que seja mais fácil para os outros visitantes encontrarem a resolução mais tarde.

    sexta-feira, 28 de agosto de 2015 15:28
  • Seu professor(a) é muito legal.... Vamos ser legais com ele também e deixar que voce resolva o desafio e matar o menor numero possiveis de gatos.

    Só algumas dicas:

    1- Busca sequencial voce vai matar muitos gatos. Por exemplo se a palavra for zebra, vc vai ter que começar no "AARÃO" e até chegar na Zebra, muitos gatos serao mortos.

    2- Como voce nao sabe qual é o numero da ultima palavra (e seu indice) fica um pouco complicado, pois saber qual é o meio do dicionario é essencial para aplicar uma busca binaria, pois esta exige que voce saiba qual é o meio da lista e funciona assim: pegue a palavra do meio da lista, e compare com a palavra alvo; verifique se ela é maior ou menor que sua palavra; se for maior vá para o meio da sublista superior e compare novamente e assim até achar... com isso voce mata somente log2 n, onde n é numero de itens da lista. Por exemplo, se a lista total tiver 10000 palavras, com esse metodo somente 14 gatos morreriam. Mas seu professor odeia gatos! Voce nao sabe e nem pode saber qual é o tamanho da lista.

    3- Como busca binaria nao é possivel, entao outro tipo de busca deve ser aplicada, e ela se chama busca exponencial e funciona assim: voce pega a primeira palavra e salta para o dobro: voce sai do 1 e vai para o 2. Verifica se a palavra do indice dois é maior ou menor (ou igual) qu o alvo.  se for menor va para o dobro, ou seja palava do indice 4 e vai indo em sequencia, 8, 16, 32.... quando vc achar uma palavra menor, voce volta para a metade da lista conhecida e começa a repetir a sequncia imaginando que o novo ponto de partida como 1...

    4- Voce pode usar o passeio aleatorio (random walk) e esse é o mais simples e com certeza vai matar bem menos gatos que o metodo sequencial (somente a metade da lista) e é assim: selecione um numero aletorio, veja qual é a palavra associada. é igual? bingo !!! somente um gato morreu. Nao... traga outro gato... sorteie outro numero e veja se acertou.. Faça isso de uma maneira a nao repetir numeros ja sorteados.

    Voce pode usar uma combinaçao de metodos, random walk com pesquisa binaria (creio que seja lá que voce vai matar menos gatos)

    Em todos os casos: denuncie seu professor(a) à sociedade protetora de animais. Mesmo que voce nao passe nessa materia ele sera preso e nunca mais vai porpor desafios como esse. :P

    Att


    William John Adam Trindade
    Analyste-programmeur
    ----------------------------------------------------------




    sexta-feira, 28 de agosto de 2015 16:34
    Moderador

  • Em todos os casos: denuncie seu professor(a) à sociedade protetora de animais. Mesmo que voce nao passe nessa materia ele sera preso e nunca mais vai porpor desafios como esse. :P

    Att


    William John Adam Trindade
    Analyste-programmeur
    ----------------------------------------------------------




    A melhor resposta!


    (rs...)
    sexta-feira, 28 de agosto de 2015 18:42