Número de Schröder

[amoreto]

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;
}

Edited April 26, 2015 at 04:36 PM by amoreto
geshi

[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 ?

[amoreto]

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

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

Edited April 26, 2015 at 04:35 PM by amoreto

[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.

Edited April 27, 2015 at 05:25 PM by bubulindo