Алгоритм програмчлал.

Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13. Бид энгийн давталт ашиглан үүнийг олж чадах юм. Гэвч үүнийг олохын тулд B үйлдэл хийх ба энэ нь 10^13 тул маш удаан ажиллана. Үүнийг хэрхэн хурдан хугацаанд шийдэх вэ? B тоо нь хоёртын бичиглэлдээ B=x[0]*(2^0)+x[1]*(2^1)+...+x[k]*(2^k) гэж задардаг байг. Тэгвэл k<=log(10^13) байх юм. Тэгвэл бид A^1, A^2, A^3, ... , A^k гэх мэт k ширхэг тоонуудыг k үйлдлээр байгуулна. Одоо энэ хоёрыг угсарвал A^B=(A^(x[0]*(2^0)))*(A^(x[1]*(2^1)))*...*(A^(x[k]*(2^k))) болох юм. Ингэснээр бид k үйлдлээр A тооны B зэргийг олж чадаж байна. Хэрвээ B тоо нь тэгш бол A^B=(A^(B/2))*(A^(B/2)) харин сондгой үед A^B=(A^(B/2))*(A^(B/2))*A гэдэг нь тодорхой юм. Эндээс бид A тооны B зэргийг мэдэхийг хүсвэл A тооны B/2 зэргийг мэдэж байхад олж чадна гэдэг нь харагдаж байна. Тэгвэл A тооны...

Рекурсивын тухай. Энэ нь өөрөө өөрийгөө дуудаж чаддаг функц юм. Жишээгээр ойлгомжтой байх болов уу? Жишээ нь бид 1  ээс  N хүртэл хэвлэмээр байлаа. Мэдээж үүнийг хийхэд амархан. Бид while, эсвэл for ашиглаад үүнийг шийдэж болно. Харин Рекурсив ашиглаад үүнийг хийвэл хэрхэн хийгдэх талаар.  Бид 1 гэсэн тоог хэвлээд дараа нь 2 гэсэн тоог хэвлэнэ. харин дараа нь 3 гэх мэт энэ нь N хүрээд зогсоно. Тэгвэл рекурсивийн зогсох нөхцөл нь N гэсэн үг ба бид N- ээс  ялгаатай K гэсэн тоог хэвлэсэн тохиолдолд 1- ээс  K хүртэл бүх тоог хэвлэсэн гэсэн үг ба K < N бага тул K+1 гэсэн тоог хэвлэх ёстой ба. Үргэлжлүүлэн хэвлэх ёстой гэсэн үг юм. Харин K == N нөхцөл биелбэл бид N хүртэлх бүх тоог хэвлэсэн гэсэн үг юм. Тиймээс үүгээр зогсоно. Бид N гэсэн тоог N-1 хүртэлх тоо хэвлэгдсэн гэж үзвэл үүний ард N гэсэн тоогоо хэвлэхэд хангалттай гэсэн үг юм. Тэгвэл N хүртэл хэвлэхийн тулд N-1 хүртэл хэвлэсэн байх ёсто...