Search This Blog

2010-05-30

Binary search. (2тын хайлт)

Нилээдгүй үр дүнтэй хайлтын арга. Алхам бүрт нийт өгөгдлийн тоо 2 дахин багасана (зураг 1). Гэхдээ зөвхөн эрэмбэлэгдсэн өгөгдлүүд дээр ажиллана.
N -г нийт өгөгдлийн тоо гэж үзвэл:
хамгийн муугаар бодоход log2(N) +1 удаа шалгалт хийгдэнэ. Харин шугаман хайлтын хувьд хамгийн муу тохиолдолд N удаа шалгалт хийгдэнэ.
Жишээ: нь 1 сая өгөгдөл дундаас хайлт хийнэ гэж үзье. Энэ нөхцөлд хамгийн муугаар бодоход шугаман хайлт нь шалгах үйлдлийг 1сая удаа хийх боломжтой юм. Харин 2тын хайлт ашиглавал хэзээ ч 20с илүү шалгалт хийгдэхгүй.

Source code :
int binSearch(int a[ ], int low, int high, int key)
{
    if(low < high)
    {
        int mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(key < a[mid])
            return binSearch(a, low, mid - 1, key);
        else return binSearch(a, mid+1, high, key);
    }
    else return -1;
}

                                           (Зураг 1)
 Зургийг эндээс.

Ойлгомжгүй, эсвэл асуух зүйл байвал холбоо бариарай залуусаа. Мөн буруу, эсвэл дутуу тайлбарлсан зүйл байвал залруулж өгнө үү.

2010-05-26

Quick sort (Асуудалтай хурдан эрэмбэлэлт)

Зээ би гэдэг хүн өдрийн сайныг өнжин хүлээж, сарын сайныг саатан хүлээж байгаад нэг өдрийг нь өлзий хишиг нь дэлгэрсэн сайн гэж итгэн QUICK SORT (хурдан эрэмбэлэлт) -оо эхлүүлсэн бөлгөө. Гэтэл лүд юм шиг буруу өдөр л байж таарав бололтой, өнөөх хурдан эрэбэлэлт маань өдгөө хүртэл үр дүнгээ хялайлгасангүй ээ. Заа ингээд буруу зөрүүг нь олохоор унтаж идэхээ умартах нь ч хаашаа юм зүгээр, гэхдээ л бодоод бодоод бодын шийр 4 гээч нь болчих бололтой юмаа.  Ухааны нь олж эс ядаад та бүхнээсээ асууя уу хэмээн сэтгэл шулуудсан учир бичсэн хэдэн мөр зүйлээ доор сийрүүлвэй. Бурууг нь тунгаан, зөрүүг нь арилгаж хайрлаач ээ.

Зээ алдаа нь болбоос 100 өгөдөл дээр ( эрэмбэлэгдээгүй ) зүгээр, 1000 болоод ирэхээрээ ажиллаад байгаа нь мэдэгдэхгүй, ажиллахгүй байгаа нь мэдэгдэхгүй болчих юмаа.

Hoare -н partition хуваах аргыг ашигласан бөлгөө.
За ингээд код нь болбоос

int partition( int a[ ], int low, int high )
{
    int piwot, right, left;
    left = low + 1 ;
    right = high ;
    piwot = a[ low ];
    while(1)
    {
        while( a[ right ] > piwot ) right--;
        while( a[ left ] < piwot && left < high ) left++;
        if ( left < right )
            swap( a, left, right );
        else{
            swap( a, low, right );
            return right;
        }
    }
}

void quickSort( int a[ ], int low, int high)
{
    int part;
    if( low < high )
    {
        part = partition( a, low, high );
        quickSort( a, low, part -1 );
        quickSort( a, part +1, high );
    }
}

2010-05-25

Heap sort (Heap эрэмбэлэлт)

Бүтэц үзэж буй, мөн бүтэц сонирхон судлаж байгаа оюунлаг залуучууддаа зориулан санаа авч болмоор хэдэн зүйл оруулъя.
Heap sort:
Heap sort -н ажиллах хуагцаа: n*log(n).
Энд n эрэмбэлэх өгөгдлийн тоо. 

2010-05-15

log2( x ): 2 Cуурьтай логарифм болон гүйцэт мод (Complete tree)

TURBO C/C++ -н math.h -д log2( ) функц тодорхойлогдоогүй байдаг юм байна.
Саяхан мод ашиглаад heap эрэмбэлэлт (heap sort) хийж байтал модны гүн, болон тухайн гүнд байх хүүгийн (node) тоог олох шаардлага гарлаа.
2 ын мод ашиглаж шийддэг асуудлууд их олон байдаг болохоор модны гүн болох хүүгийн тоог олох хэрэгцээ мөн төдий чинээ элбэ тохиолдоно.
i -р гүнд байх хүүгийн тоо: m = 2i ширхэг байна.
i -р гүн хүртэл хамгийн ихдээ байж болох хүүгийн тоо: n = 2i - 1 (гүйцэт мод).
Нөгөө талаас ямар гүнд яваагаа мэдэх хэрэгцээ гарч болох юм. Ингэхэд нэвтрэлт хийх бүрдээ тоолоод байж болно, эсвэл 2 суурьтай логарифм ашиглаад хялбархан олж болох юм. Энд '2 суурьтай логарифм' бодоох аргыг орууллаа.
Хэрэв ойлгохгүй, эсвэл илүү дэлгэрэнгүй тайлбарлуулахыг хүссэн зүйл байвал тэр тухайгаа бичиж үлдээгээрэй.
Мөн буруу зөрүү тайлбарласан зүйл байвал засч залруулна уу.

Зурхай