Сколько битовых строк длины 10

6.1 Основные комбинаторные принципы

Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых правилами суммы и произведения. Правило суммы . Если X 1 и X 2 – непересекающиеся конечные множества, содержащие n 1 и n 2 элементов соответственно, то объединение X 1 U X 2 содержит n 1 + n 2 элементов. Сформулированное правило можно распространить на случай произвольного числа слагаемых: если множества X 1 ,X 2 ,…,X k образуют разбиение множества X , то n = n 1 + n 2 +…+ n k , где n=|X| – число элементов множества X , а n i =|X i | – число элементов (мощность) множества X i , i = 1, 2,…, k . Напомним, что разбиением множества X называется набор его непересекающихся подмножеств, объединение которых дает все исходное множество X . Правило суммы можно приспособить и для подсчета числа элементов объединения двух множеств с непустым пересечением: (1) В самом деле, множества X 1 \X 2 и X 1 ∩X 2 образуют разбиение множества X 1 , поэтому

Аналогично Кроме того, множества X 1 \X 2 , X 2 \X 1 и X 1 ∩X 2 образуют разбиение множества X 1 U X 2 , так что

□ Пример . Найдем количество положительных целых чисел, меньше или раных 1000, которые делятся на 3 или на 5. Количество элементов множества S положительных целых чисел, меньших 1000, которые делятся на 3, равно 1000 3 или 333. Количество элементов множества Т положительных целых чисел, меньших 1000, которые делятся на 5, равно 1000 5 или 200. Элементами множества S∩T являются целые числа, меньшие 1000, которые делятся на 5 и на 3, и поэтому делятся

Пример . Предположим, что на курсе из 100 студентов 60 человек изучают математику, 75 — историю, а 45 человек — и то, и другое. а) Сколько студентов изучают математику или историю? Пусть универсум U — группа из 100 студентов, М — множество студентов, изучающих математику, Н — множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю,

Существует альтернативный метод решения приведенных выше задачи, который является более информативным. Рассмотрим его на следующем примере. Пример . Предположим, что из 100 студентов курса 50 изучают химию, 53 — математику, 42 — физику, 15 — химию и физику, 20 занимаются физикой 2

и математикой, 25 — математикой и химией и 5 студентов изучают все три предмета. а) Сколько студентов изучают хотя бы один из трех перечисленных предметов? б) Сколько студентов не изучают ни один из трех перечисленных предметов? в) Сколько студентов изучают только математику? г) Сколько студентов изучают физику или химию, но не изучают математику? д) Сколько студентов не изучают ни математику, ни химию? Поскольку 5 человек изучают все три предмета, а 15 человек — химию и физику, остаются 10 человек, изучающих химию и физику, но не изучающих математику. Аналогично, 25 — 5 = 20 человек занимаются математикой и химией, но не физикой, и 20 — 5 = 15 человек изучают математику и физику, но не изучают химию. Данную ситуацию изображает диаграмма Эйлера, приведенная на следующем рисунке слева Поскольку 50 студентов изучают химию и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой и 40 из них уже учтены. Поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику. а) Суммируя количество людей, принадлежащих семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов. б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 10090 = 10 человек не изучают ни один из этих трех предметов. в) Из диаграммы Эйлера следует, что 13 человек изучают только математику. г) Тридцать семь студентов занимаются химией или физикой, но не изучают математику. д) Из диаграммы Эйлера, изображенной на предыдущем рисунке справа, следует, что 75 человек изучают математику или физику. Поэтому 100 — 75 = 25 студентов не изучают ни математику, ни физику. □ Пример . Сколько имеется путей из вершины a в вершину b в сети, показанной на следующем рисунке (движение возможно только вправо или вверх)?

Обозначим множество всех путей из a в b через L ab и разобьем его на два непересекающихся подмножества: L acb – пути, проходящие через вершину c; L adb – пути, проходящие через вершину d. Имеем L ab = L acb + L adb . Очевидно, что интересующее нас количество путей зависит только от размеров решетки, поэтому обозначим через l m,n количество путей в сети, имеющей m горизонтальных и n вертикальных

□ Другое фундаментальное правило дает, доказанная ранее Теорема . Мощность декартового произведения двух конечных множеств равна произведению их мощностей A × B = A B . Обобщение ее на декартово произведение n множеств называется правилом произведения . Рассмотрим упорядоченные наборы ( a 1 , a 2 ,…, a k ) заданной длины k . Предположим, что элемент a 1 из множества X 1 может быть выбран n 1 способами, т.е. X 1 = n 1 . При уже выбранном элементе a 1 , элемент a 2 из множества X 2 может быть выбран n 2 способами, т.е. X 2 = n 2 . При фиксированных a 1 и a 2 элемент a 3 из множества X 3 может быть выбран

различных упорядоченных наборов равно произведению n 1 × n 2 × . × n k . Это означает, что Это правило часто называют комбинаторным принципом умножения. Доказательство. Будем доказывать теорему методом математической индукции. Базис индукции . Пусть n=2 . В этом случае все элементы 4

множества Х 1 х Х 2 , т. е. упорядоченные пары ( х 1 , х 2 ), можно расположить в виде прямоугольной таблицы со строками — элементами Х 1 и столбцами — элементами Х 2 . В этой таблице, очевидно, будет |X 1 | x |X 2 | элементов. Индуктивный переход . Предположим справедливость утверждения теоремы для n . Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что В случае, когда X 1 =X 2 =…=X k эта формула принимает вид X k = X k . В этом случае множество X называется алфавитом, его элементы – буквами, а элементы декартова произведения X k , т.е. упорядоченные пары из k букв ( x 1 , x 2 ,…, x k ) называют словами в алфавите X . Число k называется длиной слова. Пусть |X|=m , тогда формулу X k = X k можно сформулировать следующим образом: число слов длины k в алфавите из m букв равно m k . Пример . Битовая строка – это строка, состоящая из элементов множества <0, 1>, т.е. каждый из элементов имеет значение 0 или 1. Сколько существует битовых строк длины 5? Сколько существует битовых строк длины k ? Поскольку каждый символ строки может иметь значение 1 или 0, то существует два варианта выбора для каждой позиции. Следовательно, существует 2 x 2 x 2 x 2 x 2 = 2 5 битовых строк длины 5. По аналогичным соображениям, имеется 2 k битовых строк длины k . □ Пример . Используя правило произведения и правило суммы, найдем число различных трехзначных чисел, не содержащих одинаковых цифр, и число различных трехзначных чисел, содержащих хотя бы две одинаковые цифры Пусть a 1 , a 2 , a 3 – цифры трехзначного числа. Первую цифру a 1 можно выбрать девятью способами (в качестве нее можно взять любую цифру, кроме нуля); при фиксированной первой цифре вторую цифру a 2 можно выбрать также девятью способами (в качестве нее можно взять любую цифру, кроме a 1 ); наконец, при фиксированных первой и второй цифрах третью цифру можно выбрать восемью способами. По правилу произведения число трехзначных чисел, не содержащих одинаковых цифр, равно 9 · 9 · 8=648. Всего имеется 900 различных трехзначных чисел (от 100 до 999). Каждое из них либо содержит две одинаковые цифры, либо нет. Следовательно, имеется 900 – 648 = 252 различных трехзначных числа, содержащих хотя бы две одинаковые цифры. □

Третьим важным принципом является правило взаимно однозначного соответствия (правило биекции или правило равенства): множества A и B имеют одинаковое количество элементов | A | = | B | тогда и только тогда, когда между ними можно установить взаимно однозначное соответствие. В качестве примера применения этого принципа подсчитаем количество всевозможных подмножеств множества M, состоящего из n элементов. Так это количество не зависит от природы элементов множества М, возьмем M=<1,2,…,n>. Произвольному подмножеству A M поставим в соответствие двоичное слово α 1 α 2 . α n по следующему правилу: 1, еслиi A α i = 0 , еслиi A Это соответствие взаимно однозначное. Отсюда число всех подмножеств n – элементного множества равно числу двоичных слов длины n , т.е. равно 2 n . Пример . Сколькими способами можно разложить 10 монет разной стоимости по двум карманам? Формализуя задачу, отметим, что два кармана дадут два подмножества 10 – элементного множества; объединение множеств монет, лежащих в этих двух карманах, дает все множество; пересечение этих множеств пусто. Это значит, что те монеты, которые лежат в одном кармане, полностью определяют содержимое второго кармана. Используя правило биекции, можем сказать, что требуемых способов столько, сколько подмножеств в 10 – элементном множестве. Т.о. можем написать ответ: 2 10 =1024. □ Напомним также принцип Дирихле, который мы формулировали следующим образом. Пусть f : А —> В — функция, причем как A , так и В — конечные множества. Предположим, что А состоит из n элементов: a 1 , а 2 ,… a n . Принцип Дирихле гласит, что если |А|>|В| , то по крайней мере одно значение f встретится более одного раза. Проще говоря, найдется пара элементов a i ≠ a j , для которых f ( a i ) = f ( a j ) . Пример . Показать, что если в прямоугольнике со сторонами 6 и 8 сантиметров помещены пять точек, то существуют две точки, расстояние между которыми не более 5 сантиметров. Разделим исходный прямоугольник на четыре прямоугольника, размером 3 на 4 сантиметра каждый. Поскольку пять точек должны находиться либо внутри, либо на границах четырех прямоугольников, то хотя бы две точки должны быть либо внутри, либо на границе одного и того же прямоугольника размера 3 х 4. Но любые такие точки находятся на расстоянии не более 5 сантиметров. □

Сколько битовых строк длины 10

Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные
В выходной файл вывести количество искомых последовательностей.

Пример входного файла
5

Пример выходного файла
13

Решение

Скачать архив тестов и решений

Назовем последовательность из 0 и 1, в которой никакие две единицы не стоят подряд, хорошей. Обозначим число хороших последовательностей длины k через F_k .

Попытаемся теперь выразить количество хороших последовательностей длины k через количества хороших последовательностей меньшей длины. Для этого рассмотрим, как можно построить хорошую последовательность длины k. Если последним символом этой последовательности выбрать 0, то в качестве предыдущих k-1 символов можно взять произвольную хорошую последовательность длины k-1. А таких последовательностей F_k-1 . Если же последним символом выбрать 1, то на (k-1)-ом месте 1 стоять не может и, значит, там стоит 0. Тогда в качестве первых k-2 символов можно взять любую хорошую последовательность длины k-2, а их количество F_k-2 . Таким образом, находим, что F_k = F_k-1 + F_k-2.

Получив эту рекуррентную формулу, нам остается задать первые два значения рассматриваемой последовательности (F₀ = 1, F₁ = 2), а затем в цикле последовательно вычислить числа F₂ , F₃ , . F_N .

Можно вычислять числа F_k и не в цикле, а с помощью рекурсивной функции, основанной на выведенной нами формуле. Однако этот алгоритм неприемлем в данной задаче, т.к. он не сможет за разумное время закончить свою работу. (Заметьте: значение F_N-2 эта функция будет вычислять 2 раза – при вычислении F_N и F_N-1 , F_N-3 – 3 раза, а F₂ – число раз, по порядку равное F_N.)

Рекурсивную функцию, однако, использовать все же можно, если запоминать уже вычисленные значения (например, в статическом массиве) и никогда не вычислять их заново. Этот прием особенно эффективно применять в тех случаях, когда в процессе вычислений числа F_N нам нужны не все предыдущие значения F_k , а только некоторые из них, причем заранее сложно указать, какие именно.

Отметим также, что при указанных в условии задачи ограничениях необходимо использовать длинную арифметику, т.к. число F₁₀₀ имеет в десятичной записи 21 цифру.

Замечание
Рекуррентная формула, полученная нами при решении этой задачи, совпадает с формулой, определяющей числа Фибоначчи. Это объясняет тот факт, что F_N совпадает с (N+1)-м числом Фибоначчи.

Источники и прецеденты использования

Как найти количество строк длины N,что не содержат S как подстроку?

Дано строку что может содержать только буквы A,B,C, тогда количество всех строк длины N из етих букв будет 3^N,тогда ответ на задачу : 3^N — (количество строк что имеют подстрочку S). Как эффективно посчитать количество строк что не содержат подстроки S? А да забыл сказать S содержит только буквы A,B. Ограничения:

N = 16 1  

2 AB 

from itertools import product n = int(input()) s = str(input()) a = [''.join(i) for i in product('ABC',repeat = n) if s not in "".join(i)] print(len(a)) 

44::bit(10) 0000101100 44::bit(3) 100 cast(-44 as bit(12)) 111111010100 '1110'::bit(4)::integer 14