Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Рекурсия >> Номер 2

[Назад]    [Содержание ]    [Вперед]

  


Номер 2


  Условие: Номер 2


Задача 2. Написать программу определения количества шестизначных 'счастливых' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

  Решение задачи: Номер 2


Решение задачи 2. 1) Самое простое - это перебрать все возможные комбинации шести цифр и подсчитать число "счастливых" билетов. Count:=0; {количество "счастливых" билетов} for a1:=0 to 9 do for a2:=0 to 9 do for a3:=0 to 9 do for a4:=0 to 9 do for a5:=0 to 9 do for a6:=0 to 9 do if a1+a2+a3=a4+a5+a6 then Count:=Count+1; Условие if во вложенных циклах будет проверяться 106 раз, поэтому будем говорить, что сложность этого алгоритма 106. 2) Обратим внимание на то, что в "счастливом" билете последняя цифра a6 однозначно определяется первыми пятью: a6=(a1+a2+a3)-(a4+a5). Если 0<=a6<=9, то билет "счастливый", иначе - нет. Таким образом, мы можем убрать шестой вложенный цикл: Count:=0; for a1:=0 to 9 do for a2:=0 to 9 do for a3:=0 to 9 do for a4:=0 to 9 do for a5:=0 to 9 do begin a6:=(a1+a2+a3)-(a4+a5); if (a6>=0) and (a6<=9) then Count:=Count+1; end; Сложность алгоритма 105. 3) Если комбинаций a1 a2 a3 первых трех цифр с суммой T=a1+a2+a3 насчитывается C[T], то всего "счастливых" билетов с суммой половины T=a1+a2+a3=a4+a5+a6 будет C[T]*C[T]. Всех возможных сумм T-28 (от 0=0+0+0 до 27=9+9+9). Подсчитаем C[i], i=0, ..., 28, затем найдем интересующее нас количество "счастливых" билетов C[0]2 + C[1]2 + ... + C[27]2. Заметим, что "счастливых" билетов с суммой T столько же, сколько и с суммой 27-T. Действительно, если билет a1 a2 a3 a4 a5 a6 с суммой T - "счастливый", то таковым же является и билет (999999 - a1 a2 a3 a4 a5 a6) с суммой 27-T. Поэтому число билетов можно вычислять и по формуле 2*(C[0]2+ ... +C[13]2), т.е.рассматривать только суммы T от 0 до 13. var C:array[0..13] of longint; Count:=0; for T:=0 to 13 do C[T]:=0; for a1:=0 to 9 do {перебираем все} for a2:=0 to 9 do {возможные a1 a2 a3} for a3:=0 to 9 do begin T:=a1+a2+a3; C[T]:=C[T]+1 {нашли еще один билет} end; {с суммой T} for T:=0 to 13 do {считаем число билетов} Count:=Count+C[T]*C[T]; Count:=Count*2; {удваиваем сумму} Сложность этого алгоритма 103. 4) В пункте 3 мы перебирали комбинации цифр и искали количество комбинаций с суммами C[T]. Сейчас мы пойдем от суммы T, и по ней будем определять, какое количество комбинаций a1 a2 a3 ее имеет. Итак T=a1+a2+a3. Минимальное значение, которое может принимать a1, - это MAX{0,T-18}. Член T-18 появляется из следующих соображений: пусть a2=a3=9, тогда a1=T-18, но a1 не может быть меньше 0. Максимальное значение a1=MIN{9,T} (так как a2 и a3 неотрицательны, то a1<=T и одновременно a1<=9). Для цифры a2 аналогично получаем, что она лежит в пределах от max{0,T-a1-9} до min{9,T-a1}. Цифра a3 по T, a1 и a2 определяется однозначно. Получаем, что комбинаций a1 a2 a3 с суммой T и с первой цифрой a1 столько же, сколько возможных цифр a2, а именно min{9,T-a1}-max{0,T-a1-9}+1. Как и в пункте 3 мы можем рассматривать диапазон сумм T от 0 до 13. Count:=0; for T:=0 to 13 do begin CT:=0; for a1:=max(0,T-18) to min(9,T) do CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1; Count:=Count+CT*CT end; Count:=Count*2; Сложность этого алгоритма (т.е. количество выполнений операций присваивания внутри двух вложенных циклов) не превышает 140.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017