IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Фибоначчи
Самара
сообщение 22.11.2005 19:13
Сообщение #1


Гость






Требуется найти n-ое число Фибоначчи. Напомним, что последовательность Фибоначчи это:
F(1) = 1; F(2) = 1; F(n) = F(n - 1) + F(n - 2);

на вход n. при том ,что n до 15000
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 3)
volvo
сообщение 22.11.2005 19:23
Сообщение #2


Гость






Цитата
при том ,что n до 15000

Уууу, да тут без длинной арифметики не обойтись... При таких значениях N тип LongInt переполнится однозначно...

FAQ: Длинная арифметика
 К началу страницы 
+ Ответить 
Ирочка
сообщение 22.11.2005 19:55
Сообщение #3


Гость






А как приблизительно будет выглядеть код???
 К началу страницы 
+ Ответить 
volvo
сообщение 22.11.2005 22:05
Сообщение #4


Гость






Цитата
А как приблизительно будет выглядеть код?
Примерно вот так:
const
  _maxdig = 1000;
  _osn = 10000;

type
  Tlong = array[0.._maxdig]of integer;
  Plong = ^Tlong;

Procedure InitOne(a: PLong);
Begin
  a^[1] := 1; inc(a^[0]);
End;

procedure SumLongTwo(a,b,c:Plong);
var i,k:integer;
begin
  fillchar(c^,sizeof(c^),0);
  if a^[0]>b^[0] then k:=a^[0] else k:=b^[0];
  for i:=1 to k do
     begin
        c^[i+1]:=(c^[i]+a^[i]+b^[i]) div _osn;
        c^[i]:=(c^[i]+a^[i]+b^[i]) mod _osn;
     end;
  if c^[k+1]=0 then c^[0]:=k else c^[0]:=k+1;
end;

procedure WriteLong(var f:text;a:Plong);
var ls,s:string;
   i:integer;
begin
  str(_osn div 10,ls);
  write(f,a^[a^[0]]);
  for i:=a^[0]-1 downto 1 do
     begin
        str(a^[i],s);
        while length(s)<length(ls) do s:='0'+s;
        write(f,s);
     end;
  writeln(f);
end;

var
  Great_1, Great_2, Great_3: TLong;
  first, second, next: PLong;
  n, max: integer;
begin
  Write('n = '); ReadLn(max);

  first := @Great_1;
  second := @Great_2;
  next := @Great_3;

  InitOne(First);  { First := 1  }
  InitOne(Second); { Second := 1 }
  n := 2;
  repeat
    Inc(n);
    SumLongTwo(First, Second, Next); { next := first + second }

    First^ := Second^;
    Second^ := Next^;

  until n >= max;

  Write('n = ', n, ' : ');
  WriteLong(Output, Next);
end.

А вот как будет выглядеть результат при n = 15000 я не берусь тебе сказать... При n = 2000 получается вот такое число:
Цитата
4224696333392304878706725602341482782579852840250681098010280137
3143085843701307072241235996391415110884460875389096036076401947
1164359602927198331259873732625355580260699158591522949245390499
8722256795316982874482472992263901833716778060607011615497886719
8798583114688708762645973690867228840236544222952433479644801395
1534956297208765265606952980649984197744872015561280266540455417
1717881930324025204312082516817125
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 27.07.2025 21:24
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"