Ajuda com algoritmo

Goliathvv · 8 de março de 2010

Achei!

Uma pequena correção, para o algoritmo que eu passei antes, O(n) é a verificação para um número de casas, o programa para verificar para todas as casas até um dado número executa em O(n²).

Agora o que eu identifiquei, à esquerda temos os casos em que é possível encontrar a confeitaria, e à direita um pequeno cálculo:

8

49 -> 49 - 8 = 41

288 -> 288 - 49 = 239

1681 -> 1681 - 288 = 1393

9800 -> 9800 - 1681 = 8119

Perceba uma coisa:

239 / 41 = 5,829268292682927

1393 / 239 = 5,828451882845188

8119 / 1393 = 5,828427853553482

Em outras palavras,

Considerando Tn um valor aceitável, T(n -1) o anterior a ele e assim sucessivamente:

(Tn - T(n-1))/(T(n - 1) - T(n - 2)) =~ 5.82

Agora é só fazer um programa contendo os casos iniciais e você conseguirá encontrar todos rapidamente.

Um algoritmo pra encontrar todas as casas possíveis utilizando este cálculo seria O(n), então aí é bem mais tranquilo.

Abraços.

Baixinho04 · 8 de março de 2010

só que eu ACHO que os termos são:

6

35

204

1189

6930

40391

...

Goliathvv · 8 de março de 2010

só que eu ACHO que os termos são:
6

35

204

1189

6930

40391

...

Realmente, há uma progressão geométrica com razão aproximadamente 5,82 aí, mas infelizmente a razão não é exatamente essa(da mesma forma que não era no meu post anterior), ela vai variando um pouco, mas conforme os números vão crescendo ela estabiliza nas casas 5.8284.

Bem, o que eu recomendaria você fazer é começar com dois números, no caso o 6 e 35, fazer o cálculo e desconsiderar a parte decimal do resultado e recalcular a razão para obter o próximo valor, assim você minimiza a perda de informação.

Por exemplo:

35 / 6 = 5,833333333333333

35 * 5,833333333333333 = 204,1666666666667

Desconsidere a parte decimal e adicione-o à lista.

204 / 35 = 5,828571428571429

204 * 5,828571428571429 = 1189,028571428571

Desconsidere a parte decimal e adicione-o à lista.

1189 / 204 = 5,82843137254902

1189 * 5,82843137254902 = 6930,004901960784

Desconsidere a parte decimal e adicione-o à lista.

E assim você vai até o último valor, sempre obtendo a nova razão e desconsiderando as partes decimais. Dessa forma eu acho que é seguro obter o resultado.

Abraços.

PS:

Só um lembrete, fazendo desse jeito você obterá apenas quais são os números de confeitaria válidos, e não cada caso no qual há uma confeitaria válida. Mas tendo um número de confeitaria válido é fácil de obter a qual quantidade de casas aquele número se refere, a recíproca também é verdadeira.

Mas uma forma que eu acho que ficaria bem rápido é ter duas listas e utilizar o algoritmo desse post aqui em conjunto com a progressão que eu mostrei no post #26, afinal em ambos os casos a razão vai mudando vagarosamente.

Baixinho04 · 8 de março de 2010

Realmente, há uma progressão geométrica com razão aproximadamente 5,82 aí, mas infelizmente a razão não é exatamente essa(da mesma forma que não era no meu post anterior), ela vai variando um pouco, mas conforme os números vão crescendo ela estabiliza nas casas 5.8284.
Bem, o que eu recomendaria você fazer é começar com dois números, no caso o 6 e 35, fazer o cálculo e desconsiderar a parte decimal do resultado e recalcular a razão para obter o próximo valor, assim você minimiza a perda de informação.

Por exemplo:

35 / 6 = 5,833333333333333

35 * 5,833333333333333 = 204,1666666666667

Desconsidere a parte decimal e adicione-o à lista.

204 / 35 = 5,828571428571429

204 * 5,828571428571429 = 1189,028571428571

Desconsidere a parte decimal e adicione-o à lista.

1189 / 204 = 5,82843137254902

1189 * 5,82843137254902 = 6930,004901960784

Desconsidere a parte decimal e adicione-o à lista.

E assim você vai até o último valor, sempre obtendo a nova razão e desconsiderando as partes decimais. Dessa forma eu acho que é seguro obter o resultado.

Abraços.

PS:

Só um lembrete, fazendo desse jeito você obterá apenas quais são os números de confeitaria válidos, e não cada caso no qual há uma confeitaria válida. Mas tendo um número de confeitaria válido é fácil de obter a qual quantidade de casas aquele número se refere, a recíproca também é verdadeira.

Mas uma forma que eu acho que ficaria bem rápido é ter duas listas e utilizar o algoritmo desse post aqui em conjunto com a progressão que eu mostrei no post #26, afinal em ambos os casos a razão vai mudando vagarosamente.

acho que não rolou a logica para as partes finais e seguintes...

tipo

Numero da casa: 6
Numero da casa: 35

Numero da casa: 204

Numero da casa: 1189

Numero da casa: 6930

Numero da casa: 40391

Numero da casa: 100469

Numero da casa: 1250970

Numero da casa: 2096128

...

100469 * 5,8284 = 585573,5196
ou seja bem diferente de 1250970

xD

mas estamos chegando lá \o/

Goliathvv · 8 de março de 2010

acho que não rolou a logica para as partes finais e seguintes...
tipo

Amigo, note no detalhe que eu falei: você não vai usar exatamente um valor fixo pra multiplicar, mas sim vai atualizar o valor a cada passo. Por exemplo:

Numero da casa: 6

Numero da casa: 35 (aqui a razão é 35 / 6)

Numero da casa: 204 (aqui a razão é 204 / 35)

Numero da casa: 1189 (aqui a razão é 1189 / 204 )

Numero da casa: 6930 (aqui a razão é 6930 / 1189 )

Numero da casa: 40391 (aqui a razão é 40391 / 6930 )

Numero da casa: 40391 * (40391 / 6930) = 235416

A forma mais simples de implementar é: último valor da lista ao quadrado, dividido pelo penúltimo retorna o próximo da lista.

Agora vou indo, até mais!

Baixinho04 · 9 de março de 2010

consegui resolver o problema com uma solução muito simples de 4 linhas xD

mas demorei pra resolver... valeu a ajuda de todos

Goliathvv · 9 de março de 2010

consegui resolver o problema com uma solução muito simples de 4 linhas xD
mas demorei pra resolver... valeu a ajuda de todos

Que bom! Mas você poderia dizer qual foi a solução para que eu marque o tópico como resolvido?

A solução que eu implementei aqui foi:


    public static void calculaConfeitaria(double numeroCasas)
    {
        ArrayList<Double> possiveis = new ArrayList<Double>();
        possiveis.add(new Double(6));
        possiveis.add(new Double(35));

        double atual = possiveis.get(possiveis.size() - 1);

        while(atual <= numeroCasas)
        {
            atual = new Double((int)(possiveis.get(possiveis.size() - 1) * possiveis.get(possiveis.size() - 1) / possiveis.get(possiveis.size() - 2)));
            possiveis.add(atual);
        }

        imprimirPossiveis(possiveis);

    }

Abraços.

Goliathvv · 22 de março de 2010

Conforme solicitado, estamos reabrindo este tópico!

chic0o · 22 de março de 2010

Goliathvv,

como você pode implementar esse codigo?

poq tipo, você teria qe saber os dois primeiros numeros do array

pra poder dar continuidade no processo, e como descobrir eles?

e isso é uma formula? qual?

e como chegou nesse raciocinio?

obrigado

Goliathvv · 22 de março de 2010

Primeiramente, esse problema é um tanto esotérico. Essa coisa de perceber uma relação entre os números não é algo tão relacionado assim a algoritmos.

Mas como nós analisamos os primeiros números e "percebemos" a existência daquele padrão (que é quase uma pg, mas não é uma pg propriamente dita pois há uma variação sutil nas casas decimais, mas essa variação faz toda a diferença), podemos fazer o seguinte:

