eolymp

Пятерка за неделю 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 ?

   Для решения данной задачи достаточно добавить к алгоритму предыдущей задачи оператор выбора выполнения операции в зависимости от выполняемой операции.

  Техничесий ньюанс: При выводе ответа неоходимо избавиться от ведущих нулей, которых может быть очень много.