Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.96/25: Рейтинг темы: голосов - 25, средняя оценка - 4.96
0 / 0 / 2
Регистрация: 23.02.2015
Сообщений: 5

Длинная арифметика. Факториал

23.02.2015, 20:54. Показов 5110. Ответов 6
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый вечер, господа программисты.

Сижу сейчас и разбираюсь с кодом для вычисления факториала из Окулова (задание 10, программа 5). Вот код без изменений из книги.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
{$R+}
program my10_5;
uses crt;
const maxn = 300;
var a: array [0..maxn] of longint;
    n: longint;
    i,j,r,w: longint;
begin clrscr;
  fillchar(a,sizeof(a),0);
  write('Введите число N, факториал которого нужно подсчитать --> ');
  readln(n);
  a[0] := 1; a[1] := 1; j := 2;
  while (j <= n) and (a[0] < maxn) do
    begin
      r := 0; i := 1;
      while (i <= a[0]) or (r <> 0) do
        begin
          w := a[i]*j+r;
          a[i] := w mod 10;
          r := w div 10;
          if [U]a[a[0]+1] <> 0[/U] then inc(a[0]);
          inc(i);
        end;
      inc(j);
    end;
  write(n,'! = ');
  for i := a[0] downto 1 do write(a[i]);
  readln;
end.
Всё вроде бы верно, но для факториала 27! возникает ошибка (большие числа не пробовал). Программа выдаёт 888869450418352160768000000, а двух цифр вначале не хватает: 10888869450418352160768000000.

Проблема, как мне кажется, в подчёркнутом условии. Ведь при выходе факториала за прежние границы массива первая цифра вне границ вполне может быть нулём, как в 27!, а исходник этого не учитывает.
При замене указанного условия на i > a[0] (цифра с номером, большим, чем изначально указанный) всё становится на свои места.

Пожалуйста, подскажите, прав ли я.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
23.02.2015, 20:54
Ответы с готовыми решениями:

длинная арифметика!
Вычислить точное значение эн в степени эн факториал!

Длинная арифметика
Требуется вычислить факториал целого числа N. Факториал обозначают как N! и вычисляют по формуле: N! = 1 * 2 * 3 * … * (N-1) * N,...

