C, PHP, VB, .NET

Любимата ми група The Exploited е много стара, но за сметка на това не може да се похвали с огромно количество студийни албуми. За вече над 30 годишното си съществуване те имат само 9. Ето ги:

1. Punks Not Dead – 1981
2. Troops of Tomorrow – 1982
3. Let’s Start a War… (Said Maggie One Day) – 1983
4. Horror Epics – 1985
5. Death Before Dishonour – 1987
6. The Massacre – 1990
7. Beat the Bastards – 1996
8. Fuck the System – 2003

Кога ще излезе следващия албум?

Можем да представим поредицата от текущите албуми като една редица. Ще се интересуваме от интервала между издаваните албуми, като първия ще го приемем за „началото на епохата“, т.е. стойност 0. Разликата между първия и втория албум е една година, разликата между втория и третия е една година, разликата между третия и четвъртия е 2 и т.н. Получава се следната редица:

0 1 1 2 2 3 6 7

Ако знаем следващото число от редицата, то ще можем да кажем и през коя година ще бъде издаден албума. Какво казва математиката?

Търсим функция f(x) такава, че:

f(1) = 0
f(2) = 1
f(3) = 1
f(4) = 2
f(5) = 2
f(6) = 3
f(7) = 6
f(8) = 7

Има два популярни начина да намерим полином, който „минава“ през тези точки. Първият е интерполационния полином на Лагранж:

0(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8) / ((1-2)(1-3)(1-4)(1-5)(1-6)(1-7)(1-8))+
1(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8) / ((2-1)(2-3)(2-4)(2-5)(2-6)(2-7)(2-8))+
1(x-1)(x-2)(x-4)(x-5)(x-6)(x-7)(x-8) / ((3-1)(3-2)(3-4)(3-5)(3-6)(3-7)(3-8))+
2(x-1)(x-2)(x-3)(x-5)(x-6)(x-7)(x-8) / ((4-1)(4-2)(4-3)(4-5)(4-6)(4-7)(4-8))+
2(x-1)(x-2)(x-3)(x-4)(x-6)(x-7)(x-8) / ((5-1)(5-2)(5-3)(5-4)(5-6)(5-7)(5-8))+
3(x-1)(x-2)(x-3)(x-4)(x-5)(x-7)(x-8) / ((6-1)(6-2)(6-3)(6-4)(6-5)(6-7)(6-8))+
6(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-8) / ((7-1)(7-2)(7-3)(7-4)(7-5)(7-6)(7-8))+
7(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7) / ((8-1)(8-2)(8-3)(8-4)(8-5)(8-6)(8-7)) = f(x)

Другият е формулата на Нютон за разделените разлики):

f(x) = x-1-
(x-1)(x-2)/2+
2(x-1)(x-2)(x-3)/(2*3)-
4(x-1)(x-2)(x-3)(x-4)/(2*3*4)+
8(x-1)(x-2)(x-3)(x-4)(x-5)/(2*3*4*5)-
13(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)/(2*3*4*5*6)+
14(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)/(2*3*4*5*6*7)

И двата полинома се опростяват (интерполационния полином на Лагранж и формулата на Нютон дават като резултат едни и същи полиноми) до:

[math]f(x) = x^7/360-23x^6/240+193x^5/144-469x^4/48+28613x^3/720-1337x^2/15+1211x/12-43[/math]

Вече можем да потърсим колко години ще е разликата между 8мия и 9тия албум на групата:

[math]f(9) = 9^7/360-23*9^6/240+193*9^5/144-469*9^4/48+28613*9^3/720-1337*9^2/15+1211*9/12-43[/math]

[math]=> f(9) = 8[/math]

Това е и следващото число от поредицата. Тоест The Exploited би трябвало да издадат албума си през 2003+8 = … 2011г. Е, за наше голямо съжаление групата НЕ издаде албум през 2011г., т.е. каквото и да правят в момента – хей момчета, изоставате от графика си!

Разбира се горните съждения бяха тотално погрешни, защото когато и да издадат нов албум, ние винаги можем да намерим нов полином, който минава през всички точки, включително новата. Той просто ще е от по-висока с единица степен. Ако например приемем, че The Exploited ще издадат нов албум догодина (т.е. 2013г., ха дано), то разликата с последния албум ще е 10 години и редицата ще е станала 0 1 1 2 2 3 6 7 10. Интерполационният полином ще е:

0(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) / ((1-2)(1-3)(1-4)(1-5)(1-6)(1-7)(1-8)(1-9))+
1(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) / ((2-1)(2-3)(2-4)(2-5)(2-6)(2-7)(2-8)(2-9))+
1(x-1)(x-2)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) / ((3-1)(3-2)(3-4)(3-5)(3-6)(3-7)(3-8)(3-9))+
2(x-1)(x-2)(x-3)(x-5)(x-6)(x-7)(x-8)(x-9) / ((4-1)(4-2)(4-3)(4-5)(4-6)(4-7)(4-8)(4-9))+
2(x-1)(x-2)(x-3)(x-4)(x-6)(x-7)(x-8)(x-9) / ((5-1)(5-2)(5-3)(5-4)(5-6)(5-7)(5-8)(5-9))+
3(x-1)(x-2)(x-3)(x-4)(x-5)(x-7)(x-8)(x-9) / ((6-1)(6-2)(6-3)(6-4)(6-5)(6-7)(6-8)(6-9))+
6(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-8)(x-9) / ((7-1)(7-2)(7-3)(7-4)(7-5)(7-6)(7-8)(7-9))+
7(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-9) / ((8-1)(8-2)(8-3)(8-4)(8-5)(8-6)(8-7)(8-9))+
10(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8) / ((9-1)(9-2)(9-3)(9-4)(9-5)(9-6)(9-7)(9-8)) = f(x)

[math]=> f(x) = x^8/20160+x^7/1008-11x^6/160+803x^5/720-8311x^4/960+2621x^3/72-419701x^2/5040+20051x/210-41[/math]

Ако приемете друга година, например 2015, то редицата ще стане 0 1 1 2 2 3 6 7 12 и вие лесно ще намерите друг интерполационен полином. Всъщност:

• Което и число да сложите на края на която и да е редица, винаги ще съществува полином, който да я интерполира по показания начин!

Следователно задачите от типа „познайте следващото число в редицата“ винаги имат лесно тривиално решение по алгоритъм с намиране на интерполационен полином. Дали обаче то е „решението, което човека търси“ е напълно субективен фактор. Всъщност решение на задачата „намерете следващото число от редицата x1, x2, x3, …, xn“ може да е което и да е число по ваш дори произволен избор. Затова когато някой ви даде задача от типа „намерете следващото число…“ се обърнете към него и му кажете смело „следващото число е ПЕТ!“. И няма да сбъркате – ще можете да му намерите формула, по която наистина ще се получава, че числото е точно 5 :)