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

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

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

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

Сижу сейчас и разбираюсь с кодом для вычисления факториала из Окулова (задание 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.02.2015, 20:54
Ответы с готовыми решениями:

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

Длинная арифметика
Требуется вычислить факториал целого числа N. Факториал обозначают как N! и вычисляют по формуле: ...

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

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

6
5079 / 2651 / 2349
Регистрация: 10.12.2014
Сообщений: 10,028
24.02.2015, 07:08 2
Лучший ответ Сообщение было отмечено 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  [ТС] 3
Спасибо! Оригинальный код, нигде такого не встречал.
0
5079 / 2651 / 2349
Регистрация: 10.12.2014
Сообщений: 10,028
25.02.2015, 07:04 4
Как бы ты его встретил, если я его для тебя написал?
0
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
25.02.2015, 07:50 5
а если брать по большему основанию чем 10, например 100 для типа byte, вместо 10, то и размер массива хранения чисел вполовину сократится
1
0 / 0 / 2
Регистрация: 23.02.2015
Сообщений: 5
25.02.2015, 08:50  [ТС] 6
Цитата Сообщение от JuriiMW Посмотреть сообщение
Как бы ты его встретил, если я его для тебя написал?
Хотя бы что-то наподобие. Но нет - так и не нашёл.
Видел ещё у Полякова в учебнике вариант, где в элементы массива записывались числа по 8 цифр из факториала. Тоже нужно будет попробовать.
0
5079 / 2651 / 2349
Регистрация: 10.12.2014
Сообщений: 10,028
25.02.2015, 09:26 7
Joy, только арифметика немного усложнится!
Не в данном конкретном случае, а при разработке своего модуля „длинной арифметики“.

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

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

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

К примеру:

Ячейки:Значения = [00:00][01:11][02:01][03:10][04:01]
Что должно быть представлено публике как 110011100.
Если же не учитывать вышеприведённое условие добавление нолей, то кто-то может вывести так: 1101110.
0
25.02.2015, 09:26
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.02.2015, 09:26
Помогаю со студенческими работами здесь

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

Длинная арифметика.Чтение и вывод.
Нашел процедуры чтения и выводы длинных чисел. Но есть несколько вопросов. procedure ReadLong(var...

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

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

Сортировка вставками.множества.длинная арифметика..
Завтра надо сдать практику иначе отчислят......помогите решить хоть что нибудь 1)Сортировка...

Длинная арифметика. Вычислить точное значение (n в степени n)!
Помогите пожалуйста вычислить точное значение на Pascal: (nn)!


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru