КАТЕГОРИИ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) П Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военно дело (14632) Висока технологиите (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къщи- (47672) журналистика и SMI- (912) Izobretatelstvo- (14524) на външните >(4268) Informatika- (17799) Iskusstvo- (1338) История- (13644) Компютри- (11121) Kosmetika- (55) Kulinariya- (373) култура (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23,702) Matematika- (16,968) инженерно (1700) медицина-(12,668) Management- (24,684) Mehanika- (15423) Naukovedenie- (506) образование-(11,852) защита truda- (3308) Pedagogika- (5571) п Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) oligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97182) от промишлеността (8706) Psihologiya- (18,388) Religiya- (3217) с комуникацията (10668) Agriculture- (299) Sotsiologiya- (6455) спортно-(42,831) Изграждане, (4793) Torgovlya- (5050) превозът (2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596 ) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Telephones- (8441) Elektrotehnika- (4623) Мощност инженерно (12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

повторение отношения




Числата на Фибоначи.

При решаването на много проблеми, комбинаторни използван метод за намаляване на този проблем до проблем, свързан с по-малък брой елементи. Например, възможно е да се получи формула за броя на пермутации:

,

Това показва, че Той винаги може да бъде намален до по-малък брой на факториел.

Една добра илюстрация на строителството е проблем на Фибоначи повторение отношения. В книгата си, в 1202, на италианския математик Фибоначи донесе следния проблем. Чифт зайци носи носилката веднъж месечно, два заека (мъже и жени), с новородени зайци, два месеца след раждането на себе си донесе потомство. Колко зайци ще бъде в една година, ако в началото имаше една двойка зайци.

От условието на задачата, че след месец ще има две двойки зайци, два месеца потомство ще дам само първата двойка зайци, се появи преди два месеца, така че всички ще има 3 двойки зайци. Месец по-късно той ще има 5 двойки. И така нататък.

Ние означаваме с брой двойки зайци след месеца, считано от началото на годината. След това чрез месец броят на двойки зайци могат да бъдат намерени от формулата:

,

Тази връзка се нарича рецидив връзка. Думата "рекурсия" означава връщане назад (в нашия случай - връщане към предишните резултати).

По предположение, и Тогава съотношението имаме: , , и т.н., ,

Определение 1: Числата Те призоваха числата на Фибоначи. Това е - добре познат в областта на математиката поредица от числа:

1, 1, 2, 3, 5, 8, 13, 21, ...

В тази последователност, всеки следващ брой е сумата от предходните две числа. И съотношението на рецидиви както последователен мандат е сумата от предходните две условия.

Установяване на връзка между числата на Фибоначи и комбинаторна проблема. Да предположим, че искате да намерите броя - последователности, състоящи се от нули и единици, в които няма две единици, които не са последователни.

Ние приемаме такава последователност и я възлага чифт зайци по следния начин: дяловете на съответния месец на раждането на една от двойките "предшественици" на двойката (включително оригинала) и нули - всички други месеца. Например, последователността създава "генеалогия" - самата двойка се появи в края на 11-ия месец, родителите й в края на 7-мия месец, "Дядо" - в края на 5-ия месец, и "дядо" в края на второто месец. Първоначалната двойката криптирани последователност , Във всеки последователност от две единици, които не могат да стоят в един ред - просто се появи мъж и жена не може да произвежда потомство в един месец. Очевидно е, че различни последователности отговарят на различни двойки и обратно.

Така броят последователности с тези свойства, както и ,

Теорема 1: Броят на е сумата от двучленни коефициенти: , ако - странно, а след това , ако - дори, , в противен случай: - неразделна част от ,



Доказателство: В действителност, - броят на последователности от 0 и 1, в която няма две са в близост до уреда. Броят на последователности, съдържащи точно единици и нули, равен докато след това варира от 0 до , Прилагането на принципа на суми, получени от дадено количество.

Това уравнение може да бъде доказано по друг начин. означаваме:

, ,

на равенство От това следва, че , Освен това, ясно е, че и , Тъй като и двете последователности, и удовлетворява отношението повторение след това и ,

Дефиниция 2: отношението на рецидивите е от порядъка Ако това ви дава възможност да се изчисли през предходните членове на последователността: ,

Например, - повтаряне на втори ред, и повторение на трети ред. Фибоначи съотношение е съотношението на втория ред.

Дефиниция 3: Решение повторение връзка е последователност задоволим тази връзка.

Ако е зададено повторение - ред, това ще задоволи безкрайно много поредици като първи елементи могат да бъдат определени произволно. Но ако първият елементи са дадени, останалите членове са еднозначно определени.

Например, съотношението на Фибоначи Освен по-горе последователност 1, 1, 2, 3, 5, 8, 13, 21, ... може да отговарят и на другите последователности. Например, последователността, 2, 2, 4, 8, 12, ... се основава на същия принцип. Но ако първоначалните елементи (в тяхната последователност Фибоначи - 2), след това разтворът се определя еднозначно. Първоначалните членове да вземат толкова много, това, което е от порядъка на съотношението.

Известните повторение отношения и първоначалните членове могат да предписват от гледна точка на последователността един след друг и по този начин можем да получим някой от неговите членове. Но в много случаи не се нуждаем от всички предишни членове, и се нуждае от един конкретен потребител. В този случай, това е по-удобно да има формулата - ти срок на последователност.

Ние казваме, че последователност е разтвор на връзката на повторение, ако се извършва съотношението на заместване от идентичността на последователността.

Например, последователността Това е едно от решенията на връзката: , Това е лесно да се провери нормалното си пермутация.

Дефиниция 4: Решението на отношението на рецидив - За да се нарича общо ако зависи от произволни константи Промяната, която можете да получите всякаква решение на този коефициент.

Например, за съотношението общо решение ще ,

В действителност, това е лесно да се провери, че това е решението на нашата връзка. Ние показваме, че всяко решение може да се получи по този начин. нека и - произволно.

Тогава там са и че

Очевидно е, че за всеки , системата от уравнения има уникално решение.

Определение 5: отношението на повторение се нарича линейна, ако е писано в следния вид:

,

където - числените коефициентите.

За решаването на произволно повторение на общи правила за взаимоотношения, най-общо казано, не. Въпреки това, за решаването на задачи за повторение отношения имат общи правила решения.

Помислете първо съотношението на 2-ри ред ,

Решаването на тези отношения се основава на следните твърдения.

Теорема 2: Ако и - са разтвора на връзката на повторение на ред 2, след това за всички номера и последователност Това също е решение на тази връзка.

Теорема 3: Ако броят на Това е коренът на квадратното уравнение , След това последователността Това е решение на отношението на рецидив ,

Теореми 2 и 3 имаме следното правило за решаване на линейни повторение отношения на 2-ри ред.

Да предположим, че ние сме като се има предвид връзката повторение ,

1) образуване на квадратно уравнение Което се нарича характеристика за това съотношение. Намери всички корените на това уравнение (дори и многобройни и сложни).

2) общо решение на връзката на рецидив. Неговата структура е в зависимост от формата на корените (те са еднакви или различни).

а) Ако тази връзка има два отделни корени и , Общото решение се дава с отношението ,

Действително, от теореми 2 и 3 означава, че - разтвор и система от уравнения

- едно решение, защото осигурен ,

Например, за числата на Фибоначи, ние имаме , Характерните уравнението е: , Решаването на това уравнение, ние откриваме корените:

,

така общото решение на съотношения Фибоначи е както следва:

,

За началните условия и , т.е. за съгласуваност Ние получи за константите и система:

и ,

следователно

,

Този израз за всички физически Това е цяло число.

б) Ние сега разгледаме случая, когато корените на уравнението характеристика едно и също, т.е. след това , , т.е. характеристика уравнение на формата ,

В този случай връзката на рекурсия е в следния формат:

,

Ние показваме, че наред с изразяване - това също е решение на нашата връзка. наистина:

,

И цялостното решение в този случай ще бъде:

,

Лесно е да се види, че и Тук могат да бъдат избрани така, че всички начални условия ще бъдат изпълнени.

Забележка: Линейни повторение отношения с постоянни коефициенти на заповед по-голяма от два са решени по подобен начин.

Нека връзката е , Ние правим до характерното уравнение: ,

Ако всички корените на характеристика уравнение са различни, общото решение има формата: ,

Ако, например, След това основата на съответните разтвори:

Това повторение връзка. Общото решение на този корен съответства на част ,

Например, решаване на връзката повторение:

,

Ние правим до характерното уравнение от вида: ,

своите корени , , Следователно, общото решение е:

,