Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

amoreto

Número de Schröder

Mensagens Recomendadas

amoreto

SymKJjE.png

Se analisarmos a solução anterior verificamos que para cada produto S(i) x S(n-i-1) existe outro produto simétrico que é exatamente o mesmo, pelo que podemos calcular apenas metade dos produtos

repetidos e duplicar o seu valor de forma eficiente, usando o deslocamento (shift) para a esquerda.

Assim, é possível fazer uma implementação com aproximadamente metade das multiplicações. Tendo

isto em conta desenvolva outra função repetitiva otimizada.

Boas!

Eu fiz o código do numero de Schroder usando programação dinâmica, mas agora (não usando array) nao estou a ver como vou usar o shift, e reduzir o numero de multiplicaçoes!

Este é o meu código usando programação dinâmica(funciona), mas preciso de fazer outra funçao repetitiva optimizada como está descrito em cima!

int sd(unsigned int n)
{
int i,j,result;
int *v=malloc((n+1)*sizeof(int));

v[0]=1;

for(i=1;i<=n;i++)
{
 v[i]=0; /*coloco o array todo a zero*/

 for(j=0;j<i;j++)
    {
          v[i] += v[j] * v[i-j-1];
          count++; /*contar as multiplicaçoes*/
     }

 v[i] += v[i-1];	
}

result=v[n];
free(v);

return result;
}

Editado por amoreto
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Se analisarmos a solução anterior verificamos que para cada produto S(i) x S(n-i-1) existe outro produto simétrico que é exatamente o mesmo, pelo que podemos calcular apenas metade dos produtos

repetidos e duplicar o seu valor de forma eficiente, usando o deslocamento (shift) para a esquerda.

Assim, é possível fazer uma implementação com aproximadamente metade das multiplicações. Tendo

isto em conta desenvolva outra função repetitiva otimizada.

que solução mágica é essa ? deveria o fórum saber por magica a que se refere isso ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
amoreto

v[i] += v[j] * v[i-j-1];

a soluçao anterior é o meu código,pelo menos foi dessa maneira que implementei!

Editado por amoreto

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
bubulindo

E o que é que não entendes? Como usar o shift?

Como diz aí, usando o shift, podes multiplicar... ou seja, se fizeres shit de uma casa, multiplicas por dois, duas casas, por 4, etc, etc...

Não sei que computador tens, mas isto costuma ser possível de calcular nas calculadoras do Windows e Macosx. No windows usas a tecla Lsh em modo programador e no Macosx os <<...

Se fizeres um tracing de 4 ou 5 iterações começando em S(1), vai ser evidente onde podes multiplicar por dois (um shift para a esquerda). O problema será em indices de somatório impares já que não são tem um duplo no somatório.

Uma pequena melhoria que podes fazer no teu código é mudar o tipo de variável para unsigned int... os resultadores serão sempre positivos, logo unsigned int dar-te-á mais espaço, já que os números parecem aumentar exponencialmente.

Editado por bubulindo

include <ai se te avio>

Mãe () {

}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.