Ajuda com algoritmo

Baixinho04 · 5 de março de 2010

Olá pessoal sou novo aqui, eu estou quebrando a cabeça com um problema da faculdade... que ainda não descobri uma forma de fazer.... eu sei java, mas a lógica para fazer esse problema não me veio ainda pela cabeça, gostaria de saber se alguém tem alguma luz para como fazer.

Desde já agradeço.

A história de Chapeuzinho Vermelho é bem conhecida de todas as crianças. O que pouca
gente sabe, no entanto, é que antes de atravessar o bosque com uma cesta de doces para

a vovozinha a pequena Chapeuzinho teve de ir buscar a cesta na confeitaria da vila. Infelizmente,

como a mãe de Chapeuzinho estava de dieta fazia um tempo, ela não lembrava

mais onde cava a confeitaria e apenas conseguia lembrar que somando os números das

casas (1, 2, 3, . . . ) do início da rua até a confeitaria e depois da confeitaria até o nal da

rua ambas as somas eram iguais. Como Chapeuzinho não tem a mínima vontade de fazer

contas (e ainda hoje há sérias dúvidas sobre seu verdadeiro estágio de alfabetização), a

família terceirizou você para determinar, para todos os comprimentos possíveis de rua, em

que número a confeitaria pode estar. Você sabe ao menos que as ruas sempre começam no

número 1.

davidalain · 5 de março de 2010

Aí um algoritmo em C que resolve o problema por força bruta.


#include <stdio.h>

int somaAte(int numCasa){
 int resultado = 0;
 int contador = 0;
 while(contador < numCasa - 1){
    resultado += ++contador;
 }
 return resultado;
}

int somaApartir(int numCasa,int somaAte){
 int contador = numCasa;
 int somaApartir = 0;
 while(somaApartir < somaAte){
    somaApartir += ++contador;
 }
 return (somaApartir == somaAte);
}


int main(){

    int numCasa;
    int quantidade = 0;
    int limiteTeste = 100000;

    for(numCasa = 2 ; numCasa < limiteTeste ; numCasa++){
        if(somaApartir(numCasa,somaAte(numCasa))){
            quantidade++;
            printf("Numero da casa: %d\n",numCasa);
        }
    }

    printf("\nQuantidade de casas que resolvem o problema: %d\nTestado ate o valor: %d\n",quantidade,limiteTeste);

    getch();
    return 0;   
}

Baixinho04 · 5 de março de 2010

entendi pus aqui e funcionou legal, mas eu não pus todo problema aqui no post, uma parte dele é que tem que por como limite 400MILHÕES e se eu por isso vai demorar MUITOOOOOO para compilar. Sabe alguma forma de melhorar? valeu

davidalain · 5 de março de 2010

entendi pus aqui e funcionou legal, mas eu não pus todo problema aqui no post, uma parte dele é que tem que por como limite 400MILHÕES e se eu por isso vai demorar MUITOOOOOO para compilar. Sabe alguma forma de melhorar? valeu

Na verdade não vai demorar muito para compilar, mas para executar.

porque esse algoritmo é de força bruta (tentativa e erro).

você já pensou em fazer uma 'modelagem' do problema e verificar as associações dos casos em que são o resultado.

Exemplo:

Se você sabe que em numCasa = 6, é uma resposta, você poderia associar a quantidade de termos com os valores de somaAte e somaApartir.

Nesse exemplo somaAte = 1 + 2 + 3 + 4 + 5 e

somaApartir = 7 + 8.

Verificando que somaAte tem 5 termos e somaApartir tem 2, para numCasa = 6, então verifica nos outros casos e tenta achar uma associação com os casos verdadeiros e pensa em uma formula pra calcular somente os casos verdadeiros.

Baixinho04 · 5 de março de 2010

Na verdade não vai demorar muito para compilar, mas para executar.
porque esse algoritmo é de força bruta (tentativa e erro).

você já pensou em fazer uma 'modelagem' do problema e verificar as associações dos casos em que são o resultado.

Exemplo:

Se você sabe que em numCasa = 6, é uma resposta, você poderia associar a quantidade de termos com os valores de somaAte e somaApartir.

Nesse exemplo somaAte = 1 + 2 + 3 + 4 + 5 e

somaApartir = 7 + 8.

Verificando que somaAte tem 5 termos e somaApartir tem 2, para numCasa = 6, então verifica nos outros casos e tenta achar uma associação com os casos verdadeiros e pensa em uma formula pra calcular somente os casos verdadeiros.

Concordo que é na execução... contudo eu ja pensei nisso e os valores iniciais e suas somas não apresentam nenhuma sequencia logica... o mais perto q pensei foi um somatorio de ambos lados retirando o valor que deseja que é a casa... mas não consegui elaborar uma formula para poder utilizar

davidalain · 6 de março de 2010

o mais perto q pensei foi um somatorio de ambos lados retirando o valor que deseja que é a casa... mas não consegui elaborar uma formula para poder utilizar

Se você reparar bem no código que eu fiz, ele soma os termos anteriores e soma o termos posteriores, sem somar o termo que é o número da casa.

Uma ideia para minimizar os tempo de execução é diminuir os casos de teste de forma que não seja necessário testar todas as possibilidades até que as somas sejam iguais ou a somaAte seja maior que a somaApartir. Pensa em limitar a quantidade de termos das somas através, pensando em uma relação onde há casos que nunca serão respostas, e elimina esses casos dos testes...

(Problema de otimização de algoritmo).

Esse problema é mais matemático que de implementação de algoritmo.

Baixinho04 · 7 de março de 2010

Se você reparar bem no código que eu fiz, ele soma os termos anteriores e soma o termos posteriores, sem somar o termo que é o número da casa.

concordo contudo na linha

 int limiteTeste = 100000;

eu teria que colocar:

 int limiteTeste = [B]400000000[/B];

POR OBRIGAÇÃO DO PROFESSOR QUE PEDIU para ver todas possibilidades até esse numero.

davidalain · 7 de março de 2010

concordo contudo na linha
 int limiteTeste = 100000;
eu teria que colocar:
 int limiteTeste = [B]400000000[/B];
POR OBRIGAÇÃO DO PROFESSOR QUE PEDIU para ver todas possibilidades até esse numero.

limiteTeste = 400000000;

é a solução do problema.

Mas para responder todos os casos o tempo de execução é muuuuuuiiito grande, então deixa rodando agora que quando chegar a hora da aula dele já deve ter terminado.

Baixinho04 · 7 de março de 2010

limiteTeste = 400000000;
é a solução do problema.

Mas para responder todos os casos o tempo de execução é muuuuuuiiito grande, então deixa rodando agora que quando chegar a hora da aula dele já deve ter terminado.

Não posso pois tenho que rodar na frente do professor e ele olha o código...

sendo que leva em média 5 semanas pelaos calculos a fiz para rodar tudo..

davidalain · 7 de março de 2010

Não posso pois tenho que rodar na frente do professor e ele olha o código...
sendo que leva em média 5 semanas pelaos calculos a fiz para rodar tudo..

Então tem que otimizar o código para diminuir os casos de teste, assim ele vai rodar mais rápido, e resolver em menos tempo.

Baixinho04 · 7 de março de 2010

Então tem que otimizar o código para diminuir os casos de teste, assim ele vai rodar mais rápido, e resolver em menos tempo.

é o que estou tentando fazer, eu to tentando pensar em fazer por soma de uma P.A de razão 1 e verificando a igualdade dos termos. Contudo ainda não deu certo.... xD

davidalain · 7 de março de 2010

é o que estou tentando fazer, eu to tentando pensar em fazer por soma de uma P.A de razão 1 e verificando a igualdade dos termos. Contudo ainda não deu certo.... xD

O código que eu fiz, faz uma soma de uma PA com razão 1.

Mas a otimização que eu estou falando é de verificar o número de termos em cada PA.

Exemplo:

Se na PA que é até numCasa tiver N termos então na PA que é a partir de numCasa deve-se somar até K.

Onde K é um valor em função de N, como:

K = N/3 ou

K = sqrt(N) ou

K = N/2 - sqrt(N), ou outra.

Assim você vai limitar a quantidade de testes e diminuir o tempo de execução.

Baixinho04 · 7 de março de 2010

O código que eu fiz, faz uma soma de uma PA com razão 1.
Mas a otimização que eu estou falando é de verificar o número de termos em cada PA.

Exemplo:

Se na PA que é até numCasa tiver N termos então na PA que é a partir de numCasa deve-se somar até K.

Onde K é um valor em função de N, como:

K = N/3 ou

K = sqrt(N) ou

K = N/2 - sqrt(N), ou outra.

Assim você vai limitar a quantidade de testes e diminuir o tempo de execução.

entendi... mas como ficaria o código? estou com uma "ideia" de lógica mas não consegui ainda por pro código

pensei tipo:

Uma linha de
1 ------------------------ X -------- N

Sendo 1 a primeira casa(obrigatório)

X a casa q desejo achar

N o total de casas

pensei em algo do tipo

a soma dos termos de 1 até X for igual a X até N daria um true e retornaria o X mas não consegui por no código isso... q q acha?

Goliathvv · 7 de março de 2010

Olá Baixinho04,

Problema interessante esse, mas há uma forma simples e eficaz de atacá-lo sem ter que testar todas as possibilidades. Acompanhe a minha ideia:

A minha ideia é percorrer a lista de casas apenas uma vez, a partir das pontas.

Eu parto do começo da rua e sei qual é o número da última casa, então eu poderia fazer o seguinte: vou ter duas variáveis, uma armazenando a soma do começo até a confeitaria(vou chamá-la de C) e outra armazenando a soma da fim até a confeitaria(vou chamá-la de F), e dois apontadores, um apontando para a primeira casa e outro apontando para a última.

No começo a variável C tem valor 1 e a variável F tem valor igual ao número da última casa. Sempre que caminhar pra frente eu somo a C o valor da casa atual, incremento o apontador do início(assim agora eu estarei apontando para a casa 2), e verifico se C é maior que F.

Se for, isso significa que eu ultrapassei o limite da variável C, então eu páro nessa casa e vou somando a partir da variável F, só que para trás, dessa forma decrementando o apontador de vinda a cada casa que passo. E continuo assim até que a variável F seja maior que a variável C, dessa forma eu vou ficar fazendo um ping-pong nas casas iniciais e nas finais, até que finalmente vou chegar na confeitaria.

Veja um exemplo para entender melhor (números acima são os apontadores de cada extremidade, infelizmente não consegui alinhar direito:wacko:):


1             8
1 2 3 4 5 6 7 8
C = 1
F = 8
Aqui temos o início

   2          8
1 2 3 4 5 6 7 8
C = 3
F = 8
Andei para a direita e incrementei o apontador

   3          8
1 2 3 4 5 6 7 8
C = 6
F = 8
Andei novamente para a direita, e incrementei o contador

      4        8 
 1 2 3 4 5 6 7 8
 C = 10
 F = 8
Atenção neste momento: C é maior que F, o que significa que eu andei demais para a direita, então chegou a hora de andar com o outro apontador para equilibrar as coisas.

        4     7
  1 2 3 4 5 6 7 8
  C = 10
  F = 15
Agora eu andei demais para a esquerda, então eu tenho que contrabalancear andando para a direita com o outro apontador.

           5   7
   1 2 3 4 5 6 7 8
   C = 15
   F = 15
Bingo! A soma deu igual. Mas uma dica: a condição de parada não é as somas serem iguais, mas sim a distância entre os apontadores ser de duas casas (7 - 5 = 2). Isso porque há o risco de as somas serem iguais em diversos casos.

Este algoritmo é bem eficiente pois ele só percorre a "lista"(não há uma lista exatamente, mas é como se houvesse) uma vez. Sua complexidade é O(n), o que significa em termos práticos que se você dobrar o número de casas, o tempo dobra, e não irá crescer para valores gigantescos. Aqui no meu notebook levei 9 segundos para encontrar o resultado com 400000000 casas.

Se você não entendeu eu posso explicar novamente. Se entendeu, tente implementar essa ideia e diga depois o resultado que você conseguiu.

Para você testar aí vão alguns casos:

Total de casas: 8

Confeitaria: 6

Total de casas: 49

Confeitaria: 35

Total de casas: 288

Confeitaria: 204

Total de casas: 1681

Confeitaria: 1189

Total de casas: 9800

Confeitaria: 6930

Total de casas: 57121

Confeitaria: 40391

Total de casas: 332928

Confeitaria: 235416

Abraços.

Baixinho04 · 8 de março de 2010

Só tem um problema eu fiz isso e deu um tempo muito grande... não seu 9 segundos. e não pode contar a casa da confeitaria... tipo

1 + 2 + 3 + 4 + 5 = 15
7 + 8 = 15

6 não está na conta

----------------------

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 = 91

15 + 16 + 17 + 18 + 19 + 20 = 105

o numero 14 não pode contar

não cosnegui fazer um código otimizado para não dar muito tempo pois continua rodando muito no laço... valeu

Goliathvv · 8 de março de 2010

Só tem um problema eu fiz isso e deu um tempo muito grande... não seu 9 segundos. e não pode contar a casa da confeitaria... tipo
não cosnegui fazer um código otimizado para não dar muito tempo pois continua rodando muito no laço... valeu

Opa, foi um equívoco meu. Fiz um método somaAte que esta incluindo o último valor, quando não deveria, já corrigi a lista no meu último post.

Aí segue o código que eu fiz para verificar a confeitaria para um dado valor, ele fica em loop infinito com valores menores ou iguais a dois(isso é fácil de corrigir, mas eu preferi admitir que ninguém vai usar este algoritmo para tais casos) e ainda dá pra otimizá-lo(tem como evitar o uso de long em alguns trechos, mas isso o tornaria um pouco mais complexo), mas no geral é bem simples, dá uma olhada:

    public static void calculaConfeitaria(long casas)
    {        
        long somaMenores = 1;
        long somaMaiores = casas;

        long menorCaminhado = 1;
        long maiorCaminhado = somaMaiores;

        while(maiorCaminhado - menorCaminhado != 2)
        {

            if(somaMenores < somaMaiores)
            {
                menorCaminhado++;
                somaMenores += menorCaminhado;
            }
            else
            {
                maiorCaminhado--;
                somaMaiores += maiorCaminhado;
            }

        }

        if(somaAte(menorCaminhado + 1) == somaAPartir(menorCaminhado + 1, casas))
        {
            System.out.println("Total de casas: " + casas + "\nConfeitaria: " + (menorCaminhado + 1));
        }

    }

O que eu quis dizer é que pra verificar a localização da confeitaria para 400000000 casas foram necessários 9 segundos, então esse programa ainda leva um bom tempo para verificar todos os casos até 400000000, mas é bem menos do que o anterior.

Talvez haja algum padrão que agilize ainda mais o cálculo, vou pensar um pouco e se conseguir alguma solução eu te informo.

Abraço.

Baixinho04 · 8 de março de 2010

Opa, foi um equívoco meu. Fiz um método somaAte que esta incluindo o último valor, quando não deveria, já corrigi a lista no meu último post.
Mas você fez o algoritmo da forma que eu disse mesmo? Aí segue o código que eu fiz, ele fica em loop infinito com valores menores ou iguais a dois(isso é fácil de corrigir, mas eu preferi admitir que ninguém vai usar este algoritmo para tais casos) e ainda dá pra otimizá-lo(tem como evitar o uso de long em alguns trechos, mas isso o tornaria um pouco mais complexo), mas no geral é bem simples, dá uma olhada:
public static void calculaConfeitaria(long casas)
    {
        long tempoInicio = System.currentTimeMillis();

        long somaMenores = 1;
        long somaMaiores = casas;

        long menorCaminhado = 1;
        long maiorCaminhado = somaMaiores;

        while(maiorCaminhado - menorCaminhado != 2)
        {

            if(somaMenores < somaMaiores)
            {
                menorCaminhado++;
                somaMenores += menorCaminhado;
            }
            else
            {
                maiorCaminhado--;
                somaMaiores += maiorCaminhado;
            }

        }

        System.out.println("Total de casas: " + casas + "\nConfeitaria: "
                + (menorCaminhado + 1) + "\nTempo para a execução: " + 
                (System.currentTimeMillis() - tempoInicio)+"ms");

    }
