Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Қўшиш формулалари
Алгоритмларни таҳлил қилганда биз баъзи катталиклар йиғиндисини қўшишимизга тўғри келади. Айтайлик, бизда цикли алгоритм бор. Агар цикл ўзгарувчиси 5 қийматини олса, цикл 5 марта бажарилади, агар унинг қиймати 20 га тенг бўлса 20 бўлади. Агар цикл ўзгарувчиси М га тенг бўлса, цикл М марта бажарилади. Агар цикл ўзгарувчиси 1 дан N гача ҳамма қийматларга ўтса, цикл бажарилишининг жами сони 1 дан N гача бўлган ҳамма натурал сонлар йиғиндисига тенг бўлади. Бу йиғиндини биз кўринишида ёзамиз. Йиғинди белгисининг пастки қисмида ўзгарувчи йиғиндининг бошланғич қиймати, юқори қисмида эса – охирги қиймати турибди. Бундай ифодаланиш бизни қизиқтирган йиғинди билан қандай боғлиқлиги тушунарли.
Агар бирор қиймат шу каби йиғинди кўринишида ёзилса, натижани бошқа шу каби ифодалар билан солиштириш мумкин бўлиши учун уни соддалаштириш керак. Икки сондан каттаси . Шунинг учун йиғиндини соддалаштириш учун биз қуйидаги формулалардан фойдаланамиз, бунда С - i га боғлиқ бўлмаган ўзгарувчи.
(7.8)
(7.9)
(7.10)
(7.11)
(7.12)

(7.12) тенглиги 0 дан N гача сонлар йиғиндиси N дан 0 гача сонлар йиғиндисига тенглигини билдиради. Баъзи ҳолларда бу тенгликни қўллаш ҳисоблашларни енгиллаштиради.

(7.13)
(7.14)
(7.15)
(7.15) тенглигини ёдлаб олиш осон, агар 1 дан N гача бўлган сонларни жуфтликка ажратсак. 1 ни N га қўшиб, 2 ни N-1 га ва ҳоказо, биз ҳар бири N+1 га тенг сонлар тўпламини оламиз. Бундай сонлар нечта бўлади? Албатта, уларнинг сони жуфт қилиб ажратилган элементлар сонининг ярмига тенг, яъни N/2. Шунинг учун барча N сонларининг йиғиндиси (7.18) га тенг.
(7.16)
(7.17)
(7.18)
(7.17) тенглигини икки бўлинадиган сонлар орқали эслаб қолиши мумкин. 0 дан 10 гача бўлган икки даражасининг йиғиндиси 11111111111 иккиланган сонига тенг. Бу сонга 1 ни қўшиб 100000000000, яъни 2¹¹ ни ҳосил қиламиз. Лекин бу натижа нолдан ўнггача бўлган икки даражаларининг йиғиндисидан 1 га кўп, шунинг учун йиғиндининг ўзи 2¹¹-1 га тенг. Энди агар 10 ўрнига N қўйсак, биз (7.17) тенгликка келамиз.
Ҳар қандай сон учун
ихтиёрий А сони учун (7.19)
(7.20)
(7.21)
(7.22)
Йиғиндиларни соддалаштиришда аввал уларни (7.8)-(7.12) тенглик ёрдамида янада оддий сонларга ажратиш, сўнгра йиғиндиларни бошқа айниятлар ёрдамида алмаштириш мумкин.