Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом
Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »

Вопрос # 3 759

Раздел: Delphi » Алгоритмы, преобразования
/ вопрос открыт /

Доброго времени суток, уважаемые эксперты!
Попалась задачка, думал легкая, однако повозился значительно, может и для вас покажется интересной.
Задача проста найти факториал 2010.
Все известные типы чисел неподдерживают такое количество символов. В голову пришло считать разрядно т.е:
если 1ый разряд, состоящий из 9ти символов, переполняется то переполняемую единицу переношу во второй разряд и т.д
I1:=I1*I;
if I1 div 1000000000>0 then
begin
I2:= I2*I+(I1 div 1000000000);
I1:=I1 mod 1000000000;
if I2 div 100000000>0 then ...
все это внутри цикла i:=0 to 2010, I1..I12 -12 9ти разрядных(в моем случае) числел. Алгоритм вроде вернуый но после 40! заходит в 0 хотя предел в 12*9 символов не пройден, ошибок в нем нет(все повторяется подобно).
Подумал, может тут помогут, да и вообще заинтересует эта задача=) Спасибо.
З.Ы второй алгоритм выглядет более компактно но почему то условие игнорируется даже при True значении, тут надеюсь подскажите мой косяк в процедуре.

Приложение:
  1. procedure TForm3.Button1Click(Sender: TObject);
  2. var
  3. I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12:int64;
  4. I,S:integer;
  5. St:string;
  6. begin
  7. I1:=1;
  8. I2:=0;
  9. I3:=0;
  10. I4:=0;
  11. I5:=0;
  12. I6:=0;
  13. I7:=0;
  14. I8:=0;
  15. I9:=0;
  16. I10:=0;
  17. I11:=0;
  18. I12:=0;
  19. for i := 1 to 2022 do
  20. begin
  21. I1:=I1*I;
  22.  
  23. if I1 div 1000000000>0 then
  24. begin
  25. I2:= I2*I+(I1 div 1000000000);
  26. I1:=I1 mod 1000000000;
  27. if I2 div 100000000>0 then
  28. begin
  29. I3:= I3*I+(I2 div 1000000000);
  30. I2:=I2 mod 1000000000;
  31. if I3 div 100000000>0 then
  32. begin
  33.  
  34. I4:= I4*I+(I3 div 1000000000);
  35. I3:=I3 mod 1000000000;
  36. if I4 div 100000000>0 then
  37. begin
  38.  
  39. I5:= I5*I+(I4 div 1000000000);
  40. I4:=I4 mod 1000000000;
  41. if I5 div 100000000>0 then
  42. begin
  43.  
  44. I6:= I6*I+(I5 div 1000000000);
  45. I5:=I5 mod 1000000000;
  46. if I6 div 100000000>0 then
  47. begin
  48.  
  49. I7:= I7*I+(I6 div 1000000000);
  50. I6:=I6 mod 1000000000;
  51. if I7 div 100000000>0 then
  52. begin
  53.  
  54. I8:= I8*I+(I7 div 1000000000);
  55. I7:=I7 mod 1000000000;
  56. if I8 div 100000000>0 then
  57. begin
  58.  
  59. I9:= I9*I+(I8 div 1000000000);
  60. I8:=I8 mod 1000000000;
  61. if I9 div 100000000>0 then
  62. begin
  63.  
  64. I10:= I10*I+(I10 div 1000000000);
  65. I9:=I9 mod 1000000000;
  66. if I10 div 100000000>0 then
  67. begin
  68.  
  69. I11:= I11*I+(I10 div 1000000000);
  70. I10:=I10 mod 1000000000;
  71. if I11 div 100000000>0 then
  72.  
  73. I12:= I12*I+(I11 div 1000000000);
  74. I11:=I11 mod 1000000000;
  75. end;
  76. end;
  77. end;
  78. end;
  79. end;
  80. end;
  81. end;
  82. end;
  83. end;
  84. Edit1.Text:=Inttostr(I1);
  85. Edit2.Text:=Inttostr(I2);
  86. Edit3.Text:=Inttostr(I3);
  87. Edit4.Text:=Inttostr(I4);
  88. Edit5.Text:=Inttostr(I5);
  89. Edit6.Text:=Inttostr(I6);
  90. Edit7.Text:=Inttostr(I7);
  91. Edit8.Text:=Inttostr(I8);
  92. Edit9.Text:=Inttostr(I9);
  93. Edit10.Text:=Inttostr(I10);
  94. Edit11.Text:=Inttostr(I11);
  95. Edit12.Text:=Inttostr(I12);
  96. memo1.Lines.Add(Edit6.Text+Edit5.Text+Edit4.Text+Edit3.Text+Edit2.Text+Edit1.Text);
  97. end;
  98. end;
  99.  
  100.  
  101. procedure TForm3.TryAnother;
  102. var
  103. T:array [1..11] of integer;
  104. i,x,tc:integer;
  105. str:string;
  106. begin
  107. T[1]:=1;
  108. for x := 2 to 11 do
  109. begin
  110. T[x]:=0;
  111. end;
  112. for i := 1 to 20 do
  113. begin
  114. for tc := 0 to 10 do
  115. T[1]:=T[1]*I;
  116. if (T[tc] div 1000000000)>0 then
  117. begin
  118. T[TC+1]:= T[tc+1]*I+(T[TC] div 1000000000);
  119. T[Tc]:=T[tc] mod 1000000000;
  120. end;
  121. end;
  122. for x := 0 to 11 do
  123. begin
  124. Str:=str+(inttostr(T[11-x]));
  125. memo1.Text:=str;
  126. end;


TeM Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: TeM (статус: Посетитель)
Вопрос отправлен: 11 февраля 2010, 22:01
Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: min@y™

Вот тебе решение: модуль для работы с большими числами.

Цитата:


Это модуль для работы с очень большими числами без потери точности. Модуль даёт возможность манипулирования с 10000 и более значащими цифрами в числах. В модуле реализованы сложение, вычитание, умножение, деление, возведение в целую степень и факториал. Все функции в качестве аргументов принимают длинные строки и результат выдают тоже в виде строки.

Ответ отправил: min@y™ (статус: Доктор наук)
Время отправки: 12 февраля 2010, 08:25
Оценка за ответ: 4

Комментарий к оценке: Недумал что эта тема есть в FAQ, спс

Мини-форум вопроса

Всего сообщений: 3; последнее сообщение — 12 февраля 2010, 10:53; участников в обсуждении: 3.
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 12 февраля 2010, 05:45 [#1]:

решение этой задачи рассматривалось в журнале "Квант" году этак в 1988. Для хранения больших чисел использовались строковые переменные.
Егор

Егор (статус: 10-ый класс), 12 февраля 2010, 06:21 [#2]:

Цитата (TeM):

I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12:int64;
...
I1:=1;
I2:=0;
I3:=0;
I4:=0;
I5:=0;
I6:=0;
I7:=0;
I8:=0;
I9:=0;
I10:=0;
I11:=0;
I12:=0;
в те далёкие-далёкие времена, когда люди ещё не изобрели массивы...

или навеяно моим ответом на вопрос вопрос 3718?
Опасайтесь багов в приведенном выше коде; я только доказал корректность, но не запускал его.
— Donald E. Knuth.
TeM

TeM (статус: Посетитель), 12 февраля 2010, 10:53 [#3]:

Егор, первый алгоритм расписан полностью чтобы проследить наличие всевоззможных ошибок, если посмотреть второй алгоритм, то в нем видна и работа с массивом и решение "нагруженности" кода.
Андрей, в 1988 году небыло у меня журналов вообще=)Хранить в строковых переменных конечно можно, но как же потом с ними работать если длина числового значения всеравно лимитирована(только если по частям из строки выбирать числа и их перемножать замещая ответом умноженные величины?).
Min@y™, спасибо, сейчас попробую разобраться.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
Версия движка: 2.6+ (26.01.2011)
© 2005-2025
Текущее время: 31 октября 2025, 19:01
Выполнено за 0.03 сек.