| Главная » Статьи » Задачи по программированию |
Трамвайные билеты.
Написать программу определения количества шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних. Оптимизировать решение по времени выполнения. Количество билетов вывести в файл 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 - массив значений суммы цифр. Удачи вам в реализации!
| |
| Просмотров: 1243 | Рейтинг: 0.0/0 |
| Всего комментариев: 0 | |