Счастливые билеты.

Напишите программу для подсчета счастливых билетов, если номера билетов задаются k-значними числами, а число цифр k в номере задается как начальное даное и при решении задачи остается постоянным.
В общем задача довольно известная для 6-тизачных билетов, код ниже, но для к-значных не имею представления как ее делать...

program biletu;
var i,j,k,l,m,n:INTEGER;
    kol:longint;
begin
kol:=0;
for i:=0 to 9 do
for j:=0 to 9 do
for k:=0 to 9 do
for l:=0 to 9 do
for m:=0 to 9 do
for n:=0 to 9 do
begin
if i+j+k=l+m+n then kol:=kol+1;
end;
writeln('koli4estvo=',kol);
readln;
end.

Про теги не забываем...

Сообщение отредактировано: volvo877 - 21.10.07, 20:39

Потому что сделано по тупому! Нужно цикл вести по числам, а не по цифрам. Единственное что нужно сделать — это поразрядное извлечение цифр из числа и определение диапазона чисел с заданным количеством знаков.

Вот только не надо перебирать все комбинации... Есть очень хороший "школьный" алгоритм подсчета числа счастливых билетов:

http://www.ega-math.narod.ru/Quant/Tickets.htm

Добавлено 21.10.07, 20:57
Брежнев, если задать n = 10, куда с грохотом свалится твое "очень умное" предложение?

Цитата

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

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

****************************
Задача 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 во вложенных
циклах будет проверяться 10^6 раз, поэтому будем говорить, что
сложность этого алгоритма 10^6.
Метод 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;
Сложность алгоритма 10^5. Используя элементарное соображение,
мы уменьшили сложность алгоритма и, вообще говоря, время выполнения
программы в 10 раз!
Метод 3. Если комбинаций a1 a2 a3 первых трех цифр с суммой
T=a1+a2+a3 насчитывается C[T], то всего "счастливых" билетов с сум-
мой половины T=a1+a2+a3=a4+a5+a6 будет C[T]^2. Действительно, каж-
дое "счастливое" шестиразрядное число может быть получено склейкой
двух произвольных трехразрядных чисел с одинаковой суммой цифр.
Всего существует 28 всевозможных значений сумм T - от 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; { массив С из 14 элементов -
. . . по числу возможных сумм }
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; { удваиваем сумму }
Сложность этого алгоритма 10^3.
Метод 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;
Сложность этого алгоритма (т.е. количество выполнений
операций присваивания внутри двух вложенных циклов) есть 95.

Задача 3.
Задача опять же имеет очевидное решение, которое состоит в ге-
нерации всех 2N-разрядных чисел и проверке их на требуемое
свойство. Однако общее количество таких чисел равно 10^(2N) и поэ-
тому при N>3 практически очень трудно получить результат на ЭВМ.
Следовательно необходимо разработать алгоритм, не требующий генера-
ции чисел.
Определим через S(k,i) количество k-разрядных чисел, сумма
цифр которых равна i. Например, S(2,3)=4, так как существует 4
двуразрядных числа (03,12,21,30), сумма цифр которых равна 3. Лег-
ко заметить, что S(1,i)=1 при i<10 и S(1,i)=0 при i>9. Предположим
теперь, что мы сумели вычислить значения величин S(N,i) для всех i
от 0 до 9N, т.е. мы знаем, сколько существует N-разрядных чисел с
суммой цифр, равной 0,1,...,9N ( 9N - максимальная сумма цифр в
N-разрядном числе). Тогда нетрудно убедиться, что общее количество
"счастливых" 2N-разрядных чисел равно
P=S(N,0)^2+S(N,1)^2+...+S(N,9N)^2.
Действительно, рассуждая как и в методе 3, каждое "счастливое"
2N-разрядное число может быть получено склейкой двух произвольных
N-разрядных чисел с одинаковой суммой цифр.
Таким образом, необходимо уметь вычислять значения величин
S(k,i) для всех k<=N,i<=9k. Определим способ вычисления S(k+1,i)
через значения величин S(k,j), j<=i. Понятно, что любое k+1-разряд-
ное число может быть получено из k-разрядного добавлением еще одно-
го разряда (цифры). Следовательно
S(k+1,i) = S(k,i-ц1)+S(k,i-ц2)+...,
где ц1,ц2,... - возможные добавленные цифры. Ясно, что это 0,1,...,m
где m=min(9,i). Следовательно,
S(k+1,i) = S(k,i-0)+S(k,i-1)+...+ S(k,i-m).

Задача 3.2.
Используем метод решения задачи 3.
Решение 3.2b. Обозначим это количество Сm(k,n). Последняя циф-
ра числа в m-ичной системе счисления может принимать одно из значе-
ний 0, 1, ..., m-1. В соответствии с этим сумма цифр (n-1)-значного
числа, получающаяся из n-значного числа отбрасыванием последней
цифры, может принимать одно из значений k, k-1, ..., k-m+1. Отсюда
получаем, что
Cm(k,n)=Cm(k,n-1)+...+Cm(k-m+1,n-1).
Кроме того Cm(k,1)=1 при 0<=k<=m-1, и Cm(k,1)=0 иначе (в m-ич-
ной системе счисления существует только одно однозначное число с
суммой цифр k, 0<=k<=m-1, и ни одного такого числа, если k>=m.