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

Граф гэж юу вэ? Ирмэг болон оройгоос бүтсэн бүтцийг граф гэнэ. Энэ хаяг дээр графын тухай тодорхойлолт байгаа. Мөн математикын зарим номондээр илүү дэлгэрэнгүй тодорхойлолтууд байгаа(байх). Харин одоо графыг хэрхэн унших талаар бичье. Оролтын хувьд хоёр хэлбэртэй.  Оройн тоо өгөгдөнө. N гэе. Матриц буюу хүснэгтээр. Энэ тохиолдолд NxN харьцаатай матриц өгөгдөх ба i-р мөрийн j-р  баганы  утгаар i- аас  j-ын хоорондох ирмэг тодорхойлогдоно гэсэн үг юм. Хэрэв a[i][j]- ын  утга нь 0 бол i- аас  j хүрэх шууд ирмэг байхгүй гэсэн үг юм. Хэрвээ жингүй граф бол a[i][j]- ын  утга нь 0 эсвэл 1 байна. Хэрэв 1 бол i- аас  j хүрэх шууд ирмэг байгаа гэсэн үг юм. Харин жинтэй графын хувьд a[i][j]-ы н  утга нь 0- ээс  ялгаатай бол i- аас  j хүрэх шууд ирмэг байгаа бөгөөд түүний жин нь a[i][j]- ын  утга байх юм. Ийм бүтцээр оролтод өгөгдөх нь тун ховор юм. Учир нь 10^5 ширхэг оройтой графын мэдээллийг уншихын тулд 10^10 зэрэг ...

Хоёртын хайлт(binary search) гэх алгоритмын тухай бичнэ. Энэ удаад энгийн нэг бодлого дээр ярилцъя.  Бодлого . Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал байгаа гэж бодъё. Мөн Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9. Анализ: Энгийн давталт ашиглан олж болно. Тэгвэл хугацаа хамгийн ихдээ Q*N болох юм. Энэ нь 10^10 ба маш их үйлдэл хийж байгаа юм. Тэгвэл хэрхэн хурдан шийдэх вэ? Анхаарах зүйл нь энэ дараалал өсөхөөр эрэмбэлэгдсэн байгаа. Бид одоо X гэсэн тоог энэ дараалалд байгаа эсэхийг олох гэж байгаа гэж бодъё. Тэгвэл энэ дарааллын голын элементийн утгыг бид 1 үйлдлээр мэдэж чадна. Энэ элементийг индекс нь mid=(n+1)/2 болох ба энд 3 салах юм. a[mid] == X бол бид шууд байгаа гэдгийг нь олж чадлаа. a[mid] > X бол (mid, mid+1,..., n) хүртэлх индекстэй бүр элемент нь бидний хайж байгаа тооноос эрс их нь ...

Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. 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 тооны...