Дискретная математика.
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Дискретная математика. - 2009-11-20 16:22:43.790000
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Привет всем, кого давно не "видел")
Завтра что-то вроде среза по дискретной математике. Один тип задач не успел разобрать. Не знаю как решить.
Условие: Найти количество слов длины n в алфавите {0,1,2}, в которых нет цифр 0 и 1 по соседству.
50 просмотров и ни одного ответа. Призываю душу rgo..)
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:02:42.986666
|
|
|
The Joker
Сообщений: 3485
Оценки: 99
Присоединился: 2008-10-07 16:22:13.730000
|
quote:
ORIGINAL: Head60ty4
50 просмотров и ни одного ответа. Призываю душу rgo..) Звук 5 секунд
Ммм, я как бы понимаю, что надо найти, но не знаю алгоритма. Поэтому я бы посчитал количество возможных "слов" (т.н. размещений этих трёх символов) длины n. Потом посчитал количество возможных сочетаний 01 в комбинациях длины n. Потом умножил бы эти сочетания на 2, чтобы учесть и 01, и 10. А в конце вычел бы эти сочетания из общего количества слов.
Пример:
n = 4
k = 3
A(n,k) = A(4,3) = n!/(n-k)! = 4! / (4-3)! = 24/1=24 # 24 возможных слова
B(n, {01}) = 4 # не знаю, как формализовать
# 01XX; X01X, XX01, 0101, где X не равно 0 или 1
B(n, {10}) = 4 # те же комбинации, только 1 и 0 поменять местами
Результат = A - 2B = 16 # слов, не содержащих 0 и 1 по соседству.
quote:
ORIGINAL: Head60ty4
50 просмотров и ни одного ответа. Призываю душу rgo..) updаtе: rgo смотрит тему. Ну ты маг!
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:07:21.960000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: Head60ty4
Призываю душу rgo..)
xD
Я подумаю. Щаз времени нету. А ты попробуй сосчитать те слова, в которых есть 1 и 0 по соседству. Иногда помогает считать то, что не нужно. Мне почему-то кажется, что это как раз тот случай.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:15:32.306666
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
The Joker и rgo, спасибо :) Такое уже рассматривал. Метод включения и исключения. Но никак с конечной формулой не могу определиться :\
Ничего, ещё весь вечер на задачу.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:19:55.760000
|
|
|
leo_new
Сообщений: 132
Оценки: 0
Присоединился: 2009-01-15 14:26:47.973333
|
засунь в массив да сравнивай посимвольно
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:27:36.956666
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Так не пойдёт) n ведь. Да и программирование было позавчера (= Завтра дискретка.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:38:29.460000
|
|
|
leo_new
Сообщений: 132
Оценки: 0
Присоединился: 2009-01-15 14:26:47.973333
|
quote:
ORIGINAL: Head60ty4
Так не пойдёт) n ведь. Да и программирование было позавчера (= Завтра дискретка.
все засунул в массив А
начал посимвольно считывать с А(0) и засовывать в массив Б
условие: засунуто в массив Б n-символов?
->ДА - > считать массив Б в переменную и сравнить с условием {0.1} -> условие {0.1} не выполняеться? -> очистил массив Б и начал посимвольно считывать с А(1) и засовывать в массив Б ….
P.S. чё то я замудрил…можно же и с одним массивом сработать.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:41:08.780000
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Не оффтопь пожалуйста.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 18:46:16.226666
|
|
|
The Joker
Сообщений: 3485
Оценки: 99
Присоединился: 2008-10-07 16:22:13.730000
|
quote:
ORIGINAL: leo_new
засунь в массив да сравнивай посимвольно Куда засунуть? Человеку надо понять, как решается данный тип задач и сдать экзамен по дискретной математике.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 19:41:33.210000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Мысль о рекурсии возникла. Если мы знаем два числа:
a_k – это количество слов длины k, в которых не соседствуют 1 и 0, причём слов заканчивающихся на 2,
b_k – это количество слов длины k, в которых не соседствуют 1 и 0, причём слов заканчивающихся на 1 или 0,
тогда:
a_{k+1} = a_k + b_k,
b_{k+1} = 2*a_k + b_k.
Вроде так? Ну, я просто беру подходящее слово длины k, и приписываю к нему в конец ещё один символ. И считаю сколькими способами это можно сделать.
Поскольку мы знаем что:
a_1 = 1
b_1 = 2
то мы можем сосчитать всё что надо. Мы имеем реккуретнтное соотношение, которое в принципе можно назвать ответом на поставленный вопрос. Ну, по-крайней мере, если бы я на экзамене решал эту задачу, я бы сунул это реккурентное соотношение под нос экзаменатору и назвал бы его ответом. Если бы экзаменатор выразил бы недоумение, я бы начал давить на то, что реккурентное соотношение имеет полное право на существование. А не на экзамене, я бы взял ручку с бумажкой, и выразил бы a_n, b_n, через a_{n-2} и b_{n-2}. Может потом выразил бы через a_{n-3} и b_{n-3}. В надежде что просветление наступит.
Более простого способа получить явную зависимость, я не вижу.
[added]
ps. используемая запись:
a_k – это a с индексом k
a_{k+1} – это a с индексом k+1.
Типа как в TeX'е.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 19:46:14.223333
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Спасибо. Ща, обдумаю немного..)
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 20:00:49.090000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: The Joker
quote:
ORIGINAL: Head60ty4
50 просмотров и ни одного ответа. Призываю душу rgo..) Звук 5 секунд
Ммм, я как бы понимаю, что надо найти, но не знаю алгоритма. Поэтому я бы посчитал количество возможных "слов" (т.н. размещений этих трёх символов) длины n. Потом посчитал количество возможных сочетаний 01 в комбинациях длины n. Потом умножил бы эти сочетания на 2, чтобы учесть и 01, и 10. А в конце вычел бы эти сочетания из общего количества слов.
То ли я не понимаю, то ли неправильно это.
Количество слов длины n – это 3^n, в любой позиции в слове может стоять один из трёх символов. Но внутри слова может попастся 01 или 10, или 101, 1001, 010101. То есть мне непонятно как считать количество возможных сочетаний 01 в комбинациях длины n. А это и есть самое инересное. Вот сколько раз соседствует 0 и 1 в 01010101?
quote:
B(n, {01}) = 4 # не знаю, как формализовать
# 01XX; X01X, XX01, 0101, где X не равно 0 или 1
хм. При n == 4 всё просто. А если n == 5?
01xxx. Под xxx опять же может прятаться 01. Тут проблема как бы не сосчитать одно и то же дважды.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-20 20:11:19.573333
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
<Вот сколько раз соседствует 0 и 1 в 01010101?>
Да это не важно. Как только обнаруживается первое соседство-вычёркиваем число из списка. И так из всех возможных вариантов отнимаем этот и ему подобные, с парочкой 01 или 10.
ps: <a_{k+1} = a_k + b_k,
b_{k+1} = 2*a_k + b_k.>
Вот это почему так я, откровенно говоря, не понимаю. Ну да ладно-если это не помогает делу.
Есть такая идея. В позицию n ставим 2. Тогда на позиции (n-1) ни 0, ни 1 ставит нельзя. Таким образом сократили слово до (n-2). {*2*2*2*2….*2*2*2, где *-место где может быть 1 или 0. За левую границу не отвечаю-может заканчиваться и * и 2. В зависимости от значения n}Аналогично доведём до (n-n). Это будет 1 вариант с 1 или 0 через один. Таких позиций для 0 или 1 будет (n/2). Это у нас (2!/((n/2)-2)!*(n/2)) вариантов. Далее допустим что где-то идёт две подряд двойки. {*2*2*2*2….*22*} Так мы выстрелили одно место. Это у нас стало ( (2!/((n/2)-2)!*(n/2)) - (2!/(((n/2)-1)-2)!*((n/2)-1)) вариантов. УРА!! Рго, вроде всё верно? Надеюсь у тебя хватит терпения разобраться в куче скобок. И так у нас дойдёт до (n-n). В итоге в отвечет будет два сочетания минус здоровая сумма, красиво-записанная буквочкой сигма. Сработает?
.
.
.
вот только один недочёт остался в решении. Надо ещё зафиксировать количество вариантов с двойной двойкой, тройной и т.д. Она ведь гулять может направо налево по слову **22* или *22** и всё это надо учесть. Вроде осталось только это.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-21 12:41:05.800000
|
|
|
leo_new
Сообщений: 132
Оценки: 0
Присоединился: 2009-01-15 14:26:47.973333
|
А домашнее задание оказалось не таким уж и легким как это показалось в начале?
|
|
|
|
|
RE: Дискретная математика. - 2009-11-21 16:02:12.600000
|
|
|
The Joker
Сообщений: 3485
Оценки: 99
Присоединился: 2008-10-07 16:22:13.730000
|
quote:
ORIGINAL: rgo
То ли я не понимаю, то ли неправильно это…. Да, это действительно неправильно.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-21 16:05:41.716666
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Это не домашка. Просто готовился к срезу.
Срез написал. Решил все, помимо последней-такого типа :\ После следующего занятия по дискретке отпишу здесь как её надо было решать, если кому любопытно.
|
|
|
|
|
RE: Дискретная математика. - 2009-11-27 20:48:26.870000
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
http://i033.radikal.ru/0911/c7/d051757b7570.jpg
Вот решение. Задача такого же типа. Условие такое-Сколько слов длины n можно составить из букв алфавита {0,1,2}, при условии что сочетание 02 невозможно (20 можно.)
Слепили решение из ничего. Даже досадно(
|
|
|
|
|
RE: Дискретная математика. - 2009-11-28 07:26:44.733333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
ну дык тоже реккурентное соотношение. и оно получается, по сути, из моей системы реккурентных соотношений. :)
|
|
|
|
|
RE: Дискретная математика. - 2009-11-28 10:21:17.430000
|
|
|
Head60ty4
Сообщений: 1228
Оценки: 0
Присоединился: 2007-08-31 17:18:07.236666
|
Угу =) Только сам я оттуда не видел решения, пока не втолковали.
В ближайшие дни скину задачку ещё одну. Пока сам над ней подумаю, но пока туговато идёт. )
|
|
|
|
|
RE: Дискретная математика. - 2009-11-28 11:27:40.893333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
=)
а самое обидное, что мы не довтыкали, что решение берётся "в лоб", надо просто взять систему и исключить одну неизвестную. Уровень девятого класса.
Хотя мне кажется, если препод не совсем сволочь, ему можно было бы втереть, что реккурентная система ничем не хуже реккурентного соотношения. Собственно переход от системы к одному соотношению – это ведь просто "упрощение", которые очень любят в школьной математике, там куча задач типа "упростите выражение". А мне в универе втирали, что все "упрощения" – это достаточно бредовая деятельность, если они упрощения ради упрощения; если они не преследуют какую-то более глубинную цель. Я так и сдавал вечно. Надо взять интеграл? Я избавлю выражение от значка интеграла, получу выражение на полстраницы, и, забивая на то, что где-то что-то выноситься за скобку, что какие-то суммы сворачиваются, что где-то что-то сокращается, я выдам это за искомый ответ. Возражений со стороны преподов я не замечал, иногда бывало лёгкое недовольство, иногда они начинали тыкать пальцем, что тут можно упростить, но этим всё и заканчивалось, а зачёт я получал.
|
|
|
|
|
|
