|
#1
|
|||
|
|||
Числа фибоначчи
Мне нужно вывести 150 чисел Фибоначчи
Код:
var a,b,c: integer; begin a:=1; b:=1; while a<2000000000 do begin c:=a+b; a:=b; b:=c; memo1.text := memo1.text + Inttostr(b)+#13#10; end; После 46 цикла пошли минусы Если делать так: Код:
// Возвращает Nый элемент ряда фибоначи function Fib(N : Integer) : Integer; begin If N < 3 Then Result := 1 Else Result := Fib(N-1) + Fib(N-2); end; ......... begin for i := 1 to 20 do label1.Caption := label1.Caption + Inttostr(fib(i))+', '; программа виснет если больше 46 циклов. Как исправить? |
#2
|
|||
|
|||
1. Убрать рекурсию (сделать через вычисление с памятью и цикл)
2. Использовать Int64 (на всякий случай) Как-то так (не проверял, мог чего-то напутать слегка): Код:
unit Fibonachi; interface function Fib(N : Integer) : Int64; implementation var int_Fibs : Array Of Int64; function Fib(N : Integer) : Int64; begin If N < 1 Then Result := -1 Else If N <= Length(int_Fibs) Then Result := int_Fibs[N-1] Else Begin For I := Length(int_Fibs) To N Do Begin SetLength(int_Fibs,Length(int_Fibs)+1); int_Fibs[i] := int_Fibs[I-1] + int_Fibs[I-2]; End; Result := int_Fibs[High(int_Fibs)]; End; end; initialization SetLength(int_Fibs,2); int_Fibs[0] := 1; int_Fibs[1] := 1; finalization SetLength(int_Fibs,0); end. |
#3
|
|||
|
|||
Вот, поправил:
Код:
unit Unit1; interface uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls; type TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm} var int_Fibs : Array Of Int64; function Fib(N : Integer) : Int64; var I : Integer; begin If N < 1 Then Result := -1 Else If N <= Length(int_Fibs) Then Result := int_Fibs[N-1] Else Begin For I := Length(int_Fibs) To N-1 Do Begin SetLength(int_Fibs,Length(int_Fibs)+1); int_Fibs[i] := int_Fibs[I-1] + int_Fibs[I-2]; End; Result := int_Fibs[High(int_Fibs)]; End; end; procedure TForm1.Button1Click(Sender: TObject); var I : Integer; begin Memo1.Lines.Clear; For I := 1 To 150 Do Memo1.Lines.Add(Format('Fib(%d) = %d',[I,Fib(I)])); end; initialization SetLength(int_Fibs,2); int_Fibs[0] := 1; int_Fibs[1] := 1; finalization SetLength(int_Fibs,0); end. Но там все-равно 150 не дает, где-то уже с 90 начинаются проблемы. Даже int64 не хватает. Из идей - делать 2 int64 и "пилить" числа. Либо искать библиотеку для BigInteger (типа для 128 битных чисел или больше). Ну или делать через строку и самому писать алгоритм скложения. |