Diskreetne matemaatika - II
#128
Отправлено 01 июня 2010 - 17:47
Сообщение изменено: valeriyas (01 июня 2010 - 21:04 )
#130
Отправлено 01 июня 2010 - 21:06
valeriyas,
а может быть не стоит? преподы ведь тоже не идиоты, вдруг например маргарита увидит на форум.ее и лебедец всем нам повторение на экзамене к/р номер 1
Спасибо за столь лестную оценку моего интеллектуального уровня. Однако, никаких «вдруг» и «например» быть явно не может. Читаю ветку с начала года.
Что касается того, что вы в открытую выкладываете материалы – так это не криминал, так как это конспект, ссылки и прочие полезняшки. Это даже хорошо, если конечно поможет сдать экзамен. А вот с домашними работами был промах тогда, это да.
#135
Отправлено 02 июня 2010 - 13:00
Теперь вопрос по поводу этого задания.
"1) Сколько существует 8битных строк, либо начинающихся с единицы, либо заканчивающихся двумя нулями, либо содержащих в себе ровно 4 нуля"
Ход решения интересует, особенно про "4 нуля".
Сообщение изменено: valeriyas (02 июня 2010 - 13:02 )
#136
Отправлено 02 июня 2010 - 15:13
2^6 00 вероятно второе
0 0 0 0 1 - 1 - 1 - 1 2^4
00 00 2-2 2^4
000 0 3-1 2^4
0 000 1-3 2^4
0000 4 2^4
Видимо в сего 5* 2^4. Хотя 100% не уверен.
Плутарх - (ок. 46 — ок.120) - древнегреческий писатель, историк
#137
Отправлено 02 июня 2010 - 18:20
Ketty, спасибо, разобралась.
Теперь вопрос по поводу этого задания.
"1) Сколько существует 8битных строк, либо начинающихся с единицы, либо заканчивающихся двумя нулями, либо содержащих в себе ровно 4 нуля"
Ход решения интересует, особенно про "4 нуля".
Сколько существует 8битных строк, начинающихся с единицы?
Из восьми бит, первый уже задан - "1". Далее могут быть все возможные комбинации из 7 бит. Каждый из 7 бит может принимать одно из двух значений: "0" или "1". Количество таких комбинаций равно числу размещений с повторениями из 2 возможных значений по 7 битам: ~A(2,7)=2^7=128 (2 в степени 7).
Сколько существует 8битных строк, заканчивающихся двумя нулями?
Из восьми бит, два последних уже заданы - "00". Перед ними могут быть все возможные комбинации из 6 бит. Каждый из 6 бит может принимать одно из двух значений: "0" или "1". Количество таких комбинаций равно числу размещений с повторениями из 2 возможных значений по 6 битам: ~A(2,6)=2^6=64 (2 в степени 6).
Сколько существует 8битных строк, содержащих в себе ровно 4 нуля?
Из восьми бит четыре всегда равны "0". Остальне биты всегда равны "1". В этом случае число нулей в строке фиксировано, и различаются строки только местом расположения нулей. Причём, неважно, какой ноль займёт какое место. Количество таких комбинаций равно числу сочетаний из 8 бит по 4 местам, занытым нулями: C(8,4)=8!/(4!*4!)=(5*6*7*8)/(2*3*4)=5*2*7=70.
programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. so far, the universe is winning. © rick cook
#139
Отправлено 02 июня 2010 - 18:27
1 2^7 вероятно первое
2^6 00 вероятно второе
0 0 0 0 1 - 1 - 1 - 1 2^4
00 00 2-2 2^4
000 0 3-1 2^4
0 000 1-3 2^4
0000 4 2^4
Видимо в сего 5* 2^4. Хотя 100% не уверен.
на счет первых двух согласна, а вот последнее так:
все значения/повторяющиеся "0" * повторяющиеся "1":
8!/4!*4!=70
общее кол-во таких чисел: 2^7 + 2^6 + 70
в общем, все получили одно и то же число разными способами)
Сообщение изменено: valeriyas (02 июня 2010 - 18:27 )
#141
Отправлено 02 июня 2010 - 18:44
В первом пункте, где начало единица, мы учли и те, что содержат 4 нуля, и те, что заканчиваются на два нуля
Во втором, мы учли и первое, и третье условие и т.д.
Чтобы получить конечное число вариантов, надо из суммы (128+64+70) вычесть 3 пересечения пар условий и прибавить 2 пересечение тройки условий
(128+64+70)-32-15-35+2*10 = 200 вариантов
Сообщение изменено: teonoja (02 июня 2010 - 19:00 )
#142
Отправлено 02 июня 2010 - 19:01
Нам надо учитывать все пересечения из получившихся комбинаций!!!
В первом пункте, где начало единица, мы учли и те, что содержат 4 нуля, и те, что заканчиваются на два нуля
Во втором, мы учли и первое, и третье условие и т.д.
Чтобы получить конечное число вариантов, надо из суммы (128+64+70) вычесть 3 пересечения пар условий и прибавить 2 пересечение тройки условий
(128+64+70)-32-15-35+2*10 = 200 вариантов
да, мы уже поняли
п.с. ну ты, Женька, и запарилась. ))
#144
Отправлено 02 июня 2010 - 19:33
Нам надо учитывать все пересечения из получившихся комбинаций!!!
В первом пункте, где начало единица, мы учли и те, что содержат 4 нуля, и те, что заканчиваются на два нуля
Во втором, мы учли и первое, и третье условие и т.д.
Чтобы получить конечное число вариантов, надо из суммы (128+64+70) вычесть 3 пересечения пар условий и прибавить 2 пересечение тройки условий
[картинка]
(128+64+70)-32-15-35+2*10 = 200 вариантов
По формуле включений-исключений |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
Так что ответ
128+64+70-32-15-35+10 = 190 вариантов
Сообщение изменено: Co0l (02 июня 2010 - 19:34 )
#148
Отправлено 03 июня 2010 - 09:15
#149
Отправлено 03 июня 2010 - 10:49
1. Сколькими способами можно составить строку битов длиной 8, которая не содержит подстроку 010.
2. Fn, Ln - числа Фибоначчи и Люка соответственно.
Доказать: Ln=F(n-1) + F(n+1)
3. Найти общий член последовательности, если:
An - 2A(n-1) - 15A(n-2) = 32 - 16n
A0=-1; A1=12
#150
Отправлено 03 июня 2010 - 12:00
1. Сколько существует слов из 5 букв, составленных из букв слова PANNKOOK, таких, что две одинаковые буквы не стоят рядом.
2. Fn, Ln - числа Фибоначчи и Люка соответственно.
Доказать: 5*Fn = L(n-1)+L(n+1)
3. Найти общий член последовательности, если:
An - 4A(n-1) + 3A(n-2) + 8 = 0
A0=1; A1=3
Сообщение изменено: teonoja (03 июня 2010 - 12:01 )