The following signatures were invalid: BADSIG 40976EAF437D05B5 Ubuntu Archive Automatic Signing Key

Ubuntu дээр сайжруулалт хийхэд

W: A error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://security.ubuntu.com oneiric-security Release: The following signatures were invalid: BADSIG 40976EAF437D05B5 Ubuntu Archive Automatic Signing Key

Ийм алдаа өгвөл ингэж засах юм байна.

$ sudo -i
# apt-get clean
# cd /var/lib/apt
# mv lists lists.old
# mkdir -p lists/partial
# apt-get clean
# apt-get update

Хурдан эрэмбэлэлт (Quick Sort) - C VS Lisp

Хурдан Эрэмбэлэлтийг 1960 онд Чарльз Энтони Ричард Хоар Москвагийн Их Сургуульд оюутан байхдаа Үндэсний Физикийн Лабораторийн төсөл дээр ажиллаж, тэр үедээ энэхүү эрэмбэлэлтийг хөгжүүлсэн байна. Хурдан Эрэмбэлэлт хамгийн өргөн хэрэглэгддэг эрэмбэлэлт юм.

Хугацаа нь:

• Сайн тохиолдолд O(n log n)
• Дундаж тохиолдолд  O(n log n)
• Муу тохиолдолд O(n^2)

Алгоритм нь:

1. Гол элемент (pivot)-ээ жагсаалтаас сонгоно.
2. Жагсаалтаас гол элементээс их болон бага элементүүдийн хоёр жагсаалт үүсгэнэ.
3. Үүссэн жагсаалт бүр рекурсээр дахин их, бага гэж задарна.
4. Задарсан жагсаалтууд дараах дарааллаар нэгтгэгдэнэ: Бага элементтэй жагсаалт, гол элемент, их элементтэй жагсаалт

Си дээр:

void quicksort(int a[], int first, int last)
{
    //Гол элементээ эхний элементээр авлаа
    int pivot = first;
    int i = first;
    int j = last;
    int temp;
    if (i > j)
        return;
    for(;;)
    {
        while(a[++i] <= a[pivot] && i < last);
        while(a[j] > a[pivot]) j--;
      
        if(i > j)
            break;
       //Гол элементээс бага мөртлөө их талд нь

      //Гол элементээс их мөртлөө бага талд нь байгаа

      //Хоёр элементүүдийн байрыг сольж байна
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //Гол элементээ завсарт нь хавчуулж байна
    temp = a[pivot];
    a[pivot] = a[j];
    a[j] = temp;
    //Их, бага хоёр жагсаалтаа тус тусад нь эрэмбэлнэ
    quicksort(a, first, j - 1);
    quicksort(a, j + 1, last);
}

Лисп дээр:

(defun q-sort (list &optional (f #'<))
 ; Жагсаалт ганц элементтэй бол жагсаалтыг буцаана
  (if (null (cdr list)) list

 ; q-sort-оор эрэмбэлэгдсэн гол элементээс их биш 

; элементүүдтэй жагсаалтыг
    (append (q-sort (remove-if-not #'(lambda (x) (funcall f x (car list))) (cdr list)) f)
; Гол элемент болон
            (list (car list))

; q-sort-оор эрэмбэлэгдсэн гол элементээс их 

; элементүүдтэй жагсаалттай нэгтгэнэ
            (q-sort (remove-if #'(lambda (x) (funcall f x (car list))) (cdr list)) f))))


Жич: Гол элементийг жагсаалтын эхний эхний элементээр сонгож авсан болно.

Гол элемент сонгох дээр Принстоний Их Сургуулийн профессор доктор Роберт Седжвикийн санал болгож байгаагаар жагсаалтын голын индекс дэх  элементийг сонгох юм уу аль эсвэл эхний элемент, голын элемент, сүүлийн элемент гурвын медианаар сонгох нь үр дүнтэй.

Зөвлөмж

Голын индексийг авахдаа (first + last) / 2 гэж авч болох ч first болон last нь хоёулаа их тоо байвал нийлбэр нь орон хэтрэх аюултай тул үүнээс зайлахын тулд first + (last - first) / 2 гэж авах нь зүйтэй.  

Мөнхүү Роберт Седжвикийн санал болгосноор алгоритмыг сайжруулах тал дээр жагсаалтыг хуваасаар хангалттай бага элементтэй болоход Оруулах Эрэмбэлэлтээр эрэмбэлбэл илүү үр дүнтэй гэж үзжээ. Учир нь хэдхэн элементийг эрэмбэлэхийн тулд функц дуудах нь зардалтай юм.

Си хэлний санд qsort() Хурдан эрэмбэлэлтийн функц байдаг. Дэлгэрэнгүйг эндээс үзнэ үү!

PlayStation 1-ийг Linux дээр

Tekken гэвэл танд юу санаанд орж байна? Мэдээж PlayStaion биз дээ. За, тэгээд Tekken тоглоомоо санаад, дээр нь өөрийн цахим тооцоолуур тогломоор санагдаад нэтээс хайж эхлэв. Мэдээж Цонх анх дээр бол хамгийн шилдэг эмулетор програм бол pSX билээ. Тэгээд л Убунту дээрээ pSX суулгах гээд үзлээ. Дарс (WINE)-аар үзсэн болдоггүй ээ. За, тэгвэл Лайнукс дээрх хувилбарыг нь хайсан аз болж байна шүү. Тэгээд л татаад суулгасан чинь Убунту ахын хурдан хөгжлөөс аль хэдийнээ хоцрогдсон байдаг байгаа. Баахан амбсын файлууд нэхээд, нөгөөдөхүүдийг нь нэтээр нэг самнаад. Арай гэж олоод суулгахаар одоо энэ хэрэгтэй, тэр хэрэгтэй гээд л. Тэгж тэгж нэг юм цонх гаргадаг болгосон шүү. Тэгсэн bio файлаа уншдаггүй ээ. Хэдэн цаг нухсан бүхэн ингэж нэг талаар боллоо.



Тэгсэн бас нэг эмулетор програм оллоо. Энэ бол PCSx. Ёстой гоё сайхан ажиллуулсан чинь тохиргоо хийх бүх сонголт нь идэвхгүй байна. За яахав гээд тоглох гэсэн чинь товчлуурууд нь төө хэрийн зайтай тохируулчихсан, өнөө дайснаа цохих гэж товчлуураа хайж олоод дарах гэсээр байтал амины тал дуусаа, тэгээд нэг хөл гарны комбинд ороод л тоолуулчих нь. Энэ арай бишээ гээд л дахиад л хайж үзлээ, нэтээр олигтой юм олдсонгүй.

Тэгвэл тооцоолуур дээр суусан янз бүрийн ямар тохиргооны файлууд байна энэ тэр гэж хайж явж байгаад PCSx-ийн bio байхгүй болохгүй анзаарлаа. Даруй л pSX-ын bio-г хуулж аваад тийшээ хийчихсэн чинь болчихдог байна шүү. Тэгээд жаал нүдэлцээд л сууж байна даа хө.

1. PCSx-ээ Ubuntu Software Center-ээс суулгачих нь.
2. Нөгөө алдарт bio хавтасны файл нь: http://www.mediafire.com/?ldypt4ffge35hab
3. Татаж авсан файлаа  ~/.pcsx/bios дотор хуулаад гүйцээ

Амрах цаг боллоо!

Та компьютер дээр хир удаан суудаг вэ? Би лав нэг суугаад л ертөнцөөс тасарсан л юм шиг болчихдог. Тэгтэл сүүлийн үед нуруу өвддөг боллоо. Манай найз нар ч гэсэн нуруу нь өвддөг болжээ. Тэгээд яах вэ? өөртөө нэг зориулж нэг бүрхүүл код Убунту дээр бичлээ.

30 минут болоод нэг анхааруулга өгөөд 5 минут амарч байхаар тохирууллаа.
Код нь:

notify-send Ажилдаа\!
while true;do
    sleep 1800
    notify-send Амраад\!
    t=30
    while [ $t -gt 0 ];do
        notify-send $t
        t=`expr $t - 1`
    done
    notify-send Ажилдаа\!  
done


Энийгээ sh өргөтгөлтэй хадгалаад ажиллуулах эрх олгоод л болоо. startup applications-даа хийчихвэл машин чинь асах болгон автоматаар бүрхүүл кодоо ажиллуулчихна. Тэгээд өөртөө зориулаад 5 минут амар!

Интегралын хэсэгчлэх томъёоны гаргалгаа

Анхны тоо олох эртний Грекийн арга

За хальт юм хум харж явсан чинь нэг ийм арга байна хө. Сонирхолтой болов уу? гэж бодож байна.

За би 20 хүртэлх тоонуудаас анхны тоонуудыг ялгая.

1. 1-оос 20 хүртэлх тоогоо жагсаана.
         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2. Анхны тоо гэж хоёрхон хуваагчтай натурал тоог хэлдэг. Уг тодорхойлолт ёсоор 1 маань 1 гэсэн ганцхан хуваагчтай тул анхны тоо биш юм. Тэгэхээр 1 ийг дарлаа.
         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3. 2-ын тооноос эхлэн хоёроор тоолж тоонуудыг дарна. Тэгэхээр 4, 6, 8, 10, 12, 14, 16, 18, 20 тоонууд дарагдана.
         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4. 3-аас эхлэн гурваар тоолж тоонуудыг дарна. Тэгэхээр 6, 9, 12, 15, 18 тоонууды дарагдана.
         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5. 5-аас (4 дарагдчихсан) эхлэн таваар тоолж тоонуудыг дарна. 10, 15, 20. Аль хэдийнээ дарагдчихаж.
6. 7-оос эхлэн долоогоор тоолж тоонуудыг дарна. 14. Бас дарагдаас.
7. 11-ээс эхлэн 11-ээр. За цаашаа дарагдах тоонууд гарахгүй юм байна.
8. Одоо үлдсэн тоонууд биччихээр чинь
           2, 3, 5, 7, 11, 13, 17, 19            За энэ дээ. 1-ээс 20 хүртэлх тооны хоорондох бүх анхны тоонууд.

Цаашаа 100, 1000 энэ тэрийг ингээд бодож болно. Гэхдээ энэ арга аль ампсын үеийн арга л даа. Хэн л одоо хэдэн мянга хүртэл тоолоод суух вэ дээ.

Code::Blocks IDE-ийн xterm терминалыг gnome-terminal-аар солих

Code::Blocks гэж юу вэ?

Code::Blocks бол үнэгүй, нээлттэй эхтэй, олон үйлдлийн систем дээр ажилладаг програм хөгжүүлэгч юм. Үндсэн хөгжүүлэх програмчлалын хэл нь С\С++. Мөн DirectX, Fortran, GTK++, MATLAB, OpenGL, Qt, SDL гэх мэт олон програмыг үүсгэж чаддаг.

Олон төрлийн хөрвүүлэгчдийг дэмждэг. Тухайлбал MinGW/GCC, Digital Mars, Microsoft Visual C++, Borland C++, Watcom, LCC, Intel C++ compiler.

Dev C++, Microsoft Visual C++-ийн төслүүдийг (project) ажиллуулдаг, гэх мэт.

Си дээр програм бичихэд тун зүгээр. Eclipse дээр Си аймаар удаан ажилладаг. Терминалаас хөрвүүлнэ энэ тэр гэхээр залхуу хүрээд байдаг. Code::Blocks л хамгийн дажгүй санагдсан.

Тэгсэн нэг гэм нь терминал нь икстерм (xterm) дээр юм аа. Тэгээд жином-терминал болгох хүсэл их байлаа. Тэгсэн их амархан сольчихдог юм байна.

Settings -> Environment гэж ороод General settings цэс дотор Terminal to launch console programs: гэсэн хэсэг дээр gnome-terminal -x гэж болгоод л терминал чинь жином-терминал болчихсон байна.

Флашгот(Flashgot) дээр хүссэн Интернет Татагчаа оруулах

Миний хамгийн дуртай програмуудын нэг нь Флашгот. Жилийн өмнөхөн л Виндөвс ахаас Убунту руу шилжиж билээ. Тэгсэн нөгөө алдарт Интернет Дөвшлөүд Менежер (Internet Download Manager - АиДиЭм) гуай Лайнукс дээр байдаггүй. Сайтаас видео энэ тэр татах болсон чинь болдоггүй. Тэгээд хайж байгаад Мозилла(Mozilla) ахын Файрфокс (Firefox) дээр Флашгот байж нэг нар гардаг байна ш дээ. Флашгот бол сайт дахь медиаг барьж аваад татагчтай холбож өгдөг файрфоксын нэмэгдэл юм.

Тэгсэн бас болоогүй ээ. Нөгөө татагчид нь арай удаан байлаа. АиДиЭм шиг л хурдан татдаг татагч хэрэгтэй байлаа. Тэгсэн Аксел (Axel) гэдэг нэг сайхан залуу гараад ирлээ. Акселыг суулгахаар Флашгот дээр автоматаар нэмэгдчихдэг юм байна. Даанч нэг гэм нь терминал дээр ажилладаг татагч нар маань икстерм (xterm) терминал дээр ажиллаад байх юм. Икстерм-д би дургүй ээ.

Саяхан надад акселийн икстермийг жином-терминал (gnome-terminal)-аар солих хүсэл бий болоод Гүүглэ ахаасаа шалгаалаа. Тэгсэн Монголын Лайнукс бүлгэмийн вики дээр байна. Тэгээд л хүсэж байсан мэдлэгээ олж авлаа. Баярлалаа Лимнукс-даа.

За өөрийнхөөрөө нэг товч тайлбарлачихъя.

1. Танд Флашгот, Интернет татагч чинь байгаа
2. Интернет татагчаа ашиглах бүрхүүл (shell) кодоо бичнэ.
   
Акселын хувьд нэг иймэрхүү.

#!/bin/bash

cd /home/CHANGE_IT_TO_YOUR_USERNAME/Downloads
gnome-terminal --command "axel -an 10 $1" 

Татсан файл чинь ~/Downloads дотор хадгалагдана. Дураараа өөрчилж болно.
--command гэдгийн ардаас Татагчийнхаа командыг бичиж өгнө. Тэгээд л sh өргөтгөлтэй хадгална. Жишээ нь дээр бүрхүүл кодыг axel1.sh гэж хадгалъя.


3. Флашгот-доо нэмье. Файрфоксын tools->Flashgot->More Options гэж ороод
General цэс дээр Add гэдгийг дараад axel1 гээд нэр өгчихье. Тэгээд Executable path дээр нь өнөөх бүрхүүл код axel1.sh ээ заагаад өгнө. Тэгээд OK товч дараад дуусаа.

4. Файл татахдаа axel1 гэсэн татагчаа сонгоод л татна.

Одоо хүссэн татагчаа флашгот руу оруулж чаддаг боллоо. Баяр хүргэе!

Оруулах эрэмбэлэлт (Insertion Sort) [Lisp VS C]

Оруулах эрэмбэлэлт бол маш энгийн эрэмбэлэлт. Бид ихэвчлэн амьдралдаа энэ эрэмбэлэлтийг хэрэглэж байдаг. Үндсэн санаа нь бол жагсаалтаас нэг элементийг нь аваад эрэмбэлэгдсэн жагсаалт руу зөв байрлуулахад оршдог. Уг эрэмбэлэлтийн давуу талууд гэвэл:

1. Хялбархан, ойлгомжтой
2. Жижиг жагсаалтыг хурдан эрэмбэлдэг
3. Нэмэлт санах ой шаардлагагүй
4. Бараг эрэмбэтэй жагсаалтад илүү үр дүнтэй
5. Жагсаалтын хэмжээнээс үл хамааран эрэмбэлж эхэлдэг гэх мэт

Үндсэн санааг нь дээр дурдсан. Псевдо код нь:

 for i ←1 to i <= length(A)-1
     key ← A[ i ]
     > A[ i ] is added in the sorted sequence A[0, .. i-1]
     j ← i - 1
     while j >= 0 and A [ j ] > key
         A[ j +1 ] ← A[ j ]
         j ← j -1
     A [j +1] ← key

 Хугацааны хувьд:

                 Сайн тохиолдолд (Бараг эрэмбэлэгдсэн): Ө(n) 

                 Дундаж тохиолдолд: O(n^2)

           Муу тохиолдолд : О(n^2)

Си хэл дээр:

#include <stdio.h>
//Массиваа хэвлэнэ
void print_array(int a[], int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("%d ", a[i]);
    putchar('\n');
}

void insertion_sort(int a[], int n)
{
    int i, j;
    int key;
    for(i = 1; i < n; i++)
    {
        key = a[i];
        j = i - 1;
        //key-ээс их элементүүдийг урагшлуулж
        while(j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        //Үүссэн хоосон зайд key орно
        a[j + 1] = key;
        //Массивыг хэвлэж байна
        print_array(a, n);
    }
}

int main()
{
    int a[8] = {6, 5, 3, 1, 8, 7, 2, 4};

    print_array(a, 8);
    insertion_sort(a, 8);

    return 0;
} 

Гаралт нь:

6 5 3 1 8 7 2 4 
5 6 3 1 8 7 2 4 
3 5 6 1 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 7 8 2 4 
1 2 3 5 6 7 8 4 
1 2 3 4 5 6 7 8 

Lisp дээр:

Гаралт нь:

Өсөхөөр эрэмбэлэгдэж буй

(6) 
(5 6) 
(3 5 6) 
(1 3 5 6) 
(1 3 5 6 8) 
(1 3 5 6 7 8) 
(1 2 3 5 6 7 8) 
(1 2 3 4 5 6 7 8) 

Буурахаар эрэмбэлэгдэж буй

(6) 
(6 5) 
(6 5 3) 
(6 5 3 1) 
(8 6 5 3 1) 
(8 7 6 5 3 1) 
(8 7 6 5 3 2 1) 
(8 7 6 5 4 3 2 1) 

Лисп дээр өөрийнх нь эрэмбэлэх SORT гэсэн МАКРО байдаг. Энэ эрэмбэлэх МАКРО нь

Оруулах Эрэмбэлэлт дээр үндэслэсэн байдаг. Жишээ програм:

(setq list '(6 5 3 1 8 7 2 4))
(write-line "Lisp-ийн өөрийнх нь эрэмбэлэх функц ашиглаж байна")
(print list)

;Өсөхөөр эрэмбэлээд хэвлэж байна
(print (sort list #'<))

;Буурахаар эрэмбэлээд хэвлэж байна
(print (sort list #'>)) 

Гаралт нь:

Lisp-ийн өөрийнх нь эрэмбэлэх функц ашиглаж байна

(6 5 3 1 8 7 2 4) 
(1 2 3 4 5 6 7 8) 
(8 7 6 5 4 3 2 1)  

Дараагийн эрэмбэлэлт Хурдан Эрэмбэлэлт(Quick Sort) байна.
 

Виндөвс (Windows) дээр Лайнукс (Linux)-ыг мэдэрцгээе!

Юникс(UNIX) програмчлал үзэж байгаатай холбогдуулж бүхэл бүтэн үйлдлийн систем суулгахгүйгээр ердөө Виндөвс дээрээ л Юникс, Лайнукс програмчлалыг хийж болохуйц програмыг танилцуулж байна. Энэ бол Сигвин (Cygwin). Сигвиний уриа бол Виндөвс дээр Лайнуксыг мэдэрцгээе! За тэгээд сонирхоно биз дээ.

www.cygwin.com

 

 

VAIO зөөврийн тооцоолуурын touchpad-ын scroll-ыг ажиллуулах

Хагас жилийн өмнө дөнгөж авсан зөөврийн тооцоолуураа шууд л Убунту 11.10-ыг суулгаж билээ. Бүх зүйл л дажгүй байлаа. Гэхдээ Убунту дээр заавалчгүй нэг алдаа гардаг. Алдаа гардаг гээд би муулсангүй. Харин тэрхүү алдааг засна гэдэг л хамгийн том мэдлэг, ухааныг өгдөгөөрөө хамгийн сайхан нь.

За тэгээд Убунту 11.10 дээр touchpad-ны scroll нь ажилладаггүй юм байна. Гүүглэдээд гүүглэдээд олигтой шийдэл олж чадалгүй тэгээд хаясан юм. Тэгсэн саяхан нет ухаж байгаад ажиллуулах аргыг оллоо. За тэгээд тэрийгээ хуваалцахаар шийдлээ.

Дараах зүйлсийг хийнэ:

1. sudo gedit /etc/default/grub  гэж терминал дээрээ бичнэ
2. GRUB_CMDLINE_LINUX гэсэн дээр мөрийг олоод GRUB_CMDLINE_LINUX="i8042.reset i8042.nomux i8042.nopnp i8042.noloop" болгоно.
3. Дараа нь grub файлаа шинэчлэнэ: sudo update-grub
4. http://www.mediafire.com/?74wbdmph52sugw5 гэсэн хаягаар орж psmouse-alps-dkms_0.10_all.deb-ийг татаж аваад суулгана.
5. Тооцоолуураа дахин эхлүүлнэ.

Ингээд л таны scroll чинь ажилчихсан байна.

Сонгох Эрэмбэлэлт (Selection Sort) - C vs Lisp

Сонгох эрэмбэлэлт. Энэ эрэмбэлэлтийг Си болон Лисп хэл дээр үзье. Сонгох эрэмбэлэлтийн мөн чанар нь бол жагсаалтаас хамгийн бага элементийг сонгож жагсаалтын эхний элементтэй солиход оршдог. Хамгийн бага элементийг олохын тулд жагсаалтыг бүх элементийг шалгадаг болохоор жагсаалтын хэмжээ их үед тохиромжгүй эрэмбэлэлтийн арга юм. Харин жижиг жагсаалтыг (20, 30 элементтэй) бол хурдан эрэмбэлдэг. Бидний өмнө үздэг Хөвөх Эрэмбэлэлт-ээс арай хурдан.

Хугацааны хувьд бол O(n²).

Си дээрх код:

Гаралт нь:

Одоо Лисп дээр үзье. Лисп дээр маш хялбархан бичиж болно.

Одоо гаралтыг нь харъя:

Дараагийн эрэмбэлэлтээр Оруулах Эрэмбэлэлт (Insertion Sort) үзнээ. Явандаа бүх эрэмбэлэлтээ үзсэний дараа ерөнхий харьцуулалт хийх санаа байна. За тэгээд сонирхож байгаа хүмүүс үзэл бодлоо чөлөөтэй хуваалцаарай!

Си дээр ингэж болдог байсан юм байна ш дээ

Си дээр нэг сонин юм харлаа. Тухайлбал функц дээр. Ингэж болдог гэхээр гайхмаар ч юм шиг. Функцыг тодорхойлж бичихэд ингэж бичдэгийг анх удаа л харж байна. Хамгийн Си-гийн функцыг ингэж бичнэ гэж заалгуулж байлаа.

datatype function-name (datatype argument-list)
{
      local variable declarations;
      executable statements;
      ......................................
      return (expression);
}

За нэг ийм л юм үздэг билээ. Жишээ нь хоёр тооны ихийг олдог функц гэвэл:

int max (int a, int b)
{
      return (a > b) ? a : b;
}

Тэгсэн бас ингэж бичиж болдог юм байна шүү!

datatype function-name (argument-list)
argument declaration;
{
      local variable declarations;
      executable statements;
      ......................................
      return (expression);

}

Энэ форматаар бол дээрх мах функцыг бол ингэж бичиж болох нь:

int max (a, b)
     int a, b;
{
      return (a > b) ? a : b;
}

Гэхдээ анх сурсан минь арай эвтэйхэн юмаа. Хэ хэ.

Хөвөх эрэмбэлэлт (Bubble Sort) Х Лисп хэл Х Си хэл

За Лисп хэлийг оролдож үзэж байна. Тэгээд энэ хөвөх эрэмбэлэлтийг Лисп дээр хийж үзэхээр шийдлээ. Хөвөх эрэмбэлэлт бол хамгийн энгийн эрэмбэлэлт. Үндсэн санаа нь бол хөөс хөвөх зарчимтай адил. Усан дотор хөнгөхөнүүд нь дээш хөөрч, хүнд нь доошилдогтой адил жагсаалтын бага элементүүд аажмаар дээшилдэг. Үндсэн хийж байгаа үйлдэл нь зэрэгцээ элементүүдийг шалгаад байрыг нь солих замаар явна.

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

 

Псевдо код нь:

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

Нэг иймэрхүү байх нь. За тэгвэл Си хэл дээрх ингэж бичлээ. 

Гаралт нь:

 За тэгвэл одоо Лисп хэл дээр бичиж үзье. 

Гаралт нь:

Лисп хэлний бичиглэлийг харж байгаа байх. Си-гээс хоёр дахин бага бичлэгтэй байгаа 

биз. Дараа нь Сонголтын Эрэмбэлэлтийн тухай оруулнаа. 

Gedit дээр Lisp хэлний онцгойлолт нэмэх

За Lisp хэлний онцгойлолт (highlight) ийг http://www.mediafire.com/?3g8c4r53csj0ltx хаягаас татаж авна. Тэгээд татаж авсан шахсан файлаа задлаад install.sh гэсэн шэлл файлыг терминалаар ажиллуулна. Тэгээд gedit-ээ дахин ачааллуулахад autolisp гэсэн онцгойлолт нэмэгдсэн байна.

Gedit-ээ жаахан тоноглочихъё

Убунту хэрэглэгчид gedit програмыг андахгүй биз дээ. Тэгвэл Gedit дээрээ жаахан юм нэмье.

1. Ubuntu Software Center-ээс gedit-plugins гэдгийг суулгана.
2. Дараа нь Gedit-ийнхээ Edit цэсний Preferences-рүү орж Plugins цэс дээр дарж Embedded Terminal гэснийг нь идэвхжүүлнэ.
3. Хаалтуудыг автоматаар хаадаг байхыг хүсвэл Bracket Completion-ийг идэвхжүүлнэ.
4. Тэгээд View цэсний Bottom Panel-ийг дарахаар Gedit дээр терминал маань гараад ирнэ.
5. Edit->Preferences->Color гэсэн цэснээс Gedit-ээ гоё өнгөтэй болгож болно.

Нууцлаг хавтас хэрэг 7: 13-н гавал (Mystery Case Files 7: 13 Skulls)тоглоомны алдаа

Энэ тоглоомыг нийтдээ 9 цаг тоглож дуусгалаа. Их гоё болсон тоглоом байна. Уул нь уг тоглоомын тоглох хугацааг 7-оос 8 цаг гэснийг үзвэл би тоглож байхдаа нилээд будилсан нь харагдаж байх шиг байна. Аль эсвэл энэ тоглоомны алдаанаас болсон юм болов уу?

Өмнөх цуврал болох  Ойн төгөлийн гүнд (Dive Grove) хэмээх цуврал дээр манай Том Загас (Big Fish)-ынхан бодит хүмүүсийн дүрст бичлэг оруулсан, бас хэргийн газрууд дээр өөрөө явж очдог болсноороо давуу болсон юм. Та бүхэн санаж байгаа байх. Үүнээс өмнөх цувралуудад хэргийн газарт очихдоо газрын зураг дээрээс л сонгоод л оччихдог байсан шүү дээ. Мөн янз бүрийн оньс, бодлогуудаар дүүрэн болж чадсан билээ. Хамгийн гол нь нуугдсан зүйлсүүдийг олж түүнээсээ хэргийн оньсыг тайлан багаж, хэрэгслийг олж авдагаараа ялгаатай болсон билээ.

Манай сүүлд гарсан 13-н гавал бол Ойн төгөлын гүнд цувралын бүх шинжийг агуулсан бөгөөд үүн дээр сэжигтнүүдтэй харилцан ярьдаг болсноороо онцлог болсон юм. Сэжигтэн бүр өөр өөрсдийн зан, сэтгэлийн хөдлөлтэй бөгөөд тэдгээрээс мөрдөгч маань нэмэлт зүйлсүүдийг лавлаж асуух ба сэжигтэн бүр янз бүрийн зан аашаар хариулдаг. Энэ нь яг жинхэнэ мөрдөлт явуулж байгаа юм шиг сэтгэгдэл төрүүлж байсан юм. Гэвч энэ цувралд нуугдсан эд зүйлсийг олохоос илүүтэй оньс, бодлогуудыг бодох, хэргийн сэжүүрийг хайх гэх мэт зүйлс нь илүүтэй байсан юм. Эндээс би юу гэж бодсон вэ? гэвэл энэ хувилбар бол нуугдсан эд зүйлсийг олдог тоглоом биш юм байна гэсэн бодол төрсөн юм. Үүнээс дараачийн цуврал ямар байх вэ? гэдэг улам сонирхол татаж байна.

Уг тоглоомыг тоглож явахдаа нэг зүйлийг ер шийдэж чадахгүй гацсан юм.  Даалгавар маань "оньслогдсон хаалгыг онгойлгох аргыг ол" (find way to open trap door) гэж байсан юм. Хэдэн цаг мангуутан дэмий тэнээд тэсгэл алдан Гүүглэ (Google) ахаасаа асуулаа. Гүүглэ ах над хэдэн цахим хуудсыг зааж өгсөн юм. Тэдгээр цахим хуудсуудаас энэ асуудлыг яаж шийдэх вэ? хэмээн асууж гарав. Тэдгээр цахим хуудсуудаас миний адил тоглогчид нэг бус удаа асуусан байсныг мэдэж авлаа. Тэгэхээр зөвхөн над тохиолдсон гацалт биш болох нь тодорхой болов. Тэгээд цааш нь лавлаад байсан манай Том Загасын тоглоом хөгжүүлэгчид маань нэг өчүүхэн зүйл дээр алдаа хийсэн бололтой.

Уг хаалгыг ойнголгохын тулд түүний дэргэд буй жижиг шүүгээнд дутуу байгаа хундагануудыг олж тавих ёстой юм. Гэвч тоглоом маань намайг хаалга онгойлгох арга ол гэснээс биш хундагануудыг тавь гэсэн даалгавар өгөөгүй учир би хундагануудыг авч чадахгүй байлаа. Ингээд тоглоом маань цаашаа явах боломжгүй болов. Энийг засах арга байгааг цааш нь судалснаар мэдэв. Тэр нь юу вэ? гэвэл

C:\Documents and Settings\<user name>\Application Data\Big Fish Games\Mystery Case Files 13th Skull CE\Master Detective.profile

Гэсэн файлд манай тоглоомны явц маань бичигддэг юм байна. Уг файлаас тийм даалгавар биелэгдсэн эсэх, тийм хэрэгсэл байгаа эсэх гэсэн бөөн параметрүүд байх юм. Гол зорилго маань тэрхүү оньслогдсон хаалгыг онгойлгох аргыг ол гэсэн даалгаварыг биелэгдсэн болгож засах ёстой юм. Хэрэв тэгж засвал бидний дараачийн даалгавар нь хундагануудыг олох байх бөгөөд хундагануудыг олж шүүгээнд тавьснаар манай хаалга онгойх ёстой.

Хаана засвар хийх ёстой вэ? гэвэл уг profife файлаа notepad-аар нээнэ. Аан тийм нээхээсээ өмнө тоглоомоо гаргах хэрэгтэй. Тэгээд уг файлаасаа

     <stage>

                <name>OpenTrapDoor</name>

                <complete>false</complete>

                </stage>

Гэсэн мөрийг хайж олоод

    <stage>

                <name>OpenTrapDoor</name>

                <complete>true</complete>

                <completetriggered>true</completetriggered>

               </stage>

Болгож өөрчилж хадгална. Тэгээд тоглоомоо шинээр эхлүүлэхэд та уг даалгаварыг биелүүлчихсэн, танд дараачийн даалгаварыг өгөх болно. Энэ бол манай Том Загасын ах нарын хийсэн бяцхан сэтгэлгээний алдаа байлаа.

За энүүгээр ч цаашаа нээх асуудалгүй юм. За тэгээд хамаагүй тэр файлаа хамаагүй оролдвол та тоглоомоо хэзээ ч дуусгахгүй нөхцөл байдлыг ч бий болгох магадлалтай тул битгий оролдоорой гэж зөвлөе. Яагаад гэвэл манай даалгаварууд маань цуварч гардаг бөгөөд даалгавар бүрт тодорхой эд зүйлс нь идэвхжиж, өөр даалгаварт идэвхжихээ больдог. Тиймээс хийж чадахгүй байгаа даалгавараа ийм маягаар хийсэн болгочихвол уг даалгавараас авах эд зүйлс чинь танд байхгүй байх болох тул та дараачийн даалгавараа хийж чадахгүй болно.

Аан тийм бас нэг алдаа ч гэх үү? Аль эсвэл би учрыг нь олж чадахгүй байсан уу? бүү мэд ер шийдэж чадахгүй нэг асуудал гарсан юм. Уг даалгавар бол хаалганы цаанаас ярьж байгаа хүний яриаг сонсох юм. Энгийнээр ярьж байгаа нь сонсогдохгүй учир шилэн хаягыг хаалганд тулгаж сонсох ёстой юм байна л даа. Харамсалтай нь тэрхүү шилэн аягыг олдоггүй. Дахиан Гүүглэ ахаас асуусан бөгөөд над хаана байгааг нь зааж өглөө. Харамсалтай нь тэр газарт би өнөөх шилэн аягаа олсонгүй. Хэдэн цаг бас мангуутаж байгаад өнөөх файлаа засаад үзвэл яадаг юм бэ? гэсэн бодол төрлөө. Өмнөх шиг уг даалгаварыг хийсэн болгож өөрчилж болохгүй юм. Яагаад гэвэл уг утасны ярианаас компьютерт нэвтрэх нууц үг хаана байгааг мэдэх ёстой бөгөөд энэ даалгаварыг биелүүлэхгүй бол нууц үг байгаа газар идэвхжихгүй юм. Тиймээс компьютерийн нууц үгээ авч чадахгүй болно. Гэвч надад өнөөх шилэн аяга байдаггүй. Тиймээс өнөөх профайлаа ухлаа. Тэгээд тэндээсээ уг даалгаварыг биелүүлэхэд шилэн аяга байх эсэх дээр нь үгүй (false) гэсэн утга байхыг харлаа. Энэ параметрийг тийм (true) болгож өөрчлөөд тоглоомруугаа орсон чинь шилэн аяга гараад ирж байна шүү. Үүнээс өөр алдаа гараагүй бөгөөд цааш нь үргэлжлүүлэн тоглосоор  тоглоомоо дуусгалаа.

Миний Си хэл дээр бичсэн анхны тоглоом

Би эртнээс нэг тоглоом хийж үзэх юмсан гэж бодож явсан. Тэгээд яаж хийхээ сайн мэдэхгүй л байлаа. КтМС-д Компьютерийн График гэдэг хичээл байдаг. Тэр хичээл дээр хамгийн анх тоглоом хийж үзсэн. Delphi 7 дээр DelphiX (DelphiX гэдэг нь Delphi-г DirectX-тэй холбосон хэрэгсэл бий) гэдэг хэрэгслээр тоглоом хөгжүүлсэн. Анх компьютерийн тоглоом хийнэ гэхэд санаанд багтахгүй байсан ч хийнэ гэвэл хийдэг л юм билээ. Delphi гэдэг хэлийг ер мэдэхгүй байж шууд Delphi дээр тоглоом хийнэ гэдэг хэцүү зүйл байсан. Багш, би та нарт Delphi гэдэг хэлийг заах цаг байхгүй. Үзэх хичээлээ л буюу яаж тоглоом бичих вэ? гэдгийг л заана гэж хэлж байсан. Кодоо бичээд л ажиллуулах гэхээр баахан алдаа өгөөд л, юун дээр алдаад байгаагаа олохгүй, ямар ямар функц байдгийг ч сайн ойлгохгүй. Хэцүү зүйл зөндөө байсан шүү. Хичээлийн эцэст нэг тоглоом хийсэндээ их баяртай байдаг. Мөн тоглоом яаж хийх талаар жаахан төсөөлөл бий болсон.
Тэгээд би саяхан Си хэл дээр тоглоом бичиж үзвэл яасан юм бэ? гэж бодлоо. Си++ дээр л тоглоом бичдэг гэж сонсож байсан. Тэгээд нетээс Си дээр тоглоом бичих гэж хайхаар дандаа Си++ дээр тоглоом бичих тухай байх юм. Тэгээд би шууд л Си дээр мэддэг функцуудээ ашиглаад нэг тоглоом бичихээр шийдсэн юм. Гэхдээ тийм сүртэй тоглоом биш. Бүүр амархан, хамгийн энгийн. Тэгээд МОГОЙ гэдэг тоглоом бичихээр шийдлээ. Хулгана идэхээрээ уртасдаг. Хүрээ болон өөрийгөө мөргөхөөр тоглоом дуусдаг. Тэгээд би өөрийн бичсэн могойг сонирхуулъя гэж бодлоо. Нилээд болхи л болсон. Бас жижиг жижиг алдаанууд бий. Залхуураад тэрийг засахыг оролдоогүй л байна.

ТАТАХ

Код маань (Нилээд замбараагүй ээ, хүлцэл өчье):


/** @author Tsetsentsengel Munkhbayar
  * Snake game
  * written in Turbo C++ by C programming language
  * My first game which is written by C
  * 30 Sep 2010 */
 
#include "stdio.h"
#include "conio.h"
#include "dos.h"
#include "time.h"
#include "stdlib.h"
#include "math.h"

#define bool int

const int VK_ESC = 27;
const int VK_UP = 72;
const int VK_DOWN = 80;
const int VK_LEFT = 75;
const int VK_RIGHT = 77;
const int TIME = 200;
const char LT = 201; //Corner of left top
const char RT = 187; //Corner of right top
const char LB = 200;
const char RB = 188; // Corner of right bottom
const char H = 186; 
const char V = 205;
const char ms = 224;
const char VK_SP = 32;
const int true = 1;
const int false = 0;
static char key = 'a';
static int point = 0;
static int high_point = 0;
struct Point{
    int x;
    int y;
};

struct Snake{
    int direction;
    struct Point body[400];
    int length;
    int eaten_mouse;
}snake;

struct Mouse{
    struct Point position;
    struct Point old_position[500];
}mouse;

void initialize_snake();
void draw_snake();
void draw_mouse();
void draw_screen();
void move_up();
void move_down();
void move_left();
void move_right();
void move_snake();
bool collision_wall();
bool collision_mouse();
void collision_snake();
void controller();
void start_game();
void game_over();
void initialize_mouse();
void prolong_snake();
void title();
void border();
void draw_point();

int main(){
    start_game();
    while(1){
        clrscr();
        draw_screen();
        controller();
        move_snake();
        draw_snake();
        draw_mouse();
        if(key == VK_ESC){
            game_over();
            break;
        }
        delay(TIME);
    }
    return 0;
}
void initialize_snake(){
    int i;
    snake.direction = VK_RIGHT;
    snake.length = 5;
    snake.eaten_mouse = 0;
    for(i = 0; i < snake.length; i++){
        snake.body[i].x = snake.length - i + 10;
        snake.body[i].y = 10;
    }
}

void initialize_mouse(){
    bool Ok = true;
    int i;
    randomize();
    do{
        mouse.position.x = rand() % 19 + 6;
        mouse.position.y = rand() % 19 + 6;
        for(i = 0; i < snake.length; i++)
            if(mouse.position.x == snake.body[i].x &&
                mouse.position.y == snake.body[i].y){
           
                Ok = false;
                break;
            }
    }while(Ok == false);
}

void draw_snake(){
    int i;
    textcolor(BROWN);
    gotoxy(snake.body[0].x, snake.body[0].y);
    cprintf("X");
    for(i = 1; i < snake.length; i++){
        gotoxy(snake.body[i].x, snake.body[i].y);
        cprintf("O");
    }
}

void draw_mouse(){
    gotoxy(mouse.position.x, mouse.position.y);
    textcolor(DARKGRAY);
    cprintf("%c", ms);
}
void title(){
    gotoxy(9, 2);
    textcolor(CYAN);
    cprintf(".:: SNAKE ::.");
}
void draw_point(){
    textcolor(LIGHTGREEN);
    gotoxy(30, 1);
    cprintf("HIGHEST POINT: %d", high_point);
    gotoxy(30, 15);
    cprintf("Your points: %d", point);
    textcolor(LIGHTBLUE);
    gotoxy(30, 17);
    cprintf("ESC -> pause.");
    gotoxy(30, 18);
    cprintf("ENTER -> continue.");
}
void border(){
    int i, x = 5, y = 5;
    textcolor(WHITE);
    for(i = 1; i < 20; i++){
        gotoxy(x + i, y);
        cprintf("%c", V);
        gotoxy(x + i, y + 20);
        cprintf("%c", V);
        gotoxy(x, y + i);
        cprintf("%c", H);
        gotoxy(x + 20, y + i);
        cprintf("%c", H);
    }
    gotoxy(5, 5);
    cprintf("%c", LT);
    gotoxy(25, 5);
    cprintf("%c", RT);
    gotoxy(5, 25);
    cprintf("%c", LB);
    gotoxy(25, 25);
    cprintf("%c", RB);
}
void draw_screen(){
    title();
    border();
    draw_point();
}

void move_up(){
    int i;
    for(i = snake.length - 1; i > 0; i--){
        snake.body[i].x = snake.body[i-1].x;
        snake.body[i].y = snake.body[i-1].y;
    }
    snake.body[i].y--;
}

void move_down(){
    int i;
    for(i = snake.length - 1; i > 0; i--){
        snake.body[i].x = snake.body[i-1].x;
        snake.body[i].y = snake.body[i-1].y;
    }
    snake.body[i].y++;
}

void move_left(){
    int i;
    for(i = snake.length - 1; i > 0; i--){
        snake.body[i].x = snake.body[i-1].x;
        snake.body[i].y = snake.body[i-1].y;
    }
    snake.body[i].x--;
}

void move_right(){
    int i;
    for(i = snake.length - 1; i > 0; i--){
        snake.body[i].x = snake.body[i-1].x;
        snake.body[i].y = snake.body[i-1].y;
    }
    snake.body[i].x++;
}

void move_snake(){
    switch(snake.direction){
        case 72: move_up(); break;
        case 80: move_down(); break;
        case 75: move_left(); break;
        case 77: move_right(); break;
    }
    collision_snake();
    if(snake.eaten_mouse > 0)
        prolong_snake();
}

bool collision_wall(){
    if(snake.body[0].x < 6 || snake.body[0].x > 24 ||
        snake.body[0].y < 6 || snake.body[0].y > 24)
            return true;
    return false;
}

bool collision_mouse(){
    if(snake.body[0].x == mouse.position.x &&
            snake.body[0].y == mouse.position.y){
        point += 5;
        return true;
    }
    return false;
}

bool collision_body(){
    int i;
    for(i = 1; i < snake.length; i++)
        if(snake.body[0].x == snake.body[i].x &&
            snake.body[0].y == snake.body[i].y)
            return true;
    return false;
}

void collision_snake(){
    if(collision_wall() || collision_body()){
            delay(2000);
            game_over();
    }
    if(collision_mouse()){
        mouse.old_position[snake.eaten_mouse].x = mouse.position.x;
        mouse.old_position[snake.eaten_mouse].y = mouse.position.y;
        snake.eaten_mouse++;
        initialize_mouse();
    }
}

void prolong_snake(){
    int i;
    if(abs(mouse.old_position[0].x - snake.body[snake.length - 1].x) == 1 && mouse.old_position[0].y == snake.body[snake.length - 1].y ||
       abs(mouse.old_position[0].y - snake.body[snake.length - 1].y) == 1 && mouse.old_position[0].x == snake.body[snake.length - 1].x){
        snake.length++; 
        snake.body[snake.length - 1].x = mouse.old_position[0].x;
        snake.body[snake.length - 1].y = mouse.old_position[0].y;
        for(i = 0; i < snake.eaten_mouse - 1; i++)
            mouse.old_position[i] = mouse.old_position[i + 1];
        snake.eaten_mouse--;
    }
   
}

void controller(){

    if(kbhit()){
        key = getch();
        key = getch();
            if(key == VK_UP && snake.direction != VK_DOWN)
                snake.direction = VK_UP;
            else
                if(key == VK_DOWN && snake.direction != VK_UP)
                    snake.direction = VK_DOWN;
                else
                    if(key == VK_LEFT && snake.direction != VK_RIGHT)
                        snake.direction = VK_LEFT;
                    else
                        if(key == VK_RIGHT && snake.direction != VK_LEFT)
                            snake.direction = VK_RIGHT;
    }
}
void start_game(){
    FILE *fp;
    initialize_snake();
    initialize_mouse();
    _setcursortype(_NOCURSOR);
   
    fp = fopen("Score.dat", "rt");
    fscanf(fp, "%d", &high_point);
    fclose(fp);
   
    clrscr();
    draw_screen();
    draw_snake();
    draw_mouse();
    gotoxy(8, 15);
    printf("Press Space key");
    gotoxy(10, 16);
    printf("to start!");
    while(getch() != VK_SP){};
}
void game_over(){
    FILE *fp;
    gotoxy(30, 10);
    textcolor(RED);
    cprintf("GAME OVER");
    gotoxy(30, 11);
    cprintf("Press ESC to exit");
    gotoxy(30, 13);
    cprintf("Author: Tsetsentsengel Munkhbayar");
    if(point > high_point){
        fp = fopen("Score.dat", "wt");
        fprintf(fp, "%d", point);
        fclose(fp);
    }
    while(getch() != VK_ESC){};
    exit(0);
}

Тоон бодох математикийн бие даалт 3

https://docs.google.com/fileview?id=0B42oX7FmoFjuMDAyNDYwMDYtYmE3My00ZWU2LTk3OTItOWJhM2Q2ODY1MGM3&hl=en

Компьютерийн зохион байгуулалт, ассемблер хичээлийн лаб 11