игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 10

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

Упражнение 1:
Номер 1 
Какую функцию называют производящей для последовательности чисел  a0,a1,...,an?

Ответ:

 (1) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд расходится в какой-то области, то его называют производящей функцией 

 (2) пусть дана некоторая последовательность чисел a0,a1,...,an. Если этот ряд сходится в какой-то области к функции f(x), то эту функцию называют производящей для последовательности чисел x,x2,x3,...,xn 

 (3) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд сходится в какой-то области к функции f(x), то эту функцию называют производящей для последовательности чисел a0,a1,...,an 

 (4) пусть дана некоторая последовательность чисел a0,a1,...,an. Образуем степенной ряд a0+a1x+...+anxn+.... Если этот ряд сходится в какой-то области к функции x, то этот ряд называют производящей функцией для последовательности чисел a0,a1,...,an 

Номер 2 
Какая функция является производящей функцией для чисел Сnk,k=0,1,...,?

Ответ:

 (1) (1+x)n 

 (2) x(1+x)n 

 (3) x2(1+x)n 

 (4) x3(1+x)n 

Номер 3 
Какая последовательность удовлетворяет равенству an+2+2an+1-8an=2n

Ответ:

 (1) an=(n/12)·2n+C1(-4)n+C22n 

 (2) an=(n/12)·2n 

 (3) an=(n/12)·2n+C1(-4)n 

 (4) an=(n/12)·2n+C22n 

Упражнение 2:
Номер 1 
Какой коэффициент является наибольшим в разложении (a+b+c)10

Ответ:

 (1) коэффициент при a4b4c4 (или a3b4c3,a4b3c3). Он равен P(4,4,4)=4200 

 (2) коэффициент при a3b3c4 (или a3b4c3,a4b3c3). Он равен P(3,3,4)=4200 

 (3) коэффициент при a2b2c4 (или a3b4c3,a4b3c3). Он равен P(2,2,4)=4200 

 (4) коэффициент при a3b3c3 (или a3b4c3,a4b3c3). Он равен P(3,3,3)=4200 

Номер 2 
Какой коэффициент является наибольшим в разложении (a+b+c+d)14

Ответ:

 (1) коэффициент P(4,4,3,3) при a3b3c4d4 

 (2) коэффициент P(3,3,3,3) при a3b3c3d3 

 (3) коэффициент P(4,4,4,4) при a4b4c4d4 

 (4) коэффициент P(14,14,0,0) при a0b0c14d14 

Номер 3 
Имеется pq+r разных предметов, где  0≤r<p. Они делятся между p людьми возможно ровнее (все получают либо q, либо q+1  предметов). Сколько существует способов такого раздела?

Ответ:

 (1) (pq+r)!/(q+1)r(q!)p Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r 

 (2) Сrp*1!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r 

 (3) Сrp(pq)!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r 

 (4) Сrp(pq+r)!/(q+1)r(q!)p. Все предметы можно переставить (pq+r)! способами. После этого выберем r человек из p, которые получат q+1 предметов (Cpr способов), и разделим между ними предметы по порядку, выдавая соответственно q или q+1 предметов. Так как результат не зависит от порядка элементов в группах, то Cpr(pq+r)! надо разделить на (q)!p-r[(q+1)!]r=(q)!p(q+1)r 

Упражнение 3:
Номер 1 
Сколькими способами можно выбрать из 15 человек группу людей для работы (в группу могут входить 1, 2, 3,…, 15 человек)? Та же задача для случая выбора из n человек

Ответ:

 (1) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 25-1=624 способов. Для n человек имеем 2n-1 способов 

 (2) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 23-1=7 способов. Для n человек имеем 2n-1 способов 

 (3) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 215-1=32767 способов. Для n человек имеем 2n-1 способов 

 (4) каждый из 15 человек может или войти, или не войти в группу. Так как группа не может быть пустой, то получаем 22-1=3 способов. Для n человек имеем 2n-1 способов 

Номер 2 
Сколькими способами можно расставить 20 книг в книжном шкафу с 5 полками, если каждая полка может вместить все 20 книг?

Ответ:

 (1) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!/4! Каждой перестановке соответствует свой способ расстановки книг 

 (2) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!. Каждой перестановке соответствует свой способ расстановки книг 

 (3) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!*4! Каждой перестановке соответствует свой способ расстановки книг 

 (4) добавим к 20 книгам 4 одинаковых разделяющих предмета и рассмотрим все перестановки полученных объектов. Их число равно 24!+4! Каждой перестановке соответствует свой способ расстановки книг 

Номер 3 
В селении проживает 2000 жителей. Могут ли все из них иметь разные инициалы?

Ответ:

 (1) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 292=841, что меньше 2000, то есть: не могут 

 (2) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 294, что больше 2000, то есть: да, могут 

 (3) в русском алфавите 33 буквы, но по крайней мере с 4 букв (Ъ, Ь, Ы, Й) имена не начинаются. Поэтому общее число различных инициалов не больше 2929, что больше 2000, то есть: да, могут 



Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 10