рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛ рдХреНрдпрд╛ рд╣реЛрддреА рд╣реИ?
рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛ рдЙрди рд╡рд╕реНрддреБрдУрдВ рдХреА рдЧрд┐рдирддреА рдмрддрд╛рддреА рд╣реИ рдЬрд┐рдиреНрд╣реЗрдВ рдПрдХ рд╕рдордмрд╛рд╣реБ рддреНрд░рд┐рднреБрдЬ рдХреЗ рдЖрдХрд╛рд░ рдореЗрдВ рд╕рдЬрд╛рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред nрд╡реАрдВ рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛, рдЬрд┐рд╕реЗ \(T(n)\) рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, 1 рд╕реЗ рд▓реЗрдХрд░ \(n\) рддрдХ рдХреЗ рд╕рднреА рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХрд╛ рдпреЛрдЧ рд╣реЛрддреА рд╣реИред рдпрд╣ рд╢реНрд░реЗрдгреА 1, 3, 6, 10, 15, 21, 28 рд╕реЗ рд╢реБрд░реВ рд╣реЛрддреА рд╣реИ тАФ рд╣рд░ рдкрдж рдореЗрдВ рдЕрдЧрд▓реА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдЬреБрдбрд╝рддреА рдЬрд╛рддреА рд╣реИред рдЖрдк рдЬреЛ рднреА рдЕрдЛрдгрд╛рддреНрдордХ (non-negative) рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдбрд╛рд▓реЗрдВрдЧреЗ, рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЙрд╕рдХреЗ рд▓рд┐рдП \(T(n)\) рдмрддрд╛ рджреЗрдЧрд╛ред
рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рдЗрдирдкреБрдЯ рдмреЙрдХреНрд╕ рдореЗрдВ рдкрдж рд╕рдВрдЦреНрдпрд╛ \(n\) (рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП 10) рдЯрд╛рдЗрдк рдХрд░реЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░ рджреЗрдВред рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рддреБрд░рдВрдд рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛ рджрд┐рдЦрд╛ рджреЗрдЧрд╛, рдЬреЛ рд╡рд╣реА рдХреБрд▓ рдпреЛрдЧ рд╣реИ рдЬреЛ рдЖрдкрдХреЛ 1 рд╕реЗ \(n\) рддрдХ рдХреЗ рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ рдХреЛ рдЬреЛрдбрд╝рдиреЗ рдкрд░ рдорд┐рд▓рддрд╛ рд╣реИред рдЕрдЧрд░ рдЖрдк 0 рдбрд╛рд▓рддреЗ рд╣реИрдВ рддреЛ рдкрд░рд┐рдгрд╛рдо 0 рдЖрдПрдЧрд╛, рдХреНрдпреЛрдВрдХрд┐ рдЬреЛрдбрд╝рдиреЗ рдХреЗ рд▓рд┐рдП рдХреБрдЫ рд╣реИ рд╣реА рдирд╣реАрдВред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рдЗрд╕рдХрд╛ рдмрдВрдж-рд░реВрдк рд╕реВрддреНрд░ (closed-form formula) рд╣реИ $$T(n) = \frac{n(n+1)}{2}$$ рдПрдХ-рдПрдХ рдХрд░рдХреЗ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдЬреЛрдбрд╝рдиреЗ рдХреЗ рдмрдЬрд╛рдп, рдЖрдк \(n\) рдХреЛ рдЕрдЧрд▓реЗ рдкреВрд░реНрдгрд╛рдВрдХ \((n+1)\) рд╕реЗ рдЧреБрдгрд╛ рдХрд░рддреЗ рд╣реИрдВ рдФрд░ рдкрд░рд┐рдгрд╛рдо рдХреЛ рдЖрдзрд╛ рдХрд░ рджреЗрддреЗ рд╣реИрдВред рдпрд╣ рдЗрд╕рд▓рд┐рдП рдХрд╛рдо рдХрд░рддрд╛ рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рдкрд╣рд▓реЗ рдФрд░ рдЖрдЦрд┐рд░реА рдкрдж, рджреВрд╕рд░реЗ рдФрд░ рджреВрд╕рд░реЗ-рдЖрдЦрд┐рд░реА рдкрдж, рдФрд░ рдЗрд╕реА рддрд░рд╣ рдЖрдЧреЗ рдЬреЛрдбрд╝реЗрдВ тАФ рд╣рд░ рдЬреЛрдбрд╝реА рдХрд╛ рдпреЛрдЧ рд╣рдореЗрд╢рд╛ \((n+1)\) рд╣реА рд░рд╣рддрд╛ рд╣реИ, рдФрд░ рдРрд╕реА рдХреБрд▓ \(n/2\) рдЬреЛрдбрд╝рд┐рдпрд╛рдБ рдмрдирддреА рд╣реИрдВред рдпрд╣ рдХрд╣рд╛рдиреА рдорд╢рд╣реВрд░ рд╣реИ рдХрд┐ рдХрд╛рд░реНрд▓ рдлреНрд░реАрдбреНрд░рд┐рдЦ рдЧрд╛рдЙрд╕ рдиреЗ рдмрдЪрдкрди рдореЗрдВ рд╕реНрдХреВрд▓ рдореЗрдВ рд╣реА 1 рд╕реЗ 100 рддрдХ рдХрд╛ рдпреЛрдЧ 5050 рдирд┐рдХрд╛рд▓рдХрд░ рдЗрд╕ рддрд░реАрдХреЗ рдХреЛ рдЦреЛрдЬ рд▓рд┐рдпрд╛ рдерд╛ тАФ рдФрд░ рдЖрдк рдЗрд╕реЗ рдЦреБрдж рдЬрд╛рдБрдЪ рд╕рдХрддреЗ рд╣реИрдВ: \(100 \times 101 / 2 = 5050\)ред
рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг
рдорд╛рди рд▓реАрдЬрд┐рдП \(n = 10\)ред рддрдм $$T(10) = \frac{10 \times (10 + 1)}{2} = \frac{10 \times 11}{2} = \frac{110}{2} = 55$$ рдпрд╛рдиреА рдпреЛрдЧ \(1 + 2 + 3 + ... + 10\) рдмрд░рд╛рдмрд░ 55 рд╣реЛрддрд╛ рд╣реИ, рдФрд░ рдЗрди 55 рдмрд┐рдВрджреБрдУрдВ рдХреЛ рдПрдХ рд╕реБрдВрджрд░ рддреНрд░рд┐рднреБрдЬ рдХреЗ рд░реВрдк рдореЗрдВ рд╕рдЬрд╛рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ рдЬрд┐рд╕рдХреА рд╕рдмрд╕реЗ рдиреАрдЪреЗ рдХреА рдкрдВрдХреНрддрд┐ рдореЗрдВ 10 рдмрд┐рдВрджреБ рд╣реЛрдВрдЧреЗред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
100рд╡реАрдВ рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛ рдХреНрдпрд╛ рд╣реИ? \(T(100) = 100 \times 101 / 2 = 5050\)ред
рдХреНрдпрд╛ \(n\) рджрд╢рдорд▓рд╡ рд╕рдВрдЦреНрдпрд╛ рд╣реЛ рд╕рдХрддреА рд╣реИ? рддреНрд░рд┐рдХреЛрдгреАрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ рдХреЗрд╡рд▓ рдЕрдЛрдгрд╛рддреНрдордХ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд▓рд┐рдП рдкрд░рд┐рднрд╛рд╖рд┐рдд рд╣реЛрддреА рд╣реИрдВ, рдЗрд╕рд▓рд┐рдП рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЖрдкрдХреЗ рдЗрдирдкреБрдЯ рдХрд╛ рдкреВрд░реНрдгрд╛рдВрдХ рд╣рд┐рд╕реНрд╕рд╛ рд╣реА рд▓реЗрддрд╛ рд╣реИред
рдХреНрдпрд╛ \(T(n)\) рд╣рдореЗрд╢рд╛ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рд╣реЛрддреА рд╣реИ? рд╣рд╛рдБред \(n\) рдпрд╛ \(n+1\) рдореЗрдВ рд╕реЗ рдХреЛрдИ рдПрдХ рд╕рдо (even) рдЬрд╝рд░реВрд░ рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(n(n+1)\) рд╣рдореЗрд╢рд╛ 2 рд╕реЗ рдкреВрд░реА рддрд░рд╣ рд╡рд┐рднрд╛рдЬрд┐рдд рд╣реЛ рдЬрд╛рддрд╛ рд╣реИред