вторник, 17 августа 2010 г.

Вывод длинных чисел

[Вся длинная арифметика]
Вывод длинных чисел тесно связан с вводом). Опять же рассмотрим два случая для osn = 10 и для osn = 10000.

Первый случай:

  1. void output()
  2. {
  3.   for (int i=amount-1;i>=0;i--)
  4.     cout<<digits[i];
  5. }
* This source code was highlighted with Source Code Highlighter.

Второй случай:

  1. int len = 4;
  2. const char * digitFormat = "%.4d";
  3. ...
  4. void output()
  5. {
  6.   printf("%d",digits[amount-1]);
  7.   for (int i= amount-2;i>=0;i--)
  8.     printf(digitFormat,digits[i]);
  9. }
* This source code was highlighted with Source Code Highlighter.

Отметим важный факт во втором случае. Дело в том, что цифра при osn = 10000 может оказаться не четырехзначной. В таком случае нужно побеспокоиться, чтобы она выводилась с лидирующими нулями. Это не касается первой цифры, поэтому ее вывод реализован отдельно

7 комментариев:

  1. При наличии подпоследовательностей с нулями может лучше цикл во втором выводе реализовать так:

    for (int i=v.size()-2;i>=0;i--) {
    int len2=len;
    if (!v[i])
    while(--len2) cout<<0;
    else
    while (v[i]<pow(10.0,--len2)) cout<<0;
    cout<<v[i];
    }

    (у меня v - вектор)

    ОтветитьУдалить
    Ответы
    1. Все содержимое Вашего цикла можно заменить на printf("%04d", v[i]) (len=10000), что, собственно, и реализовано в нашем примере. Ваш вариант очень громоздкий, да и работает в несколько раз дольше.

      Удалить
    2. или так через cout:
      cout<<setw(len)<<setfill('0')<<v[i];

      Удалить
    3. Можно и так. Дело вкуса. От себя могу добавить, что использование функции pow для работы с целыми числами - плохая идея. Если очень хочется много оперировать степенями какого-либо целого числа N, то лучше заранее подготовить массив, например такой: _pow[i] = N^i. Размеры массива будут невелики, прекалк не займет много времени, зато потом возведение числа в степень будет работать за O(1)

      Удалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить
  3. На e-maxx увидел, что основание сс = 1000000000, т.е хранят по 9 элементов. А возможна ли реализация с основанием сс 2^32? И много ли придется поменять в арифметических операциях?

    ОтветитьУдалить
    Ответы
    1. основание в 9 знаков(1e9) используется как правило для сложения и/или вычитания. Это связано с тем, что промежуточные вычисления не будут превышать 2e9, что укладывается в знаковый int(4 байта). Если же речь идет об умножении, то здесь максимальная основание стоит брать как 1e4, чтобы промежуточные вычисления укладывались в 1e8.

      Если в качестве основания использовать степень двойки и хранить все в int, то максимальное основание будет 2^30 для знакового int и 2^31 для беззнакового. Это относится к операции сложения. Для умножения можете аналогично подсчитать, как это сделано для основании в виде степени десятки. Оперируя основание в виде степени двойки нужно подумать наперед о быстром переводе этого числа в нужную систему счисления. Тут на помощь могут прийти подходы перевода числа из 16/8/4- ричной системы в двоичную.

      Удалить