Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Факториал

Автор: batek 22.2.2007, 22:19

Нужно посчитать факториал 10 000 написал рекурсию, программа выдает сообщение о том что переменная переполненна. У меня вопрос какой тип данных нужно подобрать, что бы не вылазило сообщение.

Автор: VICTAR 22.2.2007, 22:38

Попробуй Int64

Автор: gambit 22.2.2007, 22:40

Попробуй int64 но врядли. Факториал 10000 это очень жестоко

Автор: W4FhLF 22.2.2007, 22:48

факториал 1000 - это число с 2500 порядками, 10000 - это нереально много, может забыть про эту задачу.

Добавлено @ 22:51
Максимальное число, которое ты можешь уместить в расширенный вещественный тип(Extended) это 10^4932, но этого будет недостаточно конечно же. Int64 это вообще всего 20 порядков.

Автор: Данкинг 22.2.2007, 22:52

А сколько времени факториал этот вычисляться будет? smile

У меня вон !1000 - и уже висит нафиг.

Автор: W4FhLF 22.2.2007, 22:58

2.8462596809170545189064132121199e+35659

Полное значение смотри в аттаче smile

Автор: batek 22.2.2007, 22:58

а можно ли как нибудь проверять переполнилась переменная или нет, но что бы программа не вылетала

Автор: Fin 22.2.2007, 23:06

Нужно создать свой собственный тип. По моим примерным подсчетам, нужно выделить под число около 16 килобайт памяти. И чуть чуть вспомнить школьную математику, а именно: как делается умножение столбиком. А 10 тысяч раз умножить столбиком, это не слишком много времени для современной вычислительной техники.

Это если нужно точно получить все цифры данного числа smile

Автор: batek 22.2.2007, 23:12

Fin,
Как тип то создать свой

Добавлено @ 23:18
Fin, У меня была такая же идея умножать столбиком. Типа два массива или 3 в одном первое число каждая цифра которого в отдельную ячейку массива, второй второе число 3 массив вспомогательный так?

Автор: Fin 22.2.2007, 23:20

Просто типизируй массив 16384 байт.
Сделай функцию, которая умножает данный массив на число типа integer. И вызывай ее с прирошением до 10 тысяч.
Дельфями я давно не баловался, поэтому более точную подсказку я не дам.

Добавлено @ 23:26
Я когда то делал битовое умножение массивов. Но там были свои трудности у меня. Тебе в принципе можно умножать байт на байт. Умножение производить в типе integer или word. Затем полученное число делиш на 256. Остаток будет записываться в этот байт. А целая часть это перенос в следуюший разряд.

Автор: batek 22.2.2007, 23:38

Fin, не непонял я

Автор: Fin 23.2.2007, 00:03

В байте помешается число от 0 и до 255.

Возьмем простой пример. Допустим у нас есть число с следуюшими байтами
[0] = 255
[1] = 255
[2] = 255

Его надо умножить на число 10 000
Получаем:
[0] 255 * 10 000 = 2 550 000
Делим его на 256. Получаем 9960 целая часть, 240 остаток от деления
Записываем в [0] <- 240

[1] 255 * 10 000 = 2 550 000
Добавляем предыдуший перенос 2 550 000 + 9 960 = 2 559 960
Делим его на 256. Получаем 9999 целая часть, 216 остаток от деления
Записываем в [1] <- 216

[2] 255 * 10 000 = 2 550 000
Добавляем предыдуший перенос 2 550 000 + 9 999 = 2 559 999
Делим его на 256. Получаем 9999 целая часть, 255 остаток от деления
Записываем в [2] <- 255

Так как у нас не осталось чисел для умножения, но есть перенос. Проводим дополнительные действия:
Перенос был 9999. Делим его на 256
Получаем 39 целая часть, 15 остаток от деления
Записываем в [3] <- 15

Перенос был 39. Делим его на 256
Получаем 0 целая часть, 39 остаток от деления
Записываем в [4] <- 39

Итого в нашем массиве будут такие числа,
[4] = 39; [3] = 15; [2] = 255; [1] = 216; [0] = 240

Автор: batek 23.2.2007, 00:26

Fin,
[0] = 255
[1] = 255
[2] = 255
в математике это число 255 255 255 * 10 000 или я не правильно понял?

Добавлено @ 00:29
или это число 765=255+255+255

Автор: Fin 23.2.2007, 00:32

Неа. В десятичной системе счисления это 255*256*256+255*256+255=16777215
А 39*256*256*256*256+15*256*256*256+255*256*256+216*256+240 = 167772150000

Автор: batek 23.2.2007, 00:41

умножу я так найду массив в котором факториал разложен побайтно потом мне байты же надо будет в число преобразовывать

Автор: Fin 23.2.2007, 00:51

Тебе в какой системе нужно выводить результаты? Я имею ввиду базис счисления.

Автор: batek 23.2.2007, 00:53

Автор: Pakshin A. S. 23.2.2007, 00:53

А если написать функцию умножения двух чисел, представленных в строковом формате? Тогда будет иметься возможность вывода больших факториалов...

Автор: Fin 23.2.2007, 00:58

тоды тебе придётся еше писать функцию деления. И делить полученный массив на 10.

Есть второй выход. Базис брать не 256 при умножении а 100 скажем. Просто не рационально будет использоваться память. И естественно нужно будет ее выделять больше. Но в 10 тичную систему счисления будет намного легче перейти smile

Добавлено @ 01:00
Pakshin A. S., Ему тогда придтся еше работать с ASCII кодами. А так можно получить тоже самое,

Автор: W4FhLF 23.2.2007, 08:56

FGInt посмотри.

Автор: batek 23.2.2007, 11:55

W4FhLF
Нет такого

Автор: batek 23.2.2007, 12:23

Определить последнюю цифру не равную 0 при вычислении факториала N!, причем N задается в пределах от 1 до 10000.

Автор: maxim1000 23.2.2007, 12:30

а эта задача уже обсуждалась smile

http://forum.vingrad.ru/index.php?showtopic=33505

Автор: batek 23.2.2007, 12:46

maxim1000,
Спасибо но все таки надо попробовать как нить найти факториал 10000

Автор: maxim1000 23.2.2007, 13:50

так я и не спорю, просто для задачи про последнюю цифру это необязательно

Автор: W4FhLF 23.2.2007, 14:39

Цитата(batek @ 23.2.2007, 11:55

)

W4FhLFНет такого

http://www.google.ru/search?hl=ru&newwindow=1&q=FGInt&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=

Автор: W4FhLF 23.2.2007, 23:18

http://shade.msu.ru/~msu-se/llong.7z

Код


procedure TForm1.Button1Click(Sender: TObject);
var
Time:dword;
n,Fac:lLongInt;
i:dword;
begin
  n.create(6);
  Fac.create($FFFF);

  Time := GetTickCount();
  Fac.strtolint('1');
  for i := 1 to 10000 do
  begin
    n.strtolint(IntToStr(i));
    Fac.umult(Fac, n);
  end;
  Memo1.Text := Fac.linttostr;
  ShowMessage('Затрачено секунд: ' + IntToStr((GetTickCount()-Time) div 1000));
end;

У меня Athlon3500+, на вычисления уходит порядка 10 сек.

Автор: Rockie 24.2.2007, 14:23

Цитата(batek @ 22.2.2007, 22:58

)

а можно ли как нибудь проверять переполнилась переменная или нет, но что бы программа не вылетала

Если переменная не unsigned то после переполнения пойдут отрицательные значения. Извините что не Delphi.

Код


#include <iostream>

int main()
{
    char c = 0;

    for(int i=0;i<1024;i++)
        std::cout<<(int)c++<<' ';

    return 0;
}

Автор: Alexeis 24.2.2007, 18:38

С модулем FGint по лучше получается. Вычисления произвел в 2 потока, на Athlon x2 3800+
Результат 0,2с для 10000! и 32с для 100000!

http://www.koders.com/delphi/fidB46DDCCA26267DE4B4FB0F7E041A8033A3783AD6.aspx?s=algorithm

Код


unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, FGInt, IdGlobal;

type
  TNewThread = class;

  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
     res      : TFGInt;
     tr1, tr2 : TNewThread;
     Cr       : TCriticalSection;
     threadsTerminated : Integer;
     Timer    : Integer;
     procedure MultByRes(value : TFGInt);
  end;

  TNewThread = class(TThread)
     constructor Create(CreateSuspended: Boolean; fromV : integer; ToV : integer);
     procedure Execute;  override;
  protected
     fromV, ToV : Integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{ TNewThread }

constructor TNewThread.Create(CreateSuspended: Boolean; fromV, ToV: integer);
begin
  inherited Create(CreateSuspended);
  self.fromV := fromV;
  self.ToV   := ToV;
end;

procedure TNewThread.Execute;
var
  Fac  : TFGInt;
  i    : dword;

begin
  Base10StringToFGInt('1', Fac);

  for i := fromV to ToV
  do
    FGIntMulByInt(Fac, Fac, i);

  Form1.MultByRes(Fac);
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  Base10StringToFGInt('1', res);
  tr1 := TNewThread.Create(true, 1, 5000);
  tr2 := TNewThread.Create(true, 5001, 10000);
  Cr  := TCriticalSection.Create;
  threadsTerminated := 0;
  Timer := GetTickCount();
  tr1.Resume;
  tr2.Resume;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  tr1.Free;
  tr2.Free;
  Cr.Free;
end;

procedure TForm1.MultByRes(value : TFGInt);
var
  S    : AnsiString;
  temp : TFGInt;
begin
  Cr.Enter;
    inc(threadsTerminated);
    temp := res;
    FGIntMul(temp, value, res);
    if threadsTerminated = 2
    then
      Begin
        MessageBox(0, PChar(IntToStr(GetTickCount()-Timer)), 'Time', 0);
        FGIntToBase10String(res, s);
        MessageBox(0, PChar(s), 'Value', 0);
      End;

  Cr.Leave;
end;

end.

Автор: Alexeyt 25.2.2007, 22:07

Народ, в чем проблема факториал посчитать?
Берем тип Extended (чтобы не было переполения. Int64 не хватит).

Код


R:= 1;
for i:= 1 to N do
  R:= R * i;

Умножаем в цикле рез-т на i, увеличивая i. Никакой рекурсии не нужно.
Естетвенно, на больших N будет потеря точности. Т.к. Extended тоже ограничен.

Автор: Alexeis 26.2.2007, 12:30

Цитата(Alexeyt @ 25.2.2007, 22:07

)

Народ, в чем проблема факториал посчитать?
Берем тип Extended (чтобы не было переполения. Int64 не хватит).

В невнимательном чтении топа. Уже написали же, что Extended - позволяет хранить числа примерно до 10^4000, 10000! это число порядка 10^35000.

Автор: Magnetto 27.2.2007, 18:33

что мешает тебе создать динамический(чтоб память економить) массив байтового типа...аля длинная арифметика...где 1 ячейка масива будет отвечать одной цифре этого большучего числа...
или...еще лучше создать тот же динамический масив из записи....где запись - переменная куда можно впихнуть 8-9 цифр...
тогда...масив из 20000-30000 ячеек сможет вмещать 180000-210000 цифр....думаю факториал 10000 вместится...

если заинтересовался - могу поподробней описать как умножать масив на масив...вплоть до подогнания исходника(так оно впринципе все просто пишется...просто разобратся нада)
=)..
насчет скороссти работы такого алгоритма ничего сказать не могу...ибо такой способ юзал только в паскале..там оно относительно надолго считало...

Автор: Stream86 21.10.2007, 18:01

Кто отлично разобрался с FGInt? Нужна помощь:
У меня есть 3 числа a,b,c. Как с помощью FGInt реализовать: а вознести в степень b, и результат взять по модулю с.
я делаю так, но возвращает пустой стринг:

Код


var a,b,c,res:TFGInt; ss,ss2,ss3,xx:string;
begin
ss:='5';
ss2:= '2';
ss3:='2';
Base256StringToFGInt(ss,a);
Base256StringToFGInt(ss2,b);
Base256StringToFGInt(ss3,c);
FGIntMulMod(a,b,c,res);
FGIntToBase256String(res,xx);
showMessage(xx);
end;

Автор: Stream86 21.10.2007, 22:24

разобрался:

Код


var a,b,c,res:TFGInt; ss,ss2,ss3,xx,ress:string;
begin
ss:='300';
ss2:= '23';
ss3:='31';
Base10StringToFGInt(ss,a);
Base10StringToFGInt(ss2,b);
Base10StringToFGInt(ss3,c);
FGIntModExp(a,b,c,res);
FGIntToBase10String(res,xx);
showMessage(xx);