Obtenha os dois primeiros valores válido através da força bruta, o que será algo relativamente rápido pois os dois primeiros números válidos para a confeitaria são 6 e 35, e adicione-os à lista.

Uma vez feito isso, crie um loop que adicionará ao fim da lista o seguinte número:

(quadrado do último) * penúltimo

E faça isso enquanto o último valor da lista for inferior ao limite estabelecido. Após o término do loop, o último valor será maior que o limite, então remova-o da lista e pronto, você tem a lista de números de confeitaria válidos.

Se não entendeu bem como funciona pode dizer que eu explico melhor.

Abraço.

chic0o · 22 de março de 2010

taaah entendi a tua solução,

mas por exemplo,

não tem como saber o tamanho da rua de acorda com o numéro da confeitaria

por exemplo

confeitaria 6 = tamanho da rua 8

confeitaria 35 = tamanho da rua 49

poq dai ele processa usando os resultados

desculpa, mas eu sou novo com Java :/

Goliathvv · 23 de março de 2010

taaah entendi a tua solução,
mas por exemplo,

não tem como saber o tamanho da rua de acorda com o numéro da confeitaria

por exemplo

confeitaria 6 = tamanho da rua 8

confeitaria 35 = tamanho da rua 49

poq dai ele processa usando os resultados

desculpa, mas eu sou novo com Java :/

Primeiro, não precisa pedir desculpas. Eu também já fui iniciante e sei que no começo as idéias ainda são um pouco nebulosas, mas com o tempo tudo fica mais claro.

E respondendo: Na verdade tem sim como descobrir o tamanho da rua dada a posição da confeitaria.

Veja bem: nós sabemos que até a casa antes da confeitaria a soma tem um valor X, então devemos apenas somar as casas depois da confeitaria até obtermos este mesmo valor X, afinal a soma dos números das casas antes e depois da confeitaria são iguais.

Exemplo:

Sabemos que a confeitaria tem número 6. Então se fizermos 1+2+3+4+5, vamos obter o valor que a soma deve ter antes e depois da confeitaria(neste caso 15).

Como nós sabemos que o valor da soma é 15, podemos ir somando os números a partir do 7 para encontrar a última casa. Outra forma de fazer, e que eu acho mais interessante, é obter o valor da soma e ir subtraindo dela cada casa após a confeitaria, até que o valor da soma seja 0. Então o loop seria algo como:


int casaAtual = confeitaria;
int somaTotal = //aqui botamos o valor da soma que calculamos antes, no exemplo foi 15

while(somaTotal != 0)
{
    casaAtual++;
    somaTotal -= casaAtual;
}

No fim da iteração teremos na variável casaAtual a última casa da rua.

Você compreendeu a ideia? Se algo não ficou claro pode falar que eu explico novamente.

Abraços.

chic0o · 25 de março de 2010

Achei!
Uma pequena correção, para o algoritmo que eu passei antes, O(n) é a verificação para um número de casas, o programa para verificar para todas as casas até um dado número executa em O(n²).

Agora o que eu identifiquei, à esquerda temos os casos em que é possível encontrar a confeitaria, e à direita um pequeno cálculo:

8

49 -> 49 - 8 = 41

288 -> 288 - 49 = 239

1681 -> 1681 - 288 = 1393

9800 -> 9800 - 1681 = 8119

Perceba uma coisa:

239 / 41 = 5,829268292682927

1393 / 239 = 5,828451882845188

8119 / 1393 = 5,828427853553482

Em outras palavras,

Considerando Tn um valor aceitável, T(n -1) o anterior a ele e assim sucessivamente:

(Tn - T(n-1))/(T(n - 1) - T(n - 2)) =~ 5.82

Agora é só fazer um programa contendo os casos iniciais e você conseguirá encontrar todos rapidamente.

Um algoritmo pra encontrar todas as casas possíveis utilizando este cálculo seria O(n), então aí é bem mais tranquilo.

Abraços.

Euuu de novo, hahha.

Cara brigadão consegui fazer o qe eu precisava.

mas ao ler esse post, fiquei meio confuso.

1 : Como tu calculou a complexidade O(n) ?

