2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 
Сообщение11.12.2008, 00:41 
Аватара пользователя
Цитата:
Меня это решение очень заинтересовало. Но я не знаю, что такое рекуррентные соотношения, только сегодня начал читать про них. Можешь объяснить как их считать? Какие начальные значения?


Это простой индукционный шаг, в котором, при уверенности в правильности всех предыдущих, делается обоснованно-корректное продвижение "вперед". Все начинается с базы - первого шага, в данном случае $g_2 = 6, g_1 = 2$ в чем легко убедится мелким перебором.

Цитата:
А как это так получилось? Здесь используется правило суммы и произведения? Как составлена эта формула? Или это общее решение рекуррентного соотношения?


Всего навсего используется тот факт, что буква 'b' может стоять только между двумя "небэ" (ну или в конце, начале цепочки).

 
 
 
 
Сообщение11.12.2008, 01:38 
xaxa3217, точно индукционный шаг, не подумал про него. Уже разобрался, кажется, перебором. т.е. для n=1 возможны вариант "а" "b" "c" g1=2;
для n=2 "аа" "bb" "ac" "ba" "bb" "bc" "ca" "cb" "cc" g2=6 и тд. формула подходит.

Пока не могу осознать, почему искомое число равно $f_7+g_7$.

Добавлено спустя 15 минут 44 секунды:

в итоге получилось 1224. т.е. больше половины от числа возможных цепочек без ограничения (2187).

 
 
 
 
Сообщение11.12.2008, 02:06 
Аватара пользователя
Не спешите доходить до $f_7 + g_7$ :) Обратите внимание еще раз на то, как были определены эти две последовательности. Перечитайте первое мое сообщение в этой теме, там вроде бы все понятно изложено. Отмечу только, что мы разбиваем искомое число вариантов на два НЕ пересекающихся класса цепочек - тех что оканчиваются на 'b' и не содержат в себе подстроки 'bb', и те что оканчиваются на что-то другое 'a' или 'c'. Любая строка не принадлежащая ни первому, ни второму классу нас вообще не устраивает (в ней есть подстрока 'bb'), именно поэтому $f_7+g_7$ в результате дает нужное кол-во.

 
 
 
 
Сообщение11.12.2008, 02:46 
Вроде бы даже разобрался, однако расписал все возможные цепочки длины 3, а таких 27. в них присутствуют abb; bba;bbb;bbc;cbb - т.е. 5 плохих цепочки. В итоге 22 интересующие нас комбинации.
Смотрим формулы :
$g_3 = 2(g_1+g_2) = 2(2+6)=16, f_3=g_2=6;   f_3 + g_3 = 24$ что-то не сходится.

 
 
 
 
Сообщение11.12.2008, 09:25 
Аватара пользователя
apatic писал(а):
Total писал(а):
писал $$2^7C_8^0+2^6C_7^1+2^5C_6^2+2^4C_5^3+2^3C_4^4$$

А как это так получилось? Здесь используется правило суммы и произведения? Как составлена эта формула? Или это общее решение рекуррентного соотношения?

Поймайте $K$ двуглавых и $N-2K+1$ одноглавых драконов и прислоните их к стенке разными способами:
:evil: ,:mrgreen: :mrgreen:, :evil: , :evil: , :evil: ,:mrgreen: :mrgreen: (всего $C_{N-K+1}^K$ способов)
Левую голову каждого двуглавого дракона замените буквой $B$, а самую правую голову в шеренге отрубите:
:evil: ,$B$ :mrgreen:, :evil: , :evil: , :evil: ,$B -$
Оставшиесы головы замените буквами $A$ и $C$ разными способами:
$A,$ $BA,$ $C,$ $C,$ $A,$ $B -$ (всего $2^{N-K}$ способов)

Таким образом, существует $2^{N-K}C_{N-K+1}^K$ подходящих слов из $N$ букв с $K$ буквами $B$

 
 
 
 
Сообщение11.12.2008, 09:55 
Аватара пользователя
apatic, ну вы даете, я даже специально программку написал, чтобы не обсчитаться:
Код:
#include <math.h>
#include <stdio.h>

int main()
{
   int g[11];
   g[2] = 6;
   g[1] = 2;
   //

   for(int i = 3; i <=7; i++)
   {
      g[i] = 2*(g[i-1]+g[i-2]);
   }
   
   printf("%u\n", g[3]+g[3-1]);
   printf("%u\n", g[7]+g[7-1]);

   return 0;
}


У меня, признаюсь, часто ошибки такого рода возникают, так что видеть в '16' число равное 18 не Вы один умеете :)

 
 
 
 
Сообщение11.12.2008, 15:43 
Граждане, большое спасибо за помощь и конечно же за терпение(особое спасибо xaxa3217 и TOTAL). В 3 ночи уже мозг опух от комбинаторики и теории графов, а эта задача прямо-таки заклинила. Но утром разобрался, расписал и защитился. Ещё раз спасибо. Мне бы ваше терпение. :D

 
 
 [ Сообщений: 22 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group