Комбинаторные алгоритмы для программистов

Упражнение 1:

Номер 1

Что понимают под методом рекуррентных соотношений (от латинского "recurrere" – "возвращаться")?

Ответ:

(1) сведение комбинаторной задачи к задаче, касающейся меньшего числа предметов

(2) сведение комбинаторной задачи к задаче, касающейся большего числа предметов

(3) сведение комбинаторной задачи к задаче, касающейся среднего числа предметов

(4) сведение комбинаторной задачи к задаче, касающейся нулевого числа предметов

Номер 2

Какая последовательность называется последовательностью Фибоначчи?

Ответ:

(1) последовательность, в которой каждое число, начиная с третьего, является суммой двух предыдущих

(2) последовательность, в которой каждое число, начиная со второго, является частным от деления на предыдущее

(3) последовательность, в которой каждое число, начиная с пятого, является разностью двух предыдущих

(4) последовательность, в которой каждое число, начиная с третьего, является разностью двух предыдущих

Номер 3

Какие числа называется числами Фибоначчи?

Ответ:

(1) числа, которые образуют последовательность Фибоначчи

(2) числа, которые не являются простыми

(3) числа, которые не являются четными

(4) числа, которые не являются нечетными

Упражнение 2:

Номер 1

Что называется поиском по числам Фибоначчи?

Ответ:

(1) метод, при котором область поиска делится в точках, являющихся числами Фибоначчи

(2) метод, при котором область поиска делится пополам

(3) метод, при котором область поиска делится на три области

(4) метод, при котором область поиска делится на четыре области

Номер 2

Обозначим число перестановок последовательности  α₁,...,α_n-1,α_n  через  P_n. Какая формула подсчета перестановок верна?

Ответ:

(1) число различных мест, которые может занять элемент α_n, равно n, и поэтому из каждой перестановки элементов α₁,...,α_n-1 получается n перестановок элементов α₁,...,α_n-1,α_n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что P_n=nP_n-1=n(n-1)P_n-2=n(n-1)...2P₁. Но P₁=1, так как из одного элемента можно сделать одну перестановку. Поэтому P_n=n(n-1)...2·1=n! Таким образом мы получили формулу P_n=n!

(2) число различных мест, которые может занять элемент α_n, равно n, и поэтому из каждой перестановки элементов α₁,...,α_n-1 получается n перестановок элементов α₁,...,α_n-1,α_n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что P_n=nP_n-1=n(n-1)P_n-2=n(n-1)...2P₁. Но P₁=1, так как из одного элемента можно сделать одну перестановку. Поэтому P_n=n(n-1)...2·1=n! Таким образом мы получили формулу P_n=n!/2

(3) число различных мест, которые может занять элемент α_n, равно n, и поэтому из каждой перестановки элементов α₁,...,α_n-1 получается n перестановок элементов α₁,...,α_n-1,α_n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что P_n=nP_n-1=n(n-1)P_n-2=n(n-1)...2P₁. Но P₁=1, так как из одного элемента можно сделать одну перестановку. Поэтому P_n=n(n-1)...2·1=n! Таким образом мы получили формулу P_n=n!/3

(4) число различных мест, которые может занять элемент α_n, равно n, и поэтому из каждой перестановки элементов α₁,...,α_n-1 получается n перестановок элементов α₁,...,α_n-1,α_n. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что P_n=nP_n-1=n(n-1)P_n-2=n(n-1)...2P₁. Но P₁=1, так как из одного элемента можно сделать одну перестановку. Поэтому P_n=n(n-1)...2·1=n! Таким образом мы получили формулу P_n=n!/4

Номер 3

Какие расстановки считаются различными?

Ответ:

(1) если расстановки либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке

(2) если расстановки отличаются всеми элементами

(3) если расстановки либо отличаются друг от друга хотя бы тремя элементами, либо состоят из одних и тех же элементов, но расположенных в разном порядке

(4) если расстановки либо отличаются друг от друга хотя бы четырьмя элементами, либо состоят из одних и тех же элементов, но расположенных в разном порядке

Упражнение 3:

Номер 1

Какие расстановки называют перестановками из n элементов?

Ответ:

(1) при составлении размещений без повторений из n элементов по k мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов, и такие расстановки называют перестановками из n элементов

(2) расстановки без повторений из n элементов по n

(3) расстановки с повторениями из n элементов по n

(4) расстановки с чередованиями из n элементов по n

Номер 2

Какие расстановки называют n - перестановками?

Ответ:

(1) расстановки с чередованиями из n элементов по n

(2) расстановки с повторениями из n элементов по n

(3) расстановки без повторений из n элементов по n

(4) расстановки, в которые входят все n элементов и могут отличаться друг от друга лишь порядком входящих в них элементов

Номер 3

Что называют k-сочетаниями из  n-элементов?

Ответ:

(1) всевозможные k-расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов

(2) всевозможные k-расстановки

(3) всевозможные k-перестановки

(4) всевозможные k-расстановки, составленные из этих элементов и отличающиеся друг от друга составом и порядком элементов

Комбинаторные алгоритмы для программистов - тест 7