Juda ham katta sonlar bilan ishlash 8 mavzu

Birlashtirish orqali saralash (Merge sort).

• Bo‘lish-boshqarish paradigmasi asosida tartiblash. Massivni ikkiga bo‘lamiz, qismlarni rekursiv ravishda tartiblang va keyin birlashtirish protsedurasini bajaring. Birinchi qismning joriy elementiga, ikkinchisi ikkinchi qismning joriy elementiga ikkita ko‘rsatkichni qo‘llang. Bu ikki elementdan minimumni tanlab, javobga joylashtiring va minimumga mos keladigan ko‘rsatgichni siljiting. Birlashtirish O(n), barcha logn darajalari uchun ishlaydi, shuning uchun murakkabligi O(nlogn). Bu oldindan vaqtinchalik masiv yaratish va vazifaga argument sifatida o‘tishi samarali bo‘ladi. Bu saralash rekursiv, hamda tez va shuning uchun elementlar soni kam bo‘lgan kvadratik o‘tish mumkin.

Saralash algoritmlari taqqoslash.

• Buning uchun barcha yaaratilgan saralash algoritmlarini bir faylga joylashtiramiz. Bularni taqqoslash uchun elementlar soni navbat bilan oshirib boramiz va natijalari sonli, grafikli keltiramiz.

Juda ham katta sonlar bilan ishlash.

• Katta sonlar bilan ishlash uchun asosan tip va uning xotiradan nechta bayt egalashini bilish muhim hisoblanadi. Tiplarni yaxshi bilsangiz kerak. Ammo C++ tilining rivojlantirilgan variantlarida turli tiplar mavjud. Tiplardan foydalanishga bir misol keltiramiz. Masalan, byte tipi bo‘lsin, xotiradan 1 bayt egallaydigan. Bu tipga mos a=200, b =100 bo‘lsa natija, 44 bo‘ladi. Qanday? Buning uchun avvalo byte tining diapozonini, ya’ni [0,255] bilish shart. Agar tipning eng yuqori qiymatiga chiqqan natija va 1 ta 0 ni ketma ket qo‘yilsa 300 chiqib keladi (255+44+1(0))=300). Har qanday tip o‘zning diapozoni doirasida hisoblashlarni bajaradi. Avvalo C++ standartlariga mos tiplarni keltiramiz.

№

Tip nomi

bayt

Ikkinchi nomi