Интерестная задача

← →
Armageddon (2002-12-28 13:57) [0]

Я уже задавал этот вопрос, но так никто и не ответил. Есть довольно - таки интерестная задача. Она предлагалась в 2002 году на областной олимпиаде. Одно время долго ламал над ней голову, но у меня ничего неполучилось, может у кого- нибудь будут предложения. Только есть некоторые ограничения:
ответ должен получится почти мгновенно(менее 1 с на сравнительно медленной машине(P-100) - "лобовое" решение проблемы не подходит).

Скорее всего необходимо вывести какую-нибудь формулу, или что-то типа этого.

Итак задача:

Требуется вычислить количество N-значных чисел в системе счисления с основанием K таких, что их запись не содержит двух подряд идущих нулей. Ограничения: 2<=K<=10, n>=2;
4<=n+k<=180.

Пример
N=2
k=10

Ответ
90

← →
Armageddon (2002-12-28 15:33) [1]

Неужели никому не интерестно

← →
VirginKiller (2002-12-28 16:07) [2]

Честно говоря, я думаю, люди сюда не за этим приходят. :-) Тебе надо на сайт с соотвествующей тематикой. В АСМ например.. :-)

← →
OxOTHuK (2002-12-28 23:24) [3]

Э брат.... разбирай числа в строке и смотри pos(s,"00") или
pos("00",s) ?? а с системой счисления сам разберешься?

← →
Sha (2002-12-28 23:56) [4]

Завтра решу.

← →
Danlicha (2002-12-29 02:16) [5]

Да вроде и не сильно сложная задачка...
Получаем все варианты - K^n - K^(n-1)
Затем отнимаем от них к-во вариантов, когда два ноля в позициях (1, 0), (2, 1), (3, 2) и т.д. А в каждой из этих позиций K^(n - 2) вариантов. Позиций n - 2.

K^n - K^(n - 1) - (n - 2) * K^(n - 2)

Вроде так...

← →
Sha (2002-12-29 11:50) [6]

Решение.

Разобьем все искомые числа на группы. В i-тую группу включим все числа, у которых
в записи ровно i не идущих подряд нулей. Всего мы получим 1+n/2 групп, считая
нулевую группу чисел, не содержащих нулей в своей записи. Ясно, что для того,
чтобы найти общее количество искомых чисел, достаточно сложить количество чисел
в каждой группе.

Найдем количество искомых чисел в i-той группе. Заметим, что нуль может быть
последним символом в записи числа, но не может быть первым. Это позволяет нам
мысленно склеить все нули в записи произвольного числа со стоящей перед ним цифрой,
образовав пары. Всего пар будет i. Обозначим каждую такую пару через x, а
каждую из оставшихся цифр через y. Таким образом, любое число из i-той группы
представимо в виде слова из букв x и y длиной в n-i символов, в котором буква
x встречается i раз, а буква y встречается n-i-i раз.

Понятно, что всего таких слов С(n-i,i)=(n-i)!/i!(n-i-i)!
Очевидно также, каждому слову соответсвует (k-1)^(n-i) различных чисел.
Поэтому всего i-тая группа содержит С(n-i,i)*(k-1)^(n-i) чисел.

При реализации данного решения на компьютере необходимо строить алгоритм
таким образом, чтобы по возможности избегать переполнения. Некоторые варианты
решения приведены ниже. procedure TForm1.Button12Click(Sender: TObject); var c, p, f: int64; i, j, k, n: integer; begin; // Вычисление n-значных (n>=2) чисел в системе счисления с основанием (k>=2), // в записи которых нет двух подряд идущих нулей. k:=10; n:=5; // Вычисление в лоб f:=0; for i:=0 to n shr 1 do begin; c:=1; for j:=1 to n-i-i do c := c * (i+j) div j; p:=1; for j:=1 to n-i do p := p * (k-1); inc(f,c*p); end; ShowMessage("Результат в лоб "+IntToStr(f)); // Быстрый вариант c:=1; p:=1; for i:=1 to n do p:=p * (k-1); f:=p; for i:=0 to n shr 1 - 1 do begin; c:=c * (n-i-i) div (n-i) * (n-i-i-1) div (i+1); p:=p div (k-1); inc(f,c*p); end; ShowMessage("Быстрый результат "+IntToStr(f)); // Проверка работает очень медленно и только для k=10 if (k=10) and (n<=6) then begin; j:=1; for i:=1 to n-1 do j:=j*k; f:=0; for i:=j to j*k-1 do inc(f,ord(pos("00",IntToStr(i))=0)); ShowMessage("Проверка "+IntToStr(f)); end else ShowMessage("Проверка не выполняется"); end;

← →
Sha (2002-12-29 12:22) [7]

2Danlicha © (29.12.02 02:16)
А как три нуля подряд считать будем?

← →
Armageddon (2002-12-29 16:20) [8]

Спасибо

← →
Danlicha (2002-12-29 19:21) [9]

Sha, а они сами посчитаются. Вообще-то я, может, и сделал ошибку, но, вроде, принцип правильный. Хорошо бы сверится...

← →
Danlicha (2002-12-29 19:22) [10]

свериться, пардон

← →
Sha (2002-12-29 19:53) [11]

← →
Danlicha (2002-12-29 23:06) [12]

Признаю свою вину, меру, степень, глубину... :)

Интерестная задача Найти похожие ветки