Lembre-se que o tempo de execução pode variar a depender da máquina utilizada.

Abraço.

entendi até mas eu preciso mostrar todas possiveis casas

8 > 6

69 > 34

e por ai vai..

E SE POR POR EXEMPLO 14 COMO NUMERO APARECERA COMO A CASA DE NUMEOR 9... o que não existe pois é a 6 xD

Goliathvv · 8 de março de 2010

entendi até mas eu preciso mostrar todas possiveis casas
8 > 6

69 > 34

e por ai vai..

E SE POR POR EXEMPLO 14 COMO NUMERO APARECERA COMO A CASA DE NUMEOR 9... o que não existe pois é a 6 xD

Eu corrigi o código para exibir apenas nos casos em que as somas de ambos os lados são iguais, dá uma olhada de novo.

E outra coisa, no caso de ter 69 casas há a solução de a confeitaria ser a número 34 mesmo?

Abraços.

Baixinho04 · 8 de março de 2010

Eu corrigi o código para exibir apenas nos casos em que as somas de ambos os lados são iguais, dá uma olhada de novo.
E outra coisa, no caso de ter 69 casas há a solução de a confeitaria ser a número 34 mesmo?

Abraços.

de ond saiu aqueles metodos "somaAte" e "somaApartir" ??

Goliathvv · 8 de março de 2010

de ond saiu aqueles metodos "somaAte" e "somaApartir" ??

Eu estava usando apenas para verificar os casos antes, mas depois lembrei da restrição, eles são esses daqui:


    public static long somaAte(long i)
    {
        long retorno = 0;        

        for(long j = 0; j < i; j++)
        {
            retorno += j;
        }

        return retorno;

    }

    public static long somaAPartir(long inicio, long fim)
    {
        long retorno = 0;        

        for(long j = inicio + 1; j < fim + 1; j++)
        {
            retorno += j;
        }

        return retorno;

    }

Eu sei que daria pra usar apenas somaAPartir, mas fiz o outro não sei por que...

Abraços.

Baixinho04 · 8 de março de 2010

Eu estava usando apenas para verificar os casos antes, mas depois lembrei da restrição, eles são esses daqui:


    public static long somaAte(long i)
    {
        long retorno = 0;        

        for(long j = 0; j < i; j++)
        {
            retorno += j;
        }

        return retorno;

    }

    public static long somaAPartir(long inicio, long fim)
    {
        long retorno = 0;        

        for(long j = inicio + 1; j < fim + 1; j++)
        {
            retorno += j;
        }

        return retorno;

    }

Eu sei que daria pra usar apenas somaAPartir, mas fiz o outro não sei por que...

Abraços.

não rolo aqui não apareceu nenhuma casa no console...

Goliathvv · 8 de março de 2010

não rolo aqui não apareceu nenhuma casa no console...

Tenta executar esse código todo:

public static void main(String[] args) {

for(long i = 3; i < 400000000; i++)
{
calculaConfeitaria(i);
}

}

public static long somaAte(long i)
{
long retorno = 0;

for(long j = 0; j < i; j++)
{
retorno += j;
}

return retorno;

}

public static long somaAPartir(long inicio, long fim)
{
long retorno = 0;

for(long j = inicio + 1; j < fim + 1; j++)
{
retorno += j;
}

return retorno;

}

public static void calculaConfeitaria(long casas)
{
long somaMenores = 1;
long somaMaiores = casas;

long menorCaminhado = 1;
long maiorCaminhado = somaMaiores;

while(maiorCaminhado - menorCaminhado != 2)
{

if(somaMenores < somaMaiores)
{
menorCaminhado++;
somaMenores += menorCaminhado;
}
else
{
maiorCaminhado--;
somaMaiores += maiorCaminhado;
}

}

if(somaAte(menorCaminhado + 1) == somaAPartir(menorCaminhado + 1, casas))
{
System.out.println("Total de casas: " + casas + "\nConfeitaria: "
+ (menorCaminhado + 1) + "\nTempo para a execução: ");
}

}

}
public class Chapeuzinho {

Baixinho04 · 8 de março de 2010

Tenta executar esse código todo:
public static void main(String[] args) {

for(long i = 3; i < 400000000; i++)
{
calculaConfeitaria(i);
}

}

public static long somaAte(long i)
{
long retorno = 0;

for(long j = 0; j < i; j++)
{
retorno += j;
}

return retorno;

}

public static long somaAPartir(long inicio, long fim)
{
long retorno = 0;

for(long j = inicio + 1; j < fim + 1; j++)
{
retorno += j;
}

return retorno;

}

public static void calculaConfeitaria(long casas)
{
long somaMenores = 1;
long somaMaiores = casas;

long menorCaminhado = 1;
long maiorCaminhado = somaMaiores;

while(maiorCaminhado - menorCaminhado != 2)
{

if(somaMenores < somaMaiores)
{
menorCaminhado++;
somaMenores += menorCaminhado;
}
else
{
maiorCaminhado--;
somaMaiores += maiorCaminhado;
}

}

if(somaAte(menorCaminhado + 1) == somaAPartir(menorCaminhado + 1, casas))
{
System.out.println("Total de casas: " + casas + "\nConfeitaria: "
+ (menorCaminhado + 1) + "\nTempo para a execução: ");
}

}

}
public class Chapeuzinho {

agora está funcioando bem, contudo está com tempo de execução lento por causa do laço... para chegar no 283.000.000 que por ali tem uma casa vai demorar MUITO!!!!

o meu professor deu uma "dica" de fazer um somatório tipo:

((A1 + An) nº termos ) / 2

soma de uma p.a. to tentando ver como posso usar isso

Goliathvv · 8 de março de 2010

agora está funcioando bem, contudo está com tempo de execução lento por causa do laço... para chegar no 283.000.000 que por ali tem uma casa vai demorar MUITO!!!!

Infelizmente está demorando mesmo. Só o caso 400000000 demora 9 segundos, então uns 100 casos próximos a ele levariam um total de 15 minutos.

Até que um tempo de execução O(n) é aceitável, mas parece que seu professor quer algo ainda melhor.

Amanhã vou ver se encontro uma solução melhor, deve haver algum padrão como você sugeriu antes.

Boa noite e abraços.

EDIT:

Vi agora a dica do seu professor, então realmente há um padrão que possibilita verificar em tempo O(1). Vou pensar um pouco no que poderia ser.

Baixinho04 · 8 de março de 2010

Infelizmente está demorando mesmo. Só o caso 400000000 demora 9 segundos, então uns 100 casos próximos a ele levariam um total de 15 minutos.
Até que um tempo de execução O(n) é aceitável, mas parece que seu professor quer algo ainda melhor.

Amanhã vou ver se encontro uma solução melhor, deve haver algum padrão como você sugeriu antes.

Boa noite e abraços.

muito obrigado pelo apoio, realmente não é aceitavel por ele, ele só aceita até 30s de execução. Ele falou que o dele faz em 17s... estou tentando ver como fazer... um colega meu cosnegui por essa esquema da doma de P.A mas não podemos ter um código igual por isso estou tentando descobrir sem pedir pra ele

Entrar

Ajuda com algoritmo

Posts recomendados

Arquivado

Quem está navegando aqui 0 usuários estão online

Últimos tópicos

Livros

Cursos

Conteúdo recente

Sobre o Clube do Hardware

Direitos autorais

Mais