Jump to content
nunopicado

Fibonacci

Recommended Posts

nunopicado

Este tópico é um quatro em um... Como o champô, mas com mais classe!  :)

Para quem não viu, veja: Touch, com Kiefer Sutherland, na Fox.

É uma série interessante, ou pelo menos o primeiro episódio.

A história gira em torno de um miudo, nascido autista, que tem a capacidade de ver a sequência Fibonacci, números divulgados no ocidente por Leonardo Fibonacci no inicio do séc. XIII (embora não descobertos por ele como o nome parece sugerir), números esses que, consta, estão presentes em toda a natureza, criando padrões que se repetem, ligando todos os elementos ao passado, presente e futuro.

Posto que do nosso três em um já temos as sugestões televisivas e a história, vamos ao nº 3:

program Project1;

uses
  crt;

var
   f0,f1,tmp: Int64;
   ch:char;

begin
     clrscr;

     f0:=0;
     writeln(f0);
     f1:=1;
     repeat
           writeln(f1);
           tmp:=f0;
           f0:=f1;
           f1:=f1+tmp;

           if wherey=25
              then begin
                        gotoxy(1,wherey+1);
                        write('ESC para terminar, qualquer outra tecla para continuar. . .');
                        ch:=readkey;
                        if ch=#0 then ch:=readkey;
                        clrscr;
                   end;
     until (ch=#27);
end.

O nº 3 é analizar este código. Este snippet gera a sequência Fibonacci dinâmicamente (ou será que não? :twisted:) e vai mostrando o resultado no ecrã.

Por fim, o nº 4: O Desafio

O desafio consiste em:

a. Analizar este snippet e verificar se realmente ele faz o que é pedido.

b. Se fizer, verificar se o faz correctamente.

c. Se não o fizer correctamente, como o corrigir (teoria)

d. Se não o fizer correctamente, como o corrigir (prática)

E então, alguém quer tentar?  ;):confused:


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
pmg

Disclaimer: nao sei Pascal ...

a. Acho que sim

b. Hmmm ... faz um calculo extra cujo resultado nao e aproveitado para nada. Alem disso 25 linhas de numeros Fibonacci devem ultrapassar em muito a capacidade dum Int64.

c. usando "big integers"

d. passo

Nota: alterei o codigo acima, basicamente simplificando-o, ate ele ser aceite pelo ideone: http://ideone.com/IF1lR


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
nunopicado

:confused: Obrigado pela resposta...

Convém notar que o writeln escreve apenas um número por cada linha...

Quanto ao resto, vamos só aguardar outras opiniões! ;)

PS: Já agora, queres especificar qual o cálculo que te parece a mais? :)


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
pmg

program Project1;

uses
  crt;

var
   f0,f1,tmp: Int64;
   ch:char;

begin
     clrscr;

     f0:=0;
     writeln(f0);
     f1:=1;
     repeat
           writeln(f1);
           tmp:=f0;
           f0:=f1;
           f1:=f1+tmp;

           if wherey=25
              then begin
                        gotoxy(1,wherey+1);
                        write('ESC para terminar, qualquer outra tecla para continuar. . .');
                        ch:=readkey;
                        if ch=#0 then ch:=readkey;
                        clrscr;
                   end;
     until (ch=#27);
end.

PS: Já agora, queres especificar qual o cálculo que te parece a mais? ;)

O programa primeiro imprime e depois calcula ... e esse calculo é usado para a proxima impressao ... que pode nao haver. Ou seja o calcula extra so é feito mesmo no fim do programa.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
nunopicado

ah, ok... ;)


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
thoga31

O desafio já vai bem adiantado, e ainda bem. Não posso deixar isto para amanhã? ;)

Disclaimer: nao sei Pascal ...

Moço, aprende e junta-te aqui aos experts, quantos mais melhor! :confused:

Olha que Pascal não é antiquado como muitos querem fazer crer... bem pelo contrário! Então, queres experimentar? :)


Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

... Então, queres experimentar? ;)

Nahhhhh ... Nao é questao de antiguidade ... Pascal e C nao sao assim tao diferentes como isso.

Se me ponho a programar em Pascal depois comeco a esquecer-me das {chavetas} em C :)

Ja ando a dizer isto ha nao sei quantos anos ... qualquer dia comeco com o (((((((( LISP ))))))))


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pwseo

Não estou a perceber bem qual é o objectivo :)

O pmg já referiu aquilo que eu referiria; rapidamente ultrapassamos a capacidade de um Int64, mas de resto parece-me estar a calcular correctamente.

É suposto darmos uma solução de como calcular com bigints?

Talvez queiras alterar wherey = 25 para wherey = windmaxy visto que (pelo menos aqui) ao executar isso num terminal o programa não reage a nada por ter isto com 24 linhas :)

Share this post


Link to post
Share on other sites
nunopicado

A questão é:

Sugestões para apresentar valores superiores ao máximo do Int64. ;)


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
pwseo

Aqui fica uma possível solução... Provavelmente podia ser optimizada de muitas formas, mas pronto... Penso que está correcta (verifiquei o último resultado e dei uma olhadela nos primeiros e deu bem). (Ideone aqui)

program bigfib;

function sum(a, b: string): string;
var
  i, n, c, t: integer;
begin
  sum := '';
  c := 0;
  n := length(b) - length(a);
  for i := 1 to n do
    a := '0' + a;
  for i := length(b) downto 1 do
  begin
    t := (ord(a[i]) + ord(b[i]) - 2 * ord('0')) + c;
    c := t div 10;
    sum := chr(ord('0') + (t mod 10)) + sum;
  end;
  if c > 0 then
    sum := chr(ord('0') + c) + sum;
end;

var
  i: integer;
  n1, n2, nt: string;
begin
  n1 := '0';
  n2 := '1';
  writeln(sum(n1, n2));
  for i := 2 to 200 do
  begin
    nt := sum(n1, n2);
    n1 := n2;
    n2 := nt;
    writeln(nt);
  end;
end.

Share this post


Link to post
Share on other sites
nunopicado

És grande Pedro! ;)

pmg: Obrigado por participares.

A solução era mesmo o uso de strings para conseguir ultrapassar os limites do Int64. :)


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
pmg

Penso que está correcta

Aparentemente, quando o tamanho da string chega aos 256 caracteres, o teu programa comeca a falhar ...

http://ideone.com/iEvf6 compara com https://oeis.org/A000045/b000045.txt


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pwseo

pmg,

O programa deve ser compilado com suporte para AnsiStrings (flag -Sh) no freepascal (senão só suportam até 256 caracteres).

Adaptei o código para imprimir a posição de cada número calculado e fiz uma comparação directa com o ficheiro de texto que utilizaste... A diferença que existe entre os dois outputs deve-se ao facto do ficheiro online ter linhas em branco no final.

pedro@laptop:~$ fpc -Mobjfpc -Sh bigfib.pas
...
pedro@laptop:~$ diff <(./bigfib) <(wget -q -O - https://oeis.org/A000045/b000045.txt)
2001a2002,2004
> 
> 
> 

De qualquer forma o objectivo aqui era demonstrar uma forma de calcular a soma de dois números representados numa string (o que está em causa nesse bug é uma limitação do Pascal facilmente corrigida por quem compila).

Share this post


Link to post
Share on other sites
nunopicado

Exacto, isso vai depender do compilador. No caso do Delphi por exemplo, isto irá compilar com WideStrings directamente, com um limite muito superior.

Salvo erro, no freepascal, pode-se conseguir igual com a directive {$MODE Delphi}


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Share this post


Link to post
Share on other sites
Firewall

Poxa ,quando vejo isto, me apercebo, de mundos,que não foram descobertos, e que meus olhos estão cegos.

ahahah, e lá vamos nós enfiar a cabeça nos livros.

O programa deve ser compilado com suporte para AnsiStrings (flag -Sh) no freepascal (senão só suportam até 256 caracteres).

Apesar, se não me confundo, não poderia fazer um encadeamento,de array, parar exceder este limite?, se asssim, poderia resumir, ou não, como estou no inicio, não sei se isto seria funcional,para este caso.

Share this post


Link to post
Share on other sites
pwseo

Podes emular strings longas (>256) da forma que quiseres (várias strings juntas, uma área de memória com expansão quando necessária, etc).

Mas como o próprio compilador já traz consigo extensões para isso mesmo, seria uma asneira não as aproveitar :)

Share this post


Link to post
Share on other sites
thoga31

@pedro-kun, adorei a tua solução. ;)

Tenho de me debruçar bem sobre ela para ver se entendo na perfeição, à primeira confundi-me um pouco (uns comentários não teriam ficado mal, eheheh ;))


Knowledge is free!

Share this post


Link to post
Share on other sites
pwseo

Pois, mas foi tudo feito mesmo antes de adormecer, daí a falta de comentários.

Basicamente, a função pega nas duas strings, assumindo que a tem um comprimento sempre menor ou igual que b e acrescenta-lhe zeros à esquerda para ficaram do mesmo comprimento.

Depois é uma questão de fazer as contas como na primária, somar pares de dígitos e anotar numa variável "quantos vão" para a próxima soma.

Amanhã depois do exame se calhar optimizo e comento isso :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.