Skip to main content

Нүүж байна

 Удаан пост хийсэнгүй ээ. 

Цаашдаа blogger ашиглахаа болиод yepchaos -руу шилжсэн байгаашүү.

Энэхүү сайтаас орж уншиж байгаарай мөн энэхүү сайт дээр хуучин постуудаа засч янзлаад, шинэ постууд оруулах болноо.

Comments

Post a Comment

Popular posts from this blog

Тооны зэрэг

Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад a^b%p буюу a тооны b зэргийг p гэсэн тоонд хуваахад гарах үлдэгдлийг олцгооё(p нь анхны тоо). Өмнө нь бид a, b <= 10^13 гэсэн тохиолдолд бодсон байгаа. Энэ удаад үүнийгээ өргөтгөн a, b гэсэн хоёр тооны оронгийн тоо нь 10^6-с бага буюу тэнцүү тохиолдолд бодоцгооё(бодъё гэдэг үг бичих гэж байсан ч яаж бичих дээр эргэлзсэн ба p long long төрлийх). fermat -н бага  теоремоор  (a^(p-1))%p = 1. Үүнийг ашиглахад энэхүү бодлого маш амархан болж байгаа. (a^b)%p = ((a%p)^b)%p тул эхлээд a тоог p-д хуваасан үлдэгдлийг олцгооё. a тоо маш олон оронтой байж болох тул бид string ашиглан уншина. Энэ тооны оронгийн тоо нь s = a.size() гэвэл a = a[s-1]*(10^0)+a[s-2]*(10^1)+a[s-3]*(10^2)+...+a[0]*(10^s-1) байх ба a%p = (a[s-1]*(10^0)%p+a[s-2]*(10^1)%p+a[s-3]*(10^2)%p+...+a[0]*(10^s-1)%p)%p байна. Одоо b гэдэг тоог харцгаая. b = k*(p-1)+l байдаг гэе(l<p-1). Тэгвэл a^b%p = (a^(k*(p-1)+l)%p = a^(k*(p-1))*a^l%p эндээс нөгөөх  теорем  ёсоор (a^(p-1))%
1 comment
Шунах »

Массив

Массивын тухай. У рьдын адил энэ хаяг дээр байгаа. Массив гэдэг бараг л олонлог гэсэн үг юм. int a[2000]  гэдэг нь a гэсэн нэртэй олонлог 2000 ширхэг тоо агуулах боломжтой гэсэн үг юм. Массивын эхний элемэнтын дугаар гэдэг бол 0 юм.            Жишээ нь:            5            5 4 -3 2 9            гэсэн оролт бол 5 ширхэг тоо орж ирэх ба эхний мөрөнд массивын хэмжээ буюу массив нь 5 ширхэг элемэнт агуулна. Дараагийн мөрөндөх тоонууд нь олонлогийн элемэнтүүд юм.            a[0] гэдэг бол 5            a[1] гэдэг бол 4            a[2] гэдэг бол -3            a[3] гэдэг бол 2            a[4] гэдэг бол 9 болох юм. // Энэ удаад массивын тухай үзэх болно.    #include <cstdio> // stdio.h гэсэнтэй ижил болно.        int  main() {        // Бодлого. орлтонд N, K болон N ширхэг бүхэл тоонууд өгөгдөх ба эдгээр тоонуудын         // нийлбэрийг ол. Дарагийн мөрөнд K-р элемэнтийг хэвлнэ. K < N && 1 <= N <= 1000.         int  n;  // массивын хэмжээ.         int  
Post a Comment
Шунах »

Тэмдэгт мөр(char)

Mэмдэгт мөрийн тухай. Энэ нь тэмдэгтүүдийн  массив гэсэн үг юм. Өөрөөр хэлбэл char a[2000] гэсэн a нэртэй массив нь 2000 ширхэг тэмдэгтийг авж чадна гэсэн утгатай юм. Тэгээд энэ линк дээр байгаа.        Жишээ оролт.        !-01Xc@        Энэ орлтын хувьд        a[0] = '!' буюу 0р тэмдэгт нь ! тэмдэг        a[1] = '-' буюу 1р тэмдэгт нь - тэмдэг        a[2] = '0' буюу 2р тэмдэгт нь 0 тэмдэг        a[3] = '1' буюу 3р тэмдэгт нь 1 тэмдэг        a[4] = 'X' буюу 4р тэмдэгт нь X тэмдэг        a[5] = 'c' буюу 5р тэмдэгт нь c тэмдэг        a[6] = '@' буюу 6р тэмдэгт нь @ тэмдэг болох юм. // Энэ удаад тэмдэг мөр үзэх болно.    #include <cstdio>    #include <cstring> // тэмдэгт мөрдээр хийгдэх үйлдлүүдийг ашиглахыг хүсвэл энэ санг заавал                        // зарлаж өгөх ёстой. Жишээ нь тэмдэгт мөрийн урт гэх мэт функцийг агуулдаг.        int  main() {        // Бодлого. 1 тэмдэгт мөр өгөхдөх ба энэ тэмдэгт мөр
Post a Comment
Шунах »

while давталт.

Happy valentine's day. while давталтын тухай.  Уншиж байгаа бүхнийгээ өөрийн болгох нь хамгийн чухал болхоор олон бодлого бодож байгаарай. Доорх кодыг урьдын адил энэ сайтад байрласан байгаа. Энэд бичсэн өгөгдсөн тооны цифрийн нийлбэрийг олох бодлогын санаа бол өгөгдсөн тооны хамгийн сүүлийн цифрийг олоод нэг хувьсагчид утгыг нэмнэ. Дараа нь энэ цифрийн урд талын цифрийг нэмнэ. Дараа нь тэрний урд талын гэх мэт гэхдээ энийг яаж нэмэх вэ? гэвэл бид хамгийн ард талын цифрийг олж чадна. Энэ нь тэр тоог 10д хуваасан үлдэгдэл юм. Харин тэрний урд талын цифрийг яаж олох вэ? гэвэл тэр тоог 10д хуваагаад гарсан хариуг 10д хуваасан үлдэгдэл юм. Гэх мэтчилэн энэ тоо 0-ээс их бол энэ үйлдлүүдийг үргэлжлүүлээд л хийгээд байх болно. Үүнийг while давталт ашиглана. Жишээ нь : 142 гэсэн тооны хувьд бодоцгооё.  Хамгийн арын цифр 2 энэ тоог хариунд нэмээд 10д хуваана. Одоо энэ тоо 14 болно. Хариу нь 2 болно. Хамгийн арын цифр 4 энэ тоог хариунд нэмээд 10д хуваана. Одоо энэ тоо 1 болно. Хариу н
Post a Comment
Шунах »

Нөхцөл шалгах үйлдэл.

Нөхцөл шалгах үйлдэл буюу if гэсэн зүйлийг үзнэ. Тайлбар хийсэн кодон дээр 3 бодлого цуг байгаа тул жоохон эвгүй байж магадгүй.(Залхуурсан болно). Дахин сануулахад энэ сайтаас бодоод яваарай. Яг бидний үзэж байгаа бодлогууд эхний хэдэн хуудсан байгаа. Доорх код энэ сайтад байгаа. Нэмж хэлэхэд ideone бол онлайн compiler бөгөөд заавал компьютэр дээрээ devc++ эсвэл өөр compiler суулгахгүйгээр энэ сайтыг ашиглаж болно. && - And буюу ба. || - Or буюу эсвэл. // Энэ удаад нөхцөл шалгах үйлдэл буюу if гэсэн нөхцлийг үзэх болно    // Мөн &&, || гэсэн логик оператор үзэх болно.    #include <stdio.h>        int  main() {       printf( "Bodlogo 1\n" );        // Бодлого 1: 2 бүхэл тооны багыг ол.         // Бодолт: Ямартай ч бид 2 бүхэл тоогоо унших ёстой. үүний тулд          // ашиглах хувьсагчдаа зарлах ёстой.         int  a, b;           scanf( "%d%d" , &a, &b);  // Бидний мэдэх унших үйлдэл             // Хэрвээ а тоо b 
Post a Comment
Шунах »

Sieve

Sieve of Eratosthenes  тухай. N тоог анхны тоо эсэхийг sqrt(N) үйлдлээр шалгаж болно. Тэгвэл 1-с N хүртэлх бүх анхны тоог ол гэсэн бол үүнийг ашиглавал ойролцоогоор N*sqrt(N) үйлдлээр хийх юм. Одоо бичих алгоритм нь илүү хурдан юм. Анхны тоо гэдэг нь зөвхөн 2 ширхэг натурал тоон хуваагчтай тоо ба өөрөөр хэлбэр анхны тоо нь өмнөх ямар ч анхны тоондоо хуваагддаггүй гэсэн үг. 2-г хамгийн эхний анхны тоо гэдгийг мэднэ. Тэгвэл 2-д хуваагддаг дараагийн бүх тоонууд анхны тоо болж чадахгүй. Тэгвэл энэхүү тоонуудыг анхны тоо биш гэж тэмдэглэе. Дараагийн тоо нь 3 ба энэ нь өмнөх бүх анхны тоондоо хуваагдаагүй тул энэ тоо нь анхны тоо. Тэгвэл 3-д хуваагддаг дараагийн бүх тоонууд анхны тоо биш. Дараагийн тоо нь 4 ба энэ нь 2-д хуваагддаг тул анхны тоо биш гэж тэмдэглэгдсэн. Дараагийн тоо нь 5 ба энэ нь  анхы  тоо биш гэж тэмдэглэгдээгүй ба өмнөх бүх анхны тоондоо  хуваагдаагүй  тул анхны тоо. Тэгвэл 5-д хуваагддаг дараачийн тоонууд нь анхны тоо биш болох юм. Энэ мэтчилэн бодвол хугацааны үнэлг
Post a Comment
Шунах »

for давталт

for давталтын тухай.  Доорх код энэд байгаа. Энэ сайт бол анхан шатнаас нь эхэлж байгаа хүмүүст бол хамгийн зохимжтой сайт юм. for( хувьсагчийн анхын утга; хувьсагчийн биелүүлэх нөхцөл; хувьсагчийн өөрчлөгдөх хэсэг ) {         хэрвээ хувьсагчийн биелүүлэх нөхцөл үнэн байвал энэ {} хаалтан доторх үйлдлүүд хийгдэнэ.         энэ хаалтан доторх үйлдлүүд хийж дууссаны дараа хувьсагч нь өөрчлөгдөнө.     }     Ерөнхий бүтэц бол иймэрхүү. // Энэ удаад for давталтын тухай оруулна.        #include <stdio.h>        int  main() {        // Давталт нь гэдэг нь маш чухал зүйлийн нэг юм. (Энэ нээх чухал өгүүлбэр биш).             // Бодлого. нэг бүхэл тоо өгөхөд 1-ээс тэр тоо хүртэл бүх тоог нэг мөрөнд хэвлээд         // дараагийн мөрөнд 1-ээс тэр тоо хүртэлх 3д хуваагддаг тоонуудын нийлбэрийг ол.             // энэ бодлогыг давталт ашиглаж бодно.         // (Давталт үзэх гэж байж тодорхойшдээ яах гэж бичвээ).             int  n, i, s;         // бид 3д хуваагддаг тоонууды
Post a Comment
Шунах »

Тооны зэргийг Log(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 тооны
Post a Comment
Шунах »

String

String-н тухай. Мөн cin, cout. String гэж юу вэ? энэ нь хэмжээгээ өөрчилж чаддаг тэмдэгт төрлийн утга авдаг массив гэж хэлж болно. char a[2000] гэвэл 2000 хүртэлх л тэмдэгтийг агуулж чадна. Харин string a; гэвэл энэ нь өөрийн уртыг өөрчилж чадна. Тэгээд доорхи код энэ хаяг дээр байгаа. Мөн ард нь үг нэмэх мөн 2 тэмдэгтийг ижил эсэхийг шалгах гэх мэт үйлдлүүдэд char-ын массиваас илүү амар юм. Бид char төрлийн массиваар 2 тэмдэгтийг ижил эсэхийг шалгавал индекс бүр дэх үсэг бүрийг ижил эсэхийг шалгана. Харин string төрөлд бол ТэмдэгтМөр1 == ТэмдэгтМөр2 гэхэд л хангалттай. Мөн ард нь элемэнт нэмэхэд  ТэмдэгтМөр = ТэмдэгтМөр + ТэмдэгтМөр1; гэхэд л болно. Гэхдээ char төрөлд ард нь нэмдэг функц байгаа. string a = ""; хоосон болгох a = "aBg"; // a гэдэг тэмдэгт мөр aBg болгож байна. a += "123123"; // 123123 гэсэн тэмдэгт мөрийг нэмж байна. cout << a[0] << endl; // 0р элемэнтийг хэвлэх. // Энэ удаад string гэх зүйлийн талаар үзэх болно.     
2 comments
Шунах »

Шинэ жил боллоо. Гэсэн ч ахиад л зэрэг.

Шинэ жил боллоо. Гэсэн ч ахиад л зэрэг. Өнөөх л a^b%mod-оо бодоцгооё. Бид хувиргалт хийгээд a, b < mod болгож чадна. Харин mod <= 10^13 гэвэл a^b бодох явцад үржвэр нь хамгийн ихдээ ойролцоогоор 10^26 болох юм. Гэтэл long long төрөлд үүнийг хийж чадах билүү? Тэгхээр өмнөх бодолтууд зөв биш гэдгийг анзаарсан байх. Үүнийг хэрхэн шийдэх вэ? Асуудал нь үржих үйлдэл нь том тооны хувьд асуудалтай байгаа тул үүнийг зөв олох хэрэгтэй. x*(y/2)%mod -г мэдэж байхад бид x*y олж чадна. Өмнө нь ашиглаж байсан санаа буюу a^b олсон бодлоготой адил болж байна.
Post a Comment
Шунах »