Сложение беззнаковых длинных целых

Чтение и вывод чисел в такой модели реализуется через строковый тип и в дополнительном описании не нуждается. Рассмотрим сложение двух неотрицательных чисел, каждое из которых сохранено в виде последовательности цифр.

Рис. 40. Поразрядное суммирование

Очевидно, при поразрядном суммированиичисел, которое начинается с конца строки, каждый разряд результата определяется по сумме трёх величин – переноса и соответствующих разрядов операндов. В разряд записывается остаток от деления этой суммы на 10, а переносом в следующий разряд идёт частное от деления нацело этой суммы на 10.

Рассмотрим задачу, иллюстрирующую применение такого подхода

Задача №215.  Длинные A+B

Найти сумму чисел A и B

Входные данные

В двух строках записаны числа Aи B, не превышающие 10¹⁰⁰⁰

Выходные данные

Одно число – сумма A и B.

Решение

#include <iostream>

using namespace std;

int main(){

string a, b, c = "";

cin >> a >> b;

int lena = a.length()-1, lenb = b.length()-1,

     maxl = max(lena, lenb), carry = 0, op1, op2;

for(int i=0;i<=maxl;i++){

     op1 = i<=lena ? a[lena-i]-'0' : 0; 

     op2 = i<=lenb ? b[lenb-i]-'0' : 0;

     c = char((op1 + op2 + carry) % 10 + '0') + c;

     carry = (op1 + op2 + carry) / 10;

}

if(carry) c = char(carry + '0') + c;

cout << c;

}

Задача №216.  2^N (acmp.ru)

Необходимо вычислить значение 2ⁿ.

Входные данные

В единственной строке входного файла INPUT.TXT записано натуральное число n (0 < n < 1000).

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести значение 2ⁿ.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3	8
2	10	1024
3	72	4722366482869645213696

Решение

Воспользуемся моделью представления «число=строка». Данное решение можно использовать для любого K^N, при K≤9

#include <fstream>

#include <algorithm>            //описаниеreverse

#define BASE 2

using namespace std;

int main(){      

ifstream cin("input.txt");

ofstream cout("output.txt");

string ans="1", tmp;

int power,len, carry, expr,last;

cin >> power;

for(int i=1;i<=power;i++){

   tmp=ans;

   len=tmp.length();

   ans.clear();

   carry=0;

   for(intj=0;j<len;j++){  //каждый раз умножаем столбиком

       expr = (tmp[j]-'0')*BASE + carry;

       last = expr%10;          //последняяцифра

       carry = expr/10;         //перенос

       ans.push_back('0'+last);

   }

   if(carry)ans.push_back('0'+carry); //последний перенос

}

reverse(ans.begin(),ans.end());  //переворачиваем строку

cout << ans;

}

В строке ans хранится в символьной форме результат последнего умножения на BASE. Строка tmpявляется промежуточной и используется для временного хранения результата перед возведением в следующую степень.

Задача №217.  Длинный факториал

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

N! = 1 * 2 * 3 * … * (N-1) * N, причем 0! = 1.

Так же допустимо рекуррентное соотношение: N! = (N-1)! * N

Входные данные

В единственной строке записано одно целое неотрицательное число N (N < 1000).

Выходные данные

Вывести одно целое число — значение N!

Пример

№	Ввод	Вывод
1	6	720
2	17	355687428096000

Решение

#include <iostream>

using namespace std;

string mult(string x, int y){ //полудлинное умножение через строку

int carry = 0, t;

string result = "";

for (int i = x.size() - 1; i >= 0; i--){

    t = int(x[i] - '0')*y + carry;

   carry = t/10;

   result = char(t%10 + '0')+result;

}

while(carry){         //в разряде переноса остались цифры

   result = char(carry%10 + '0') + result;

   carry /= 10;

}

return result;

}

 

int main(){

int n;

string str = "1";

cin >> n;

for(int i = 2; i <= n; i++) str = mult(str, i);

cout << str << endl;

}

