Пятерка за неделю 3
A + B
Реализовать длинное сложение можно по-разному. В литературе встречается много описаний этого алгоритма. Опять же, чисто с методологической точки зрения дадим описание несколько иного подхода к решению данной задачи, который базируется на работе со строками и сложении чисел в столбик, изучаемом учениками в младших классах.
Почти детальное словесно-формальное описание алгоритма:
…
прочесть количество примеров N
дляTот1доN
нц
прочесть входную строку st
k := len(st)
stA := “” // обнулили переменную для строки первого слагаемого
stB := “” // обнулили переменную для строки второго слагаемого
stC := “” // обнулили переменную для строки суммы
p := 0 // обнулили буфер для переноса разряда
i := 1 // стали на начало строки
пока st[i] <> “+” // пока не встретили символ сложения
нц
stA := stA + st[i] // приклеиваем очередной символ к слагаемому
i := i+1
кц
ka := i-1 // количество цифр в 1-м слагаемом
i := i+1
пока i <= k // аналогично обрабатываем второе слагаемое
нц
stB := stB + st[i]
i := i+1
кц
kb := k – ka - 1
k := ka // больше цифр в первом слагаемом
если kb > k // если во втором слагаемом цифр больше
то k := kb
все
k := k+1 // возможен перенос еще одного разряда
stA := "0" + stA
stb := "0" + stB
kA := len(stA)
kB := len(stB)
если kA < k // в случае необходимости
тодля i от 1 до k-kA
нц
"0" + stA // дописываем недостающее количество нулей к слагаемому А
кц
все
если kB < k // в случае необходимости
тодля i от 1 до k-kB
нц
"0" + stB // дописываем недостающее количество нулей к слагаемому В
кц
все
для i от k до 1 шаг -1
нц
преобразовать stA[i] в переменную А
преобразовать stB[i] в переменную B
C := A + B + p
p := C div 10
C := C mod 10
преобразовать С в строку st0
stC := st0 + stC // приклеиваем результат спереди
кц
если stС[1] = “0”
тоудалить из строки stС первый символ
все
вывести результат – строку stС
кц
…
Описанный подход, естественно, не является наиболее оптимальным, но именно он наиболее понятен при первичном объяснении длинной арифметики учащимся.
A + B ?
Для решения данной задачи достаточно добавить к алгоритму предыдущей задачи оператор выбора выполнения операции в зависимости от выполняемой операции.
Техничесий ньюанс: При выводе ответа неоходимо избавиться от ведущих нулей, которых может быть очень много.