Acm timus ru Stone pile 1005



Download 22,56 Kb.
Sana29.03.2020
Hajmi22,56 Kb.
#42865
Bog'liq
2 5222102795057889858

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 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish