Acm timus ru Stone pile 1005



Download 22.56 Kb.
Sana29.03.2020
Hajmi22.56 Kb.
Acm timus ru Stone pile 1005.

Stone pile 1005.
Ушбу масалани купчилик ечишга уринишган булиши табиий хол. Биз куйида уни 2та ечиш усули билан танишамиз. Уларнинг иккаласи хам барча мумкин булган холатларни текширишга асосланган.
Хуш айтингчи "барча мумкин булган холатлар"  нима узи?
Бу саволга жавоб бериш учун 3 та тошни олайлик ва уларни кандай тартибда тарозига куйиш мумкинлигини текшириб чикайлик:  Тошларни шартли равишда A, B, C деб белгилайлик.
     Чап тарозида                  Унг тарозида                    Фарки

1.     [ ]                                       [ A, B, C ]                     |  (A + B +C) - ( 0 ) |

2.     [ A ]                                   [ B, C ]                          |  (B + C) - ( A )      |
3.     [ B ]                                   [ A, C ]                          |  (A + C) - ( B )      |

4.     [ C ]                                   [ A, B ]                          |  (A + B) - ( C )      |

5.     [ A, B ]                              [ C ]                               |  (C) - ( A + B)       |

6.     [ A, C ]                              [ B ]                               |  (B) - (A+C)          |

7.     [ B, C ]                              [ A ]                               |  (A) - (B+C)          |

8.     [ A, B, C]                          [ ]                                   |  ( 0 ) -  (A+B+C)   |


Шуни фахмлаш кийин эмаски, агар тошлар сони `n`  та булса барча мумкин булган холатлар сони  мос равишда  2^n   га тенг булади ( уйлаб куринг). Барча мумкин булган холатларни кискача ёзилиши учун R(n)  деб белгилай колайлик.
Масала шартида  n<= 20  дейилган, демак барча мумкин булган холатлар сони эса мос равишда   R(n)  <= 2^20 = 1 048 576  булади.  Бу компьютер учун унчалик катта сон эмас, хар холда бемалол 2 секунд вактда хисобласа булади .
Факат битта муаммо коляпти:  Ушбу холатларни кандай генерация киламиз?!
Бу ерда бизга рекурсия жуда хам катта ёрдам беради.

фараз килайлик бизда Left,  Right  -- булар мос равишда чап ва унг тарози палласидаги тошларни огирликлари булсин, хамда  W[1..n] - бу тошларни огирликлари булсин.


Биз куйидагича иш тутамиз, i = 1..n  хар бир тошни 1) ёки чап тарози палласига  ; 2) ёки унг тарози палласига куйишимиз керак ( шартга кура хар битта тош албатта тарозини бирор палласига куйилиши шарт). 

int    calc(  int i, int n,  int left, int right,  int w[n] ) ;

// ушбу функция 0, 1, ..., i-1, тошларни тарози палласига куйиб, энди i-чи тошни тарозини чап ёки унг палласига куйган холда, мумкин булган фаркдан энг кичигини топсин.

Хуш уни танасини кандай ёзамиз. Эслатиб утаман - бу функция олдин айтганимдек рекурсив булади, демак энг аввало рекурсияни тугаш шартини ёзишимиз керак.
int calc( int i, int n, int left, int right, int w[n] )

{

       // index 0..n-1,  демак i ==n булса хамма тошлар тарозига куйилиб булинган.

       if ( i == n )

      {  

             // фарки  чап ва унг паллардаги огирликлар айирмасига тенг,
            // албатта модул олиш хам керак.

             return abs( left - right); 

      }
          // бу ерда колган кисми ёзилади.
}

Эндиги навбат функцияни колган кисмини ёзиш колди. Хуш, олдин айтганимдек  i-чи тошни ёки чап ёки унг паллага куйишимиз керак, демак код куйидагича булади:



int calc( int i, int n, int left, int right, int w[n] )
{
      // index 0..n-1,  демак i ==n булса хамма тошлар тарозига куйилиб булинган.
       if ( i == n ) 
      {  

           // фарки  чап ва унг паллардаги огирликлар айирмасига тенг,
           // албатта модул олиш хам керак.

             return abs( left - right);
      }

          // 
бу ерда колган кисми ёзилади.
        //чапга куйсак, left -> left + w[i] булади,  i  эса  i+1  га узгаради, 
       // яъни i+1 -чи тошни куйишни бошлайди.
      int left_side = calc( i + 1, n , left + w[i],  right,  w );  

      // 
унгга куйсак, right -> right + w[i] . i  эса  i+1  га узгаради
      int right_side = calc( i + 1, n , left,  right + w[i],  w ) ;
      
     // натижа эса  left_side ва  right_side  нинг кайси кичик булса шуниси булади
    return  ( left_side < right_side ) ?  left_side : right_side;
}



Якунда тулик дастурни келтираман:


#include

int abs( int x ) { return x > 0 ? x : -x; }

int min(int x, int y) { return x >y ? y : x ; }

