Задача 2: Трамвайные билеты.
Написать программу определения количества шестизначных "счастливых"
трамвайных билетов, у которых сумма первых трех цифр совпадает с
суммой трех последних.
Оптимизировать решение по времени выполнения. Количество билетов
вывести в файл output.txt
Решение:
Логично устроить цикл в цикле, затем считать сумму первых и
последних трех цифр и сравнивать их между собой.
Как считать сумму цифр?
For Spec
:= 1 to 3 do
Begin
K := K + Luck mod 10;
Luck := Luck div 10;
End;
где Luck - число, в
котором надо посчитать сумму цифр, K - сумма цифр (более правильная
реализация с циклом while, но это я предоставлю реализовать вам ;).
Итак, у нас два цикла, в которых перебираются 1000 чисел, итого
1000000 итераций, т.е. мы перебираем все возможные билеты, но делаем
это не очень явно.
Попробуем разогнать программу в 1000 раз :). В этом нам поможет
динамическое программирование, т.е. сохранение уже полученных
однажды результатов.
Рассмотрим трехзначное число. Сумма цифр этого числа может принимать
значения от 0 до 27, т.е. мы можем просто посчитать сколько чисел от
0 до 999 с данной суммой цифр и записать это значение в массив от 0
до 27.
Т.к. второе число также трехзначное, то мы можем пользоваться для
него тем же массивом данных. Тогда, после подсчета кол-ва чисел с
данной суммой цифр, мы можем достаточно просто подсчитать количество
"счастливых билетов":
For I :=
0 to 27 do
L := L + M[I] * M[I];
где I - счетчик, L
- кол-во счастливых билетов, M - массив значений суммы цифр.
Удачи вам в реализации!
Далее
ð
