MCP рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдХрдиреЗрдХреНрдЯ рдХрд░реЗрдВ тЖТ

рдЧрдгрдирд╛ рджрд░реНрдЬ рдХрд░реЗрдВ

рдПрдХ рдЛрдг-рд░рд╣рд┐рдд рдкреВрд░реНрдгрд╛рдВрдХ рджрд░реНрдЬ рдХрд░реЗрдВ (0 рд╕реЗ 92 рддрдХ)ред

рд╕реВрддреНрд░ (рдлреЙрд░реНрдореВрд▓рд╛)

рд╡рд┐рдЬреНрдЮрд╛рдкрди

рдкрд░рд┐рдгрд╛рдо

Fibonacci number F(10)
55
рдлрд┐рдмреЛрдирд╛рдЪреА рд╢реНрд░реЗрдгреА рдХрд╛ n-рд╡рд╛рдБ рдкрдж
рдкрдж рд╕реВрдЪрдХрд╛рдВрдХ (n) 10
F(0) рд╕реЗ F(n) рддрдХ рдХрд╛ рдпреЛрдЧ 143
рд╕реНрд╡рд░реНрдгрд┐рдо рдЕрдиреБрдкрд╛рдд ╧Ж 1.618034

рдлрд┐рдмреЛрдирд╛рдЪреА рд╢реНрд░реЗрдгреА рдХреНрдпрд╛ рд╣реИ?

рдлрд┐рдмреЛрдирд╛рдЪреА рд╢реНрд░реЗрдгреА рдЧрдгрд┐рдд рдХреЗ рд╕рдмрд╕реЗ рдкреНрд░рд╕рд┐рджреНрдз рдкреИрдЯрд░реНрди рдореЗрдВ рд╕реЗ рдПрдХ рд╣реИред рдпрд╣ 0 рдФрд░ 1 рд╕реЗ рд╢реБрд░реВ рд╣реЛрддреА рд╣реИ, рдФрд░ рдЗрд╕рдХреЗ рдмрд╛рдж рдХреА рд╣рд░ рд╕рдВрдЦреНрдпрд╛ рдЕрдкрдиреЗ рдареАрдХ рдкрд╣рд▓реЗ рдХреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ рд╣реЛрддреА рд╣реИ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, рдФрд░ рдЗрд╕реА рддрд░рд╣ рдЖрдЧреЗред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЖрдкрдХреЗ рдЪреБрдиреЗ рд╣реБрдП рдХрд┐рд╕реА рднреА рдЛрдг-рд░рд╣рд┐рдд (non-negative) рд╕реВрдЪрдХрд╛рдВрдХ рдХреЗ рд▓рд┐рдП \(F(n)\) рдпрд╛рдиреА n-рд╡рд╛рдБ рдкрдж рд▓реМрдЯрд╛рддрд╛ рд╣реИ, рд╕рд╛рде рд╣реА рдЙрд╕ рдмрд┐рдВрджреБ рддрдХ рдХреЗ рд╕рднреА рдкрджреЛрдВ рдХрд╛ рдЪрд▓рддрд╛ рдпреЛрдЧ рдФрд░ рд╡рд╣ рд╕реНрд╡рд░реНрдгрд┐рдо рдЕрдиреБрдкрд╛рдд \(\varphi\) рднреА рдмрддрд╛рддрд╛ рд╣реИ рдЬрд┐рд╕рдХреА рдУрд░ рдпрд╣ рд╢реНрд░реЗрдгреА рдмрдврд╝рддреА рдЬрд╛рддреА рд╣реИред

1, 1, 2, 3, 5, 8 рднреБрдЬрд╛рдУрдВ рд╡рд╛рд▓реЗ рд╡рд░реНрдЧреЛрдВ рд╕реЗ рдмрдиреА рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рд░реНрдкрд┐рд▓
рд╣рд░ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдЕрдкрдиреЗ рд╕реЗ рдкрд╣рд▓реЗ рдХреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ рд╣реЛрддреА рд╣реИ, рдЬрд┐рд╕рд╕реЗ рдкреНрд░рд╕рд┐рджреНрдз рд╕рд░реНрдкрд┐рд▓ рдмрдирддреА рд╣реИред

рдЗрд╕ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ

