Хамтдаа хөгжицгөөе

Зав зай арай гайгүй болсон дээрээ хэдэн юм хүүхдүүдэд заагаад өгье гэж хэдэн материал бэлдлээ. Доорх хэдэн сэдэв дээр шаардлагатай онол, алгоритмыг заагаад 8-10н бодлого бэлдсэн байгаа. Шууд онлайн линкийг нь тавих болно, гэхдээ би өөрөө бодлогын өгүүлбэрийг нь орчуулаад блог дээрээ тавина, мөн бодолтын ерөнхий санаа, анализыг нь хэлж өгнө, шаардлагатай гэвэл C++ дээрх бодолтоо тавина.

1. Coding exercise - энд нээх онол шаардахгүй, гэхдээ хоёртын хайлт гэх мэтчилэн арга техникууд хэрэгтэй, гэхдээ зөвхөн анхан шатны мэдлэг л хэрэг болно.

2. Mathematics - Хэрэгтэй мат-уудыг шаардах бодлогууд байх болно. Мэдээж эхлээд өөрөө тайлбарлана.

3. Data Structures - өгөгдөлийн бүтэц

4. Dynamic programming - динамик програмчлал

5. Basic graph algorithms - графын энгийн алгоритмууд

6. Shortest Path algorithms - богино замын алогритмууд

7. String Algorithms

8. Computational Geometry



Бодлогууд бүгд http://poj.org/  - дээр байгаа тул энд бүртгүүлнэ үү.



За шууд эхний сэдэв болох Coding Exercise-руу ороё



Энд онол гэх заагаад байх юм байхгүй байх. Гэхдээ миний блогийг доош нь гүйлгээд C++ STL I, II гэсэн пост мөн бодлогуудын анализуудыг уншчихад гэмгүй.



Доорх бодлогуудыг бодно уу.

1004 - Нэгэн хүний сүүлийн нэг жилийн сар бүрийн орлого өгөгдсөн бол тухайн жилийн орлогын дундажийг олох. Оролт 12 ширхэг бутархай тоо, гаралт бодлогын хариултыг 2 орны нарийвчлалтай  $тэмдэгийн араас шууд хэвлэнэ.

Анализ: Оролтын бүх тоог нэмээд 12т хуваах байх аа.

source

----

1003 - Зурагт үзүүлсний дагуу N хөзрийг хөзрийн урттай тэнцүү урттай тавцан дээр давхарлан унагалгүй байж болох хамгийн уртаар нь дээр дээрээс нь тавив. Ингэхийн тулд хэрэв нэг хөзөр байвал тавцангийн 1/2 хэсэг дээр хөзрөө тавина, хэрэв 2 хөзөр байвал хамгийн доод талын хөзрийг тавцангийн 1/3 дээр, 2дахь хөзрийг 1дэх хөзрын 1/2 дээр тавьснаар 1/2+1/3=5/6 уртыг үүсгэж чадна. Ерөнхий тохиолдолд N хөзөр байхад 1/2+1/3+..+1/(N+1) урт үүсгэж чадна гэж үзье. Тэгвэл с гэх ганц бутархай тоо өгөгдсөн бол ядаж с урт үүсгэхийн талд хамгийн багадаа хичнээн хөзөр хэрэгэй болохыг олно уу.

Оролт нь олон тестээс бүрдэх ба 0.00 үед тест дуусна. Мөн тест бүр [0.01;5.20] байна.

Гаралт нь мөр бүрт тухайн тестийн хариуг нэг мөрөнд хэвлэнэ.

Анализ: с тоо хамгийн ихдээ 5.20 тул бодлогын хариу тийм ч том тоо биш байгаа нь харагдах байх. Тэгвэл шууд К-г 1-ээс авахуулаад тухайн К хөзөр с-ээс их буюу тэнцүү хүртэл урттай байх хүртэл нь шууд хайгаад явчихад болно. Энэ хайлт нь утга бүрийг нэг бүрчилэн шалгаж байгаа тул шугаман хайлт гэж нэрлэж байгаа юм. Код дээр search_linear гэсэн функцыг харна уу. Энэ бодолт шууд давна, бодлогын хязгаарлалт хамаагүй бага байгаа тул O(K). Ерөнхийдөө бодлогыг бодож, тухайн хязгаарлалт, хугацаанд амжуулж л байвал болоо гэсэн бодолтой байх хэрэгтэй. Хамгийн чухал нь юу сурч авав гэдэгээ байнга эргэж харж байгаарай.

Бодолтыг илүү хурдан болгож чадах уу? Хоёртын хайлт ашиглана. Бид К-г хамгийн багадаа 1, хамгийн ихдээ -276 гэдэгийг эхний бодолтыг хийгээд харчиж чадна.

compute_length(N) гэсэн функц нь N ширхэг хөзөр өгөгдсөн үед үүсгэж чадах уртыг нь олдог байг. Тэгвэл бодлого маань c<=compute_length(K) байх хамгийн бага К-г ол гэсэн үг. Тэгэхээр К маань өөрөө 1-ээс 276-н хооронд байж болох тул энэ завсарт хоёртын хайлтыг хийнэ гэсэн үг. O(Log(K)).