2 : E como chegar a lógica que tu comentou ali, diminui um do outro e depois dividir??

3 : Como é possivel (por exemplo) 204²/35 ser igual a 204*5.8285

Goliathvv · 25 de março de 2010

Euuu de novo, hahha.
Cara brigadão consegui fazer o qe eu precisava.

mas ao ler esse post, fiquei meio confuso.

1 : Como tu calculou a complexidade O(n) ?

2 : E como chegar a lógica que tu comentou ali, diminui um do outro e depois dividir??

3 : Como é possivel (por exemplo) 204²/35 ser igual a 204*5.8285

1 - É simples para esse caso. O meu algoritmo anterior fazia o seguinte: para saber se um dado número era válido, ele percorria todas as casas para aquele número, ou seja, é como se houvesse uma lista com N casas e eu percorresse da casa 1 até a N(tinha aquele pingue-pongue entre a primeira metade e a segunda metade, mas a lista é percorrida completamente da mesma forma, então isso é irrelevante). Assim sendo, para uma quantidade N de casas, eu precisei percorrer N elementos da lista, então a complexidade é O(n).(repito que nem sempre é tão simples assim)

Já o algoritmo para verificar todas as possibilidades de 1 até N é O(n²), pois em cada caso eu tenho que fazer o algoritmo anterior. Ou seja, se eu quero testar de 1 até 50 casas quais valores admitem uma confeitaria, eu tenho que, para cada valor aplicar o meu algoritmo anterior.

Dessa forma tenho que percorrer uma lista de tamanho 1 para o caso 1.

Tenho que percorrer uma lista de tamanho 2 para o caso 2.

.

Tenho que percorrer uma lista de tamanho 49 para o caso 49.

Tenho que percorrer uma lista de tamanho 50 para o caso 50.

Aí vem um truque: ao invés de supor que eu tenho 50 casos e que em cada um o valor vai aumentando em uma unidade, eu posso supor que tenho 25 e dizer que nesses 25 percorro a lista completa. Veja como:

Se eu unir o caso 50 com o caso 1, terei que percorrer uma lista de tamanho 51.

Se eu unir o caso 49 com o caso 2, terei que percorrer uma lista de tamanho 51.

Se eu unir o caso 48 com o caso 3, terei que percorrer uma lista de tamanho 51.

Então depois de unir todos os pares, eu terei 25 casos na qual a lista é de tamanho 51.

Sabemos que o nosso N era 50, então eu terei que percorrer N/2 casos de tamanho N+1. Ou seja, vou percorrer os elementos (N/2)*(N+1) vezes. Isso me dá O( (N/2)*(N+1)), mas em termos de complexidade valores constantes não interessam, então podemos ignorar a divisão por 2 e a soma com 1, o que nos dá: O(n * n) = O(n²).

Isso significa que, se você deseja dobrar o número de casas que quer verificar, o tempo vai quadruplicar. Então se para descobrir os valores válidos para 100 casas eu levo 1ms, para descobrir os valores válidos no caso de 1000, eu vou levar 100ms.

2 - Cara, isso aí foi testando mesmo. Eu já fiz vários exercícios de PA e PG(principalmente no tempo de vestibular:p), e um ou outro era mais sutil(como é o caso desse problema), então eu testei algumas possibilidades simples e nesse caso eu consegui. Deve haver uma lógica matemática por trás disso, mas não tive muita paciência pra sentar e perceber algo mais claro.

3 - Simples, 204/35 = 5.8285.

Como 204²/35 = 204 * 204/35,

temos que 204²/35 = 204 * 5.8285

Mas como eu disse depois: 5.8285 não é o valor correto a ser utilizado, isso porque conforme os números vão crescendo, este valor é alterado um pouco, de modo que para três números consecutivos tal diferença não é tão grande, mas para valores maiores o cálculo começará a dar errado, então o correto é sempre utilizar os último e penúltimo números da lista para efetuar o cálculo e sempre ignorar o valor decimal do novo elemento calculado.

Acho que não fui muito claro em algumas partes, mas qualquer coisa é só falar que eu explico melhor.

Abraço.