Ввод длинного числа с клавиатуры

Поскольку мы не можем прочитать вводимое число ни в какой стандартный целочисленный тип, прочитаем его в строку:

char s [1000];

…

После этого каждый символ строки превратим в цифру и запишем ее в массив a.

Обратите внимание: последний символ попадает в первый элемент массива, предпоследний – во второй и т.д.

Не забудьте изначально обнулить массив с!

Как это будет на Си?

Сразу будем пользоваться строками!

char a[1000], b[1000], c[1000] = {‘0’};

Читаем числа a и b слева – направо (от старших разрядов к младшим). Вот пример для ввода числа a:

int a[1000], b[1000], c[1000] = {‘0’};

int i, n;

char r;

gets(a);

n = strlen(a);

// реверс строки от младших разрядов к старшим

for (i=0; i < n/2; i++) {

r = a[i];

a[i] = a[n - i - 1];

a[n - i - 1] = r;

}

puts(a);

// и добавляем нули (цифры ноль!) в конец строки

memset ( a + n, ‘0’, 1000 - n );

Сложение двух чисел

Сложение выполняется “столбиком”:

	a[1]	a[2]	a[3]	a[4]	a[5]	…
+
	b[1]	b[2]	b[3]	b[4]	b[5]	…
	с[1]	с[2]	с[3]	с[4]	с[5]	c[6]	…

При этом нужно позаботиться о переносах:

1. перенос сразу записывается в другой разряд

2. при сложении учитывается перенос из предыдущего разряда

Код получается очень простой и симметричный:

s := a[i] + b[i] + c[i]; // складываем a[i] c b[i], учитываем перенос из предыдущего разряда

с[i] := s mod 10; // последнюю цифру s записываем в c[i]

c[i+1] := s div 10; // записываем перенос в следующий разряд

Это мы делаем циклом для всех i от 1 до 1000. Именно здесь нам и будет важен тот факт, что пустые ячейки массивов a и b были заполнены нулями. Тогда и все ненужные ячейки массива с также будут заполнены нулями.

Цифры и ASCII-коды в Си

for (i = 0; i < 999; i++) {

// складываем a[i] c b[i], учитываем перенос из предыдущего разряда

s = a[i] + b[i] + c[i] - 3*'0';

c[i] = '0' + s % 10; // последнюю цифру s записываем в c[i]

c[i+1] = '0' + s / 10; // записываем перенос в следующий разряд

}

Вывод числа на экран

Вывод длинного числа состоит из двух этапов.

1. Идя по массиву справа налево найдем “начало” (старший разряд) числа:

i:=1000;

while s[i]=0 do // ищем первую ненулевую цифру

I := i+1

2. Выводим все цифры справа налево, начиная с найденной:

for j := I downto 1 do

write(s[i]);

Как это сделать в Си

i = 999;

while (c[i]== '0') i--;// ищем первую ненулевую цифру

//Выводим все цифры справа налево, начиная с найденной:

for (n = i; n>=0; n--) putchar(c[n]);

Умножение длинного числа на короткое

Коротким мы будем называть число, которое помещается в стандартный тип данных (при этом нам необходимо, чтобы после умножения на цифру результат также не выходил за пределы стандартного типа данных).

Разобьем этот алгоритм на две части:

1. Умножим каждую цифру длинного числа a на короткое число k и сохраним результаты в массиве c, не заботясь о переносах:

c[i] := a[i] * k;

2. Пройдем по полученному массиву и “сделаем переносы”:

for i:=1 to 1000 do begin //следующие строки важно выполнить именно в таком порядке

c[i+1]:=c[i+1]+(c[i] div 10);

c[i]:=c[i] mod 10;

end;