длинная арифметика
помогите мне из этого умножения сделать сложение препод сказал тут нужно поменять умножить на плюс но я че тока не менял не получается( {...

6
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
24.02.2015, 07:08
Лучший ответ Сообщение было отмечено CbIncus как решение

Решение

Молодец! Возьми с полочки конфетку.

Я, к примеру, не стал бы описывать массив четырёхбайтовых элементов для хранения значений не превышающих байта (0..10 — это 1/25 от байта) !
Есть некоторая задержка при приведении больших чисел к меньшим, но выигрыш в памяти даст получить факториал для более больших чисел.

(Вообще не понятно почему размерность выбрана именно до 300 цифр? Всего лишь 170! имеет в своём составе уже 307 цифр.)

Только вот длину числа нужно вывести в отдельную переменную.

Короче! Я бы переписал всё примерно вот так:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const
  { Искать факториал для чисел не больше 7000 }
  LongLength = 25000; { В числе 7000! цифр будет не больше }
 
var
  LongLen : Word;
  Long : array [0..LongLength] of Byte;
  N, LongN, i : Word;
  D : Word;
begin
  Write('N = '); ReadLn(N);
  
  { Сюда бы по идее вставить обработчик правильности ввода числа не больше 7000 }
  
  LongN   := 1; { В массиве хранится факториал числа }
  LongLen := 0; { Длина массива }
  Long[0] := 1; { Данные массива }
  
  while LongN < N do { Пока не получен факториал искомого числа }
    begin
      Inc(LongN); { Сейчас получим факториал для числа }
      
      { Умножение Long на LongN }
      D := 0;
      for i := 0 to LongLen do
        begin
          D := D + LongN * Long[i]; { Приведение типов к Word }
          (* Нужно быть уверенным, что D+7000*9 не больше 65535. *)
          
          Long[i] := D mod 10;
          D := D div 10;
        end;
        
      { Перенос десятичных значений скинем в Long }
      while D > 0 do
        begin
          Inc(LongLen);
          if LongLen > LongLength then { Переполнение }
            begin
              WriteLn('Произошло переполнение при нахождении ', LongN, '!');
              Halt(-1);
            end;
            
          Long[LongLen] := D mod 10;
          D := D div 10;
        end;
    end;
  
  Write(N, '! = '); for i := LongLen downto 0 do Write(Long[i]); WriteLn;
  WriteLn('Длина числа = ', LongLen);
  i := 0; while Long[i] = 0 do Inc(i);
  WriteLn('Число нолей в конце числа = ', i);
end.
Если захотите переделать под более большие числа, то переменную накопления десятичных переносов нужно изменить на Longint.
1
0 / 0 / 2
Регистрация: 23.02.2015
Сообщений: 5
24.02.2015, 15:49  [ТС]
Спасибо! Оригинальный код, нигде такого не встречал.
0
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
25.02.2015, 07:04
Как бы ты его встретил, если я его для тебя написал?
0
Эксперт Pascal/Delphi
2388 / 1300 / 1492
Регистрация: 29.08.2014
Сообщений: 4,665
25.02.2015, 07:50
а если брать по большему основанию чем 10, например 100 для типа byte, вместо 10, то и размер массива хранения чисел вполовину сократится
1
0 / 0 / 2
Регистрация: 23.02.2015
Сообщений: 5
25.02.2015, 08:50  [ТС]
Цитата Сообщение от JuriiMW Посмотреть сообщение
Как бы ты его встретил, если я его для тебя написал?
Хотя бы что-то наподобие. Но нет - так и не нашёл.
Видел ещё у Полякова в учебнике вариант, где в элементы массива записывались числа по 8 цифр из факториала. Тоже нужно будет попробовать.
0
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,059
25.02.2015, 09:26
Joy, только арифметика немного усложнится!
Не в данном конкретном случае, а при разработке своего модуля „длинной арифметики“.

Появятся проблемы с переполнением при выполнении простых арифметических операций, а значит появятся затруднения при отладке!

9 · 9 = 81 — влезет в байт. Нужно будет только сделать перенос десятичных регистров.
99 · 99 = 9801 — уже не лезет в байт. Следовательно нужно тратиться на приведение типов… Это — дополнительное время!

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

К примеру:

Ячейки:Значения = [00:00][01:11][02:01][03:10][04:01]
Что должно быть представлено публике как 110011100.
Если же не учитывать вышеприведённое условие добавление нолей, то кто-то может вывести так: 1101110.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.02.2015, 09:26
Помогаю со студенческими работами здесь

Длинная арифметика
Так вот я неаписал программу на сложение. Все с ней норм, а вот с произведением не идет почемуто. Найдите ошибки если не сложно. В...

Длинная арифметика
Уважаемые, помогите решить задачку, горит ужасно помогите пожалуста, срочно надо: 1.Составить программу для вычисления числа (2^64) –1, в...

Длинная арифметика.Чтение и вывод.
Нашел процедуры чтения и выводы длинных чисел. Но есть несколько вопросов. procedure ReadLong(var f:text;a:Plong); var ch:char; ...

Формирование матрицы, длинная арифметика.
1)натуральное число (длинное целое) можно представить в виде произведения нескольких натуральных чисел (не менее двух) разными...

Сортировка массивов и длинная арифметика
Ребят, помогите пожалуйста. Очень нужен ПОЛНЫЙ КОД. Вот задачи: 1. В городе имеется m банков. Известны величины задолженностей банков...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
PowerShell Snippets
iNNOKENTIY21 11.11.2025
Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru