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

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

n = 1, 2, 3, ...

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

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

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

Last Fibonacci value in table (n = 13)
233
рдЕрдВрддрд┐рдо рд╕реВрдЪрдХрд╛рдВрдХ рдкрд░ F_n
n F_n
Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдЯреЗрдмрд▓ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?

рдпрд╣ рдЯреВрд▓ рд╕реВрдЪрдХрд╛рдВрдХ (рдЗрдВрдбреЗрдХреНрд╕) рдорд╛рдиреЛрдВ рдХреА рдПрдХ рд░реЗрдВрдЬ рдХреЗ рд▓рд┐рдП рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛рдУрдВ \(F_n\) рдХреА рдЯреЗрдмрд▓ рдмрдирд╛рддрд╛ рд╣реИред рдЖрдк рдкрд╣рд▓рд╛ рдЗрдВрдбреЗрдХреНрд╕ n, рд╣рд░ рдкрдВрдХреНрддрд┐ рдореЗрдВ n рдХрд┐рддрдирд╛ рдмрдврд╝реЗрдЧрд╛ (рд╡реГрджреНрдзрд┐), рдФрд░ рдХрд┐рддрдиреА рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдЪрд╛рд╣рд┐рдП тАФ рдпрд╣ рд╕рдм рдЪреБрдирддреЗ рд╣реИрдВред рдЗрд╕рдХреЗ рдмрд╛рдж рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╣рд░ n рдХреЗ рд╕рд╛рде рдЙрд╕рдХрд╛ рдлрд┐рдмреЛрдирд╛рдЪреА рдорд╛рди рджрд┐рдЦрд╛рддрд╛ рд╣реИ рдФрд░ рдпрд╣ рднреА рджрд░реНрд╢рд╛рддрд╛ рд╣реИ рдХрд┐ рд╢реНрд░реГрдВрдЦрд▓рд╛ рдХрд┐рддрдиреА рддреЗрдЬрд╝реА рд╕реЗ рдмрдврд╝рддреА рд╣реИред рдпрд╣ рдкреВрд░реА рддрд░рд╣ рдЧрдгрд┐рддреАрдп рдЯреВрд▓ рд╣реИ, рдЗрд╕рд▓рд┐рдП рджреБрдирд┐рдпрд╛ рднрд░ рдореЗрдВ рдПрдХ рдЬреИрд╕рд╛ рдХрд╛рдо рдХрд░рддрд╛ рд╣реИ рдФрд░ рдЗрд╕рдореЗрдВ рдХрд┐рд╕реА рджреЗрд╢ рдпрд╛ рдХреНрд╖реЗрддреНрд░ рдХреА рдХреЛрдИ рдорд╛рдиреНрдпрддрд╛ рд╢рд╛рдорд┐рд▓ рдирд╣реАрдВ рд╣реИред

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

рд╕реВрдЪрдХрд╛рдВрдХ n рдХрд╛ рдкреНрд░рд╛рд░рдВрднрд┐рдХ рдорд╛рди (рдпрд╛рдиреА рдкрд╣рд▓рд╛ рджрд┐рдЦрдиреЗ рд╡рд╛рд▓рд╛ n), рд╡реГрджреНрдзрд┐ (рд╣рд░ рдкрдВрдХреНрддрд┐ рдореЗрдВ n рдХрд┐рддрдирд╛ рдмрдврд╝реЗ), рдФрд░ рджреЛрд╣рд░рд╛рд╡реЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ (рдХрд┐рддрдиреА рдкрдВрдХреНрддрд┐рдпрд╛рдБ) рджрд░реНрдЬ рдХрд░реЗрдВред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рдпрджрд┐ рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 1, рд╡реГрджреНрдзрд┐ 1 рдФрд░ 13 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдЪреБрдиреЗрдВ, рддреЛ рдпрд╣ рдХреНрд▓рд╛рд╕рд┐рдХ рд╢реНрд░реГрдВрдЦрд▓рд╛ 1, 1, 2, 3, 5, 8, ... рдмрдирд╛рддреА рд╣реИ рдФрд░ \(F_{13} = 233\) рддрдХ рдкрд╣реБрдБрдЪрддреА рд╣реИред

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

рдлрд┐рдмреЛрдирд╛рдЪреА рд╢реНрд░реГрдВрдЦрд▓рд╛ рдЗрд╕ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ (рд░рд┐рдХрд░реНрд╕рди) рд╕реЗ рдкрд░рд┐рднрд╛рд╖рд┐рдд рд╣реЛрддреА рд╣реИ:

$$F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \;\; (n \ge 3)$$

рдЗрд╕рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдмрд┐рдиреЗрдЯ рдХрд╛ рдмрдВрдж рд░реВрдк (Binet's formula) рднреА рд╣реИ тАФ

$$F_n = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \cdot \sqrt{5}}$$