ВАЖНО: Одним из преимуществ данной модели представления длинных чисел является простота операций деления

Задача №218.  Очень длинное число

Учитель математики Сергей Иванович хочет проверить, какой остаток дает число 19202122…979899 (подряд записаны двузначные числа от 19 до 99) при делении на 3¹, 3², 3³ и 3⁴. Сергей Иванович подозревает, что число делится без остатка на все указанные делители. Помогите ему проверить, прав ли он.

Подсказка: признак делимости по сумме цифр как для чисел 3 и 3²=9 в случае 3³ и 3⁴ не применим.

Выходные данные

YES если Сергей Иванович прав, NO– если он ошибается.

Решение

Сохраним число Сергея Ивановича в строковый поток stringstreamst, а затем будем его посимвольно считывать. Воспользуемся модификацией деления методом «уголка».

 1920212223...99│ 81

-162│ 23...

300

 -243

57 и т.д.

Проиллюстрируем это на примере табличного процессора

Рис. 41. Решение задачи "Очень длинное число" в табличном процессоре

Если последний остаток в итоге окажется нулевым, значит Сергей Иванович прав.

#include <iostream>

#include <sstream>

using namespace std;

int main(){

string s;

string streamst(s);  // связываем поток st со строкой s

for(int i = 19; i <= 99; i++) st << i;//записываем число в поток

char t;

int temp=0;

for (int i = 1; i <= 3; i++){

     st >> t;

     (temp *= 10) += t - '0';

}

while (st >> t){  

((temp %= 81) *= 10) += t - '0';

cout << (temp % 3 ? "NO" : "YES");

}

В итоге Сергей Иванович окажется прав J

 

19.2 Модель 10^n

Представление числа напоминает представление многочлена, только вместо x в соответствующей степени имеем основание β в нужной степени. Как известно, многочлен a₀ + a₁x + a₂x² + … + a_nxⁿ удобно представлять в виде массива, элементы которого представляют коэффициенты a_i, а индекс i — определяет соответствующую степень x. Длинное число хранится аналогично, осталось определиться с выбором основания β.

Например, то же самое число 123456789 можно представить в десятитысячной (β = 10⁴) системе счисления следующим образом:

123456789₁₀ = 1*(10⁴)² + 2345*(10⁴)¹ + 6789*(10⁴)⁰

Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества:

1. сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789);

2. значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа. В общем, компьютер одинаково быстро складывает одноразрядные и 32-разрядные числа, поэтому этим следует воспользоваться.

 

Задача №219.  Сумма произведений (acmp.ru)

Требуется вычислить сумму произведений цифр каждого N-значного числа. При этом следует учесть, что если в числе встречается цифра 0, то произведение его цифр равно нулю. Для N=3 искомая сумма представлена следующим рядом:

S = 1*0*0 + 1*0*1 + 1*0*2 + … + 9*9*8 + 9*9*9 = 91125

Входные данные

В единственной строке записано натуральное число N (N < 1000).

Выходные данные

В единственную строку нужно вывести одно целое число — сумму произведений всех N-значных чисел.

Примеры

№	Ввод	Вывод
1	1	45
2	3	91125
3	5	184528125

Решение

Легко заметить, что требуемые числа S_nобразуют геометрическую прогрессию с шагом 45. В самом деле, если S₁=45, то

аналогично для S₃ и т.д.

#include<cstdio>

#define SIZE 400                     //ячеек в массиве

#defineBASE 1000000             //основание системы счисления

intn, i, a[SIZE]={45,};         //a[0]=45,остальныенули

int main(){

scanf("%d",&n);

for(;--n;){                 //вычисление 45^n

   for(i=0; i<SIZE; i++) a[i] *= 45;

   for(i=0; i<SIZE-1; i++){

       a[i+1] += a[i] / BASE;

       a[i] %= BASE;

   }

}

for(i=SIZE; !a[--i];); //вывод ячеек длинногочисла

printf("%d",a[i]);           //первая ненулевая как есть

for(;i--;) printf("%.6d",a[i]); //остальные с нулями спереди

}