Okorosso

двойной факториал для длинной арифметики

May 6th, 2021
789
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <string>
  5. #include <vector>
  6.  
  7. // сишный стиль для упрощения вывода незначащих нулей для ячеек, кроме поседней
  8. typedef std::vector<int> lnum; // вектор интов становится типом лнам
  9. const int base = 1000 * 1000 * 1000; // сколько цифр в одной ячейке
  10.  
  11. void print(lnum a) { // функция вывода
  12.     bool flag = false; //это флаг для вывода самой последней ячейки
  13.     FILE *fout = fopen("output.txt", "a"); // открыти файла на запись
  14.     for (int i = a.size() - 1; i >= 0; i--)
  15.         if ((a[i] != 0) || (a[i] == 0 && flag == 1)) { // проверка, является ли наша ячейка последней
  16.             if (flag == 0) {
  17.                 flag = true;
  18.                 fprintf(fout, "%d", a[i]); // вывод ячейки, д - это число
  19.             } else
  20.                 fprintf(fout, "%09d", a[i]); // вывод незначащих нулей в ячейке
  21.         }
  22. }
  23.  
  24. lnum toVec(std::string &str) { // преобразование строки в длинное число
  25.     lnum toReturn; // переменная для возращаемого числа
  26.     for (int i = (int) str.length(); i > 0; i -= 9)
  27.         if (i < 9)
  28.             toReturn.push_back(atoi(str.substr(0, i).c_str())); // если менше 9, то заполняем от 0 дл i число
  29.         else
  30.             toReturn.push_back(atoi(str.substr(i - 9, 9).c_str())); // заполняем зеркално
  31.     return toReturn;
  32. }
  33.  
  34.  
  35. lnum multiply(lnum a, lnum b) { // умножение длинных чисел
  36.     lnum c(a.size() + b.size()); // число длинной, равной сумме длин двух умножаемых чисел
  37.     for (size_t i = 0; i < a.size(); ++i)
  38.         for (int j = 0, carry = 0; j < (int) b.size() || carry; ++j) { // ВАЖНО, т.к у нас условие с ИЛИ,
  39.             // то наш итератор для второго числа может быть больше длины второго числа, поэтому строкой ниже
  40.             // в тернарке мы проверяем вышли ли мы за длину Б, и если вышли, то домножаем на 0,
  41.             // чтобы не выйти за пределы массива и добавляем туда остаток от предудыщего деления,
  42.             // и получаем текущее число, с которым работаем ниже
  43.             long long cur = c[i + j] + a[i] * 1ll * (j < (int) b.size() ? b[j] : 0) + carry;
  44.             c[i + j] = int(cur % base); // закидываем в ячейку нового числа текущее число, мод деления на основание
  45.             carry = int(cur / base); // записываем в остаток деленное текущее число на основание
  46.         }
  47.     while (c.size() > 1 && c.back() == 0) // удаляем незначащие нули
  48.         c.pop_back();
  49.     return c;
  50. }
  51.  
  52.  
  53. lnum doubleFact(int n) { // нахождение двойного факториала
  54.     std::string one = "1";
  55.     lnum res = toVec(one); // в лнаме по умолчанию лежит единичка
  56.     for (int i = n; i >= 2; i -= 2) { // проходим циклом от н до нуля с шагом 2, чтобы четные оставались четными,
  57.         // а нечетные нечетными
  58.         std::string toMultiply = std::to_string(i); // конвентируем в строку итератор
  59.         lnum toMult = toVec(toMultiply); // создаем лнам, равный итератору, используя переменную строкового типа выше
  60.         res = multiply(res, toMult); // перемножаем число с предыдущего шага (или 1 при первой итерации) и итератор
  61.     }
  62.     return res;
  63. }
  64.  
  65.  
  66. int main() {
  67.     using namespace std;
  68.     ifstream cin("input.txt");
  69.     ofstream cout("output.txt");
  70.     int n;
  71.     cin >> n;
  72.  
  73.     lnum result = doubleFact(n);
  74.     print(result);
  75.  
  76.     return 0;
  77. }
  78.  
RAW Paste Data