| Вопрос: Детская задача | Добавлено: 10.03.04 17:12 |
Автор вопроса:  Pashenko | ICQ: 176176951 |
|
Возвращаясь к вопросу, обсуждавшемуся здесь: http://vbnet.ru/forum/show.asp?id=37580. Предлагаю простенькую задачку на сообразительность: сосчитать количесво "счастливых" билетов в полной пачке.
Номера билетов с 000001 по 999999. Счастливым считается билет, у которого сумма первых трёх цифр равна сумме последних трёх цифр.
Вот и всё, желаю удачи
P. S. Алгоритмы с количеством итераций больше 2000 не предлагать |
.
.
| Ответы | Всего ответов: 4 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 12.03.04 01:06 |
|
Не, эта фигня широкоизвестна. Можно было предложить что-нибудь поинтереснее... |
||
|
Номер ответа: 2 Автор ответа:  MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #2 | Добавлено: 12.03.04 04:59 |
|
Ну, для окружной олимпиады потянет, хотя, думаю, минут за 6 сделаю... |
||
|
Номер ответа: 3 Автор ответа:  ASiD ICQ: 259132473 Вопросов: 19 Ответов: 23 |
Профиль | | #3 | Добавлено: 21.09.04 22:10 |
|
Вот текст с g6progs.narod.ru... Он на паскале, но по-моему разобраться можно Задача g6_1002: Трамвайные билеты. Написать программу определения количества шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних. Оптимизировать решение по времени выполнения. Количество билетов вывести в файл output.txt Решение g6_1002: Логично устроить цикл в цикле, затем считать сумму первых и последних трех цифр и сравнивать их между собой. Как считать сумму цифр? 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 * M; где I - счетчик, L - кол-во счастливых билетов, M - массив значений суммы цифр. Удачи вам в реализации! |
||
|
Номер ответа: 4 Автор ответа: Mihalыch ICQ: 373-509-101 Вопросов: 56 Ответов: 330 |
Профиль | | #4 | Добавлено: 22.09.04 02:27 |
|
А вот еще задачка:
Сообщество роботов живет по следующим правилам: - один раз в начале года они объединяются в группы по три или пять роботов; - за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых; - роботы объединяются так, чтобы собрать за год наибольшее количество роботов; - каждый робот живет три года после сборки Известно, что начальное количество равно «К» и все они только что собраны. Сколько роботов будет через «N» лет ? |
||
Страница: 1 |