ПРОГРАМ

санамж

2009 оны 03-р сарын 19 Нийтэлсэн Энх-Оч
Санамж !!! Хэрэв урьдчилан сэргийлэх арга хэмжээ авахгүй бол компьютертэй ажиллах нь эрүүл мэндэд хортой / Хэмжээг мм-ээр илэрхийлэв./ Өөрийн эрүүл мэндэд муугаар нөлөөлөхгүй байлгахын тулд дараах зөвлөмжийг биелүүлэх шаардлагатай. Компьтерийн ард буруу суугаад байвал мөр болон бүсэлхийгээр өвддөг болж болно. Урагшаа бөхийлгүй арагшаа налалгүй ямар нэгэн хүч гаргалгүй чөлөөтэй сууна. Хөлөө нугалалгүй, жийлгүй, хоёр хөл нэг нь нөгөөгийнхөө хажууд шалан дээр гишгэсэн байдалтай байрлана.өндөр намыг нь тохируулдаг сандалтай бол зураг дээр харуулсан байдалтай суух шаардлагатай. Удаан хугацаагаар компьютер дээр ажиллавал нүд ядардаг. Тийм учраас 5 минут тутамд нүдээ дэлгэцнээс салгаж, хол зайнд орших өөр зүйлийг харж байгаарай. Хэрхэн түргэн шивж сурах вэ ? - Товчнууд руу харалгүйгээр оруулахын нууц нь товчийг дарсны дараа заавал үндсэн байрлал руу хуруугаа буцаах явдал юм. / дарсан бол буцаан / гэсэн үйлдлийг давтан хийгээд байвал хуруунаас товч хүртэлх зайг аяндаа мэдрэн эзэмшээд түргэн шивж сурна. Компьтерийн иж бүрдэл

c++

