Хуудсууд

2009-12-25

Сайн тэсвэр хатуужилтай болмоор юм байна даа

Сүртэй аймар тэсвэр хатуужил бишээ, юмыг өөр зүйлд сатаарахгүй хянамгай уншиж дадах хэрэгтэй юм байна. Саяхан хийсэн хэрэглээний програмыг (feeditor.com) хийхэд хэд хэдэн стандартын бичиг баримт, мөн төчнөөн RFC унших хэрэгтэй боллоо. Зарим нэгнээс нь ойлгож мэдсэнээ тоймлож блогтоо тавихыг бодноо.

Ассемблэр дээр програм бичих

Өчигдөр CodeWarrior татаж авлаа, үнэхээр лаг юмаа хэхэ. Ингээд доор сарыг аваад тухайн сар хэдэн хоногтойг A аккумляторт буцаадаг програс бичлээ. LCD цаг хийсэн лабораторт хэрэг болсон юм л даа. Илүү хурдан ажиллах кодны санаа байвал хуваалцаарай хүмүүсээ.
MY_EXTENDED_RAM: SECTION
YEAR        DS.w 1
MONTH       DS.b 1
DAY         DS.b 1

MyCode:     SECTION
main:
_Startup:
Entry: 
            LDD    #2006
            STD    YEAR
            LDAA   #4
            STAA   MONTH
            LDAA    #5
            STAA   DAY
            JSR   DAYBYMONTH
            SWI

DAYBYMONTH:             ; returns # of days in ACC A
            LDAB   MONTH    
            CMPB   #2      
            BEQ   TSTLEAP  
                       
            CMPB   #8       
            BGE   AUTUMN   
            LDAA   MONTH     
            ASRA 
            BCC     D30
            LDAA    #31      
            RTS
AUTUMN:     
            LDAA   MONTH     
            ASRA 
            BCS     D30
            LDAA    #31
            RTS
D30:        
            LDAA    #30
            RTS
TSTLEAP:
            LDD   YEAR
            LDX   #4
            IDIV
            TBNE   D,NOTLEAP
            LDAA   #29
            RTS
NOTLEAP:
            LDAA   #28
            RTS

2009-11-28

Монгол хэл дээрх wikibook төслийг устгах гэж байна

wikibook төсөл нь wikipedia-гийн дүү төсөл бөгөөд хэрэглэгчдэд нээлттэй эх (дан ганц програм хангамж биш) дээр тулгуурласан ном хамтарч бичих боломж олгоно. Энэхүү төсөл нь дэлхийн олон хэл дээр байдаг ба амжилттай хэргэжиж олон ном бий болж хүн бүр үнэ төлбөргүй уншиж болно. Харин энэ төслийн Монгол хэл дээрх төсөл устгах гэж байна. Учир нь манайхнаас хэн ч юу ч бичиж эхлүүлэхгүй байжээ. М.Эрдэнэчимэг багшийн орчуулсан "Open Source" номын өмнөх үгийг уншиж байлаа. Тэнд энэ орчуулгаа mn.wikibooks.org сайтад тавинаа гэж байна, тэгэхээр нь гоё санаа төрөөд энэний өмнө бичсэн "Линүксийн цөмийн програмчлал" бичлэгээ бас тэнд тавиад аажим аажимаар ном болгьё гэж бодлоо. Тэгээд сайтанд бүртгүүлээд шинэ хуудас нээх гэсэн болсонгүйээ. Хэн ч ямарч өөрчлөлт гаргаж болохгүй юм байна. Учир нь энэ оны 4-р сарын байдлаар Монгол хэл дээрх төслийг хаахаар болсон байна. Бүгдээрээ энэ талаар хамтарч үгээ хэлж байгаад буцааж нээх хэрэгтэй байна. Бас чадах чинээгээрээ ном нэмж байх хэрэгтэй байна. Бид чинь бүхэл бүтэн нэг үндэстэн улс шүү дээ.

2009-11-27

Линүксийн цөмийн програмчлал

Юникс (Unix) үйлдлийн систем нь маш их алдар хүндийг олсон боловч академээс гадуур хэрэглэхэд маш их өндөр өртэгтэй худалдагддаг байсан бөгөөд лиценз нь AT&T, Novell зэрэг томоохон компаниудын гар дамждаг байж л дээ. Тиймд хакерууд нээлттэй эх буюу үнэгүй тараагддаг "Юникстэй төстэй" (Unix-like) үйлдлийн системүүдийг хийж эхэлжээ. Ингээд Minix, BSD, Linux, Darwin гэх мэт үйлдлийн системүүд гарч ирлээ. Эдгээрээс Линүкс (Linux) нь нээлттэй эхийн хамт олны дунд маш их амжилтийг олж хөгжүүлэгдэж иржээ. Анхлан Линүкс үйлдлийн системийн цөмийг бичсэн, тухайн үедээ Финланд улсад оюутан байсан Лайнус Тровалдс нь одоог хүртэл Линүксийн цөмийг хөгжүүлэх явцад идэвхтэй оролцсоор байгаа юм.

Линүксийн хөгжүүлэлтэнд бусад нээлттэй эхийн хөгжүүлэлтийн үйл явцын адил байнгын оролцогч цөөн тооны мэргэжилийн хакерууд байх ба илүү олон тооны мэргэжилийн болон сонирхогч програмистууд оролцоно. Гэхдээ эдгээр нь Линүксийн цөм буюу kernel-ийг програмчлан нээлттэй эх кодыг нь kernel.org вэбсайтаар тараана. Үүн дээр үндэслээд хувь хүмүүс, албан байгууллагууд, ашгийн бус байгууллагууд, товчхондоо бол хүссэн хэн боловч өөрийн гэсэн Линүксийг бий болгон хэрэглэж болно. Эдгээрийн жишээ гэвэл: Red Hat Enterprise Linux, Mandriva, Debian, Ubuntu, ArchLinux, Puppy Linux, Knoppix, Damn Small Linux, Backtrack гээд өчнөөнийг дурдаж болно.

Цөмийг нь шинээр суулгахдаа өөрчилж болно. Энд нэгэн жишээг авч үзье.

Эхлээд зарим нэгэн юмыг тодорхой болгъё:

Програм нь хэрэглэгчийн түвшинд ажиллаж болно, эсвэл системийн түвшинд ажиллаж болно. Тиймч учраас хэрэглээний програм болон систеийн програм гэж нэршил байдаг боловуу. Хэрэглээний програм нь системийн дуудлага (system call) ашиглан системийн хэсэг болон техник хангамжтай харьцана. Жишээ нь энгийн C програманд fopen, printf, scanf зэрэг коммандууд нь цаанаа open, write, read системийн дуудлагуудыг ашиглан файл нээх, дэлгэцэнд бичих, дэлгэцнээс үсэгт авах зэрэг үйлдлийг хийнэ.

Юниксийн төрлийн үйлдлийн системүүдэд top гэсэн комманд ашиглаж санамжинд суурьлагдсан процессуудыг харж болдог билээ. Энэ нь Виндовс үйлдлийн системийн Task Manager гэсэн үг л дээ.

Тэгэхээр нэг ийм юм хийж туршиж үзье; системийн дуудлага ашиглан ажилж буй процессийг top дээр харагддаггүй болгодог.

Би Дэбиан (Debian) үйлдлийн систем дээр ажиллаж байгаа. Ингээд доорх коммандуудаар зарим програмуудыг татаж авья. # гэсэн тэмдэг нь root хэрэглэгчээр орсон гэсэн үг. Ер нь бол бүх юмаа тэгж хийсэн.

Програмуудынхаа листийг шинэчилэнэ:

# apt-get update

Линүксийн цөмийг татаж авна. Миний цөм Linux kernel 2.6.26 учир мөн адил цөмийг татна. Хэрэв таны ажилж буй Линүксийн цөм нь өөр бол тохирох цөмийг татаж авна уу.

# apt-get install linux-source

Цөмийг суулгахад хэрэглэгдэх багцыг татаж авна.

# apt-get install kernel-package

Мөн доорх туслах багажуудыг татаж авна:

# apt-get install fakeroot
# apt-get install libncurses5-dev
Ингээд хэрэгтэй зүйлсээ татаад суулгачихлаа. Линүксийн цөмийн эх код /usr/src/ хавтасанд хадгалагдсан байгаа. Түүнийг задална:
# tar xjvf linux-source-2.6.26.tar.bz2
# cd linux-source-2.6.26
/usr/src/linux-source-2.6.26 хавтас үүсэх бөгөөд энд Линүксийн хэрэгтэй файлууд бий. Одоо бидэнд тохиргооны .config файл хэрэгтэй. Энэ файлын тусламжтайгаар үйлдлийн систем маань ямар, ямар файл системийг дэмжих үү, ямар ямар техник хангамж дэмжих вэ гэдгийг тохируулж болно. Та өөрийн урьтаж бэлдсэн .config файлыг хэрэглэж болно, эсвэл үйлдлийн системийн /boot/ хавтасанд орших config-2.6.26-x-xxx файлыг хуулж тавиад нэрийг нь .config болгож өөрчилсний дагуу хэрэглэж болно.
mv /boot/config-2.6.26-2-686 /usr/src/linux-source-2.6.26/.config
Одоо кодоо өөрчилж эхэлье. Туршилтаа одоо илүү нарийн дэтальчилж доорх шатуудад хуваая:
  1. Процессийн бүтцэд visible гэдэг шинж чанар өгөөд анхны утгыг 1 гэж өгье
  2. Тодорхой нэгэн ажилж буй процессийн pid нь өгөгдсөн байхад visible утгыг нь 0 эсвэл 1 болгодог системийн дуудлага хийе
  3. Ажилж буй процессуудын visible утгуудыг нь шалгаад 1 байвал л top дээр харагддаг болгьё
  4. Хэрэглээний түвшинд ажиллаад шинэ системийн дуудлагыг ашигладаг шалгах програм бичье
Доорх алхамууд дээр /usr/src/linux-source-2.6.26 хавтасан дотор ажиллана. Жишээ нь include/linux/ гэдэг нь үнэндээ /usr/src/linux-source-2.6.26/include/linux/ хавтас юм. Харин / тэмдэгтээр эхэлсэн бол Линүкс үйлдлийн системийн үндсэн (/) файлаас эхэлж байна гэж ойлгоно уу.

1-р шатны ажилаа хийе. Процессийн бүтэц нь include/linux/sched.h файлан доторх "struct task_struct {}" тодорхойлолтонд багтана. Тэр бүтцийн тодорхойлолтын хамгийн дор нь "int visible;" гээд нэмнэ. Ингэснээр доорх шиг харагдах болно.

struct task_struct {
    volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
    void *stack;
    atomic_t usage;
    unsigned int flags;
        ...
        int visible;
};
Шинэ процесс үүсэхэд kernel/fork.c файлан доторх copy_process() функц хэрэглэгдэнэ. Тэнд visible утгаа 1 гэж зааж өгнө. Ингэснээр доорх шиг харагдах болно.
static struct task_struct *copy_process(unsigned long clone_flags,
     unsigned long stack_start,
     struct pt_regs *regs,
     unsigned long stack_size,
     int __user *child_tidptr,
     struct pid *pid)
{
    ...
    struct task_struct *p;
    ...
    p = dup_task_struct(current);
    p->visible = 1;
    ...
}

2-р шатны ажилаа хийе.

  • Интэл (Intel) чиптэй компьютерт arch/x86/kernel/syscall_table_32.S файлд доорхыг нэмнэ.
    long sys_set_visibility
  • include/linux/syscalls.h файлд системийн дуудлагын прототипийг нэмнэ.
    asmlinkage int sys_set_visibility(pid_t pid, int flag);
  • arch/x86/include/asm/unistd_32.h файланд системийн дуудлагын бүртгэлийг хамгийн сүүлийн бүртгэлийг нэгээр нэмэгдүүлж оруулна.
    #define __NR_...            332
    #define __NR_set_visibility 333
    
  • mycall хавтасыг үүсгээд set_visibility.c файлыг үүсгэж доорхыг нэмнэ.
    #include <linux/kernel.h>
    #include <linux/sched.h>
    asmlinkage long sys_set_invisibility(pid_t pid, int flag) {
    
         struct task_struct *task = &init_task;
     
         do {
             if(task->pid == pid){
                  task->visible = flag;
                  return 0;
             }
         } 
         while ( (task = next_task(task)) != &init_task );
         return -1;
    }
    
  • Эцэст нь цөмийг компайл хийхэд ашиглагдах Makefile-уудад өөрчлөлтүүдээ мэдэгдэнэ. /usr/src/linux-source-2.6.26/Makefile файлд доорхыг нэмнэ.
    core-y := ... mycall/
    
    mycall/Makefile үүсгэж доорхыг нэмнэ.
    obj-y := set_visibility.o
    

3-р шатны ажилаа хийе. Ажиллаж байгаа хэсгүүдийн /proc хавтасанд үүссэн мэдээллийг авдаг хэсгийн код нь fs/proc/base.c файлын proc_pid_readdir() функцэнд байна. Доорх мэдээллийг нэмж бичнэ:

...
int proc_pid_readdir(struct file * filp, void * dirent, filldir_t filldir)
{
    ...
    struct tgid_iter iter;
    ...
    iter.task = NULL;
    ...
    for (iter = next_tgid(ns, iter);
        iter.task;
        iter.tgid += 1, iter = next_tgid(ns, iter)) {
            if (iter.task->visible == 1) {
                filp->f_pos = iter.tgid + TGID_OFFSET;
                if (proc_pid_fill_cache(filp, dirent, filldir, iter) < 0) {
                    put_task_struct(iter.task);
                    goto out;
                }
            }
     }
     ...
}
...

4-р шатны ажилаа хийе. Шалгах програмыг (test.c) бичээд Desktop дээр хадгалаад компайл хйинэ. test.c

#include <sys/unistd.h>
#include <stdio.h>
#define __NR_set_invisibility 328

int main(void) {
    int x,y,z=-1;
    while (1) {
        printf("Hello! You can set visibility of a process with this program.\n");
        printf("Enter '<pid> <flag>' and hit! : Process ID, : 0 to make invisible ");
        printf("and 1 to make it visible again.\n");
        scanf("%d %d", &x, &y);
  
        z = syscall(__NR_set_invisibility, x, y);  
        if (z == 0) {
             printf(">>> Your modification was successful! Please review with 'top'!\n");
        } else {
             printf(">>> Error! There was a problem. Most probably, the process with this pid doesn't exist!");  
        }
    }
}
Дээрх кодоо компайл хийгээд програм болгочихье.
/home/dagvadorj/Desktop # gcc test.c -o test
Ингээд Линүкс цөм дээр хийх өөрчлөлтүүдээ хийж дууслаа. Одоо ингээд Линүкс цөмөө компайл хийе. Эхлээд цөм дээрээ тохиргоогоо хийнэ. Энд Линүксийн ямар техник хангамж, файлын систем дэмжих вэ гэдгийг тохируулж болно.
# cd /usr/src/linux-source-2.6.26
# make menuconfig
Жич: Дараа дараагийн алхмуудын дараа шинэ Линүксийн үйл ажиллагаанд ямарваа нэгэн алдаа гарвал хуучин тохиргоогоо make oldconfig гэсэн коммандаар сэргээж болно. Дараагийн алхамд хуучин компайлаас үлдсэн зүйлийг устгана.
# make-kpkg clean
Жич: Анх удаа компайл хийж буй тохиолдолд ингэж хийх шаардлагагүй гэдгийг анхаарна уу. Дараа нь Линүксийг компайл хийнэ. Доорх нь 20 минутаас 1 цаг үргэлжилж болно. Энэ хугацаа нь Линүксийн ямар техник хангамж, файл систем дэмжиж ажиллахаар тохируулагдсанаас шалтгаална. Илүү олон зүйл дэмжвэл илүү удна гэсэн үг. "harbin" гэдэг үгийн оронд таны өөрийн дурын нэр байж болно. Монгол хэл дээрх анхны сонин Харбинд хэвлэгдэж байсан, тэнд Гадаад Монголын мэргэжилтэн гар бие оролцож байсныг санан ийн нэрлэсэн билээ.
# fakeroot make-kpkg -initrd -append-to-version=-harbin linux_image linux_headers
Ингэсний дараа /usr/src хавтасанд 2 ширхэг .deb өргөтгөлтэй файл үүснэ. Тэдгээрийг доорх коммандуудаар суулгана.
# dpkg -i linux-image-2.6.26-harbin-2.6.26-harbin-10.00.Custom_i386.deb
# dpkg -i linux-headers-2.6.26-harbin-2.6.26-harbin-10.00.Custom_i386.deb
/boot хавтасанд Линүкс асахад хэрэгтэй initrd.img-2.6.26-harbin, vmlinuz-2.6.26-harbin ба бусад файлууд үүссэн байна. Зарим тохиолдолд /boot/initrd.img-2.6.26-harbin файл үүсээгүй байж болно. Энэ үед:
mkinitramfs -o /boot/initrd.img-2.6.26-harbin
/boot/grub/menu.lst файлд доорх эхлүүлэх сонголт нэмэгдсэн байгаа.
title   Debian/GNU Linux, kernel 2.6.26-harbin
root    (hd0,1)
kernel  /boot/vmlinuz-2.6.26-harbin root=/dev/hda2 ro quiet
initrd  /boot/initrd.img-2.6.26-harbin
Одоо компьютерээ reboot хийхэд эхлэх сонголт дээр harbin гарч ирэх бөгөөд сонгоод орно уу! top програмыг ажиллуулна уу!
# top
Доорх дэлгэц гарч ирнэ: Desktop дээр байгаа test програмыг ажиллуулсны дараа: 1,2,3 бүхий процессууд харагдахгүй байгааг анхаарна уу! За ингээд Линүксийн цөмийг жаахан ч гэсэн өөрчилөөд ажиллуулж үзлээ.

2009-11-15

Моторолла 6800

Моторолла 6800 бол нилээн дээхний 8 бит дээр ажилладаг бичил схем билээ. Өмнөх бичлэг дээр Intel x86 дээр бичсэн Фибоначийн дараалал олдог бодлогыг MC6800 дээр бичье.
  org $0000
  clra
  clrb  
  ldaa #6  ; find F6
  staa $001E  ; n=6
  ldaa #1  ; A=F0
  ldab #1  ; B=F1
start: staa $001F  ; Fn=A
  aba   ; A=A+B  
  dec $001E  ; n=n-1  
  tst $001E  ; test if n=0
  bne notyet ; if not branch to notyet   
  swi   ; software interrupt  
notyet: ldab $001F  ; b=Fn
  jmp start  ; jump to start


2009-11-11

Ассемблэр дээр код бичих

Ассемблийн хэл дээр бичигдсэн програм нь машины хэлрүү хялбархан хөрвүүлэгдэнэ. Энд NASM ашиглан жишээнүүд авч үзье. NASM нь Intel x86 хэл дээр ажиллана. Доорх програмыг авч үзье:
segment .data                   ; used for assigned variables
  msg  db   "Hello, world!",10
  len  equ  $ - msg             ; macro to calculate length of msg
                                ; equ for constant, ($-msg) means substract
                                ; msg's head address location from current address location

segment .text

global _start

_start:                         ; starting point

  mov  eax,4                    ; print system call
  mov  ebx,1                    ; standard output
  mov  ecx,msg                  ; the message to print
  mov  edx,len                  ; the length
  int  80h                      ; software interrupt

  mov  eax,1                    ; exit system call
  mov  ebx,0                    ; successful
  int  80h                      ; software interrupt

гэж бичээд foo.asm нэр өгч хадгалья. Дээрх програмын обьект файлыг Линүксд зориулж үүсгэхдээ:
nasm -f elf foo.asm -o foo.o
Одоо доорх коммандаар машины хэл дээрх кодыг нь харья:
nasm -f elf foo.asm -l foo.lis
Ингэхэд foo.lis файл үүссэн байна. Агуулгыг нь харвал:
1                                  segment .data
2 00000000 48656C6C6F2C20776F-     msg  db   "Hello, world!",10
3 00000009 726C64210A         
4                                  len  equ  $ - msg
5                                  
6                                  segment .text
7                                  global _start
8                                  
9                                  _start:
10 00000000 B804000000                  mov  eax,4
11 00000005 BB01000000                  mov  ebx,1
12 0000000A B9[00000000]                mov  ecx,msg
13 0000000F BA0E000000                  mov  edx,len
14 00000014 CD80                        int  80h
15                                  
16 00000016 B801000000                  mov  eax,1
17 0000001B BB00000000                  mov  ebx,0
18 00000020 CD80                        int  80h
эндээс компьютэрийн RAM санамж дээр бичигдэж ажиллах машины код харагдаж байна. Хэдийгээр эхний хаяг 0x00000000 гэж харагдаж байгаа ч санамжинд хуулагдах үед үйлдлийн систем хоосон буй өөр хаягаа оноож өгнө. Дээрх машины коп нь програмаас гараад software interrupt хийж байгаа учир линкэр ашиглан уншигддаг програм болгож болно:
ld foo.o -o foo -e _start
Тэгээд шууд ./foo гээд ажиллуулж болно. Одоо өөр нэг жишээ авч үзье. Доорх жишээнд C хэл дээр бичигдсэн програмаас ассемблэрийн хэл дээр бичигдсэн рутинийг ажиллуулах болно. bar.c
#include 

