Задача по программированию.

физик, 490 просмотров

Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:

* 1010230 — правильное 7-значное число;
* 1000198 не является правильным числом;
* 0001235 — не 7-значное, а 4-значное число.

Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.
Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 1800.

Примечание:
Писать программу не надо. Подскажите, пожалуйста, как с помощью комбинаторики получить ответ.

Примечание:
Mirraz7
Да это задача с тимуса.

Примечание:
Lelikoid
Для небольших n можно писать рекукрсию, для чуть больших можно писать динамику. А конкретно для этой нужна комбинаторика, до которой я никак додуматься не могу.(

Ответы:

Zmicer

и? вопрос где?

warrior

вопрос, вероятно, напишите алгоритм, а, лучше, программу, которая делает это...

Mirraz7

Задача с тимуса:

Lelikoid

Ну как, можно в лоб
Сделать N вложеных циклов по K итераций.
Ну и счетчик правильных вариантов.
Все просто. А уж оптимальный вариант это какраз надо самому думать иначе смысл в таких задачах...

ioncorpse

K^N - (N-1)*K^(N-2) где ^ это знак возведения в степень.
Объясняю подробнее:
* K^N это общее число различных чисел
* Второе - кол-во неправильных, неправильное это любое число типа ****00****. Комбинаторика рулит;)

ioncorpse

Точнее второе множество это:
K^(N-2) +
K^(N-2) - K^(N-3) +
K^(N-2) - K^(N-3) - K^(N-4) +
K^(N-2) - K^(N-3) - K^(N-4) - K^(N-5) +
....
Т.к. в моем первом ответе некоторые числа считаются два раза.

16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.