Сайн УУ

Анхны тоо Анхы тоо гэдэг нь яг 2 ширхэг ялгаатай хуваагчтай натурал тоог хэлдэг. Жишээ нь 2, 3, 5, 7 гэх мэт үргэлжлээд явна. N гэсэн тоо өгөгдөхөд тухайн тоог анхны тоо эсэхийг хэрхэн мэдэх вэ? Мэдээж бид [1, N] завсарт гүйгээд N тоог маань хэд нь хувааж байгаа вэ гэдгийг тоолоход болно. Үүнээс хурднаар шалгаж чадах уу? Анхны тоо зөвхөн 2 хуваагчтай гэхээр 1 болон өөртөө л хуваагддаг гэсэн үг ба N тоог [2, N-1] завсарт ямар ч тоо хуваадаггүй бол анхны тоо мөн....

Үндэсний олимпиад гэж юу вэ? Үндэсний олимпиад нь жил бүр зохион байгуулагддаг ба ACM-ICPC буюу Олон улсын програмчлалын олимпиадын нэг шат гэж хэлж болно. ACM-ICPC нь дэлхийн хэмжээний хамгийн том оюутнуудын дундах програмчлалын тэмцээн ба Сургууль дотроо Бүсээс шалгарах Бүсийн аварга Сүүлийн шат Гэсэн байдлаар зохион байгуулагддаг. Дүрмийн хувьд багууд хүссэн ном, матералыг авж орох боломжтой 3 хүртэлх гишүүнтэй байх ба 12 орчим бодлогыг 4 цагийн турш дундаа 1 computer дээр боддог....

Disjoint Set Union (Union Find) өгөгдлийн бүтцийн тухай. Нэрнээс нь харвал union буюу нэгтгэх find буюу хайх, disjoint буюу салангид гэсэн гурван үгээр энэхүү өгөгдлийн бүтэц нэрлэгджээ. Мэдээж энэхүү гурван гол ойлголтыг агуулсан байхнээ. Өөрөөр хэлбэл энэ нь Find буюу ямар хэсэгт байгааг хайх үйлдлийг хийнэ Union буюу салангид байгаа 2 хэсгийг нэгтгэх гэсэн 2 гол үйлдэлтэй. Өөрөөр хэлбэл бидэнд анх салангид олон хэсгүүд байгаа ба түүнийг хэрхэн хялбар байдлаар нэгтгэх, тухайн элэмэнт аль хэсэгт байгааг олоход ашигладаг....

Граф гэж юу вэ? Wikipedia: Ирмэг болон оройгоос бүтсэн бүтцийг граф гэнэ. Би: заа Граф нь зүйлсийн холбоо хамаарлыг дүрсэлсэн нэг хэлбэр гэж хэлж болно. Жишээ нь найзуудын хамаарлыг авж үзье. A нь B-тэй найз, B нь C-тэй найз, C нь D-тэй найз ба D нь A-тай мөн B-тэй найз гэвэл. Бид тухайн хүмүүсийг орой гэж хэлээд хоорондын найзын холбоосыг ирмэг гээд иймэрхүү байдлаар дүрсэлж болохнээ. Тэгвэл энэхүү граф нь 4 оройтой 5 ирмэгтэй холбоост граф байх нь....

Хоёртын хайлт гэх алгоритм хаа сайгүй л явж байдагдаа. Энгийн мөртлөө хүчтэй санааг агуулж байдаг. Ер нь нэрнүүдэд их учир бий шүү. Жишээ бодлого дээр авж үзье. Бодлого Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал, Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9. Analysis Хүсэлт бүрийн хувьд N ширхэг тоо бүртэйгээ тэнцүү эсэхийг шалгахад болно....

Бодлого A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13 Бид энгийн давталт ашиглан үүнийг олж чадна. Өөрөөр хэлбэл A тоог B удаа үржүүлэх ба энэ нь бид 10^13 удаа үржүүлэх хэмжээний зүйлийг ярьж байна. Энэ нь ер нь хэр их үйлдэл вэ? Маш их ба 1 секундэнд 300сая үйлдэл хийдэг гэж төсөөлийлдөө тэгвэл 9 цаг гаруй ажиллахнээ. Бид тооны зэрэг олохын тулд 9 цаг хүлээнэ гэдэг бол тэнэг хүн тэвчээртэй гэдэг шиг л болох нь дээ...

C++ хэлэнд бид өөрсдөө бичих шаардлагагүй хялбарчилсан олон төрлийн өгөгдлийн бүтэц байдаг ба түүний тухай ярилцяа. Эхний ээлжинд тэдгээр нь юу хийдэг ямархуу бүтэцтэй тухай бичих ба цаашдаа бүгдийг нь өөрсдөө кодыг нь бичээд яаж ажилладдаг болхыг нь бичнэ гэж бодож байна. Array Array тухай. Array олон зүйлийг багтааж чаддаг сав гэж төсөөлж болноо. Одоогийн байдлаар бид 1 хувьсагчид 1-л утга хадгаж байгаа тэгвэл бидэнд 2000 хувьсагч хадгалах хэрэгтэй болвол яах вэ?...

Рекурсивын тухай. Функцын тухай бид өмнөх post дээр үзсэн билээ. Тэгвэл тухайн функц нь өөрөө өөрийгөө дуудвал юу болох вэ? Үүнийг рекурсив функц гэдэг. Жишээ нь int sum(int a, int b) { return sum(a, b); } гэдэг функцийг харя. sum гэдэг нь 2 хувьсагч авдаг ба int-н утга буцаахнээ. Гэхдээ дотроо өөрийгөө дуудсан байгаа нь ба энэ юу болох бол? Мэдээж хязгааргүй ажиллах ба би лав ийм зүйлийг хүсэхгүй байна. Ер нь тэгхээр хэрэгтэйм болуудаа?...

Програмчлалыг хэрхэн сурах вэ? Миний хувьд хэрхэн бичдэг юу хийдгийг уншаад дараа нь бодлого бодож эхэлсэн. Тийм болхоор эхний ээлжинд C, C++ програмчлалын хэлний энгийн үйлдлүүд түүний тухай бичих гэж байна. Сая хэлсэнчлэн бодлого бодох нь маш хэрэгтэй ба анх эхэлж байгаа бол энэ сайтаас эхлээд бодоод явбал зүгээр. Англиар бодлого ойлгоход асуудалгүй гэвэл codechef, codeforces- сайтаас бодоод яваарай. Доорх кодыг хэрхэн ажлуулах боломжтой вэ гэвэл ideone гээд online tool байгаа ба үүнийг ашиглаж болно....

Энэхүү блог дээр алгоритм програмчлал сонирхож буй хэн бүхэнд зориулж өөрийн мэдэж буй зүйлээс хуваалцах болно. Би л гэхэд анх 11р ангидаа л код бичих тухай сонсож байсан ба сонирхоод интернэтээс монгол хэлдээр код хэрхэн бичих тухай мэдээлэл олж чадаагүй. Бусад хүүхдийг мэдээллээс битгий хоцроосой мөн монгол кодерууд олон болоосой гэсэндээ энэ блогийг нээхээр шийдсэн. Анхан шатнаас нь алгоритмын хичээл оруулах болхоор хүн болгонд ойлгомжтой байх. Асуух зүйл гарвал сэтгэгдэл үлдээгээрэй....