Написать программку определения количества шестизначных счастливых билетов, у которых сумма первых
Написать программку определения количества шестизначных счастливых билетов, у которых сумма первых 3 десятичных цифр одинакова сумме 3 последних десятичных цифр.
Описание входных данных
Входные данные отсутствуют.
Описание выходных данных
Одно число итог решения задачки.
1 ответ
Ленька
Решение принималось к рассмотрению, если программка выдавала правильный ответ nbsp;- 55252.
1) Самое обычное - это перебрать все вероятные комбинации шести цифр и подсчитать число quot;счастливыхquot; билетов.
Count:=0; количество quot;счастливыхquot; билетов
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;
или следующий вариант:
Count:=0;
for t:=0 to 999999 do nbsp;begin
a1:=t div 100000;
a2:=t div 10000 mod 10;
a3:=t div 1000 mod 10;
a4:=t div 100 mod 10;
a5:=t div 10 mod 10;
a6:=t mod 10;
if a1+a2+a3=a4+a5+a6 then count:=count+1;
end;
Условие if во вложенных циклах будет проверяться 10^6 раз, потому будем говорить, что сложность этих алгоритмов 10^6.
2) Обратим внимание на то, что в quot;счастливомquot; билете последняя цифра a6 совершенно точно определяется первыми пятью:
a6=(a1+a2+a3)-(a4+a5).
Если 0lt;=a6lt;=9, то билет quot;счастливыйquot;, по другому - нет. Таким образом, мы можем убрать 6-ой вложенный цикл:
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 (a6gt;=0) and (a6lt;=9)
then Count:=Count+1;
end;
Сложность метода 10^5.
3) Если композиций a1 a2 a3 первых 3-х цифр с суммой T=a1+a2+a3 насчитывается C[T], то всего quot;счастливыхquot; билетов с суммой половины 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, затем найдем интересующее нас количество quot;счастливыхquot; билетов
C[0]2 + C[1]2 + ... + C[27]^2.
Заметим, что quot;счастливыхquot; билетов с суммой T столько же, сколько и с суммой 27-T. Вправду, если билет a1 a2 a3 a4 a5 a6 с суммой T - quot;счастливыйquot;, то таким же является и билет (999999 - a1 a2 a3 a4 a5 a6) с суммой 27-T. Потому число билетов можно вычислять и по формуле
2*(C[0]2+ ... +C[13]2),
т.е.рассматривать только суммы T от 0 до 13.
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; удваиваем сумму
либо последующий вариант
count:=0;
for t:=0 to 27 do c[t]:=0;
for t:=0 to 999 do begin
a1:=t div 100;
a2:=t div 10 mod 10;
a3:=t mod 10;
c[a1+a2+a3]:=c[a1+a2+a3]+1;
end;
for t:=0 to 27 do count:=count+c[t]*c[t];
Сложность этих алгоритмов 10^3.
1) Самое обычное - это перебрать все вероятные комбинации шести цифр и подсчитать число quot;счастливыхquot; билетов.
Count:=0; количество quot;счастливыхquot; билетов
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;
или следующий вариант:
Count:=0;
for t:=0 to 999999 do nbsp;begin
a1:=t div 100000;
a2:=t div 10000 mod 10;
a3:=t div 1000 mod 10;
a4:=t div 100 mod 10;
a5:=t div 10 mod 10;
a6:=t mod 10;
if a1+a2+a3=a4+a5+a6 then count:=count+1;
end;
Условие if во вложенных циклах будет проверяться 10^6 раз, потому будем говорить, что сложность этих алгоритмов 10^6.
2) Обратим внимание на то, что в quot;счастливомquot; билете последняя цифра a6 совершенно точно определяется первыми пятью:
a6=(a1+a2+a3)-(a4+a5).
Если 0lt;=a6lt;=9, то билет quot;счастливыйquot;, по другому - нет. Таким образом, мы можем убрать 6-ой вложенный цикл:
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 (a6gt;=0) and (a6lt;=9)
then Count:=Count+1;
end;
Сложность метода 10^5.
3) Если композиций a1 a2 a3 первых 3-х цифр с суммой T=a1+a2+a3 насчитывается C[T], то всего quot;счастливыхquot; билетов с суммой половины 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, затем найдем интересующее нас количество quot;счастливыхquot; билетов
C[0]2 + C[1]2 + ... + C[27]^2.
Заметим, что quot;счастливыхquot; билетов с суммой T столько же, сколько и с суммой 27-T. Вправду, если билет a1 a2 a3 a4 a5 a6 с суммой T - quot;счастливыйquot;, то таким же является и билет (999999 - a1 a2 a3 a4 a5 a6) с суммой 27-T. Потому число билетов можно вычислять и по формуле
2*(C[0]2+ ... +C[13]2),
т.е.рассматривать только суммы T от 0 до 13.
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; удваиваем сумму
либо последующий вариант
count:=0;
for t:=0 to 27 do c[t]:=0;
for t:=0 to 999 do begin
a1:=t div 100;
a2:=t div 10 mod 10;
a3:=t mod 10;
c[a1+a2+a3]:=c[a1+a2+a3]+1;
end;
for t:=0 to 27 do count:=count+c[t]*c[t];
Сложность этих алгоритмов 10^3.
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
Рассматривая литературный язык как сложное взаимодействие книжного языка и разговорного,В.И.Чернышёв горячо
Разные вопросы.
Арабы входят в __________________ групп народов. Местом расселения арабов с незапамятных
Разные вопросы.
Грузовой автомобиль марки краз за одну поездку может доставить 7.500 кирпичей
Математика.
Определить предложения какие они по цели высказывания и по интонации
Русский язык.
"Три толстяка" Называли эту площадь Площадью Звезды последующей причине.
Русский язык.
на одной грядке коротышки посадили 3 ряда морковок по 8 штук
Разные вопросы.
эссе на тему какое образование дается в каждой семье
Қазақ тiлi.
Put the verb in brackets into the Present Indefinite.
1The Volga ,
Английский язык.
Сколько стоит коктейль молочный? Точную цену надо?
Математика.
Составить рассказ Из чего складывался культ монарха помазанника Божьего?
История.
Облако тегов