Как определить количество вариантов

1. scientes 288 21.04.21 11:18 Сейчас в теме
На собеседовании предложили задачу. Подсчитать количество различных неубывающих последовательностей, составленных из цифр всех 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.

Решил, но не уверен что правильно. Какие будут идеи ?
По теме из базы знаний
Ответы
Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
5. SlavaKron 21.04.21 12:58 Сейчас в теме
(1)
составленных из цифр всех 64 значных чисел
А разве может быть в таком числе-последовательности больше 10 знаков? Или я не так понял?
6. scientes 288 21.04.21 13:55 Сейчас в теме
(5)Число 64-х значное в десятичной системе исчисления. В числе 64 цифры.
7. SlavaKron 21.04.21 13:59 Сейчас в теме
(6) А, ну да, я почему-то подумал, что цифры не могут повторяться при "неубывающей последовательности", то есть 64, например, единицы удовлетворят условию.
8. scientes 288 21.04.21 14:08 Сейчас в теме
(7) Цифры могут повторяться. Есть различные числа, которые записаны одинаковыми цифрами. Все эти числа заменяются одним, в котором цифры образуют неубывающую последовательность. Например для 3-х значного числа, 122,221,212 заменяются на 122.
10. dhurricane 21.04.21 17:11 Сейчас в теме
(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
	
КонецЦикла;

ПоказатьПредупреждение(, КоличествоВариантов);
Показать
11. spacecraft 21.04.21 20:44 Сейчас в теме
(1) все просто. Для двузначных чисел будет 45.
Для трехзначных - 450
для 64 - 45 и 62 ноля. (45*10^62)

Это просто половина матрицы (9*10 ^(количество знаков-2))х10
12. spacecraft 21.04.21 21:24 Сейчас в теме
(11) обсчитался. Формула не такая. Не учел уменьшение последующих убываний. Но для двузначных чисел 45 точно.
13. scientes 288 22.04.21 14:24 Сейчас в теме
(11) Для двухзначных будет 54.
2. starik-2005 3036 21.04.21 11:40 Сейчас в теме
А "10" - это неубывающая последовательность?
3. scientes 288 21.04.21 11:57 Сейчас в теме
(2)Неубывающая, когда каждый последующий член не меньше предыдущего. Значит 10 убывающая, а 01 неубывающая.
9. starik-2005 3036 21.04.21 16:58 Сейчас в теме
(3) "01" - это не число из двух знаков (фактически "0" в начале отбрасывается).
4. soft_wind 21.04.21 12:38 Сейчас в теме
кажется 45 должно быть
9 - это с "0" (убывает)
9 - 11,22 а эти которые ни туда ни сюда - надо считать? в принципе не убывает
14. scientes 288 28.04.21 13:45 Сейчас в теме
Привожу свой код. Используется метод динамического программирования.
функция ПодсчетВариантов(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
Оставьте свое сообщение

Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот