Информатика • 11 класс

Задачи длинной арифметики. Многоразрядные целые числа (C++)

Ограниченность встроенных типов данных. Например, даже 64-битное целое число не может содержать более 20 десятичных цифр, в то время как реальные задачи могут требовать работы с числами в сотни и тысячи цифр.
Ключевые проблемы:
- эффективное хранение – как компактно представить многоразрядное число;
- реализация операций – алгоритмы сложения, умножения, деления усложняются при работе с массивами;
- производительность – наивные реализации работают неприемлемо медленно;
- оптимизация памяти – баланс между скоростью и использованием ресурсов.
  Пример. Подсчитать факториал 100 (100!).
  #include ＜iostream＞
  using namespace std;
  const int N = 33, int d = 1000000;
  int i, j, k, s;
  long mas [N + 1];
  int main () {
    mas [0] = 1;
    for (j = 2; j <= 100; j++) { k = 0;
      for (i = 0; i <= N; i++) {
        s = mas [i] * j + k; mas [i] = s % d;
        k = s / d; } }
    bool first = true;
    for (i = N; i >= 0; i--) {
      if (mas [i] != 0 || !first) { if (first) {
        cout << mas [i]; first = false; }
      else { cout << mas [i]; } } }
  return 0; }

Было полезно?