Статья Автор: Лебедев Дмитрий Алексеевич

Перебор k-значных наборов простой структуры

Вернемся к задаче 2.

Задание 2: Сколько существует наборов из 7 десятичных цифр, в который cуммарное количество цифр 0 и 5 равно суммарному количеству цифр 3 и 7

Решение вышеизложенным способом "не пройдет, поскольку теперь нужно учитывать "ведущие нули" числа.
Решение можно немного подправить, и это будет сделано позднее для общего случая.
Пока попробуем использовать строчное предсталение чисел, которое легко получить для представления в системах счисления с основаниями 10, 2, 8, 16. (функции str, bin, oct, hex)

Попробуем добавить к числу из не более k-знаков цифру 1 в k+1 - разряд.
Получим число из полуинтервала от 10^k до 2*10^k.
Если это число перевести в строчный формат и взять k "последних" знаков, то строка будет содержать "ведушие нули" k-значной записи
Используем этот прием для решения поставленной задачи

ans, k = 0, 7
for n in range (10**k, 2*10**k):
    s = str(n)[-k:]
    a05 = s.count('0') + s.count('5')
    a37 = s.count('3') + s.count('7') 
    if a05 == a37 : ans +=1
print(ans)

Разберем еще одну задачу.

Задание 3

Сколько существует "двоичных" наборов длины  20,  для которых выполняется ровно одно из условий

цифра 1 в наборе встречается не менее 12 раз и в наборе нет подпоследовательности из 7 и более подряд идущих цифр 1
цифра 0 в наборе встречается не менее 13 раз и в наборе нет подпоследовательности из 7 и более подряд идущих цифр 0
в наборе есть подпоследовательность из 5 подряд идущих цифр 0 и в наборе есть подпоследовательность из 5 подряд идущих цифр 1

Напишите свою версию программы. Ваш результат будет проверен

# Напишите здесь свою версию программы
ans, ans1, ans2, ans3 = 0, 0, 0, 0
n, m = 20, 14
for x in range (2**n, 2*2**n):
    s = bin(x)[-n:]
    r1 = (s.count('1') >= 12) and not ('1111111' in s)
    r2 = (s.count('0') >= 13) and not ('0000000' in s)
    r3 =('1'*5 in s) and ('0'*5 in s)
    if r1 : ans1 +=1
    if r2 : ans2 +=1
    if r3 : ans3 +=1
    if int(r1) + int(r2) + int(r3) == 1 : ans += 1
print(f' условию 1 удовлетворяет {ans1} наборов\n условию 2 удовлетворяет {ans2} наборов\n условию 3 удовлетворяет {ans3} наборов\nСТРОГО ОДНОМУ из трех условий удовлетворяет {ans} наборов')


p = int(input()) # основание системы счисления
k = int(input()) # ограничение на число цифр числа

Чтобы оставить комментарий нужна авторизация

Печать