Bài tập trên lớp 1

Bài tập 2:

Cho hình chữ nhật gồm nxm hình vuông đơn vị.

Hãy liệt kê tất cả các đường đi từ đỉnh ở ô vuông  cuối cùng góc bên trái  lên đỉnh của o vuông trên cùng góc bên phải.

Biết mỗi bước đi chỉ  được phép sang phải hoặc lên trên theo các cạnh của hình vuông đơn vị.

                                  

Tổng độ dài đường đi = n + m

Solve:

(i)                Biểu diễn các phương án của bài toán

(ii)              Xây dựng thuật toán trên biểu diễn vừa rồi

Biểu diễn:

X= {x1,x2,x3,…,xn}

Quy ước: xi = 1     lên trên

                  Xi = 0  sang phải

Có 2^(n+m) phương án

Giá trị thỏa mãn : Tổng X[1] + X[2] + X[3]+ … + [X(n+m) ] = n

 #include"iostream"
using namespace std;

int *X,n,m, amount = 0, OK =1;

//Initialize X[]

void Init(){
     
     cout<<"Nhap do dai canh: "; cin >> n; cin >> m;
     
     X = new int[m+n];
     for( int i =1; i<= m+n;i++){
          
          X[i] =0;
          }
     
     }
     
int Test(){
    
    int S =0;
    for(int i =1;i<= m+n;i++){
            
            S+= X[i];
            }
    if ( S == n)return 1;
    else return 0;
    
    }
     
void Result(){
     
     cout<< " Cach di thu " << ++amount <<":"<< endl;
     for( int i=1; i<= m+n ;i++){
          if( X[i] == 1) cout<<"Len tren ---> ";
          else cout<<"Buoc sang phai --->  ";
          }
     cout<< endl<<endl;
     }
     
void Next_Bit_String(){
     
     int i = m+n ;
     while(i>0 && X[i]){
               
               X[i] = 0; --i;
               }
               
     if( i>0) X[i] = 1;
     else OK =0; 
     
     }
     
int main(){
    
    Init();
    while(1){
              
              Next_Bit_String();

              if(OK==0)break;
              if(Test())Result();
                       
                       
              }
              
              delete (X);
              cout<< endl;
              system("pause");
              return 0;
    
    }

Bài 3:
Nhà thám hiểm cần đem theo 1 cái túi trọng lượng không quá B có n đồ vật cần đem theo.
Đồ vật I có trọng lượng ai; giá trị sử dụng Ci
Tìm cách đưa vào túi sao cho tổng giá trị sử dụng là Max.
Solve:
Biểu diễn a =(a1, a2, a3,…,an)
C = ( C1, C2,C3,…, Cn)
Xây dựng giải thuật:
D = { X1, X2, X3,…, Xn}
Sao cho a1X1 + a2X2 + a3X3+….+ anXn <= B
Tạo hàm kiểm tra: f(X) = C1X1 +…+ CnXn đạt MAX, X thuộc D

#include <iostream>
using namespace std;

int  *X,n, amount = 0, OK = 1, B, *C, Max=0;

struct Things{
       int weight;
       int value;     
       }  *A;

void Init(){
       cout<< "Nhap so do vat can dem theo: "; cin >> n;
       cout<< "\nNhap trong luong toi da: "; cin>> B;
       A = new Things [n]; 
       X = new int [n];
       C= new int[n];
       // Nhap du kien cho mang A
       cout<<"\nTrong luong va gia tri cua do vat: "; 
       for ( int i =1; i<=n;i++){
           cout<<"\n Vat " << i << ":  ";
           cin>> A[i].weight;
           cin>> A[i].value;
           X[i] =0;  C[i]=0;
           }
       
       }
       
void Result(){
     
     cout<<"Cach thu " << ++amount << "mang vat : " ;
     for( int i =1; i<=n;++ i){
          
          if(X[i])cout<<" "<< i;
          }
     cout<< endl;
     }
       
void Next_Bit_String(){
     
     int i =n;
     while( i>0 && X[i])
        {
            X[i] = 0;
             --i;
            }
     
     if( i>0) 
       X[i] = 1;
     else
       OK = 0; // The end 
     
     }
     
int Test(){
    int S = 0;
    for ( int i =1; i<=n; i++){
         S += A[i].weight*X[i];
        }
    if( S<= B && S!=0) 
 {
        int K = 0;
        for(int i=1; i<=n;i++) K += A[i].value*X[i];
  if(K > Max)
  {
  for(int i=1; i<=n; i++) C[i]=X[i];
  Max = K;
  }
 return 1;
 }
    return 0;  
    
    }
    
int main(){
    
    Init();
    while(1)
    {
    
       Next_Bit_String();
       if (OK == 0 )break;
       if(Test())  
         Result();
    }
    //delete (A);
    //delete (X);
    cout<<"\ncach xep toi uu la : ";
    for(int i=1; i<=n; i++){
            
    if(C[i]) cout<<" \nDo vat thu "<<i;
    
    }
    cout<<"\n tong gia tri : "<< Max << endl;
    
    system("pause");
    return 0;
}