66
Определение суммы цифр числа на ЭВМ
Е. Х. АЛАРКОН,
А. Н. ВИЛЕНКИН
На подготовительном отделении одного вида будущим абитурентам предложили следующую задачу.
Сумма цифр страниц ключа равна 3684. Найти количество страниц в этой книге.
Как решать эту задачу? И как научить компьютер или микрокалькулятор решать эту задачу? Первое, что приходит в голову: научать со страницы 1 и добавлять к сумме S (первоначально равной 0) цифры, которые записан номер очередной страницы, пока не достигем до 3684. Для этого надо прежде всего научить компьютер выделять из номера страницы цифры, которые этот номер записан. Например, из номера n=128 надо получить три числа: 1, 2, 8 (мы ограничимся трехначными числами). Воспользовемся функцией [x] — «целая часть x». Она есть на компьютерх и МК-61, на других (программируемых) микрокалькуляторах ее можно реализовать следующей подпрограммой.
№ строки Команда код
80 1 01
81 + 10
82 X→Π 43
83 KΠ→X Γ3
84 Π→X 63
85 B/O 52
Действие этой подпрограммы основано на том, что команда косвенной индикации вызова из регистра RG3 не только уменшает содержимое RG3 на 1, но и уменшает его еще до целого числа, если только содержимое RG3 больше 1 и изобразяется с естественным расположением запятой. Разумеется, регистр RG3 не должен использовать в основной программе. При обращении к подпрограмме исходное число должно быть в регистре X, там же получится результат. (Иного еще надоставлять команду 79 В↑ 52.)
Для получения числа сотен трехначного числа n надо взять [n/100]. Это и будет как раз целое число сотен, содержащихся в числе n. Обозначим его через R2:
R2=[n/100].
Дальше уберем из числа n сотни, не трогая десятики и единиццы, а для этого из числа n вычитем [n/100]·100, пусть это будет число m. Оно — двузначное и содержит десятики и единиццы числа n. (Так, если n=128, то m=28.) Что делать с ним, уже понятно:
R1=[m/10]
будет число десятиков, а
R0=m-[m/10]·10
— число единиц. Тепер пишем подпрограмму вычисления суммы цифр числа n, т. е. суммы R0+R1+R2, и основную программу вычисления суммы (цикл по k от 1 до n) цифр номеров страниц от 1 до n. Запустим ее для вычисления суммы цифр номе-
67
ров страниц «Квана» (n=80) и посмотрим, что получится.
Если программа поставлена на компьютер, то ответ получится быстро. Но понятно, что время работы ЭВМ зависит от n — чем больше n, тем больше будет работать компьютер. Все можно поprobовать в программу печать результатов и останов при получении числа 3684 (или больше), запустить эту программу для достаточно большого n и получить ответ исходной задачи.
Если программа поставлена на микрокалькулятор, то время работы будет 10—13 минут, потому что цикл обработки номера одной страницы занимает 7—10 секунд, а страниц 80.
Но за 10 минут мы и так можем найти исходную сумму, причем не складывая все цифры всех номеров страниц. Будем сначала искать сумму единиц. Здесь нам надо сложить числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 и опять 1, 2, …, таких сумм будет воспользоваться от 01 до 80). 1+2+…+9=45, 45×8=360. С десятками еще легче: единица встретиется 10 раз (от 10 до 19), как и двойка, и тройка… до семерки включительно. Только 8 десятков появятся лишь один раз. Получаем сумму числа десятков в виде (1+2+…+7)·10+8=288. Итого: 288+360=648 — исходная сумма. Ее вскоре и даст микрокалькулятор.
Теперь ставить ясно, что метод простого сложения цифр микрокалькутора добавется до числа 3684 примерно за час. Это слишком долго. А нельзя ли поставить на микрокалькулятор вычисление суммы цифр страниц от 1 до n тем способом, который мы искали сумму цифр страниц «Квана»? Число вычислений по этому способу почти не зависит от n, так что время работы будет невелико.
Попробуем. Пусть число страниц равно n и записьается цифрами i, j, k. Это обозначается так: n=ijk. Пусть сначала i=0, j=0 (число n—однозначное). Тогда исходная сумма равна k(k+1)/2 — это сумма арифметической прогрессии 1, 2, …, k. Обозначим эту сумму f1(k): f1(k)=k(k+1)/2. В частности, f1(9)=45.
Пусть теперь n=jk и j≠0 (число n—двузначное). Искомую сумму разобем на две части: от 01 до (j−1)9 и от j0 до jk. Первую сумму считаем так, как мы считали сумму цифр номеров страниц «Квана»: единицы — 45j, десятки — 10(j−1)j/2. Во второй сумме k+1 число, сумма числа десятков равна j(k+1), единиц — f1(k), исключая сумма f2(jk) имеет вид
f2(jk)=45j+5j(j−1)+j(k+1)+f1(k)=j(5j+41+k)+f1(k).
В частности, f2(99)=900 (это пригодится в дальнейшем), формула «работает» и для однозначных чисел (j=0).
Пусть теперь n=ijk и i≠0. Опять разобем сумму на две части: от 001 до (i−1)99 и от i00 до ijk. Считаем первую сумму. Десятки и единицы (вместе) дают i·f2(99)=900i (ясно почему?). Сотни дают 100(i−1)i/2 (каждая цифра сотен употребляется 100 раз). Считаем вторую сумму. Сотни дают i(10j+k+1), а десятки и единицы дают f2(jk). Искомая сумма f3(ijk) имеет вид
f3(ijk)=900i+50i(i−1)+i(10j+k+1)+f2(jk)=i(50i+10j+k+851)+f2(jk).
Эта формула «работает» и для двузначных чисел (i=0), и для однозначных (i=j=0).
Итак, формулы получены. Их легко поставить даже на программируемый микрокалькулятор, и после ввода в него числа n он за 15 секунд будет вычислять исходную сумму, например: f3(96)=849, f3(200)=1902 и т. п.
Выиграв в скорости, мы коe-что потеряли. Тепер мы уже не можем запустить программу и ждать, когда она doit до числа 3684. Что делать — придетя воспользоваться методом проб и ошибок (иногда называем «метод тыка»). «Ткнем» в число 200 — мало. Попробуем f3(400)=4204 — много. Пробуем f3(300)=3003 — мало. И так далее, пока не doit до исходного.
(Окончание см. на с. 70)