Tuesday, December 13, 2016

Միակապ ցուցակի կարգավորումը (Insertion sort)

Վերջերս մի հարցազրույցի ժամանակ խնդիր առաջադրվեց C լեզվով իրականացնել միակապ ցուցակի (singly linked list) կարգավորման ալգորիթմը՝ անպայման ռեկուրսիայի օգտագործմամբ։ Ես ընտրեցի տեղադրումով կարգավորման (insertion sort) մեթոդը։ Ստորև ներկայացնում եմ դա։

Նախ՝ ցուցակի հանգույցի (node) սահմանումը, որտեղ բանալին double տիպի է․
typedef struct _node node;
struct _node {
    double data; /* բանալի */
    node* next;  /* կապ */
};
Հիմա տեղադրումով կարգավորման մասին։ Ալգորիթմի էությունն այն է, որ ամեն մի քայլում հերթական տարրը (իմ դեպքում՝ հանգույցը) տեղադրվում է իր ճիշտ տեղում։ Բնականաբար բուն տեղադրման գործողությունը կարևոր գործողություն է։ Սահմանում եմ insert_into() ֆունկցիան, որը տրված հանգույցը տեղադրում է տրված ցուցակի իր ճիշտ տեղում և վերադարձնում է ձևաձոխված ցուցակը։
node* insert_into( node* n, node* l )
{
    /* եթե ցուցակը դատարկ է, ապա տրված հանգույցը 
       վերադարձնել որպես կարգավորված ցուցակ */
    if( NULL == l ) {
        n->next = NULL;
        return n;
    }

    /* եթե տրված հանգույցի բանալին փոքր է տրված ցուցակի 
       առաջին հանգույցի բանալու արժեքից, ապա տրված 
       հանգույցը կցել ցուցակի սկզբից */
    if( n->data <= l->data ) {
        n->next = l;
        return n;
    }

    /* ռեկուրսիվ կանչով տրված հանգույցը տեղադրել ցոցակի 
       պոչի մեջ, ապա նախնական ցուցակի առաջին հանգույցը 
       կապել ձևափոխված պոչին */
    l->next = insert_into(n, l->next);
    return l;
}
Ցուցակը կարգավորող sort_list() ֆունկցիան պարզապես կանչում է insert_into() ֆունկցիան․
node* sort_list( node* l )
{
    /* ցուցակը դատարկ լինելու դեպքը */
    if( NULL == l )
        return NULL;

    /* ցուցակի առաջին հանգույցը տեղադրել կարգավորված 
       պոչի մեջ՝ ճիշտ տեղում */
    return insert_into(l, sort_list(l->next));
}
Այսքանը։

Friday, December 9, 2016

Թվի երկուական ներկայացման ևս մի մեթոդի մասին

Մի անգամ արդեն ես առիթ եմ ունեցել գրելու ամբողջ թիվը տասական ներկայացումից երկուական ներկայացման ձևափոխելու մասին։ ՀայIT.orgԹվի ձևափոխումը տասականից երկուական տեսքի հոդվածում գրել եմ ձևափոխության ռեկուրսիվ եղանակի մասին, որտեղ օգտագործել եմ ծրագրավորման լեզվում տողերի կոնկատենացիայի հնարավորությունը։

Հիմա ուզում եմ խոսել այն մասին, թե ինչպես կառուցել թվի երկուական ներկայացումը, երբ լեզվում տողերի կցման հնարավորություն չկա, և արդյունքը պետք է գրել սիմվոլների բուֆերի մեջ։ Ընդունված մեթոդն այն է, որ տրված տասական թիվը, քանի դեռ այն զրո չի դարձել, հաջորդաբար բաժանվում է `2`֊ի, և բաժանումից ստացված մնացորդները գրառվում են հակառակ կարգով։ Այստեղ խնդիրն այն է, որ կամ պետք է հենց սկզբից մնացորդները բուֆերի մեջ գրառել հակառակ հաջորդականությամբ՝ նախապես իմանալով երկուական տեսքի զբաղեցրած նիշերի քանակը, կամ մնացորդները գրառել դրանց ստացվելու ուղիղ հաջորդականությամբ և վերջում վերադասավորել հակառակ կարգով։ Թվի երկուական տեսքի զբաղեցրած նիշերի քանակը կարելի է ստանալ լոգարիթմի օգնությամբ․ \(length=\lceil\log_2{n}\rceil\)
// տարբերակ I
void bin_a( int num, char* res )
{
  size_t length = log(num)/log(2);
  while( num ) {
    res[length--] = "01"[num & 0x01];
    num >>= 1;
  }
}

// տարբերակ II
void bin_b( int num, char* res )
{
  char* p = res;
  while( num ) {
    *p++ = "01"[num & 0x01];
    num >>= 1;
  }

  while( p > res ) {
    char t = *(--p);
    *p = *res;
    *res = t;
    ++res;
  }
}
Թե զբաղեցնելիք նիշերի քանակը, և թե մնացորդները հակառակ գրելուց հետո դրանք շրջելը ես համարում եմ ավելորդ աշխատանք։ Ստորև ցուցադրում եմ մի եղանակ, որում թվի տասական տեսքից երկուական տեսքի կառուցումը կատարվում է առանց վերը նշված «ավելորդ» (կամ ոչ ցանկալի) գործողությունների։

Եվ այսպես, int bin( int num, char* res ) ֆունկցիան արգումենտում ստանում է ձևափոխվելիք թիվը և արդյունքը գրառելու տեղը (նիշերի բուֆեր), իսկ վերադարձնում է երկուական ներկայացման նիշերի քանակը։ Սա ինտերֆեյսը։ Իսկ իրականացումը ռեկուրսիվ է․ բազա) եթե num֊ը փոքր է 2֊ից, ապա բուֆերի սկզբում գրել '0' կամ '1' համապատասխան նիշը, քայլ) եթե num֊ը մեծ է կամ հավասար երկուսի, ապա bin() ֆունկցիան ռեկուրսիվ կանչել num / 2 քանորդով ու ստանալ len թիվը, որը բուֆերում այդ քանորդի զբաղեցրած նիշերի քանակն է, ապա բուֆերի len + 1 դիրքում գրել num % 2 մնացորդին համապատասխան '0' կամ '1' նիշը։ Ռեկուրսիայի բազային ճյուղում որպես արդյունք ֆունկցիան պետք է վերադարձնի 1, քայլի ճյուղում՝ len + 1։

Ահա իրականացումը C լեզվով․
int bin( int num, char* res )
{
  if( num < 2 ) {
    *res = "01"[num];
    return 1;
  }

  int len = bin(num >> 1, res);
  *(res + len) = "01"[num & 0x01];
  return 1 + len;
}
Նկարագրված երեք ֆունկցիաների արդյունքները համեմատելու համար օգտագործում եմ test_bin() ֆունկցիան․
bool test_bin( int num )
{
  char res_a[32] = { 0 };
  bin_a(num, res_a);

  char res_b[32] = { 0 };
  bin_b(num, res_b);

  char res[32] = { 0 };
  bin(num, res);

  bool pass = 0 == strcmp(res, res_a);
  pass = pass && (0 == strcmp(res, res_b));
  
  if( !pass )
    printf("| num = %d\tres = %s\tres_a = %s\tres_b = %s\n",
           num, res, res_a, res_b);
  else
    printf("| num = %d\tres= %s\n", num, res);

  return pass;
}