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

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

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

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

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

Sum of the first 10 cubes
3,025
╬г k┬│ for k = 1 to 10
рдкрджреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ (n) 10
рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ n(n+1)/2 55
рд╕рд░реНрд╡рд╕рдорд┐рдХрд╛ (n(n+1)/2)┬▓

рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рдХрд░рддрд╛ рд╣реИ

рдпрд╣ рдЯреВрд▓ рдкрд╣рд▓реЗ n рдкреВрд░реНрдг рдШрдиреЛрдВ рдХрд╛ рдпреЛрдЧ рдирд┐рдХрд╛рд▓рддрд╛ рд╣реИ, рдпрд╛рдиреА \(1^{3} + 2^{3} + 3^{3} + \ldots + n^{3}\)ред рд╣рд░ рдкрдж рдХреЛ рдПрдХ-рдПрдХ рдХрд░рдХреЗ рдЬреЛрдбрд╝рдиреЗ рдХреЗ рдмрдЬрд╛рдп, рдпрд╣ рдПрдХ рдорд╢рд╣реВрд░ рд╕реВрддреНрд░ (closed-form identity) рдХрд╛ рдЗрд╕реНрддреЗрдорд╛рд▓ рдХрд░рддрд╛ рд╣реИ рдЬреЛ n рдЪрд╛рд╣реЗ рдХрд┐рддрдирд╛ рднреА рдмрдбрд╝рд╛ рд╣реЛ, рддреБрд░рдВрдд рд╕рдЯреАрдХ рдЙрддреНрддрд░ рджреЗ рджреЗрддрд╛ рд╣реИред

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

рдкрджреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ n рдХреЗ рд▓рд┐рдП рдХреЛрдИ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдбрд╛рд▓реЗрдВ рдФрд░ рдирддреАрдЬрд╛ рджреЗрдЦреЗрдВред рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╕рд╛рде рдореЗрдВ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ (triangular number) \(n(n+1)/2\) рднреА рджрд┐рдЦрд╛рддрд╛ рд╣реИ, рддрд╛рдХрд┐ рдЖрдк рд╕рдордЭ рд╕рдХреЗрдВ рдХрд┐ рдЙрддреНрддрд░ рдХреИрд╕реЗ рдмрдирддрд╛ рд╣реИред

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

рдЗрд╕рдХрд╛ рдореБрдЦреНрдп рдкрд░рд┐рдгрд╛рдо рд╣реИ рдирд┐рдХреЛрдореИрдХрд╕ рд╕рд░реНрд╡рд╕рдорд┐рдХрд╛ (Nicomachus identity):

$$\sum_{k=1}^{n} k^{3} = \left( \frac{n\left(n+1\right)}{2} \right)^{2}$$

рд╣реИрд░рд╛рдиреА рдХреА рдмрд╛рдд рдпрд╣ рд╣реИ рдХрд┐ рдкрд╣рд▓реЗ n рдШрдиреЛрдВ рдХрд╛ рдпреЛрдЧ рдмрд┐рд▓реНрдХреБрд▓ рдкрд╣рд▓реЗ n рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЗ рдпреЛрдЧ рдХреЗ рд╡рд░реНрдЧ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред рдЕрдВрджрд░ рдХрд╛ рд╣рд┐рд╕реНрд╕рд╛ \(n(n+1)/2\) рджрд░рдЕрд╕рд▓ nрд╡реАрдВ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ \(T(n)\) рд╣реИред рдпрд╛рдиреА рдШрдиреЛрдВ рдХрд╛ рдпреЛрдЧ рд╕реАрдзреЗ-рд╕реАрдзреЗ \(T(n)\) рдХрд╛ рд╡рд░реНрдЧ рд╣реИред рдЗрд╕рд╕реЗ рдЧрдгрдирд╛ \(O(1)\) рд╣реЛ рдЬрд╛рддреА рд╣реИ тАФ рдХрд┐рд╕реА рд▓реВрдк рдХреА рдЬрд╝рд░реВрд░рдд рдирд╣реАрдВ тАФ рдФрд░ рдкреВрд░реНрдгрд╛рдВрдХ рдЗрдирдкреБрдЯ рдХреЗ рд▓рд┐рдП рдпрд╣ рд╣рдореЗрд╢рд╛ рд╕рдЯреАрдХ рд░рд╣рддреА рд╣реИред

рдмрдврд╝рддреЗ рдШрдиреЛрдВ рдХрд╛ рдвреЗрд░ рдЬреЛ рдПрдХ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд╡рд░реНрдЧ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИ
рдкрд╣рд▓реЗ n рдШрдиреЛрдВ рдХрд╛ рдпреЛрдЧ n-рд╡реЗрдВ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд╡рд░реНрдЧ, \((n(n+1)/2)^{2}\), рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред

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

рдорд╛рди рд▓реАрдЬрд┐рдП \(n = 4\): рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ рд╣реЛрдЧреА \(4\times5/2 = 10\)ред рдЗрд╕рдХрд╛ рд╡рд░реНрдЧ рдХрд░рдиреЗ рдкрд░ \(10^{2} = 100\) рдорд┐рд▓рддрд╛ рд╣реИред рд╕реАрдзреЗ рдЬреЛрдбрд╝рдХрд░ рдЬрд╛рдБрдЪреЗрдВ: \(1 + 8 + 27 + 64 = 100\)ред рджреЛрдиреЛрдВ рдмрд░рд╛рдмрд░ рдЖрддреЗ рд╣реИрдВ, рдЬреЛ рд╕рд░реНрд╡рд╕рдорд┐рдХрд╛ рдХреА рдкреБрд╖реНрдЯрд┐ рдХрд░рддрд╛ рд╣реИред

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

рдХреНрдпрд╛ рдпрд╣ рд╕рд┐рд░реНрдлрд╝ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд▓рд┐рдП рд╣реА рдХрд╛рдо рдХрд░рддрд╛ рд╣реИ? рд╣рд╛рдБ тАФ рдпрд╣ рд╕рд░реНрд╡рд╕рдорд┐рдХрд╛ \(k = 1\) рд╕реЗ n рддрдХ рдХреЗ рдкреВрд░реНрдгрд╛рдВрдХ рдкрджреЛрдВ рдХреЗ рдпреЛрдЧ рдкрд░ рд▓рд╛рдЧреВ рд╣реЛрддреА рд╣реИ, рдЗрд╕рд▓рд┐рдП n рдПрдХ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред

рдЙрддреНрддрд░ рд╣рдореЗрд╢рд╛ рдкреВрд░реНрдг рд╡рд░реНрдЧ рдХреНрдпреЛрдВ рд╣реЛрддрд╛ рд╣реИ? рдХреНрдпреЛрдВрдХрд┐ рдпреЛрдЧ \(T(n)^{2}\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИ, рдЬрд╣рд╛рдБ \(T(n)\) nрд╡реАрдВ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рд╕рдВрдЦреНрдпрд╛ рд╣реИ; рдФрд░ рдХрд┐рд╕реА рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рд╡рд░реНрдЧ рд╣рдореЗрд╢рд╛ рдкреВрд░реНрдг рд╡рд░реНрдЧ рд╣реА рд╣реЛрддрд╛ рд╣реИред

рдХреНрдпрд╛ n рдмрд╣реБрдд рдмрдбрд╝рд╛ рд╣реЛ рд╕рдХрддрд╛ рд╣реИ? рд╣рд╛рдБред рдЪреВрдБрдХрд┐ рдпрд╣ рд╕реВрддреНрд░ closed-form рд╣реИ, рдмрдбрд╝реЗ рд╕реЗ рдмрдбрд╝реЗ n рдХрд╛ рднреА рдЬрд╡рд╛рдм рддреБрд░рдВрдд рдорд┐рд▓ рдЬрд╛рддрд╛ рд╣реИ тАФ рд╣рд╛рд▓рд╛рдБрдХрд┐ рдмрд╣реБрдд рдЬрд╝реНрдпрд╛рджрд╛ рдмрдбрд╝реЗ рдорд╛рди рд╕рд╛рдорд╛рдиреНрдп рдлрд╝реНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ (precision) рдХреА рд╕реАрдорд╛ рд╕реЗ рдмрд╛рд╣рд░ рдЬрд╛ рд╕рдХрддреЗ рд╣реИрдВред

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