2009 оны 03-р сарын 19 Нийтэлсэн Энх-Оч
Тооллын систем Тоог дүрсэлж бичих бөгөөд тоон дээр үйлдэл хийх дүрмүүдийн системийг тооллын систем гэдэг. 0,1,2,3,. . . ,9 гэсэн арван цифрээр аравтын, 0 ба 1 –ээр хоёртын 0,1,2,. . . ,7 (найман)-ээр наймтын 0,1,2,3,. . . ,9, A, B, C, D, E, F(арван зургаан) –ээр арван зургаатын тооллын системийн тоо бичигдэнэ. Тоо ямар тооллын системд бичигдсэн байгааг хоёртын тооны төгсгөлд B(binary- хоёрт) үсэг, арван зургаатын тооны эхэнд H(hexa-арван зургаат) үсэг, наймтын тооны эхэнд O(octal- наймт) үсэг бичнэ. Харин аравтын тоог ердийн бичдэг шигээ бичнэ. Жишээ: 2002, 555 100В, 101001В О745, О11017 H2002, H1АВС Хоёртын тооллын системд арифметикийн 4 үйлдэл хийх дүрэм: x y x+y x y x-y x y x*y x y x:y 0 0 0 0 0 0 0 0 0 0 0 - 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 10 10 1 1 1 1 1 1 0 - Жишээ: 101 + 1 110 1111 + 1 10000 101110 - 1 101101 10-т 2-т 8-т 16-т 0 0 0 0 1 1 1 1 2 10 2 2 3 11 3 3 4 100 4 4 5 101 5 5 6 110 6 6 7 111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F 16 10000 20 10 17 100001 21 11 18 100010 22 12 Хүснэгт-1 10-тын системд хоёртын зэрэг байх тоог 2-тод шууд бичиж болдог. 1=20=1B 2=21=10B 16=24=10000B Энэ шинжийг ашиглан ямар ч тоог 10-таас 2-т руу хялбархан хөрвүүлж болно. Жишээ: 300=256+32+8+4=28+25+22=100100100B 1015=1024-9=10000000000B-1001B=1111110111B Урвуугаар 2-тоос 10-т руу тоог хөрвүүлэхэд энэ аргыг хэрэглэж болно. Жишээ: 1111110111B=1+2+4+16+32+64+128+256+512=1015 1011B=1+2+8=11 • 2-тоос 16-тад хөрвүүлэхийн тулд 2-тын тоог баруун талаас нь дөрөв, дөрвөөр нь бүлэглэж, бүлэг тус бүрийг хүснэгт-1 дэх 16-тын харгалзах тоогоор сольж бичнэ. Жишээ: 100’1111’0110B=H4F6 11’1111’0111B=H3F7 • 16-таас 2-т руу шилжүүлэхдээ 16-тын цифр бүрийг 2-тын харгалзах дөрвөн оронтой тоогоор сольж бичнэ. Жишээ: H1ABC=1’1010’1011’1100B H321F=11’0010’0001’1111B • 2-т ба 8-тын системийн хооронд тоог хөрвүүлэхдээ тоогоо гурав гурваар нь бүлэглэж бүлэг бүрээ харгалзах цифрээр солино. • Тоог янз бүрийн тооллын системд бичиж болно. 1015=111111B Орчин үеийн микро компьютерт ASCII(American Standart Codes for information Interchange) кодыг өргөн хэрэглэдэг. 10-т 32 48 64 80 96 112 16-т 20 30 40 50 60 70 0 0 space 0 @ P ‘ p 1 1 ! 1 A Q a q 2 2 “ 2 B R b r 3 3 # 3 C S c s 4 4 $ 4 D T d t 5 5 % 5 E U e u 6 6 & 6 F V f v 7 7 ‘ 7 G W g w 8 8 ( 8 H X h x 9 9 ) 9 I Y i y 10 A * : J Z j z 11 B + ; K [ k { 12 C , < L l | 13 D - + M ] m } 14 E . > N ^ n 15 F / ? O - o Мэдээллийг хэмжих нэгж • Утга нь хоёртын нэг цифрээр илэрхийлэгдэх мэдээллийг 1 бит(binary digit) мэдээлэл гэнэ. • 8 бит урттай, өөрөөр хэлбэл утга нь хоёртын найман оронтой тоогоор илэрхийлэгдэх мэдээллийг нэг байт (byte) гэнэ. 8 бит=1 байт • 1024byte=1KB (Kilobyte) • 1024KB=1MB (Megabyte) • 1024MB=1GB (Gegabyte) Компьютерийн санах ой Аливаа компьютер нь мэдээлэл санах, мэдээлэл боловсруулах, мэдээллийг түүнд оруулах ба түүнээс гаргахад зориулагдсан хэсгүүдээс бүтсэн байдаг. Энэ хэсгүүдийг компьютерийн байгууламж гэж нэрлэдэг. • Компьютерээр боловсруулах бүх төрлийн мэдээллийг санаж хадгалах зориулалттай байгууламжийг компьютерийн санах ой, (main memory-память) гэнэ. • Орчин үед үүрийн урт n=8, 16, 32 байх микро компьютер ба n=48, 64 байх том компьютерийг ашигладаг. • N=16 байх тохиолдлыг жишээ болгож үзье. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 0 Энэ үүрийн утга 1111101001110110В=65535-(1024+256+128+8+1)=65535-1417=64118 • ТЭМ-д мэдээлэл дүрсэлж хадгалах үүрийн урт хязгаарлагдпмал учраас компьютерийн ийм үүрэнд санаж болох тоон мэдээлэл мөн заагтай, өөрөөр хэлбэл энэ үүрэнд санах хамгийн бага, мөн хамгийн их тоо гэж байна. • Жишээ нь, үүрийн урт 16 байх үед үүрэнд бичиж болох тэмдэггүй (эерэг) бүхэл тооны утга H0000..H0FFFF буюу 0..216 -1=0..65535 байна. • Үүрийн урт ямарч байсан энэ үүрэнд санах тооны доод (minint) ба дээд (maxint) зааг болох хоёр тоо оршино. Maxint+1 тоо үүрэнд багтахгүйд хүрдэг. Учир нь: 15 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 • Энэ үзэгдлийг орон дүүрэх буюу хэт дүүрэлт (overflow-переполнение) гэнэ. • Үүрийн ахмад оронгийн битийг тооны тэмдэгт зориулж нэмэх тэмдгийг 0-оор, хасах тэмдгийг 1-ээр дүрсэлдэг. 15 0 s 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 битийн урттай үүрийн хувьд maxint=215-1=32767 (s=0) • Сөрөг бүхэл тоог ямар хэлбэртэй дүрслэх вэ? а тооны хувьд түүний эсрэг тоог – а гэвэл а+(-a)=0 байх ёстой. • а тооны 2-тын бичлэгт 1-ийг 0-оор, 0-ийг 1-ээр сольж түүн дээр 1-ийг нэмэхэд гарах тоог а тооны 2-тын гүйцээлт гэж нэрлэдэг. Жишээ нь: а =0000000001111011В байг. Тэгвэл түүний гүйцээлт нь 111111110000100+1=1111111110000101В. Энэ тоо хасах тэмдэгтэй тоо байна. Анхны тоо ба түүний хоёртын гүйцээлт хоёрын нийлбэрийг олъё. 15 0 a= 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 + 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2-тын гүйцээлт нь а тооны эсрэг тоо –а-тай тэнцүү байна гэсэн дүгнэлт хийж болно. • Аливаа тооны эсрэг тоог түүний хоёртын гүйцээлт хэлбэртэй дүрсэлдэг. Жишээ нь: 5=0000000000000101B -5=1111111111111011B 1=00000000000000011B -1=1111111111111111B a=1100000010010000B -a=0011111101110000B 1995=0000001111100101B -1995=1111110000011011B Одоо 16 битийнг урттай үүрэнд санаж болох хамгийн бага бүхэл тоо ямар байхыг үзье. -a=1000000000000000B тооны эсрэг тоог олбол а=1000000000000000B=215=32768 байна. Иймээс 16 битээр дүрслэх хамгийн бага тоо minint=-32768 байх ба аливаа бүхэл тоо n нь [minint, maxint] завсарт байна. • Олон үүрэнд дүрслэгдсэн тоог давхар нарийвчлалтай тоо гэнэ. Жишээ нь 16 битийн 2 үүрэнд санах давхар нарийвчлалтай бүхэл тоо нь завсарт байна. Орчин үед давхар нарийвчлалтай тоог боловсруулдаг нэмэлт байгууламжийг (процессор) компьютерт хэрэглэдэг болсон. Бид зөвхөн бүхэл тоог дүрслэх тухай ярилаа. Компьютерт бутархай хэсэгтэй аравтын бутархайг бодит тоо гэж нэрлээд бүхэл тооноос ялгаатай хэлбэртэй дүрсэлж, мөн ялгаатай аргаар үйлдэл хийж боловсруулдаг гэж ойлгох нь зүйтэй. • Компьютерийн санах ой нь үүрэнд мэдээлэл бичих, үүрийн утгыг унших гэсэн зөвхөн хоёрхон үйлдэл биелүүлдэг. • Бичих үйлдлийн үед үүрийн хаяг болон энэ үүрэнд бичих шинэ мэдээлэл шаардагдана. Бичих үйлдэл биелэгдэхэд үүрийн хуучин утга устаж зөвхөн шинэ утга хадгалагдана. Бичих үйлдлийг програмчлалд хаяг=утга гэсэн хэлбэртэй бичдэг. Унших үйлдлийн үед үүрийн хаягийг өгөхөд л хангалттай. i хайрцаганд байгаа утгыг уншиж 1-ийг нэмэх гэсэн үйлдийг шууд i+1 гэж бичнэ. I=i+1 гэсэн бичлэг утгатай бөгөөд i үүрийн утгыг 1-ээр нэмэгдүүлэх үйлдэл болно. • Санах ойн үүрийн тоог ТЭМ-ы санах ойн багтаамж гэнэ. Алгоритмын тухай ойлголт Алгоритмын тухай ойлголт нэгэн төрлийн бодлогуудыг бодох ерөнхий арга олох гэсэн оролдлоготой холбоотойгоор үүссэн. Алгоритм гэдэг нэр нь персийн математикч Abu Ja’far Mohammed ibn Musa al Khowarizmi –н нэрнээс гаралтай. Аливаа бодлогыг бодох (ажлыг гүйцэтгэх) үйлдлүүдийн төгсгөлөг дарааллыг алгоритм гэнэ. Жишээ. Өгөгдсөн m,n натурал тоонуудын хамгийн их ерөнхий хуваагчийг (ХИЕХ) ол. Бодолт. Өгөгдсөн 2 натурал тооны ихийг багад нь, дараа нь багыг нь эхний хуваалтын үлдэгдэлд, цаашид өмнөх хуваалтын үлдэгдлийг дараагийн хуваалтын үлдэгдэлд хуваах үйлдлийг ээлжит хуваалтын үлдэгдэл тэг болтол үргэлжлүүлэхэд эцсийн хуваагч нь ХИЕХ болно. Алгоритм 1. m,n тоонуудыг оруул. 2. Хэрэв mn бол m-д m тоог n тоонд хувааж үлдэгдлийг олгоод 4-р алхамд шилж. Эсрэг тохиолдолд 3-р алхамд шилж. 3. n-д n тоог m-д хувааж үлдэгдлийг олгоод 5-р алхамд шилж. 4. Хэрэв m=0 бол ХИЕХ(m,n)=n болно. Төгсгө. Эсрэг тохиолдолд 2-р алхамд шилж. 5. Хэрэв n=0 бол ХИЕХ(m,n)=m болно. Төгсгө. Эсрэг тохиолдолд 2-р алхамд шилж. Алгоритм дараах шинжүүдтэй. Үүнд: 1. Үр дүнтэй байх. 2. Алхмуудад хуваагдсан байна. 3. Төгсгөлөг алхамтай байна. 4. Түгээмэл байх. Өөрөөр хэлбэл өгөгдлөөрөө ялгаатай ижил төрлийн бодлогыг бодох ерөнхий алгоритм зохиох. Алгоритмд хэмжигдэхүүнүүдийг өөр хооронд ялгах, тэдгээр дээр хийх үйлдлийг бичихийн тулд үг үсгээр тэмдэглэдэг. Энэ тэмдэглэгээг хэмжигдэхүүний нэр гэнэ. Нэр нь заавал үсгээр эхэлсэн байх ба дурын тооны үсэг, цифрээс тогтоно. Хэмжигдэхүүний нэр нь уг хэмжигдэхүүний утга хадгалагдаж байгаа санах ойн үүрийн хаягийг төлөөлнө. Алгоритмын явцад хэмжигдэхүүний утга өөрчлөгдөхгүй байвал түүнийг тогтмол хэмжигдэхүүн гэнэ. Эсрэг тохиолдолд хувьсагч гэнэ. Хэмжигдэхүүнийг үйлдлийн тэмдгээр холбож илэрхийлэл үүсгэнэ. Үйлдлүүд 1. Арифметик үйлдэл Нэмэх(+), хасах(-), үржих (*), хуваах(/), бүхэл тоог бүхэл тоонд хуваахад гарах үлдэгдэл олох (mod) 2. Логик үйлдэл Зөвхөн үнэн эсвэл худал утга авдаг хэмжигдэхүүнийг логик хэмжигдхүүн гэнэ. Логик хэмжигдэхүүн дээр логик нэмэх (or), логик үржих(and), үгүйсгэл (not) үйлдлүүдийг хийдэг. Цаашид үнэн утгыг 1, худал утгыг 0 гэж тэмдэглэе. X Y X and Y X or Y not X 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 3. Жиших үйлдэл (>=,<=,<,>,,=) 4. Функц хэрэглэх sin(x), cos(x), tg(x), ctg(x), x, ln(x), , arctg(x), [x]- х тооны бүхэл хэсэг, {x}- х тооны бутархай хэсэг. Алгоритм дараах алхмуудаас тогтоно. Үүнд: 1. Оруулах алхам. Хувьсагчдын анхны утгыг оруулж өгөх шаардлагатай байдаг. Жишээ нь ax2+bx+c=0 тэгшитгэлийг бодохын тулд a,b,c хувьсагчдын утгуудыг оруулж өгнө. 2. Утга олгох алхам. Тодорхой томъёогоор өгөгдсөн илэрхийллийн утгыг бодох, гарсан үр дүнг ямар нэг хувьсагчийн утга болгон хадгалах үйлдлийг утга олгох үйлдэл гэнэ. хувьсагч=илэрхийлэл 3. Гаргах алхам Алгоритмын үр дүнг мэдээлэх шаардлагатай байдаг. 4. Нөхцөл шалгах алхам Алгоритмд тодорхой нөхцөл шалгаж нөхцөл биелэх эсэхээс хамаарч ялгаатай замаар үргэлжлүүлэх шаардлага гардаг. Алгоритмын алхмуудыг геометрийн дүрсээр дүрсэлснийг блок схем гэдэг. Дараах хүснэгтэд геометрийн дүрсийн зориулалтыг харуулав. Алхам Блок схемд дүрслэх хэлбэр Жишээ 1. Оруулах алхам 2. Утга олгох алхам 3. Гаргах алхам 4. Нөхцөл шалгах 5. Эхлэл ,төгсгөл 6. Тайлбар 7. Холбоос Жишээ 1 Өгөгдсөн 3 оронтой тооны цифрүүдийн нийлбэрийг ол. //example1 #include #include void main() { unsigned int n,a,b,c,s; do{printf("n="); scanf("%d",&n); } while(n<100 | n>1000); a=n/100; n=n%100; b=n/10; c=n%10; s=a+b+c; printf("SUM=%d",s); } Алгоритмыг алхмуудын биелэгдэх дэс дарааллаар нь шугаман, салаалсан, давталттай гэж ангилна. Шугаман алгоритм Алхмууд нь дэс дарааллаараа зөвхөн ганц удаа биелэгдэж байвал шугаман алгоритм гэнэ. Жишээ 2 Өгөгдсөн R радиустай тойргийн урт ба талбайг ол. L=2R, S=R2 // example 2 #include #include #define Pi 3.141592; void main() { float L,R,S; do { printf("R="); scanf("%f",&R); } while(R<=0); L=R*Pi; S=L*R; L=L*L; printf("S,L=%3.5f %f",S,L); } Салаалсан алгоритм Алгоритмын зарим алхам биелэгдэх эсэх нь ямар нэг нөхцлөөс хамаарч ялгаатай замаар биелэгдэж байвал тийм алгоритмыг салаалсан алгоритм гэнэ. 1 0 1 0 if(нөхцөл) үйлдэл 1; if(нөхцөл) үйлдэл ; else үйлдэл 2 ; Жишээ 3 x ба y бодит тоонууд өгөгджээ. z-ийн утгыг дараах томъёогоор ол. // example 3 #include #include void main() { float x,y,z; printf("x,y=");scanf("%f%f",&x,&y); if(x>y) z=x-y; else z=y-x+1; printf("z=%3.5f",z); } Жишээ 4 ax2+bx+c=0 тэгшитгэлийг бод. 1. a0 үед a) D>0 бол 2 шийдтэй. b) D=0 бол x=-b/2a гэсэн давхар шийдтэй. c) D<0 бол бодит шийдгүй. 2. a=0 үед a) b0 бол x=-c/b гэсэн 1 шийдтэй. b) b=0 үед (a) c0 бол шийдгүй. (b) c=0 бол төгсгөлгүй олон шийдтэй. // example 4 #include #include #include void main() { float a,b,c,d; clrscr(); printf("a,b,c=");scanf("%f%f%f",&a,&b,&c); if(a==0) if(b==0) if(c==0) printf("togsgolgyi olon shiidtei"); else printf("shiidgyi"); else printf("1 shiidtei x1=%f",-c/b); else { d=b*b-4*a*c; if(d<0) printf("bodit shiidgyi"); else if(d>0){ printf("x1=%fn",(-b+sqrt(d))/(2*a)); printf("x2=%f",(-b-sqrt(d))/(2*a)); } else printf("dabhar shiidtei x12=%f",-b/(2*a)); } } Давталттай алгоритм Алгоритмын нэг юмуу хэсэг алхмууд хэд хэдэн удаа давтагдан биелэгдэж байвал уг алгоритмыг давталттай алгоритм гэнэ. Давталтын алхмуудыг давталтын бие буюу циклийн бие гэнэ. Давталттай алгоритмыг нөхцөлт давталт, тоолуурт давталт (параметрт) гэж ангилна. Ямар нэг нөхцлийг биелэхгүй (эсвэл биелэх) болтол бүлэг алхмуудыг давтаж байвал нөхцөлт давталт гэнэ. Нөхцөлт давталтыг өмнөх нөхцөлтэй, дараах нөхцөлтэй гэж ангилна. a. Өмнөх нөхцөлтэй б. Дараах нөхцөлтэй давталт давталт Прогарммчлалын си хэлэнд дараах хэлбэрээр бичдэг. while(нөхцөл) { циклийн do{ циклийн бие бие } } while(нөхцөл) Харин давталтын тоо тодорхой бол тоолуурт давталт гэнэ. Давталтыг тоолж байгаа хувьсагчийг тоолуур гэнэ. Тоолуурт давталтыг зохиохдоо : • тоолуурын эхний утгыг олгоно. • Тоолуурын утга эцсийн утгатаа хүрээгүй бол давталтын биеийг биелүүлнэ. • Давталтын биеийн төгсгөлд тоолуурын утгыг тодорхой алхмаар өөрчилнө. • Давталтын бие дотор тоолуурын утгыг өөрчилж болохгүй. • Давталтын дотор бүхлээрээ багтсан өөр давталтыг бичиж болно. • Зарчмын хувьд давталт төгсөхөөс өмнө гарч болно. for(тоолуур=эх,нөхцөл, алхам) {циклийн бие} Жишээ 5 m (m>1)- бүхэл тоо өгөгджээ. 4k #include void main() { int m,k,P; clrscr(); while(m<=1){printf("m=");scanf("%d",&m);} P=1;k=0; while(P #include void main() { int N,S=0,M,k=0; clrscr(); do{printf("N=");scanf("%d",&N); }while(N<0); do{ M=N%10; N=N/10; S=S+M; k++; }while(N!=0); printf("S,k=%d %d",S,k); } Жишээ 7. Өгсөн N натурал тоо хүртэлх бүх анхны тоог ол. Бодолт. Ямар нэг сондгой k - тоог анхны тоо мөн эсэхийг шалгахдаа 3- аас хүртэлх сондгой тоонуудад хуваах хэрэгтэй. Хэрэв ямар ч тоонд хуваагдахгүй бол анхны тоо мөн. ( Эсвэл сондгой k - тоог анхны тоо мөн эсэхийг шалгахдаа к хүртэлх бүх анхны тоонуудад хуваах хэрэгтэй.) // example 7 #include #include #include void main() { int N,k,I; clrscr(); do{printf("N=");scanf("%d",&N); }while(N<2); printf("2"); for(k=3;k<=N;k+=2) {I=1; do{I+=2; }while((k%I!=0)&&(I<=sqrt(k))); if(I>sqrt(k)) printf("%4d",k); } } Жишээ 8. N натурал тооны факториалыг ол. N!=1*2*3*4*. . . . . . . . . (N-1)*N // example 8 #include #include void main() { int N,I,P=1; clrscr(); do{printf("N=");scanf("%d",&N); } while(N<1); for(I=1;I<=N;I++) P=P*I; printf("%d",P); } Жишээ 9. f(0)=0, f(1)=1, f(2n)=f(n) ,f(2n+1)=f(n)+f(n+1) бол өгөгдсөн N утганд f(N)- ийг ол. Бодолт. f(n)- ийг шууд олох зорилго тавъя. g(n,i,j,)=if(n)+jf(n+1) туслах функц авъя. Тэгвэл g(2n,i,j)=if(2n)+ jf(2n+1) =if(n)+j(f(n)+f(n+1))= =(i+j)f(n)+jf(n+1)=g(n,i+j,j) . Үүнтэй адилаар g(2n+1,i,j)= g(n,i,i+j) Эдгээр томъёог ашиглавал f(n)=1*f(n)+0*f(n+1)=g(n,1,0)=. . . . . . . . . . . . . .=g(0,k,t) болно. f(n)=g(n,1,0)=g(0,k,t)=kf(0)+tf(0+1)=tf(1)=t Эндээс бидний зорилго t -г олоход оршино. // example 9 #include #include void main() { int N,k=1,t=0; clrscr(); do{printf("N=");scanf("%d",&N); }while(N<0); while(N!=0) { if(N%2==0) k=k+t; else t=k+t; N=N/2; } printf("%d",t); } Жишээ 10. Өгөгдсөн n натурал тоо полиндром мөн эсэхийг шалга. Бодолт. Уг тоог хөрвүүлэхэд өгөгдсөн тоотой тэнцүү бол полиндром. // example 10 #include #include void main() { int n,k,S=0,t; clrscr(); do{printf("n=");scanf("%d",&n); }while(n<=0); t=n; do{ k=n%10; n=n/10; S=10*S+k; } while(n!=0); printf("%d",S); if(t==S) printf("yes"); else printf("no"); } Жишээ 11. Цифрүүдийн нийлбэр нь өгсөн n натурал тоотой тэнцүү байх бүх 3 оронтой тоог ол. Бодолт. M= i=1,9 j=0,9 k=0,9 утгуудыг авна. 3 -давхар цикл гүйлгэж i+j+k=n нөхцлийг хангах тоонуудын хувьд M=100*i+10*j+k томъёогоор уг тоог олж болно. Энд нийт 900 удаа нөхцөл шалгах үйлдлийг хийнэ. Энэ арга сайн биш. Өөр хувилбар авч үзье. Зуут ба аравтын орны цифрүүд i,j мэдэгдэж байх үед нэгжийн орны цифрийг өгөгдсөн нөхцлийг хангаж байхаар k=n-i-j (0<=k<=9) гэж олж болно. Энд нөхцөл шалгах үйлдэл нийт 90 удаа хийгдэнэ. M=100*i+10*j+k = 100*i+10*j+n-i-j=99*i+9*j+n (0 #include void main() { int n,i,j,k,M; clrscr(); do{printf("n=");scanf("%d",&n); } while(!(0 #include void main() { int n,i,P=1; float S=0,T=1,x; clrscr(); do{printf("n=");scanf("%d",&n); } while(n<1); printf("x=");scanf("%f",&x); for(i=1;i<=n;i++){P=P*i; T=T*x/P; S=T+S; } printf("%3.4f",S); } Массивын тухай ойлголт Нэг ижил төрлийн олон тоог санах ойн дэс дараалсан үүрэнд хадгалж улмаар түүний элементүүдийг дугаараар нь олж боловсруулах хэрэгсэл программчлалын бүх хэлэнд байдаг. Ерөнхий нэртэй ижил төрлийн хувьсагчдыг хүснэгт хэмжигдэхүүн буюу массив гэнэ. Массивын элементүүдийг ялгах болон байрлалыг нь заахын тулд элементийн дугаарыг (индекс) хэрэглэнэ. Массивын элементүүд санах ойн дараалсан үүрүүдэд байрлана. Массивын нэр, элементийн төрөл, тоог тодорхойлж өгнө. Энэ үйлдлээр массивыг хадгалах санах ой хуваарилагдана. Алгоритмд массивыг дараах хэлбэрээр тодорхойлно. Массивын элементүүдэд утга олгох ба гаргахдаа элемент нэг бүрчлэн олгох ба гаргах үйлдлийг хийнэ. Жишээ 13. n элементтэй нэг хэмжээст массивын элементүүдийг 1,2,3,......,n дараалсан натурал тоонуудаар байгуул. // example 13 #include #include void main() { int n,i,a[50]; clrscr(); do{printf("n=");scanf("%d",&n); } while(n<1); for(i=1;i<=n;i++) {a[i]=i; printf("a[%d]=%dn",i,a[i]);} } Жишээ 14. A(n) массивын элементүүдийг буурах эрэмбээр байрлуул. Бодолт. Эхлээд бүх элементүүдээс хамгийн ихийг нь олоод эхний элементтэй байрыг нь солино. Дараа нь эхний элементээс бусад элементүүдийн хамгийн ихийг олж 2-р элементтэй байрыг нь солино. Энэ үйлдлийг давтан хийх замаар эрэмбэлнэ. i- массивын элементийн индекс j- хамгийн их элемент олох үйлдлийн тоолуур k- алхам бүрийн хамгийн их элементийн дугаар max- алхам бүрийн хамгийн их элемент Жишээ 15. n (0<=n<10000) натурал тоог үгээр бич. Жишээ нь 253- хоёр зуун тавин гурав #include #include #include main() {char *a1[10]={"тэг", нэг","хоёр","гурав","дөрөв","тав","зургаа","долоо", "найм ", "ес"}; char *a2[9]={ нэг","хоёр","гурван","дөрвөн","таван","зургаан","долоон", "найман ", "есөн"}; char *a3[9]={“арав","хорь","гуч","дөч","тавь","жар","дал", "ная ", "ер"}; char *a4[9]={“арван","хорин","гучин","дөчөн","тавин","жаран","далан", "наян ", "ерэн"}; int n,k; clrscr(); do{ printf("n=");scanf("%d",&n); }while(0>n | 9999999){k=n/1000; n=n%1000; printf("%s ",a1[k]); if(n==0) exit(0); } if(n>99){k=n/100; n=n%100; if(n==0){printf("%s zyy ",a2[k-1]); exit(0);} else printf("%s zyyn ",a2[k-1]); } if(n>9){k=n/10; n=n%10; if(n==0) {printf("%s ",a3[k-1]);exit(0);} else printf("%s ",a4[k-1]); } printf("%s ",a1[n]); Олон хэмжээст массив Тодорхой тооны мөр баганаас тогтсон хүснэгтийг хоёр хэмжээст массив гэх ба массивын элемент нь мөр ба баганын дугаарыг заасан хоёр индекстэй байна. aij - i мөр j баганын элемент 2 хэмжээст массивын элементийг оруулахдаа (гаргах) дараах хэлбэрийн давхар циклийг ашиглана. Индексийн тоо нь 2-оос их юмуу тэнцүү байх массивыг олон хэмжээст массив гэнэ. Жишээ: Математикт m мөртэй, n баганатай тоон хүснэгтийг матриц гэж нэрлэдэг. гэж тэмдэглэдэг. Матриц нь 2 хэмжээст массив болно. Элементүүдийг нь санах ойн дэс дараалсан үүрүүдэд мөр мөрөөр нь цувуулж хадгалах бөгөөд элементүүдийг нь индексээр нь олдог. Жишээ: Өгөгдсөн A(m,p), B(p,n) матрицуудын үржвэр C(m,n) матрицийг ол. C матрицийн элементүүд нь байдаг. #include #include main() {int I,j,k,p; float s,a[20][20],b[20][20],c[20][20]; clrscr(); printf(“m,p,n=”); scanf(“%d%d%d”,&m,&p,&n); for(i=1;i<=m;i++) for(j=1;j<=p;j++) {printf(“a[%d][%d]=”,&I,&j); scanf(“%f”,&a[i][j]); } for(i=1;i<=p;i++) for(j=1;j<=n;j++) {printf(“b[%d][%d]=”,&I,&j); scanf(“%f”,&b[i][j]); } for(i=1;i<=m;i++) {for(j=1;j<=n;j++) {s=0; for(k=1;k<=p;k++) s=s+a[i][k]*b[k][j]; c[i][j]=s; printf(“%3.4f”,c[i][j]); } printf(“n”); } } Дэд алгоритм Тодорхой үр дүн өгдөг эсвэл үйлдэл хийдэг бие даасан шинжтэй алгоритмыг тусад нь бичиж олон дахин ашиглах боломжтой. Ийм алгоритмыг дэд алгоритм гэнэ. Дэд алгоритмуудыг ялгахын тулд нэрлэнэ. Үндсэн алгоритмaac дэд алгоритмыг дуудах, дэд алгоритмаас буцах гэсэн үйлдлүүдийг хэрэглэдэг. Үндсэн алгоритмаас дэд алгоритмд дамжуулах утгыг аргумент эсвэл параметр гэх ба харин дэд алгоритмаас үндсэн алгоритмд дамжуулах утгыг дэд программын үр дүн гэнэ. Дэд алгоритмыг нэрээр нь дуудаж хэрэглэнэ. Дэд алгоритм үндсэн алгоритмд утга буцаах ба буцаахгүй байж болно. Үндсэн ба дэд алгоритмуудад бүгдэд нь хэрэглэгдэх хувьсагчийг глобаль хувьсагч, зөвхөн тодорхой нэг дэд алгоритмд хэрэглэгдэх хувьсагчийг локаль хувьсагч гэнэ. Дэд алгоритмыг үндсэн алгоритмд дуудахдаа нэрээр нь дуудна. -дэд алгоритмын эхлэл -төгсгөл Жишээ 16. Өгөгдсөн m,n натурал тооны ХИЕХ-ийг ол. // example 16 #include #include int xuex(int m,int n) {int k; if(n>m) {k=m;m=n;n=k;} while(n>0){k=m%n;m=n;n=k;} return(m); } void main() {int m,n,k; clrscr(); printf("m,n=");scanf("%d%d",&m,&n); k=xuex(m,n); printf("%d",k); } Жишээ 17. Нийлбэрийг ол. (n- бага тохиолдолд ) 1+22+33+44+. . . . . . .+nn= //example 17 #include #include int zereg(int k,int m) {int P=1,i; for(i=1;i<=m;i++) P=P*k; return(P); } void main() {int n,S=0,i; clrscr(); printf("n=");scanf("%d",&n); for(i=1;i<=n;i++) S=S+zereg(i,i); printf("%d",S); } Жишээ18. Бодит тоон дараалал a1,a2,. . . . . . . .,a2n өгөгдсөн бол a1, a2n, a2, a2n-1, a3, a2n-2,. . . . . . . . ., an, an+1 гэсэн шинэ дараалал үүсгэ. //example 18 #include int n,a[20]; void move(int k) {int i,T,b; T=a[k]; for(i=k;i<=2*n-1;i++) {b=a[i+1];a[i+1]=T;T=b;} a[k]=T; } main() { int i; printf("n=");scanf("%d",&n); for(i=1;i<=2*n;i++) {a[i]=i;printf("%3d",a[i]);}printf("n"); for(i=2;i<=2*n-2;i+=2) move(i); for(i=1;i<=2*n;i++) printf("%3d",a[i]);printf("n"); } Жишээ 19. F0=F1=1, Fn=Fn-2+Fn-1 (n>=2) тоонуудыг Фибоначийн тоонууд гэдэг. Фибоначийн тоонуудыг ол. //example 19 #include #include int F[100]; void Fibonachi(int n) {int i; F[0]=1;F[1]=1; for(i=2;i<=n;i++) F[i]=F[i-2]+F[i-1]; return; } void main() {int n,i; clrscr(); printf("n=");scanf("%d",&n); Fibonachi(n); for(i=0;i<=n;i++) printf("%3d",F[i]); } Рекурсив Өөрөө өөрийгөө дуудсан дэд алгоритмыг рекурсив гэнэ. Рекурсив нь зогсох нөхцөл хүртэл өөрийгөө дуудан ажиллаад, дараа нь дуудагдсан дарааллаараа гэдрэг буцна. Жишээ 20. Аравтын тооллын системийн n тоог хоёртын тооллын системд шилжүүл. Бодолт. Аравтын тоолын тоог хоёртын тоололд шилжүүлэхдээ уг тоог 2-т хувааж үлдэгдлийг авч , бүхэл хэсгийг нь дахин 2-т хуваах үйлдлийг үлдэгдэл 0 болтол давтаад үлдэгдлүүдийг дарааллынх нь эсрэг байрлуулна. //example 20. #include #include void bits(int n) { if(n) {bits(n/2); printf("%d",n%2); } } void main() {int n; clrscr(); printf("n=");scanf("%d",&n); bits(n); } Жишээ 21. n! - олох //example 21 #include #include int fac(int n) { if(n) return(n)*fac(n-1); else return(1) ; } void main() {int n; clrscr(); printf("n=");scanf("%d",&n); printf("%d",fac(n)); } Аливаа асуудлыг рекурсивээр шийдэх нь: 1. Энэ асуудлыг түүнтэй ижил боловч хялбар асуудлаар солих 2. Энэ шилжилтийг сүүлчийн бодлогын шийд илэрхий болох хүртэл үргэлжлүүлэх гэсэн хоёр шатаас тогтдог. Жишээ 22. Ханойн цамхаг. Нэг гол баганад угласан хэмжээгээрээ ялгаатай n дугуйг, жижиг дугуй дээр том дугуйг хэзээ ч тавихгүйгээр өөр голд нэг нэгээр нь шилжүүлэх алгоритм зохио. Туслах нэг гол ашиглана. Энэ ажлыг n дугуйг а баганаас b багана руу с баганыг ашиглан зөөх move(n,a,b,c) дэд алгоритм болон а голд байгаа хамгийн дээрх жижиг дугуйг авч b-д тавих үйлдэл хийдэг put(a,b) туслах алгоритмаар гүйцэтгэе. 1 2 3 Тэгвэл болох ба цаашид гэх мэт хялбар үйлдэлд шилжих ба 1-р параметрийн утга өөрөөр хэлбэл цамхагийн голд 1 дугуй үлдсэн үед тэр дугуйг шууд авч тавьж болох учир move(1,a,b,c)=put(a,b) байна. Эрэмбэлэлтийн энгийн аргууд Программын тооцоолох ажилд нөлөөлөх нэг үндсэн үйлдэл бол эрэмбэлэлт юм. Эрэмбэлэлт нь өгөгдлийг тодорхой дарааллаар тухайлбал өсөхөөр эсвэл буурахаар зохион байгуулах үйлдэл юм. Эрэмбэлэгдсэн өгөгдөл нь хайлтыг хурдасгах чухал ач холбогдолтой. Эрэмбэлэгдэх өгөгдөл нь хэд хэдэн талбаруудаас тогтох бичлэгүүд байж болох ба энэ үед эрэмбэлэлтийг аль нэг талбарын утгаар хийдэг. Энэ талбарыг түлхүүр гэнэ. Хэрэв эрэмбэлэгдэх нийт өгөгдөл нь санах ойд хүрэлцэхүйц бага хэмжээтэй бол дотоод эрэмбэлэлт гэнэ. Хэрэв өгөгдлийн хэмжээ нь дотоод эрэмбэлэлтээр хийгдэхээргүй их хэмжээтэй бол гадаад эрэмбэлэлт гэнэ. Эрэмбэлэлтийн аргуудыг харьцуулах гол хэмжүүр бол тэдгээрийн ажиллах хугацаа юм. Эрэмбэлэлтийн алгоритмын түлхүүр үйлдэл нь харьцуулах ба утга солилцох гэсэн 2 үндсэн үйлдлээр тодорхойлогдоно. Сонгон эрэмбэлэх арга Энэ арга нь массив дахь хамгийн бага элементийг олж массивын эхний элементтэй сольж, дараа нь удаах бага элементийг олж массивын 2-р элементтэй солих байдлаар массивын бүх элементийг эрэмбэлэдэг юм. Дараах 8 бүхэл тоо агуулах массивыг энэ алгоритмаар хэрхэн эрэмбэлэхийг алхам алхмаар үзүүлье. 77 33 44 11 88 22 66 55 11 33 44 77 88 22 66 55 11 22 44 77 88 33 66 55 11 22 33 77 88 44 66 55 11 22 33 44 88 77 66 55 11 22 33 44 55 77 66 88 11 22 33 44 55 66 77 88 11 22 33 44 55 66 77 88 Сонгон эрэмбэлэх алгоритмыг дараах SelectionSort функцээр тодорхойллоо. Эрэмбэлэлтийн энэ арга нь маш цөөн өгөгдөлтэй массивын хувьд сайн ажилладаг. Энэ алгоритм нь өгөгдлийн анх өгөгдөх дарааллаас үл хамаарч ойролцоогоор n2 харьцуулалт, n солилцох үйлдэл хийдэг. Дээрхээс ажиглавал гадаад давталтын алхам бүрд нэг солилт ба n-i харьцуулалт хийж байна. Иймээс нийт харьцуулалтын тоо ба алгоритмын ажиллах хугацааг илэрхийлэх f(n) функцийн утга f(n)=(n-1)+(n-2)+. . .+2+1=n(n-1)/2=O(n2) гэж тодорхойлогдоно. Орлуулан эрэмбэлэх арга Энэ аргын үндсэн үйлдэл нь эрэмбэлэгдсэн массивт эрэмбэлэлтийг алдагдуулалгүй шинэ элемент оруулах үйлдлээр тодорхойлогддог. Өөрөөр хэлбэл эрэмбэлэгдсэн элементүүдийн шинэ элементээс их элементүүдийг нэг байрлал баруун тийш шилжүүлэх байдлаар орвол зохих байрлалыг чөлөөлж өгнө. Орлуулан эрэмбэлэх алгоритмыг дараах insertion sort функцээр үзүүллээ. Шинээр оруулах элементийг гадаад давталт i-ээр массивын 2 дахь элементээс эхлэн авна. Эхний алхамд хамгийн эхний элементийг эрэмбэлэгдсэн массив гэж үзэн 2-р элементийг эхний элементтэй харьцуулан байрлалыг нь олсноор 2 элементтэй эрэмбэлэгдсэн массив гарган авна. Удаах алхамд үүсгэсэн 2 элемент бүхий эрэмбэлэгдсэн массивтаа массивын 3 дахь элементийг оруулах байдлаар массивын төгсгөл хүртэл бүх элементийн хувьд давтан гүйцэтгэнэ. Энэ алгоритмыг массивт хэрхэн ажиллахыг үзүүлье. 77 33 44 11 88 22 66 55 77 33 44 11 88 22 66 55 33 77 44 11 88 22 66 55 33 44 77 11 88 22 66 55 11 33 44 77 88 22 66 55 11 33 44 77 88 22 66 55 11 22 33 44 77 88 66 55 11 22 33 44 66 77 88 55 11 22 33 44 55 66 77 88 Орлуулан эрэмбэлэх алгоритмын харьцуулалтын тоо f(n) функцийг эхлээд хамгийн муу тохиолдол болох буурахаар эрэмбэлэгдсэн өгөгдлийн үед авч үзье. Энэ үед массивын k дахь элемент бүрийн хувьд дотоод давталтын хамгийн их k-1 харьцуулалтыг гүйцэтгэнэ. Эндээс f(n)=1+2+3+. . .+(n-1)=n(n-1)/2=O(n2) гэж тодорхойлогдох ба харьцуулалтын тооноос 2 дахин бага солилцох үйлдэл хийгдэнэ. Бөмбөлгөн эрэмбэлэлтийн арга Энэ арга нь массивын зэргэлдээ элементүүдийг харьцуулан, шаардлагатай бол утгыг солих замаар хамгийн их элементийг хойш шилжүүлэн массивын төгсгөлд байрлуулдаг. Ингэснээр хамгийн их элемент эцсийн байрлалаа олох ба үндсэн элементүүдийн хувьд мөн үйлдлийг давтан хийснээр удаах хамгийн их элемент массивын төгсгөлийн өмнөх байрлалыг эзлэнэ. Ийм байдлаар массивын нийт элемент эрэмбэлэгдэж дуустал гүйцэтгэдэг. Tүүвэр N элементтэй эх олонлогоос М элементийг дураар сонгон авъя. Үүнийг М элементтэй түүвэр гэх түүврийг буцаалттай ба буцаалтгүй гэж хоёр ангилна. Эх олонлогоос авсан элементээ буцааж хийхгүйгээр дараагийн элементийг авдаг бол буцаалтгүй түүвэр гэнэ. Харин авсан элементээ буцааж хийгээд дараагийн элементийг авдаг бол буцаалттай түүвэр гэнэ. N элементтэй эх олонлогоос авсан М элементтэй буцаалттай түүврийн тоо NM байна. N элементтэй эх олонлогоос авсан M элементтэй, эрэмбэ харгалзах буцаалтгүй түүврийг N-ээс M-ээр авсан гүйлгэмэл гэх ба гэж тэмдэглэнэ. байна. N=M үед N-ийн сэлгэмэл гэнэ. Сэлгэмэлийг гэж тэмдэглэх ба байна. N элементтэй эх олонлогоос авсан М элементтэй дэд олонлогийн тоог N-ээс М-ээр авсан хэсэглэл гэнэ. Хэсэглэлийг гэж тэмдэглэх ба байна. Хэсэглэл, сэлгэмэл Алгоритм программчлалд n ширхэг элементтэй эх олонлогийн бүх сэлгэмэлийг олох эсвэл k ширхэг элементтэй хэсэглэл олох бодлого элбэг тохиолддог. Ийм төрлийн бодлого нь олонлогийн элементүүдийн дугааруудаас сэлгэмэл эсвэл хэсэглэл зохиох бодлогод шилжинэ. Жишээ 23. 1,2,3, . . . . . . . . .,n тоонуудын бүх сэлгэмэлийг ол. Бодолт Өмнөх сэлгэмэлээс нь дараагийн сэлгэмэлийг үүсгэх замаар хамгийн сүүлчийн сэлгэмэл (n,n-1,. . . . . .,3,2,1) байхаар олъё. Эхний сэлгэмэлийг (1,2,3. . . . . .,n) гэж авна. Тухайн сэлгэмэлийн арын элементээсээ бага, хамгийн их дугаартай элемент a[k] ба түүнээс хойно оршдог, түүнээс их элементүүдийн хамгийн бага элемент a[j] хоёрын байрыг солиод a[k] элементээс хойш орших элементүүдийг өсөх эрэмбээр байрлуулж шинэ сэлгэмэл үүсгэе. дэд алгоритм (min дугаар олох) Дэд алгоритм (sort) // example 23 #include #include int a[100],n,k; int min(int t) {int B,i,R; B=a[t];R=t; for(i=t;i<=n;i++) if((a[i]>a[k])&&(a[i]a[j]) {min=a[j];k=j;} a[k]=a[i];a[i]=min; } } void main() {int i,j,b; clrscr(); printf("n=");scanf("%d",&n); for(i=1;i<=n;i++) {a[i]=i;printf("%3d",a[i]);} do{i=n; printf("n"); while((i!=1)&&(a[i-1]>a[i])) i--; if(i!=1){ k=i-1; j=min(k+1); b=a[j];a[j]=a[k];a[k]=b; sort(k+1); for(j=1;j<=n;j++) printf("%3d",a[j]); } }while(i!=1); } Жишээ 24. 1,2,3, , , , , , , ,n тоонуудаас к ширхэг элементтэй бүх хэсэглэлийг зохио. Бодолт. Эхний хэсэглэлийг 1,2,3, . . . .,к гэж авна. Өмнөх хэсэглэлээс дараагийн хэсэглэлийг үүсгэх замаар хамгийн сүүлчийн хэсэглэл n-k+1,n-k+2,. . . . . .,n байхаар олъё. k-р элементээс эхлэн уг элемент авч болох хамгийн их утгандаа хүрсэн эсэхийг шалгана. Нөхцөл биелэхгүй бол утгыг нь нэгээр нэмэгдүүлж, түүнээс хойш орших элемент бүрийг өмнөх элементээсээ нэгээр их байхаар байгуулж шинэ сэлгэмэл үүсгэе. i- р элементийн авах хамгийн их утга нь n-k+i байна. //example 24 #include #include int n,k,a[100]; void hes() {int i,t; for(i=1;i<=k;i++) printf("%3d",a[i]); printf("n"); i=k; while((i!=0)&&(a[i]==n-k+i)) i--; if(i!=0) {a[i]=a[i]+1; for(t=i+1;t<=k;t++) a[t]=a[t-1]+1; hes(); } } main() {int i,j; printf("n,k=");scanf("%d%d",&n,&k); for(i=1;i<=k;i++) a[i]=i; hes(); } Буцаалттай түүвэр Жишээ 25. 1,2,3, , , , , , , ,n тоонуудаас к ширхэг элементтэй бүх буцаалттай түүврийг зохио. Бодолт. Эхний түүврийг 1,1,1, . . . .,1 гэж авна. Өмнөх түүврээс дараагийн түүврийг үүсгэх замаар хамгийн сүүлчийн түүвэр n, n,. . . . . .,n байхаар олъё. K-р элементээс эхлэн уг элемент n утгатай болсон эсэхийг шалгана. Нөхцөл биелэхгүй бол утгыг нь нэгээр нэмэгдүүлж, түүнээс хойш орших элемент бүрийг нэг болгож шинэ түүвэр үүсгэе. //example 25 #include #include int n,k,a[100]; void tuub() {int i,t; for(i=1;i<=k;i++) printf("%3d",a[i]); printf("n"); i=k; while(i!=0 && a[i]==n) i--; if(i!=0) {a[i]=a[i]+1; for(t=i+1;t<=k;t++) a[t]=a[t-1]+1; tuub(); } } main() {int i,j; printf("n,k=");scanf("%d%d",&n,&k); for(i=1;i<=k;i++) a[i]=1; tuub(); } Динамик программчлалын бодлого Анхны бодлогоос бага хэмжээтэй дэд бодлогуудыг бодож тэдгээрийн үр дүнг хүснэгтэд хадгалан, түүнийгээ өмнөхөөс том хэмжээтэй бодлого бодоход ашиглаж болох төрлийн бодлогыг динамик программчлалын бодлого гэнэ. Динамик программчлалын бодлогын хувьд анхны бодлогын шийдийг олсон гэвэл түүний дурын хэсэг нь анхны бодлоготой төсөөтэй дэд бодлогын шийд болно. Жишээ 26. A[n,n]- массивын a[1,1] нүднээс эхлэн баруун, доош гэсэн давших чиглэлд нүднүүдийг дамжин явсаар A[n,n] нүдэнд очих, дамжсан нүд бүр дээрх тоонуудын нийлбэр хамгийн их байх, хамгийн богино замыг ол. Бодолт. Массивын нүдэнд шилжих ээлжит шилжилт бүр нь эсвэл баруун, эсвэл доош чиглэлд нэг нүдээр шилжих учир бүх зам адил урттай байна. Массивын дурын (i,j) нүдийг авч үзье. Энэ нүдэнд (i-1,j) эсвэл (i,j-1) нүднүүдээс шилжиж болно. (1,1) нүднээс эдгээр хоёр нүд тус бүрт хүрэх оновчтой зам мэдэгдэж байгаа тохиолдолд (i,j) нүдэнд шилжих хамгийн оновчтой зам нь тэдгээр нүдэн дэх тоог нэмэхэд нийлбэр нь хамгийн их байх тэр нүд мөн тэр нүдийг (i,j) нүдтэй холбосон хэрчмийг багтаасан тэр л дэд зам болно. (1,1) нүднээс (1,2) ба (2,1) нүднүүдэд шилжих хамгийн оновчтой зам нь нэгэн утгатай тодорхойлогдоно. Эдгээрийг мэдсэнээр дээр дурдсан аргаараа (1,3), (2,2), (3,1) нүднүүдэд шилжих оновчтой замыг тодорхойлж тэдгээрийг (замд орших нүдэн дэх цифрүүдийн нийлбэр ба сүүлчийн хэрчмийн чиглэл хоёр) хүснэгтийн харгалзах нүдэнд бичнэ. Энэ үйлдлийг хүснэгтийн бүх нүд бөглөгдөж дуустал үргэлжлүүлэе. Тэгвэл (n,n) нүдэнд шийд болох замын цифрүүдийн нийлбэр ба замын хамгийн сүүлчийн чиглэлийг гарган авна. Ийм хүснэгттэй болсноороо замаа хялбархан сэргээж болно. Бүхэл тоон бодлого 1. Өгөгдсөн гурван эерэг тооны арифметик болон геометрийн дунджийг ол. 2. x, y, z бодит тоонууд өгөгдөв. b- ийн утгыг ол. a. б. 3. нийлбэрийг ол. 4. үржвэрийг ол. 5. нийлбэрийг ол. 6. x,y,z- бодит тоонууд өгөгдөв. Гурвалжны талууд болох уу? 7. Өгөгдсөн n натурал тоо хүртэлх бүх сондгой тоонуудын нийлбэрийг ол. 8. Өгсөн 2 бүхэл тооны хамгийн бага ерөнхий хуваагдагчийг ол. 9. Өгсөн натурал тоог анхны үржигдхүүнд задал. Жишээ нь 21=3*7, 52=22*13 10. n- натурал тоог 2 натурал тооны квадратуудын нийлбэрт тавигдах эсэхийг тогтоо. 11. 7x+9y=90 тэгшитгэлийн бүхэл шийдийг ол. 12. n- натурал тоо, х-бодит тоо өгөгджээ. Дараах нийлбэрийг ол. a. b. c. 13. Эхний 2 цифрийн нийлбэр нь сүүлчийн 2 цифрийн нийлбэртэй тэнцүү байх бүх 4 оронтой анхны тоог ол. 14. Өгөгдсөн n- натурал тооноос хэтрэхгүй бөгөөд сүүлчийн цифр нь квадратынхаа сүүлчийн цифртэй тэнцэх бүх тоог ол. 15. Өгөгдсөн тоог дараалсан натурал тоонуудын нийлбэрт хэдэн янзаар задалж болох вэ? 16. Квадрат нь цифрүүдийнхээ нийлбэрийн кубтэй тэнцэх бүх хоёр оронтой тоог ол. 17. N- натурал тооны цифрүүдийг оронгийн зэрэгт дэвшүүлж нэмэхэд уг тоотой тэнцүү бол Армстронгийн тоо гэдэг. Жишээ нь 153=13+53+33 2,3,4 оронтой бүх Армстронгийн тоог ол. 18. N-натурал тооны цифрүүд бичигдсэн дарааллаараа арифметик прогресс үүсгэх эсэхийг тодорхойл. 19. Аравтын тооны к тооллын систем дэх тоог ол. 20. - бутархайн үеийг ол. Жишээ нь n=1,m=7 үед үе нь 142857 21. - бутархайг хураа. 22. Он сар өдрийг илэрхийлсэн 3 тоо өгөв. Тэгвэл тухайн өдөр ямар гариг вэ? 4, 400-д хуваагддаг жил нь өндөр ба харин 100-д хуваагддаг нь өндөр жил биш. 23. Оныг заасан n тоо өгөгдөв. Энэ онд хичнээн “Даваа” гариг байна вэ? 24. Тухайн жилийн 2 сарын эхний ням гаригт багш нарын баяр болдог бол өгөгдсөн жилийн багш нарын баярын өдрийг ол. 25. Календар зохио. 26. x,y (x>0,y>0) -бодит тоонууд өгөгдөв. yk-1Xp+3<.. . . . .>Xp+k нөхцлийг хангах хамгийн урт дэд дарааллыг ол. 13. 100х100 хэмжээтэй дөрвөлжин шугамтай цаасан дээр бие биенээ огтлоогүй ,давхцаагүй ,шүргээгүй тэгш өнцөгтүүд зурагдсан байв. (Тэгш өнцөгт бүр бүтэн нүд агуулна. ) A(100,100) массив өгөгдсөн бөгөөд A(i,j)=1 бол тэгш өнцөгтийн нүд, A(i,j)=0 бол тэгш өнцөгтийн нүд биш гэж үзнэ. Тэгш өнцөгтийн тоог ол. 14. A(n) массивын элементүүдийн эрэмбийг алдагдуулахгүйгээр тэгээс ялгаатай элементүүдийг массивын эхэнд тэг элементүүдийг массивын төгсгөлд байрлуул. 15. Гурвалжны оройн координатууд өгөгдсөн байхад өгсөн цэг гурвалжин дотор орших эсэхийг тогтоо. 16. Бодит тоон дараалал a1,a2,...,a2n өгөгдсөн бол а1,а2и,a2,a2n-1,a3,a2n-2,..,an,an+1гэсэн шинэ дараалал үүсгэ. 17. Нэгдүгээр мөр нь a1j=2j+3 томъёогоор, хоёрдугаар мөр нь а2j=j-3/(2+j) томъёогоор, дараагийн мөр бүр нь өмнөх 2 мөрийн харгалзах гишүүдийн нйилбэртэй тэнцүү байх aij (i,j=1,7) матриц зохио. 18. Натурал тоо n өгөгджээ. 1,2,...n тоонуудаас 2 натурал тооны квадратуудын нийлбэр хэлбэртэй дүрсэлж болох бүх тоог ол. Тооны квадрат таних дэд алгоритм зохио. 19. Натурал тоо n өгөгджээ. n,n+1,n+2,...,2n тоонууд дотор ялгавар нь 2-той тэнцүү байх хос анхны тоо байгаа эсэхийг тогтоо. Анхны тоо таних дэд алгоритм зохио. 20. Нэмэлт массив хэрэглэлгүйгээр А(N) массиваас анхны тоонуудыг устгаж өөрчлөгдсөн массиваа хэвлэ. Жишээ: 21 13 84 2 1 51-ээс устгавал 21 84 15 1 болно. 21. Өгөгдсөн A(N,M)массиваас мөр болгоноос минумимийг сонгон авч тэдгээрээс максимумыг дугаартай нь хэвлэ. 22. A[n,n] өгөгдсөн массив гол диагналь, дагуу тэгш хэмтэй эсэхийг шалга. 23. A[n,n] өгсөн массивын 2 диагналийг хооронд нь соль. 24. A[n,n] массив өгөв. A(n,n) -ын мөрөндөө хамгийн их болоод мөн багандаа хамгийн бага болох бүх элементийн байрлалыг ол. Хичээн тийм элемент байна вэ? 25. Мөр ба багана болон 2 диагналь дээрх тоонуудын нийлбэрүүд тэнцүү байдаг матрицыг шидэт гэдэг. A(N,N) матриц шидэт эсэхийг шалга. 26. A[n,m] массив өгөв. А11 элементийг эргүүлэлтийн төв болгож цагийн зүүний эсрэг 90 градус эргүүлж В(m,n) массивт хий. 27. A[n,n] массивт хамгийн олон орсон k ширхэг ялгаатай элементийг байрлалуудтай нь хэвлэ. 28. a[n] массивын элементээр гэсэн массив үүсгэ. 29. A(n) массиваас хамгийн урт үргэлжилсэн тэнцүү элементийн эхлэл ба төгсгөлийг олж уг элементээ хэвлэ. 30. A(n)-массивын эерэг ба сөрөг элементүүдийн (тэг элемент алинд ч орохгүй) тоог ол. 31. B(m) массивийн хамгийн их ба бага элементүүдийг ганц циклийн тусламжтайгаар ол. 32. M тооны 2-тын бичлэг мэдэгдэж байхад M+1 тооны 2-тын бичлэгийг ол. 33. Өгсөн n ширхэг эдлэлээс жин нь 30-аас хэтрэхгүй байх, үнэ нь хамгийн их байхаар сонго. Эдлэлүүдийн үнэ ба жин өгөгдөнө. 34. A(n,n) массивын харлуулсан хэсгийн a. Нийлбэрийг ол б. Хамгийн их ба бага элементийг ол. 35. А(n)-эрэмбэлэгдсэн массив, к-бодит тоо өгөгджээ. Массивын эрэмбийг алдагдуулахгүйгээр к тоог байрлуулж n+1 элементтэй шинэ массивыг байгуул. 36. 1,2,3, . . . .,n2 тоонуудыг зурагт үзүүлсэн маягаар байрлуулж n эрэмбийн квадрат матриц үүсгэ. 37. Хавтгайд n ширхэг цэг өгөгдөв. Хамгийн их талбайтай гурвалжин үүсгэх 3 цэгийг ол. 38. Паскалын гурвалжны эхний n мөрийг ол. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 . . . . . . . . . . . . . . . . . . . . . . . . 39. AxB тэгш өнцөгт өгөгдөв. Тэгш өнцөгтийн нүд бүрийг дэлгүүрийн нэг тасаг гэж үзээд уг тасгууд дахь барааны үнэ өгөгдсөн байг. Хулгайч 1x1 тасгаас эхлэн AxB тасгаар гадагш гарахдаа хамгийн бага замыг туулан хамгийн их үнэтэй бараануудыг сонгон авч гарах маршрутыг ол. Хулгайч хажуу тийш болон дээш чиглэлд үргэлж давших чиглэлд явна. 40. A(n,n) массив зөвхөн 0,1,5,11 гэсэн утгуудаас тогтоно. Элементүүд нь хоорондоо ялгаатай байх A(i,j), A(i,j+1), A(i+1,j), A(i+1,j+1) дөрвөл хэд байгааг тодорхойл. 41. Систем тэгшитгэлийг гауссын аргаар бод. Тэмдэгт мөрийн бодлого 1. Өгөгдсөн үгэнд х үсэг хэдэн удаа орсон эсэхийг тодорхойл. 2. Өгөгдсөн өгүүлбэрт хамгийн олон давтагдан орсон үгийг ол. 3. Өгөгдсөн үг полиндром эсэхийг шалга. 4. Өгөгдсөн өгүүлбэр дахь үгнүүдийг цагаан толгойн эрэмбээр нь хэвлэж гарга. 5. Өгүүлбэрт орсон хамгийн урт ба богино үгийг ол. 6. Өгөгдсөн үсгүүдийн дараалал дахь цагаан толгойн дарааллаараа байгаа дэд дарааллуудыг ол. 7. Өгөгдсөн хоёр өгүүлбэрт зэрэг орсон хамгийн урт үгийг ол. 8. Өгөгдсөн өгүүлбэрээс хамгийн олон гийгүүлэгч орсон үгийг ол. 9. Өгөгдсөн тэмдэгтүүдийн дарааллаас хоосон зайг хасаж, тэмдэгтүүдийг зүүн тийш шах. Гарчиг 1. Тооллын систем 3 2. Алгоритмын тухай ойлголт 11 3. Шугаман ба салаалсан алгоритм 15 4. Давталттай алгоритм 20 5. Массивын тухай ойлголт 31 6. Дэд алгоритм 39 7. Рекурсив 43 8. Эрэмбэлэтийн энгийн аргууд 47 9. Түүвэр 51 10. Динамик программчлалын бодлого 59 11. Бүхэл тоон бодлого 60 12. Массивын бодлого 62 13. Тэмдэгт мөрийн бодлого 66