int calc(  int i , int n, int left, int right, int w[ ] ) //
w[n] - хато беради :))
{
     if ( i == n ) return abs( left - right);
     int left_side = calc( i + 1, n , left + w[i], right, w );
     int right_side = calc( i + 1, n , left,  right + w[i] ,  w);

    return min( left_side, right_side);


int main()


{
      int w[20];
      int n;
   
      std::cin >> n;
      for(int i = 0; i < n; i++) std::cin >> w[i];

     // бошлангич холда,  i = 0 , left = 0, right = 0  булади.
    std::cout << calc( 0, n, 0, 0, w ) << std::endl;

   return 0;

}
якунда айтиб утмокчиманки, бу усулни асимптитотикаси O( 2 ^ n) га тенг.

-------------------------------------------------------------------------------------------------------------


Юкорида айтиб утганимдек, биз 2та усулни куриб утамиз. Навбат ана шу 2 -усулга етиб келди. Бу усул хам барча мумкин булган холларни тахлил килишга асосланган, фарки унда рекурсия ишлатилмайди. У  сонни 2-лик санок системасига асосланган, гап шундаки агар n-битли сонни барча битларини тахлил килсак, ва агар i-бит  1 булса ,  i-тошни чап паллага,  агар 0 булса унг паллага куямиз десак, айнан барча мумкин булган холатларни осонгина генерация килишимиз мумкин.
Буни тушуниш учун келинг аввало юкоридаги жадвалга кайтайлик:

       Чап палла                               Унг палла                    шу холатга мос сон

                                                                                         C B  A 

1.     [ ]                                       [ A, B, C ]                        '0  0  0' (2)   -> 0 (10)


2.     [ A ]                                   [ B, C ]                             '0  0  1' (2)   -> 1 (10)
3.     [ B ]                                   [ A, C ]                             '0  1  0' (2)   -> 2 (10)  
4.     [ C ]                                   [ A, B ]                             '1  0  0' (2)   -> 4 (10)
5.     [ A, B ]                              [ C ]                                  '0  1  1' (2)  ->  3 (10)
6.     [ A, C ]                              [ B ]                                  '1  0  1' (2)  ->  5 (10)
7.     [ B, C ]                              [ A ]                                  '1  1  0' (2)  ->  6 (10)
8.     [ A, B, C]                          [ ]                                      '1  1  1' (2)  ->  7 (10)

Куриб турганингиздек, охирги устунда 0..7  гача булган барча сонлар катнашган, гарчи хар-хил тартибда булса хам, демак  n-та тош булса, 0 .. (2^n)-1   гача барча сонлар катнашади, уларнинг кандай тартибда келиши масала ечимига умуман таъсир килмайди (буни уйлаб куринглар).


Куйида айнан 'code'  - бирор n-bit ли сондан фойдаланиб кандай килиб тошларни чап ва унг паллаларга куйишни куриб утамиз:

int  calc(  int code, int n, int w[] )

{

     // бошлангич холда тарози паллаларида тош йук, демак огирлик 0 га тенг.

      int left = 0;

      int right = 0;


      for(int i = 0; i < n; ++i)

      {  

            // code  ни i-битини оламиз

            int bit = (code >> i ) & 0x01;

         

           //  агар i-бит 1 га тенг булса, i-тошни чап

           if (bit == 1 )  

                     left += w[i]; 

            else  //  акс холда унг паллага куямиз.

                    right+=w[i];

      }
      // якунда чап ва унг паллардаги фаркни хисоблаймиз.

      return abs( left - right);



}
А асосий функциямиз эса куйидагича булади:

int main()

{

   // .... тошларни укиб олами....

   // .............................

  // асосий хисоблаш жойи

  int result = 1000 * 1000 * 1000 ; // maximal son

 //  code = 0... (2^n)-1   хамма сонларни оламиз

  for( int code = 0;  code <  (1 << n ); ++code)

  {

          int current_min = calc( code, n , w );

          if ( current_min <  result ) 

                result = current_min;

   }


  std::cout << result;
}
Аммо бу усулнинг асимптотикаси O( n * 2^n ) га тенг.

--------------------------------------------------------------------------------------------



Автор: Khurshid Normuradov
Download 22.56 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
davlat pedagogika
nomidagi toshkent
guruh talabasi
pedagogika instituti
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
rivojlantirish vazirligi
samarqand davlat
haqida tushuncha
navoiy nomidagi
toshkent davlat
nomidagi samarqand
ta’limi vazirligi
Darsning maqsadi
vazirligi toshkent
Toshkent davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
Ўзбекистон республикаси
Alisher navoiy
matematika fakulteti
bilan ishlash
Nizomiy nomidagi
vazirligi muhammad
pedagogika universiteti
fanining predmeti
таълим вазирлиги
sinflar uchun
o’rta ta’lim
maxsus ta'lim
fanlar fakulteti
ta'lim vazirligi
Toshkent axborot
махсус таълим
tibbiyot akademiyasi
umumiy o’rta
pedagogika fakulteti
haqida umumiy
Referat mavzu
fizika matematika
universiteti fizika
ishlab chiqarish
Navoiy davlat