source

--

1007 - зөвхөн A C G T гэсэн тэмдэгтүүдээс бүрдэх n урттай m шихрэг тэмдэгт мөрүүд өгөгдсөн. Тэмдэгт мөр бүрийн хувьд К гэсэн тоог бодож олно. Энэ нь ямар нэгэн с тэмдэгт нь хичнээн ширхэг өөрөөс нь урд байрлах ёстой тэмдэгтийн урд байрлаж байгаа вэ гэдэгийг тоолно. Тухайн тэмдэгт мөрийн хувьд бүх тэмдэгтүүдийн хувьд дээрх тоог олоод нэмэхэд гарах утгаар К-г тодорхойлно. Тэгвэл тэмдэгт мөр бүрийн хувьд К-г бодож олоод К-уудын хувьд өсөхөөр эрэмблэ гэсэн бодлого. Жишээг нь сайн харж бодлогоо бүрэн ойлгоно уу.

Анализ: Хамгийн энгийн бодолт бол C++ дээр compare функц үүсгэж эрэмблэх бодлого.

source

Анализ2 К-г ямар нэгэн тоон дарааллын хувьд инверс тоо гэдэг. Бидний өмнөх бодолт маань бүх хосуудыг шалгаж байгаа тул хугацааны үнэлгээ нь квадрат O(N^2). Үүнийг рекурс ашиглан O(NlogN)-д бодож болно. Үндсэн санаа нь

F(S) функц нь S-г эрэмблээд мөн тухайн S-н инверсийг тоолдог гэж үзье, (S.sorted, inverse).

S тэмдэгт мөрийн эхний хагасыг left, үлдсэн тэмдэгт мөрийг right гэе, S=left+right. Хэрэв left, right хоёр хоюулаа эрэмлбэгдсэн бол энэ хоёрыг нэгтгэж эрэмбэлсэн шинэ тэмдэгт мөр үүсгэхдээ K-г тоолчиж чадна. Тэгвэл рекурсик хамаарал буюу бодлогын хариу маань

F(S)=>

-> ll = F(left), rr = F(right)

-> S.sorted = left.sorted+right.sorted.

-> S.inverse = left.inverse+right.inverse+K

-> return (S.sorted, S.inverse)

Анзаарч чадсан бол дээрх алгоритм маань merge_sort байгаа. Тэгэхээр merge_sort ашиглан инверсийг O(NlogN)-д олж чадахнээ. source

Анализ3 Ер нь бол энэ бодлогоны хамгийн хурдан бодолт нь Trie өгөгдөлийн бүтэц ашиглах.

--

2140 - N<10 br="" n="">

Анализ Дараалсан тооны нийлбэрт тавихын тулд хамгийн том тоо нь N/2+1 байх нь ойлгомжтой. Шууд бүх боломжийг нь шалгана уу.

source

--

2136 - Өгөгдлөөс зөвхөн том үсэгнүүдийт тус бүр хэд байгааг тоолоод жишээний гаралт шиг хэвлэ.

Анализ Том үсэгнүүдийг A-0, B-1, .., Z-25 гэж дугаарлая. cnt[26] массив дотор үсэг тус бүр хэдэн удаа орсныг нь тоолоод харгалзах дугаараар нь массивын индекс болгож хадгалана. Энэ санаа маш олон бодлого, алгоритмд ашиглагддаг.

source

--

1504 хоёр тоо өгөгдсөн бол энэ хоёр тооны цифрүүдийг урвуулаад хооронд нь нэмээд гарсан хариуг бас дахин урвуулаад хэвлэ. Аль ч тохиолдолд тоо 0-ээр эхэлсэн байж болохгүй.

Анализ шууд хэлснээр нь хий

source

--

1001 R бодит тоо болон N натурал тоо өгөгдсөн бол R^N-г ол. Хэрэв хариу бүхэл тоо бол цэг тавих хэрэггүй. Мөн хариу урт, ардаа 0 агуулах хэрэггүй

Анализ Залхууралгүй, мөн үнэхээр сурмаар мөн өөрийхөө C++ мэдлэгээ сайжруулж сайн код бичдэг болмоор байвал энэ бодох ёстой. Цаас үзэг бариад өөрийг компьютер гэж бодоод алгоритмыг нь гарга.

source

--

3251 - NxN (N<=100) хэмжээтэй хөлөг өгөгдсөн, нүд бүр B, J, * аль нэг нь байна. Тэгвэл * бусад тэмдэгтүүд ямар нэгэн квадрат дүрсийн 4-н булан болж чадахыг олоод хамгийн том квадратын талын уртыг олно уу. Үүсэж болох квадрат нь заавал x, y тэнхлэгтэй параллел байх албагүй.

Энэ бодлогыг хэр бодохнуу хармаар байна. Бодсон нь доор коммент үлдээж санаа бодол, мөн асуух юмаа асуувал дуртай хариулна. Амжилт



Дараагийн пост Математик байх болно.