На собеседовании предложили задачу. Подсчитать количество различных неубывающих последовательностей, составленных из цифр всех 64 значных чисел.
Пример для двухзначных чисел.
Всего чисел 90 (10.....99).
Среди них 9 пар, которые оканчиваются на 0 (10,20,30...90).
Чисел, которые состоят из разных цифр (исключая ноль) будет 9*8. Числа с разными цифрами образуют 9*8=72 пары, которые образуют 36 различных неубывающих последовательностей ( 21 и 12 = 12)
И есть еще 9 чисел, которые состоят из одинаковых цифр (11,22...99). Тогда количество неубывающих последовательностей будет 9+36+9=54.
Решил, но не уверен что правильно. Какие будут идеи ?
Пример для двухзначных чисел.
Всего чисел 90 (10.....99).
Среди них 9 пар, которые оканчиваются на 0 (10,20,30...90).
Чисел, которые состоят из разных цифр (исключая ноль) будет 9*8. Числа с разными цифрами образуют 9*8=72 пары, которые образуют 36 различных неубывающих последовательностей ( 21 и 12 = 12)
И есть еще 9 чисел, которые состоят из одинаковых цифр (11,22...99). Тогда количество неубывающих последовательностей будет 9+36+9=54.
Решил, но не уверен что правильно. Какие будут идеи ?
По теме из базы знаний
- Как получить из текста в BPMN схему. Видеоинструкция
- ТЗ как обязательный атрибут в автоматизации. Реальные кейсы из 16-ти летнего опыта
- Развитие и стресс: как они связаны и что с этим делать
- Postgres как предчувствие. Вычисляем процент импортозамещения в режиме Highload от 1С
- Как я стал Экспертом по технологическим вопросам за 3 месяца. Часть 2 (обновлена)
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(1) Могу предложить посчитать в лоб (считать будет очень долго):
Разрядность = 64;
// Массив цифр числа. Старший разряд в начале массива, младший - в конце.
РазрядыЧисла = Новый Массив(Разрядность);
// Инициализация: самое первое (наименьшее) число,
// удовлетворяющее условиям, состоит из одних единиц.
Для Индекс = 0 По Разрядность - 1 Цикл
РазрядыЧисла[Индекс] = 1;
КонецЦикла;
// Подсчет вариантов.
КоличествоВариантов = 0;
Пока РазрядыЧисла[0] <> 10 Цикл
// Засчитываем и выводим текущую комбинацию.
КоличествоВариантов = КоличествоВариантов + 1;
//ПредставлениеЧисла = СтрСоединить(РазрядыЧисла);
//Сообщить(ПредставлениеЧисла);
// Вычисляем следующую комбинацию цифр, увеличивая младший разряд на 1.
Индекс = Разрядность - 1;
РазрядыЧисла[Индекс] = РазрядыЧисла[Индекс] + 1;
Если РазрядыЧисла[Индекс] <> 10 Тогда
Продолжить;
КонецЕсли;
// Если увеличивать уже некуда, увеличиваем на 1 предшествующий разряд.
// И так по цепочке к старшему разряду.
Пока Индекс > 0 И РазрядыЧисла[Индекс] = 10 Цикл
Индекс = Индекс - 1;
РазрядыЧисла[Индекс] = РазрядыЧисла[Индекс] + 1;
КонецЦикла;
// Остановились на некотором разряде.
// Чтобы последовательность цифр была неубывающей,
// все последующие цифры должны быть равны той, на разряде которой остановились.
// Например, было число 1299. После увеличения на 1 получили 13ХХ.
// Значит подходящим числом станет 1333.
Пока Индекс + 1 < Разрядность Цикл
РазрядыЧисла[Индекс + 1] = РазрядыЧисла[Индекс];
Индекс = Индекс + 1;
КонецЦикла;
// Обход вариантов закончится тогда, когда старший разряд будет содержать число 10.
// Это случится после работы с числом вида 999..9
КонецЦикла;
ПоказатьПредупреждение(, КоличествоВариантов);
Показать
Привожу свой код. Используется метод динамического программирования.
Ответ: 64->97 082 021 464
функция ПодсчетВариантов(iSize) э
arr=new Array;
for i=0 to 9 do
arr.Add(1);
enddo;
for j=2 to iSize do
dest=new array;
s=arr[0];answer=0;
dest.Add(s);
for i=1 to 9 do
s=s+arr[i];
dest.Add(s);
answer=answer+s;
enddo;
arr=dest;
message(""+j+"->"+answer);
enddo;
КонецФункции
ПоказатьОтвет: 64->97 082 021 464
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот