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

DFS-н тухай Энэ удаад DFS буюу гүний нэвтрэлт гэх алгоритмын тухай бичих болно. Жишээ нь бидэнд нэг граф өгөгдсөн ба энэ графт хэдэн компонент буюу хэдэн салангид хэсэг байгааг ол гэсэн бодлого байг. Бид 1-р оройгоос энэ оройтой холбогдсон эхний орой луу очъё. Дараа нь тэр оройтой холбогдсон гэхдээ 1-р оройгоос ялгаатай эхний орой луу очъё. Хэрвээ 1-р орой дээр очих юм бол хязгааргүй үргэлжилнэ . Дараа нь тэр оройгоос түүнтэй холбогдсон гэхдээ өмнө нь очоогүй   орой луу  очно. Энэ мэт бид нэг орой дээр иртэл үүнтэй холбогдсон бүх орой дээр өмнө нь ямар нэгэн байдлаар ирсэн бол яах вэ? Энэ тохиолдолд бид энэ орой дээр ирсэн орой луу буцна гэсэн үг юм. Тэгээд тэр оройн 2дахь өмнө очоогүй   орой л уу   явна. Гэх мэт цааш яваад гацлаа. Тэгвэл дахиад буцна. Гэх мэт үргэлжилсээр 1-р оройтой ямар нэгэн байдлаар   холбогдсон   орой дээр   очсон байх болно. Тэгвэл энэ нь 1 компонент болох юм. Хэрвээ 2-р орой энэ   компонентод   орж чадаагүй бол...

Түвшний нэвтрэлт(BFS-Breadth first search) гэх алгоритмын тухай бичих болно. Жишээ бодлого дээр ярилцъя. Бидэнд нэг граф өгөгдсөн байгаа гэж бодъё. Тэгээд нэг хүсэлт байгаа тэр нь хоёр орой өгөгдөх ба энэ хоёр оройн хооронд хамгийн багадаа хэдэн ширхэг оройгоор дамжин очих вэ? гэдгийг олох юм. Бид одоо X гэсэн орой дээр байгаа. Y орой хүрэх хамгийн богино замыг олцгооё. Бид X орой дээр 0 зам туулж ирсэн гэж үзэж болох юм. Мөн энэ оройг 0-р түвшин гэж үзье. Тэгвэл 1 гэсэн түвшинтэй орой гэж ямар оройг хэлэх вэ? Энэ оройнууд бол X оройтой шууд ирмэгээр холбогдсон оройнууд юм. Тэгвэл 1-р түвшинтэй орой дээр 1 гэсэн зам туулж ирнэ. Тэгвэл 2-р түвшин гэдэг нь 1-р түвшний оройтой шууд ирмэгээр холбогдсон оройнууд байх юм.  Энэд  нэг анхаарах зүйл байгаа нь 1-р түвшинтэй оройнуудтай 0-р түвшний орой холбогдсон байгаа ба бид энэ оройг 2-р түвшин гэж хэлэх нь буруу юм. Тиймээс өмнө нь ирээгү...

Граф гэж юу вэ? Ирмэг болон оройгоос бүтсэн бүтцийг граф гэнэ. Энэ хаяг дээр графын тухай тодорхойлолт байгаа. Мөн математикын зарим номондээр илүү дэлгэрэнгүй тодорхойлолтууд байгаа(байх). Харин одоо графыг хэрхэн унших талаар бичье. Оролтын хувьд хоёр хэлбэртэй.  Оройн тоо өгөгдөнө. 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) хүртэлх индекстэй бүр элемент нь бидний хайж байгаа тооноос эрс их нь ...