int star();
int fibo(int k);

int main() {
 int k,i;
 k = star();
 printf("Number is: %d\n", k);
 k = fibo(5);
 printf("5-th Fibonacci number is: %d\n", k);
 for(i=0;i<=8;i++) {
  printf("%d ", fibo(i));
 }
 printf("\n");
 return 0;
}

bar.asm

global star
global fibo

segment .bss
 sum resb 1

segment .text

star: mov ecx,8
 mov edx,9
 add ecx,edx
 mov [sum],ecx
 mov eax,[sum] 
 ret
fibo: push ebp
 mov ebp,esp
 mov eax,1
 mov ebx,1
 mov edx,[ebp+8]
 cmp edx,1
 jle fstop
 dec edx
fstep: mov ecx,eax
 add eax,ebx
 dec edx
 mov ebx,ecx
 cmp edx,0
 jne fstep 
fstop: pop ebp 
 ret
Ажиллуулахдаа:

1 - Ассемблэр кодноос обьект файл үүсгэнэ:

    nasm -f elf bar.asm -o barasm.o
2 - C кодноос обьект файл үүсгэнэ:
    gcc -c bar.c -o barc.o
3 - Обьект файлуудыг холбоно:
    gcc barasm.o barc.o -o bar
4 - Програмыг ажиллуулна:
    ./bar

USB дээр Damn Small Linux суулгах

  1. dsl-[version]-embedded.zip файлыг татаж аваад форматласан USB санамжийн төхөөрөмжид задална
  2. syslinux -ma G: гэж USB төхөөрөмжөө Bootable болгоно
  3. BIOS дээр компьютерээ USD төхөөрөмжөөс эхэлж Boot хийдэг болгоод асаана
Damn Small Linux нь маш жижиг хэмжээтэй (~50MB) бөгөөд Knoppix дээр суурилсан учир RAM дээр шууд ачааллана. mydsl-load комманд ашиглаад tar.gz, tar.bz2, dsl гэх мэт өргөтгөлтэй програмуудыг хялбархан суулгаж болно. mount /dev/hda1, mount /dev/sda1 гээд хатуу диск болон USB дисктэйгээ холбогдчихно.

2009-08-10

Android дээр хэрэглээний програм хөгжүүлэх

Android нь анхлан Google-ийн зүгээс хөгжүүлэгдэн нээлттэй эх кодтой болгогдсон гар утсанд зориулагдсан үйлдлийн систем юм. Android нь Linux кернел дээр ажилладаг. Кодыг Java програмын хэл ашиглан хөгжүүлнэ. SDK нь JSON, SQLite, HttpClient гэх мэт маш хэрэгцээтэй бүтээгдэхүүнүүдийг агуулдаг учир програм хөгжүүлэхэд тун хялбар болгож байна. Энд Android SDK ашиглан програм хөгжүүлье. Гэхдээ алхам алхам явахгүй, гүйцэд код тайлбарлах маягаар урагшлах болно.

Програм

UBList нь түрээслүүлэх болон зарах үл хөдлөх хөрөнгө хайх Android системтэй үүрэн телефонд зориулсан хэрэглээний програм (үүнээс хойш "програм" гэнэ) юм. UBList програмыг ашиглан ямарваа нэгэн хот дотор дүүрэг, хороолол, хайж буй үл хөдлөх хөрөнгийн төрөл болон үнийн дээд хязраарыг сонгосны (хоосон орхиж болно) дагуу хайлт хийн хайлтан дотроосоо зар сонгон илүү их мэдээллийг олж авах мөн газрын зураг дээр байршлыг нь харах, зар тавьсан этгээдрүү залгах боломжтой. Энэхүү програм нь Улаанбаатар болон дэлхийн бусад том метрополь хотуудад үл хөдлөх хөрөнгө хайгсадад хэрэгцээтэй байх боловуу.
Энэ бичлэгийг дуусгаагүй байгаадаа хүлцэл өчье!

GMail дээр уншаагүй майлүүдээ харах

GMail дээр уншаагүй майлүүдээ олох гэж зовдог байж билээ. Search mail дээр нь in:unread гээд таагаад бичээд хайсан болчихлоо. :P

Counting sort буюу Тоолж жагсаах алгоритм

Энэ адилтгах програмыг харж байгаад Тоолж жагсаах алгоритмыг бичлээ.
#include 

using namespace std;

void countingsort(int *from, int *to, int size) {

    int bound;

    //calculate the bound
    bound = from[0];
    for(int i=1; i < size; i++) {
        if(bound < from[i]) bound = from[i];
    }
    bound = bound+1;

    // counting elements to temporary array
    // of bound length
    int *tmp = new int[bound];
    for (int i=0; i < bound; i++) {
        tmp[i] = 0;
    }
    for (int i=0; i < size; i++) {
        tmp[from[i]]++;
    }

    // processing temporary array
    for (int i=1; i < bound; i++) {
        tmp[i] += tmp[i-1];
    }

    // moving elements to final array
    for (int i=0; i < size; i++) {
        tmp[from[i]]--;
        to[tmp[from[i]]] = from[i];
    }

    delete tmp;
}

int main() {
    int from[8] = {0,4,5,0,3,4,9,4};
    int to[8] = {0};

    cout << "The initial array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << from[i] << " ";
    }
    cout << endl;

    countingsort(from, to, 8);

    cout << "The final array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << to[i] << " ";
    }
    cout << endl;

    system("PAUSE");
    return 0;
}

Android Developer Challenge 2

Android Developer Challenge 2 найман сард бүртгэл нь эхлэх юм байна.

Android дээр явцыг хянах

JavaScript, ActionScript болон бусад хэлүүд дээр debug хэрэглэхгүйгээр UI эсвэл лог ашиглан програмын run-time дахь явцыг хянах нь маш үр ашигтай болдог билээ.

Тэгвэл Android дээр ингэж хийдэг юм байна.

Эхлээд яаж dialog box гаргаж ирэх вэ гэвэл:

import android.app.AlertDialog;
import android.app.AlertDialog.Builder;

private AlertDialog.Builder alert;

alert = new AlertDialog.Builder(this);
alert.setPositiveButton("OK", null);
alert.setCancelable(true);

alert.setMessage(R.string.alert_msg);
alert.create().show();

Програмаа бичээд алдаагүй компайл хийсэн ч гэлээ “The application … has stopped unexpectedly. Try again!” гээд бүдүүлэг бээрэгхэн мессеж гарч програм ажиллахгүй байх нь элбэг. Тэгвэл

adb catlog

гэж лог ажиллуулаад хянаж байх ашигтай.

Эндээ бас доорх кодыг run-time хэрэглэж өөрөө хянах мессеж харж байж болно.
import android.util.Log;

Log.w("My warning message >>> ", "My message goes here!");

Windows дээр Apache Ant суулгах

Юун түрүүн JDK суулгагдсан байх хэрэгтэй.

  1. Apache Ant програмын binary хувилбарыг http://ant.apache.org сайтнаас татаж авна.
  2. Татаж авсан apache-ant-1.7.1-bin.zip файлаа задална. C:\Ant гэсэн байрлалд задалсан гэж үзье.
  3. Виндовс үйлдлийн системийн Control Panel дотор System-рүү ороод Advanced табд ороод Environment Variables товчлуур дээр дарна.
  4. Гарч ирсэн цонхонд доорх өөрчлөлтүүдийг хийнэ. User variables-д ANT_HOME хэсэгт C:\Ant, CLASS_PATH хэсэгт C:\Ant\lib; гэж оруулна.
  5. Мөн System variablesPath хэсэгт C:\Ant\bin; гэж оруулна.

Одоо C\:>ant гэхэд ажиллах ёстой.

Вэб буюу Мэдээллийн Сүлжээ

Вэбийн тренд гэж яригддаг. Гэхдээ энэ ухагдахуунд бизнесмен биш, харин инженер үүднээс хандсан богинохон танилцуулга хийе гэж бодлоо.

Интернэтийн үүсэл хөгжлийн талаар зөндөө нийтлэл байдаг. Товчхон дурдах хэрэгтэй болов уу. Анхлан АНУ-гийн DoD (U.S. Department of Defense) буюу Батлан Хамгаалах Яамны зүгээс гүйцэтгэгдсэн ARPANET төсөл нь академийн ертөнцөд хэрэглэгдэж эхэлснээр яваа яваандаа Интернэтийн эх болжээ. Интернэт нь олон тооны суурин сүлжээг холбосон илүү өргөн хэмжээний сүлжээнүүдийн цогц юм. Интернэтийн тусламжтайгаар дэлхийн өнцөг булан дахь компьютерын ард сууж буй хүн бүхэн мэдээ, мэдээлэл солилцож чадах боллоо. Гэхдээ Веб гэж тэр үед байхгүй байлаа.

Өнгөрсөн жил Big Bang буюу Том Тэсрэлтийг батлах оролдлогоороо нэлээн цуу тарьсан Шведцарь дахь Европийн Цөмийн Судлалын Төвд (CERN) ажилж асан Их Британы эрдэмтэн Тим Бэрнэрс-Ли (Tim Berners-Lee) Интернэтэд мэдээлэл дамжуулах Өндөр Хурдтай Текст (HyperText) гэгчийг сэджээ. Энэ онолдоо зохицуулан мэдээлэл илэрхийлэх HTML (HyperText Mark-Up Language) болон мэдээлэл дамжуулах протокол HTTP (HyperText Transfer Protocol) боловсруулсан байна. HTML болон HTTP нь өнөөг хүртэл Веб дэх мэдээлэл дамжуулах үндсэн технологиуд юм. Вэбийн стандартчилалыг зохион байгуулах үүднээс W3C (Worldwide Web Consortium) консорциум байгуулагдсан ба сүүлд мөн Вэбийн үр ашигтай зөв хэрэглэх үүднээс SemanticWeb байгууллага ажиллаж байгаа бөгөөд хийсэн ажлаараа Их Британы хатан хаанаас Sir цол авч язгууртан болсон Сир Тим Бэрнэрс-Ли аль аль байгууллагад идэвхтэй оролцож байна.

Америкт HTML болон HTTP-д зориулж хэрэглэгчийн компьютер дээр ажиллах хэсэгч програм (бравзр) Mosaic түгэж хойноос нь Netscape гарч иржээ. Харин Microsoft корпораци өөрсдийн бүтээгдэхүүн Internet Explorer-ыг Windows 95 үйлдлийн системтэй үнэгүй тарааж эхэлснээр “Бравзрын Дайн”-д Netscape ялагдаж интернэтийн агуулгын томоохон тоглогч AOL-д зарагдан удалгүй Netscape Navigator програм нээлттэй эхтэй болсноор Mozilla Firefox болон Mozilla сан гарч ирэн Microsoft-ийн толгой дээр цахиур хагалсан гэж болно. Харин сүүлийн үед гарч ирсэн Google Chrome нь мөн шинэлэг бөгөөд маш чадвартай технологи болсон билээ.

Өндөр хурдтай текст буюу HTML-ийг боловсруулах технологи ч мөн хөгжиж ирлээ. Мэдээж HTML-ээр илэрхийлэгдсэн хуудас дан ганц текст харуулахгүй, зурагнаас авхуулаад төрөл бүрийн обьектийн илэрхийлэл дамжуулж, бравзр буюу бравзр дээр суурилсан програм тэднийг хэрэглэгчид харуулна. HTML хуудас статик бус динамик буюу програмын хэлээр урьдчилан боловсрогддог болсон нь шинэ зүйл биш билээ. Perl, CGI, PHP, ASP, CFM нар нь бүгд HTML хуудас боловсруулна. Мөн илүү дэвшилтэт Java, C#, Python, Ruby зэрэг хэлүүдийг ашигладаг Java 2 EE, ASP.NET, Ruby on Rails, JSF зэрэг платформууд байна. Веб хуудас бүхлээрээ эсвэл нэг хэсэг нь урьдчилан програмчлагдан сүлжээгээр дамжуулагдсанаар веб хуудсаар дамжуулан өгөгдлийн сантай харьцах гэх мэт олон боломж гарч ирнэ. Ийм төрлийн програмчлалыг сервер-талт програмчлал гэнэ.

Вэб хуудаснуудын болон обьектуудын байрлах компьютерыг сервер гэх ба Интернэтээр дамжуулан веб хуудсыг бравзр дээр харуулж буй компьютерыг клайнт буюу хэрэглэгч гэнэ. Вэб хуудас бравзр дээр ачаалласаны дараа мөн програмчлал агуулж байж болно. Энэ нь ихэвчлэн Netscape-ээс гаралтай JavaScript хэлээр гүйцэтгэгдэнэ.

Сүүлийн үед AJAX буюу Web 2.0 (цаашлаад SaaS, RIA гэх мэт олонг дурьдаж болно) гэж их сонсогдох боллоо. Орчин үед веб сайтууд компьютер дээр суурилагдсан програмын хийж чадах бүх юмыг хийдэг болсноор барахгүй, шинэ үйл болсон бүрийд хуудас тэр чигээрээ дахин ачааллах хэрэггүй болж хэрэглэгчид хялбарчлал болон цаг хугацаа ихийг хожуулж байна. AJAX (Asynchronous JavaScript And XML) технологиийн тусламжтайгаар ачааллагдсан вэб хуудсан дээрх JavaScript програм далдуур өөр хуудас ачааллан гарсан хариуг буцааж хүлээж авах боломжтой болжээ.

Stack

Stack нь компьютерийн програмчлалд их хэрэглэгдэх өгөгдлийн бүтэц юм. Ажиллах зарчмын хувьд LIFO (last in first out) буюу “сүүлд нэмэгдсэн нь эхэлж гарна” гэж тайлбарлагдана. Монгол хэлээр юу гэж хэрэглэж болох вэ гэж бодоод “Болор Толь”-руу орж үзвэл “бухал”, “овоо”, “тавиур” гэсэн үгүүд байж болох.

Энд нэг жишээ тавья! Уул нь генерик өгөгдөл дээр жишээ бол сайн байх ч, одоохондоо зөвхөн бүхэл тооны жишээ тавья:

stack.h
#ifndef _STACK_H
#define _STACK_H

typedef struct {
   int logiclen;
   int alloclen;
   int * elems;
} stack;

void StackNew(stack * s);

void StackDispose(stack * s);

void StackPush(stack * s, int value);

int StackPop(stack * s);

#endif

stack.c
#include 
#include "stack.h"

void StackNew(stack * s) {
    s->logiclen = 0;
    s->alloclen = 4;
    s->elems = malloc(4*sizeof(int));
}
void StackDispose(stack * s) {
    free(s->elems);
    free(s);
}
void StackPush(stack * s, int value) {
    s->elems[s->logiclen] = value;
    s->logiclen++;
}
int StackPop(stack * s) {
    s->logiclen--;
    return s->elems[s->logiclen];
}

program.c
#include 
#include "stack.h"

int main() {
    stack s;
    StackNew(&s);
    StackPush(&s, 4);
    StackPush(&s, 5);
    StackPush(&s, 6);
    printf("%d\n", StackPop(&s));
    printf("%d\n", StackPop(&s));
    printf("%d\n", StackPop(&s));
    StackDispose(&s);
    system("PAUSE");
    return 0;
}

Google Wave

Google-ийн шинэ бүтээгдэхүүн Google Wave үнэхээр электрон шуудангаас авахуулаад олон юм өөрчилж чадах байхаа. Google I/O 2009 семинар дээр болсон танилцуулах видеог эндээс үзнэ үү! “Icland is an icland.” -> “Iceland is an island.” :D

Обьект хандлагат програмчлал

#include 
#include 

using namespace std;

class Fraction {
 unsigned int num;
 unsigned int denom;
 public:
  Fraction() { }
  Fraction(unsigned int , unsigned int );
  Fraction(const Fraction & );
  bool operator==(const Fraction & z) {
   return (z.num == num && z.denom == denom);
  }
  bool operator<(const Fraction & z) const {
   if ((float)num/denom < (float)z.num/z.denom)
    return true;
   else
    return false;
  }
  void setDenom(int new_denom) {
   denom = new_denom;
  }
  unsigned int getNum() const {
   return num;
  }
  unsigned int getDenom() const {
   return denom;
  }
};

Fraction::Fraction(unsigned int new_num, unsigned int new_denom) {
 num = new_num;
 denom = new_denom;
}

Fraction::Fraction(const Fraction & z) {
 num = z.num;
 denom = z.denom;
}

template
class MyArray {
 int mysize;
    Type * content;
    public:
        MyArray(int);
  MyArray(const MyArray & z) {
   mysize = z.mysize;
   content = z.content;
  }
  Type & operator[](int i)  {
   if (i < 0) throw string("index out of bounds");
   else if (i > mysize) throw string("index out of bounds");
   return content[i];
  }
  const Type & operator[](int i) const {
   if (i < 0) throw string("index out of bounds");
   else if (i > mysize) throw string("index out of bounds");
   return content[i];
  }
  bool contains(Type elem) const {
   int i;
   for (i=0; i < mysize; i++) {
    if(content[i] == elem) return true;
   }
   return false;
  }
  const Type & operator!() const {
   int i=0;
   for (int j=1 ; j <= mysize; j++)
    if (content[i] < content[j]) i=j;
   return content[i];
  }
};

template
MyArray::MyArray(int size) {
 mysize = size;
    content = new Type[size];
}

ostream& operator <<(ostream& out, const Fraction& z)  // Overloading <<
{
 out << "( " << z.getNum() << "/" << z.getDenom() << " )";
 return out;
};
int main(int argc, int ** argv) {
    int i;
 MyArray m1(5); // creates an empty 5-element-integer array inside the object m1;
 MyArray m2(3); // creates an empty 3-element-integer array inside the object m2;
 for (int i = 0; i <= 5; i++ ){
  try{
   m1[i] = i;
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }

 MyArray m3 = m2 = m1;

 for (i = 0; i <= 5; i++ ){
  try{
   cout << m3[i] << " ";
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }

 if (m1.contains(3))
  cout << "Element 3 is contained in the array" << endl;
 else
  cout << "Element 3 is not contained in the array" << endl;

 cout << "The largest element in the array: " << !m1 << endl ;

 MyArray m4(3); // An array with two empty spaces

 Fraction cObj1(3, 5); // A Fraction object with an unsigned numerator and unsigned denominator
 Fraction cObj2 = cObj1;
 Fraction cObj3 (3,4);
 cObj2.setDenom(7); // sets the denomenator of the Fraction object as 7

 try {
  m4[0] = cObj1;
  m4[1] = cObj2;
  m4[2] = cObj3;
 }
 catch(const string & err_msg){ // exception handler
  cout << err_msg << endl; //writes "index out of bounds"
 }

 for (i = 0; i < 3; i++ ){ // NOTE: burada yanlislikla i<=3 yazildigini sanip degistirdim
  try{
   cout << m4[i] << " ";
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }
 if (m4.contains(Fraction(3,7)))
  cout << "The element is contained in the array" << endl;
 else
  cout << "The element is not contained in the array" << endl;

 cout << "The largest element in the array: " << !m4 << endl ;

    return 0;
}

Windows дээр Haskell ажиллуулах

Haskell програмын хэлийн хамгийн алдартай компайлэр нь GHC буюу Glasgow Haskell Compiler юм байна. Энэ интэрпрэтэр буюу компайлэрийг Windows дээр хэрэглэснээ бичиж үлдээе!
Prelude> :cd C:/Haskell/
Prelude> :load Main.hs
*Main> main
C:/Haskell/Main.hs файлын агуулга нь доорх шиг байна.
module Main where

main = do
     putStrLn "Hello, World!"

Процесс хоорондын харилцаа буюу IPC

#include < stdio.h >
#include < stdlib.h >
#include < string.h >
#include < sys/sem.h >
#include < sys/shm.h >
#include < sys/types.h >
#include < sys/ipc.h >
#include < time.h >

#define SEMKEY (1492)
#define SHMKEY (1493)
#define SHMKEY2 (1494)

int obid() {
 int shmid2;
 int * bestbid;
 if ((shmid2 = shmget(SHMKEY2, sizeof(int), 0666)) < 0) {
  exit(-1);
 }
 if ((bestbid = shmat(shmid2, NULL, 0)) == (int *) -1) {
  exit(-1);
 }
 if (*bestbid == -1)
                printf("Үнэ хаялтын шийдвэр хүлээгдэж байна.n");
 while (*bestbid == -1)
                sleep(1);
 return 0;
}

int main(int argc, char **argv){
 int n;
 int semid;
 int shmid, shmid2;
 pid_t pid;
 int retval;
 int i; // for iteration i.e., C99 standard
 struct sembuf operations[1];
 int * bids, * bestbid;
 int semval;
 int rndnum;
 int min;
 int processid;

 if (argc < 2) {
  printf("Алдаа: Ажиллуулмаар байгаа процессийн тоо хэмжээг оруулаагүй байна.n");
  exit(-1);
 }
 n = atoi(argv[1]);

 /* Semaphore */

 semid = semget(SEMKEY, 1, 0666 | IPC_CREAT);
 if(semid < 0)
 {
  exit(-1);
 }

 union semun {
  int val;
  struct semid_ds *buf;
  ushort * array;
 } argument;
 argument.val = n;

 if( semctl(semid, 0, SETVAL, argument) < 0) {
                printf("Алдаа: Сэмафорын утгыг өгч чадсангүй.\n");
                exit(-1);
        }

 /* Shared memory for bids */

 if ((shmid = shmget(SHMKEY, n*sizeof(int), IPC_CREAT | 0666)) < 0) {
  exit(-1);
 }

 if ((bids = shmat(shmid, NULL, 0)) == (int *) -1) {
  exit(-1);
 }

 /* Shared memory for the minimum bid */

 if ((shmid2 = shmget(SHMKEY2, sizeof(int), IPC_CREAT | 0666)) < 0) {
  exit(-1);
 }

 if ((bestbid = shmat(shmid2, NULL, 0)) == (int *) -1) {
  exit(-1);
 }

 *bestbid = -1;

 for (i=0; i < n; i++) {
  pid = fork();
  if (pid < 0) {
   printf("Алдаа: Хүүхэд процесс үүсгэхэд алдаа гарлаа.\n");
  } else if (pid == 0) { //child process
   processid = i;
   semval = semctl(semid, 0, GETVAL, argument);

   rndnum = (abs((getpid() * rand())) % 1000) + 10;

   *(bids+semval) = rndnum;

   printf("Процесс #%d: %d MNT Үнэ санал болголоо. ", i, rndnum);

   operations[0].sem_num = 0;
   operations[0].sem_op = -1;
   operations[0].sem_flg = 0;

   if (semval == 1) {
    printf("Шийдвэр хүлээгдэж байна.\n");
                min = *(bids+i);
    for(i=1; i <= n; i++) {
     if (min > *(bids+i+1) & i+1 <= n) {
      min = *(bids+i+1);
     }
    }
    *bestbid= min;
    printf("Хамгийн бага үнийн санал: %d MNT. obid функцд хүлээгдэж байсан процессууд ажилна.\n", *bestbid);
   }

   retval = semop(semid, operations, 1);

   if(retval == 0)
   {
    if (obid() == 0) {
                    printf("Процесс #%d: obid функцээс буцлаа. \n", processid);
                }
    exit(0);
   }

  } else { //parent process
   if (semctl(semid, 0, GETVAL, argument) == 0) {
    semctl(semid,0,IPC_RMID,0);
                shmctl(shmid,IPC_RMID,0);
                shmctl(shmid2,IPC_RMID,0);
                exit(0);
   }
  }
 }

 printf("n");
 return 0;
}

Insertion Sort Algorithm буюу Нэмж Жагсаах Алгоритм

void insertionsort(int * input, int n) {
     int j;
     int i;
     int key;
     for(j=1; j < n; j++) {
        key = input[j];
        i = j-1;
        while(i >= 0 && input[i] > key) {
            input[i+1] = input[i];
            i--;
        }
        input[i+1] = key;
     }
}

int main() {
    int i;
    int array[] = {9,8,7,6,4,2};

    insertionsort(&array, 6);
    for (i=0; i<6; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    system("PAUSE");
    return 0;
}

Дээрх алгоритм нь массивт байгаа тоонуудыг хоёр дахиас нь эхлэн тоо тус бүрийг өмнөх тоонуудтай нь харицуулан өмнөх тооноосоо бага бол байрыг нь сольж үргэлжлүүлэн итерацаар ажилна.

Хамгийн муугаар бодож байж алгоритмын үнэ цэнийг олж авна. Жишээ нь дээрх “нэмж жагсаах” алгоритмийн хувьд массив дахь тоонууд эсрэгээрээ (ихээсээ багаруу) жагсаагдсан байрлалтай бол n2 үйлдлийн дараа алгоритм ажилаа хийж дуусан байна. Өөрөө хэлбэл O(n2).

2009-08-07

Шугаман хайлт буюу lsearch

C хэлний санамжийг яаж ашигладагийг анзаарахын тулд шугаман хайлт буюу lsearch алгоритмыг авч үзье! Энэ алгоритм нь “генерик” буюу буюу бүхий л өгөгдлийн төрөл дээр ажиллана. (Жишээ нь: int, char, short гэх мэт)

void * lsearch(void * key, void * base, int n, int elemSize,
                int (* cmpfn)(void *, void *))
{
    int i;
    for(i=0; i < n; i++) {
        void * elemAddr = (char *)base + i*elemSize;
        if(cmpfn(key, elemAddr) == 0)
            return elemAddr;
    }
    return NULL;
}

Дээрх функц нь доорх 5 параметрийг авч байна:

  • key – хайх түлхүүр
  • base – санамжинд хайж эхлэх хаяг
  • n – санамжин дахь хайх урт
  • elemSize – элементийн хэмжээ
  • cmpfn – тэнцүү эсэхийг шалгах функцийн прототип

Зарчмын хувьд энэхүү алгоритм нь компьютерийн санамж буюу RAM дээрх нэгэн байршилаас (void * base) эхлэн тус бүр өгөгдсөн ижил урттай (int elemSize) тодорхой тооны (int n) элемент дунд нэг обьект (void * key) байгаа эсэхийг шалгана. 6-р мөрөнд void * elemAddr=(char *)base + i*elemSize; гэж зааснаар base-ийн зааж буй нэг byte мэдээллээс хойш i*elemSize алхам хойно гэсэн утга заажээ.

Харин өгөгдсөн элементүүдийн төрөлөөс шалтгаалан тэнцүү эсэхийг шалгах функц нь өөр өөр байж болох учир функцийн прототипийг зааж өгсөн (int (* cmpfn)(void *, void *)) байгаа ба алгоритмийг хэрэглэгч өөрөө тэр функцыг тодорхойлох хэрэгтэй. Жишээ нь өгөгдсөн массив дотор тодорхой нэгэн тоо байгаа эсэхийг шалгах програм бичье.

int IntCmp(void * elem1, void * elem2) { 
    int *ip1 = elem1; 
    int *ip2 = elem2; 
    return *ip1-*ip2; 
} 

int main(int argc, char * argv[]) { 
    int array[] = {4,2,3,7,11,6}; 
    int size = 6; 
    int number = 7; 

    void * found = lsearch(&number, array, size, sizeof(int), IntCmp); 

    if (found == NULL) 
        printf("Not found!\n"); 
    else
        printf("Found.\n"); 

    system("PAUSE"); 
    return 0; 
}

Cliché

Ихэвчлэн алгоритм бичихэд хэрэг болдог өгөгдлийн бүтцүүд байдаг. Жишээ нь: stack, queue, heap гэх мэтчилэн. Яг хэрэг болохоор зарчмыг нь санаад кодыг нь санадаггүй, эсвэл ахиж бичих хэрэгтэй болчихоод байхын энэ болон бусад хэрэгтэй кодуудын өөрт хэрэгтэй санагдсаныг нь эмхлээд хадгалаад байя гэж бодлоо.

2009-07-19

Python програмын хэл

Python их таалагдлаа. Python нь функсионел ч, обьект хандлагат ч аль альнаар нь хэрэглэгдэж болдог. “Мад шалгах” (“Check the Check” problem) бодлогыг бодсон кодоо толилуулья:

import sys

#шатрын хөлгийг оруул
fin = open(sys.argv[1], "r") #аргумент дээр зааж өгсөн файлыг унш
lineList = fin.readlines()
fin.close()

#үндсэн код
i = 0
count = 1
matrix = []

for line in lineList:
  if line == '\n': #хоосон мөр байвал
     checkBlack = check(matrix,x,y,0) #хар ноён мадлагдсан эсэх
     checkWhite = check(matrix,x1,y1,1) #цагаан ноён мадлагдсан эсэх
     if checkWhite == True and checkBlack == True:
         print("Тоглоом# " + str(count) + ": Хоёр ноён мадлагдсан.");
     elif checkWhite == True and checkBlack == False:
         print("Тоглоом# " + str(count) + ": Цагаан ноён мадлагдсан.");
     elif checkWhite == False and checkBlack == True:
         print("Тоглоом# " + str(count) + ": Хар ноён мадлагдсан.");
     else: print("Тоглоом# " + str(count) + ": Аль нь мадлагдаагүй.");
     i = 0
     count = count+1
     matrix = []
  else: #хоосон мөр биш бол матрикст нэм
     matrix.append(line)
     if str.find(line, 'k') != -1: #хар ноён байвал байршлыг тогтоо
         x = i
         y = str.find(line, 'k')
     if str.find(line, 'K') != -1: #цагаан ноён байвал байршлыг тогтоо
         x1 = i
         y1 = str.find(line, 'K')
     i = i + 1
Дээрх кодонд check гээд нэг функц байна. Үүрэг нь ноёны мадлагдсан эсэх. Код нь:
toys = ['p','n','b','r','q','k','P','N','B','R','Q','K']

def contains(toys, item):
    i = 0
    while i < 12:
        if toys[i] == item: return True
        i = i+1
    return False

def check(matrix,x,y,n): # n=1: цагаан, n=0: хар

    if n==0: index = 6
    else: index = 0

    p = toys[index+0]
    n = toys[index+1]
    b = toys[index+2]
    r = toys[index+3]
    q = toys[index+4]
    k = toys[index+5]

    # бэрсийн хөл дээр шалгах
    if x+2 <= 7:
        if y-1 >= 0 and matrix[x+2][y-1] == n: return True
        if y+1 <= 7 and matrix[x+2][y+1] == n: return True
    if x+1 <= 7:
        if y-2 >= 0 and matrix[x+1][y-2] == n: return True
        if y+2 <= 7 and matrix[x+1][y+2] == n: return True

    # хүү болон ноёны хөл дээр эсэхийг шалгах - диагонал
    if x-1 >= 0 and y+1 <= 7 and (matrix[x-1][y+1] == p or matrix[x-1][y+1] == k): return True;
    if x-1 >= 0 and y-1 >= 0 and (matrix[x-1][y-1] == p or matrix[x-1][y-1] == k): return True;
    if x+1 <= 7 and y+1 <= 7 and (matrix[x+1][y+1] == k): return True;
    if x+1 <= 7 and y-1 >= 0 and (matrix[x+1][y-1] == k): return True;

    # ноёны хөл дээр эсэхийг шалгах
    if x+1 <= 7 and matrix[x+1][y] == k: return True;
    if y+1 <= 7 and matrix[x][y+1] == k: return True;
    if x-1 >= 0 and matrix[x-1][y] == k: return True;
    if y-1 >= 0 and matrix[x][y-1] == k: return True;

    # тэрэг эсвэл бэрсийн хөл дээр эсэхийг шалгах
    toys[index+4] = '*'; # бэрсийг массиваас арилгах
    toys[index+3] = '*'; # тэргийг массиваас арилгах

    i = y+1
    while i <= 7:
        if contains(toys, matrix[x][i]) == True: break;
        elif matrix[x][i] == r or matrix[x][i] == q: return True;
        i = i+1

    i = y-1
    while i >= 0:
        if contains(toys, matrix[x][i]) == True: break;
        elif matrix[x][i] == r or matrix[x][i] == q: return True;
        i = i-1

    i = x+1
    while i <= 7:
        if contains(toys, matrix[i][y]) == True: break;
        elif matrix[i][y] == r or matrix[i][y] == q: return True;
        i = i+1

    i = x-1
    while i <= 7:
        if contains(toys, matrix[i][y]) == True: break;
        elif matrix[i][y] == r or matrix[i][y] == q: return True;
        i = i-1

    toys[index+3] = r; # тэргийг массивт буцааж нэм
    # бэрс болон тэмээний хөл дээр эсэхийг шалгах
    toys[index+2] = '*'; # тэмээг массиваас арилгах

    i = x+1
    j = y+1
    while i <= 7 and j <= 7:
        if contains(toys, matrix[i][j]) == True: break;
        elif matrix[i][j] == b or matrix[i][j] == q: return True;
        i = i+1
        j = j+1

    i = x-1
    j = y-1
    while i >= 0 and j >= 0:
        if contains(toys, matrix[i][j]) == True: break;
        elif matrix[i][j] == b or matrix[i][j] == q: return True;
        i = i-1
        j = j-1

    i = x-1
    j = y+1
    while i >= 0 and j <= 7:
        if contains(toys, matrix[i][j]) == True: break;
        elif matrix[i][j] == b or matrix[i][j] == q: return True;
        i = i-1
        j = j+1

    i = x+1
    j = y-1
    while i <= 7 and j >= 0:
        if contains(toys, matrix[i][j]) == True: break;
        elif matrix[i][j] == b or matrix[i][j] == q: return True;
        i = i+1
        j = j-1

    toys[index+2] = b; # тэмээг массивт буцааж нэм
    toys[index+4] = q; # бэрсийг массивт буцааж нэм
    return False

Програмын ажиллах горим

Дээрх програм нь текст маягаар бичигдсэн шатрын хөлгийг аргументээр авна. Жишээ нь хөлөг доорх маягаар өгөгдсөн байхад:
..k.....
ppp.pppp
........
.R...B..
........
........
PPPPPPPP
K.......

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

rnbqk.nr
ppp..ppp
....p...
...p....
.bPP....
.....N..
PP..PPPP
RNBQKB.R

........
........
........
........
........
........
........
........

гаралт нь доорх шиг байна:
Тоглоом #1: Хар ноён мадлагдсан.
Тоглоом #2: Аль нь мадлагдаагүй.
Тоглоом #3: Цагаан ноён мадлагдсан.

Кодыг ажиллуулах

Дээрх эх кодыг ажиллуулахдаа Linux дээр Python суулгагдсан бол:
$ python ./check.py "input.txt"
гээд л ажиллуулчихна. Харин Windows дээр бол эхлээд binary executable файл үүсгэх хэрэгтэй:
>>> import py_compile
>>> py_compile.compile("check.py")
Ингэснээр check.py файлын байгаа хавтаст check.pyc гэсэн executable файл үүсэх болно. Дараа нь Windows cmd prompt дээрээ:
check.pyc input.txt
гээд ажиллуулчихна.

Сайн уу, дэлхий

Сайн байцгаана уу? Энэ бол энэ блогийн маань printf("Hello, World!"); бичлэг маань. Тэгээд одоо бичээд байна даа. :D Уул нь энэхүү блогоо "Хаалган хот" нэрээр Wordpress дээр хөтөлж байснаа Blogspot-д дассанаас болснуу энд бичмээр санагдлаа.