рдЬреЛ рд╡рд╣реА рдкреВрд░реНрдгрд╛рдВрдХ рджреЗрддрд╛ рд╣реИ, рдкрд░ рдмрдбрд╝реЗ n рдХреЗ рд▓рд┐рдП рдлреНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рддреНрд░реБрдЯрд┐ рд╣реЛ рд╕рдХрддреА рд╣реИред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╕рдЯреАрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИред \(n \le 0\) рдХреЗ рд▓рд┐рдП рдпрд╣ рд╕рд╛рдорд╛рдиреНрдпреАрдХреГрдд (рдиреЗрдЧрд╛рдлрд┐рдмреЛрдирд╛рдЪреА) рдирд┐рдпрдо \(F_{-n} = (-1)^{n+1} F_n\) рдЕрдкрдирд╛рддрд╛ рд╣реИ, рдЬрд┐рд╕рд╕реЗ \(F_0 = 0\), \(F_{-1} = 1\), \(F_{-2} = -1\) рдорд┐рд▓рддрд╛ рд╣реИред

рдЖрд░реЗрдЦ рдЬреЛ рджрд┐рдЦрд╛рддрд╛ рд╣реИ рдХрд┐ рдкреНрд░рддреНрдпреЗрдХ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдкрд┐рдЫрд▓реА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ рд╣реИ
рдкреНрд░рддреНрдпреЗрдХ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдЙрд╕рд╕реЗ рдкрд╣рд▓реЗ рдХреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ рд╣реЛрддреА рд╣реИред

рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг

рдпрджрд┐ рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 5, рд╡реГрджреНрдзрд┐ 2 рдФрд░ 4 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рд╣реЛрдВ, рддреЛ n рдХреЗ рдорд╛рди 5, 7, 9, 11 рд╣реЛрдВрдЧреЗред рдЗрдирдХреЗ рдлрд┐рдмреЛрдирд╛рдЪреА рдорд╛рди рдХреНрд░рдорд╢рдГ 5, 13, 34 рдФрд░ 89 рд╣реИрдВред рдЗрд╕рд▓рд┐рдП рдЯреЗрдмрд▓ рдХрд╛ рдЕрдВрддрд┐рдо рдорд╛рди \(F_{11} = 89\) рд╣реЛрдЧрд╛ред

рдЧреНрд░рд╛рдлрд╝ рдЬрд┐рд╕рдореЗрдВ рд╕реВрдЪрдХрд╛рдВрдХ рдмрдврд╝рдиреЗ рдкрд░ рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛рдПрдБ рддреЗрдЬрд╝реА рд╕реЗ рдКрдкрд░ рдЙрдарддреА рд╣реИрдВ
рдЬреИрд╕реЗ-рдЬреИрд╕реЗ рд╕реВрдЪрдХрд╛рдВрдХ n рдмрдврд╝рддрд╛ рд╣реИ, рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛рдПрдБ F_n рддреЗрдЬрд╝реА рд╕реЗ рдмрдврд╝рддреА рд╣реИрдВред

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

рдХреНрдпрд╛ рд╡реГрджреНрдзрд┐ 1 рд╕реЗ рдЕрдзрд┐рдХ рд╣реЛ рд╕рдХрддреА рд╣реИ? рд╣рд╛рдБред рд╡реГрджреНрдзрд┐ 2 рд╣реЛрдиреЗ рдкрд░ рд╣рд░ рджреВрд╕рд░рд╛ рдЗрдВрдбреЗрдХреНрд╕, рд╡реГрджреНрдзрд┐ 3 рд╣реЛрдиреЗ рдкрд░ рд╣рд░ рддреАрд╕рд░рд╛ рдЗрдВрдбреЗрдХреНрд╕ рд▓рд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдФрд░ рдЗрд╕реА рддрд░рд╣ рдЖрдЧреЗред

рдХреНрдпрд╛ рдЛрдгрд╛рддреНрдордХ рд╕реВрдЪрдХрд╛рдВрдХ рд╕рдорд░реНрдерд┐рдд рд╣реИрдВ? рд╣рд╛рдБ, рдиреЗрдЧрд╛рдлрд┐рдмреЛрдирд╛рдЪреА рд╡рд┐рд╕реНрддрд╛рд░ рдХреЗ рдЬрд╝рд░рд┐рдПред рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 0 рд░рдЦрдиреЗ рдкрд░ \(F_0 = 0\) рдорд┐рд▓рддрд╛ рд╣реИред

n рдХрд┐рддрдирд╛ рдмрдбрд╝рд╛ рд╣реЛ рд╕рдХрддрд╛ рд╣реИ? рдорд╛рди 64-рдмрд┐рдЯ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рд╕реЗ рдЧрдгрдирд╛ рдХрд┐рдП рдЬрд╛рддреЗ рд╣реИрдВ рдФрд░ рд▓рдЧрднрдЧ \(F_{90}\) рддрдХ рд╕рдЯреАрдХ рд░рд╣рддреЗ рд╣реИрдВ; рдЗрд╕рдХреЗ рдЖрдЧреЗ рдмрд╣реБрдд рдмрдбрд╝реЗ рдорд╛рди рдУрд╡рд░рдлрд╝реНрд▓реЛ рд╣реЛ рд╕рдХрддреЗ рд╣реИрдВред

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