(Kỹ thuật nhánh cận) Bài toán dãy ABC

Dãy ABC:


Cho trước một số nguyên dương N ( N<= 100), hãy tìm một xâu chỉ gồm các ký tự A,B,C thỏa mãn các điều kiện sau:


*Có độ dài N
*Hai đoạn con bất kỳ liền nhau đều khác nhau. ( Đoạn con là 1 dãy các ký tự liên tiếp của xâu).
*Có ít ký tự C nhất.


Nếu dãy X[1...n] thỏa mãn điều kiện 2 dãy con liền kề bất kỳ khác nhau thì 4 kí tự liên tiếp bao giờ cũng phải chứa  một ký tự C.


Như vậy với một dãy gồm k ký tự liên tiếp thì dãy đó bao giờ cũng phải có >= k div 4 ( ký tự C).


Tại bước thử chọn X[i] nếu ta đã có T[i] ký tự C thì n-X[i] còn lại có ít nhất (n-X[i])div 4 ký tự C.


Như vậy số ký tự C trong dãy luôn luôn >= T[i] + (n- X[i]) div 4


Ta có thể dùng điều kiện này để đánh giá có nên tiếp tục lựa chọn và gọi đệ quy hay chuyển sang phương án khác.

 BÀI TOÁN : DÃY ABC
                        
program ABC_STRING;
const
   
      InputFile = 'ABC.INP';
      OutputFile = 'ABC.OUT';
      max = 100;
      
var

      N,MinC : Integer;
      X,Best : array[1...max] of 'A'...'C';
      T      : array[0...max] of Integer;
      {T[i] cho biet so ky tu 'C' trong doan X[1] den X[i]}
      
      f      : Text;
      
      
{Ham Same(i,l) cho biet xau l ky tu ket thuc tai x[i] }
{co trung voi xau l ky tu lien truoc no hay khong }

function Same(i,l : Integer) : Boolean;

var
      j,k : Integer;
      
      begin
      
             j:= i - l; {j la vi tri cuoi doan lien truoc doan do}
             
             for k:= 0 to l-1 do
               
                 if X[i-k] < > X[j-k] then
                    begin
                      
                           Same := False; Exit;
                    end;
                  
                  Same := True;
                  
      end;
      
      
{ Ham Check(i) cho biet X[i] co lam hong tinh khong lap}
{ cua day X[1...i] hay khong }

function Check( i: Integer) :boolean;

var
    
       l:Integer;
       for l:= 1 to i div 2 do  { thu cac do dai l }
           if Same (i,l) then
    { Neu co xau do dai l ket thuc boi x[i] bi trung voi xau lien truoc}
    
    begin
    
       Check := False; Exit;
       
    end;
    
       Check := True;
    end;
    
{Giu lai ket qua vua tim duoc vua tim duoc vao}
       {BestConfig ( MinC va mang Best)}
       
procedure KeepResult;
begin

     MinC := T[N];
     Best := X;

end;

{Thuat toan quay lui co nhanh can }

procedure Attempt( i: Integer); {Thu cac gia tri co the co cua X[i]}

var

      j:= 'A'...'C';
      
begin
      for j:= 'A' to 'C' do
      begin
      X[i] := j;
      if Check(i) then {Neu them gia tri do ma khong lam hong vong lap }
      begin
      
            if j = 'C' then T[i] := T[i-1] +1
             {Tinh T[i] qua T[i-1] }
             
            else T[i] := T[i-1];
            
            if T[i] + (N-i) div 4 < MinC {Danh gia n can }
            
                if i = N then KeepResult;
                
                else Attempt(i+1);
            
      end;
      end;
end;

procedure PrintResult;

var
      i: Integer;
      
begin

      for i:= 1 to N do Write ( f,Best[i]);
      
      WriteLn(f);
      WWriteLn(f,' " C " - Letter Count: ',MinC);
      
end;

begin

      Assign (f,InputFile);Reset(f);
      
      ReadLn (f,N);
      Close(f);
      Assign(f,OutputFile); Rewrite(f);
      
      T[0] := 0;
      MinC := N;
      {Khoi tao cau hinh BestConfig ban dau la rat toi }
      
      Attempt (1);
      
      PrintResult;
      
      Close(f);
      
end.

//Giai bai toan ABC su dung ky thuat nhanh can
                         //DEV-C ++
                         
#include<iostream>
#include<fstream.h>
#define MAX 101
#define TRUE 1
#define FALSE 0

//var 

char X[MAX], Best[MAX];  //X[] de luu cac ky tu trong qua trinh xet
                         // Best[] de luu phuong an toi uu nhat        
int MinC;
int T[MAX];  // T[i] luu so luong ky tu C tu X[1] den X[i]
int N;       // Do dai cua xau can tim

//Ham same cho biet xau l ky tu ket thuc boi X[i] 
//co trung voi xau l ky tu lien truoc no khong
bool Same( int i, int l )
{
     int j,k;
     j = i-l; //{ j la vi tri cuoi doan lien truoc no}
     for( k =0; k< l;++k)
     if ( X[i-k] != X[j-k]) return FALSE; // 2 xau khac nhau
     return  TRUE; // 2 xau giong nhau
     
}

bool Check( int i ) 
//Ham check cho biet phan tu X[i] 
//co lam mat tinh khong lap cua day X[1...i] khong
{
     int k = i >>1;
     for( int l = 1;l<= k;++l)
     if (Same(i,l))return FALSE; // X[i] khong thoa man
     return TRUE; // X[i] thoa man
     
}

void KeepResult()
{
     MinC = T[N];
     for ( int i =1;i<= N;++i)
     Best[i] = X[i];
     
}


//THUAT TOAN QUAY LUI CO NHANH CAN

void Attempt( int i)
{
     
     for(char j = 'A';j<= 'C';++j)
     {
          X[i] =j ;
          if(Check(i))
          {
                      if(j == 67)T[i] = T[i-1] +1; // Xac dinh T[i] dua vao T[i-1];
                      else T[i] = T[i-1];
                      
                      if( T[i] + (N-i)>>2 < MinC)
                      {
                          if( i == N)KeepResult();
                          else 
                              Attempt(i+1);
                      }
          }
     }
}

void PrintResult()
{
     int i;
     std::cout<<"String is : "<<std::endl;
     for( int i =1;i<= N;++i)
     std::cout<<Best[i];
     std::cout<<std::endl<<"Count of character 'C' is : " << MinC;
     
}

int main()
{
     fstream f;
     f.open("Giai bai toan ABC su dung ky thuat nhanh can.txt");
     f>>N;
     T[0] = 0;
     MinC = N; //Khoi tao cau hinh toi nhat
     Attempt(1); //Xet cac kha nang cua X[1];
     PrintResult();
     std::cout<<std::endl;
     system("pause");
     return 0;
}