рдкрдж рдХрд╛ рд╕реВрдЪрдХрд╛рдВрдХ \(n\) рджрд░реНрдЬ рдХрд░реЗрдВ (0 рд╕реЗ 92 рддрдХ рдХреА рдПрдХ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛) рдФрд░ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рддреБрд░рдВрдд \(F(n)\) рд▓реМрдЯрд╛ рджреЗрдЧрд╛ред 92 рдХреА рдКрдкрд░реА рд╕реАрдорд╛ рдЗрд╕рд▓рд┐рдП рд░рдЦреА рдЧрдИ рд╣реИ рддрд╛рдХрд┐ рдорд╛рдирдХ 64-рдмрд┐рдЯ рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ рдореЗрдВ рдкрд░рд┐рдгрд╛рдо рдмрд┐рд▓реНрдХреБрд▓ рд╕рдЯреАрдХ рд░рд╣реЗрдВ; рдЗрд╕рд╕реЗ рдЖрдЧреЗ рдХреЗ рдорд╛рди рдХреЗрд╡рд▓ рдЕрдиреБрдорд╛рдирд┐рдд рд╣реЛ рдЬрд╛рддреЗ рд╣реИрдВред рдкрд░рд┐рдгрд╛рдо рдкреИрдирд▓ рд╕рдВрдЪрдпреА рдпреЛрдЧ \(F(0)+F(1)+\dots+F(n)\) рднреА рджрд┐рдЦрд╛рддрд╛ рд╣реИ, рдЬреЛ рд╕реБрд╡рд┐рдзрд╛рдЬрдирдХ рд░реВрдк рд╕реЗ \(F(n+2) - 1\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред

рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛

рдЗрд╕рдХрд╛ рдореВрд▓ рдирд┐рдпрдо рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ рд╣реИ:

$$F(n) = F(n-1) + F(n-2),\quad F(0)=0,\ F(1)=1$$

рдЬрд┐рд╕рдХреЗ рдмреАрдЬ (рд╢реБрд░реБрдЖрддреА рдорд╛рди) \(F(0)=0\) рдФрд░ \(F(1)=1\) рд╣реИрдВред рдПрдХ рдмрдВрдж-рд░реВрдк рд╕реВрддреНрд░ рднреА рд╣реИ, рдЬрд┐рд╕реЗ рдмрд┐рдиреЗ рдХрд╛ рд╕реВрддреНрд░ (Binet's formula) рдХрд╣рддреЗ рд╣реИрдВ:

$$F(n) = \frac{\varphi^{n} - \psi^{n}}{\sqrt{5}},\quad \varphi=\frac{1+\sqrt5}{2}$$

рдЬрд╣рд╛рдБ \(\varphi = \frac{1+\sqrt5}{2} \approx 1.618\) рд╕реНрд╡рд░реНрдгрд┐рдо рдЕрдиреБрдкрд╛рдд рд╣реИ рдФрд░ \(\psi = \frac{1-\sqrt5}{2}\) рдЗрд╕рдХрд╛ рд╕рдВрдпреБрдЧреНрдореА (conjugate) рд╣реИред рдЬреИрд╕реЗ-рдЬреИрд╕реЗ \(n\) рдмрдврд╝рддрд╛ рд╣реИ, рд▓рдЧрд╛рддрд╛рд░ рдЖрдиреЗ рд╡рд╛рд▓реА рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдЕрдиреБрдкрд╛рдд \(F(n+1)/F(n)\) рдзреАрд░реЗ-рдзреАрд░реЗ \(\varphi\) рдХреА рдУрд░ рдЕрднрд┐рд╕рд░рд┐рдд рд╣реЛрддрд╛ рдЬрд╛рддрд╛ рд╣реИред

рджреЛ рдкрдЯреНрдЯрд┐рдпрд╛рдБ F(n-1) рдФрд░ F(n-2) рдорд┐рд▓рдХрд░ рдкрдЯреНрдЯреА F(n) рдмрдирд╛рддреА рд╣реИрдВ
рд╕реВрддреНрд░: рд╣рд░ рдкрдж рдкрд┐рдЫрд▓реЗ рджреЛ рдкрджреЛрдВ рдХреЗ рдпреЛрдЧ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред

рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг

рдорд╛рди рд▓реАрдЬрд┐рдП \(n = 10\)ред рд╢реНрд░реЗрдгреА рдХреЛ рдХреНрд░рдо рд╕реЗ рдмрдирд╛рддреЗ рд╣реБрдП: \(F(2)=1\), \(F(3)=2\), \(F(4)=3\), \(F(5)=5\), \(F(6)=8\), \(F(7)=13\), \(F(8)=21\), \(F(9)=34\), \(F(10)=55\)ред рдпрд╛рдиреА \(F(10) = 55\)ред \(F(0)\) рд╕реЗ рд▓реЗрдХрд░ \(F(10)\) рддрдХ рдХрд╛ рдпреЛрдЧ $$F(12) - 1 = 144 - 1 = 143$$ рд╣реЛрддрд╛ рд╣реИред

рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓

рдХреНрдпрд╛ рдпрд╣ рд╢реНрд░реЗрдгреА 0 рд╕реЗ рд╢реБрд░реВ рд╣реЛрддреА рд╣реИ рдпрд╛ 1 рд╕реЗ? рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдорд╛рдирдХ рдкрд░рдВрдкрд░рд╛ \(F(0)=0\) рдФрд░ \(F(1)=1\) рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(F(2)=1\) рд╣реЛрддрд╛ рд╣реИред

n рдХреА рд╕реАрдорд╛ 92 рдкрд░ рд╣реА рдХреНрдпреЛрдВ рд░рдЦреА рдЧрдИ рд╣реИ? \(F(92)\) рд╡рд╣ рд╕рдмрд╕реЗ рдмрдбрд╝реА рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдЬреЛ 64-рдмрд┐рдЯ рд╕рд╛рдЗрдиреНрдб рдкреВрд░реНрдгрд╛рдВрдХ рдореЗрдВ рдмрд┐рд▓реНрдХреБрд▓ рд╕рдЯреАрдХ рд╕рдорд╛ рдЬрд╛рддреА рд╣реИ; рдЗрд╕рд╕реЗ рдмрдбрд╝реЗ рд╕реВрдЪрдХрд╛рдВрдХреЛрдВ рдкрд░ рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ рдЦреЛ рдЬрд╛рдПрдЧреАред

рд╕реНрд╡рд░реНрдгрд┐рдо рдЕрдиреБрдкрд╛рдд рдХрд╛ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕реЗ рдХреНрдпрд╛ рд╕рдВрдмрдВрдз рд╣реИ? рд╣рд░ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдЙрд╕рдХреЗ рдкрд┐рдЫрд▓реЗ рдкрдж рд╕реЗ рднрд╛рдЧ рджреЗрдиреЗ рдкрд░ рдЬреЛ рдорд╛рди рдорд┐рд▓рддрд╛ рд╣реИ, рд╡рд╣ \(\varphi \approx 1.6180339887\) рдХреЗ рдФрд░-рдФрд░ рдХрд░реАрдм рд╣реЛрддрд╛ рдЬрд╛рддрд╛ рд╣реИред

рдЕрдВрддрд┐рдо рдЕрдкрдбреЗрдЯ: