Acm timus ru Stone pile 1005

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