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

Ví dụ:

Duyệt tất cả các xâu nhị phân có độ dài n

(i)                Tìm các giá trị thỏa mãn: 2^n

(ii)              Xác định thuật toán tổng quát.

Xâu nhị phân X = ( x1, x2, x3,…,xn)

Xây dựng các biến toàn cục: OK = 1 , count =0;

#include "iostream"
using namespace std;

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

// Initialize for X[]
void Init(){
cout<<"Nhap n = "; cin >> n;
X = new int [n];  // buffer for X[] with n elements
for ( int i =0; i<=n; i++)
X[i] =0; // assigned   

}

void Result(){

cout<< "\nGia tri nhi phan thu " << ++ amount << " = ";
for( int i =1; i<=n; i++)
cout<< "  " << X[i];

}

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;

}

int main(){

Init();
while( OK){

Result();
Next_Bit_String();       
}

delete (X);
cout<< endl;
system("pause");
return 0;
}

Bài 1: Cho dãy số An = {a1, a2, a3, …, an } gồm n số tự nhiên khác nhau: Hãy duyệt tất cả các dãy con của dãy số An sao cho tổng các phần tử của dãy con đó bằng một số k cho trước. Ví dụ: An = {5,10 ,15, 20, 25, 30, 35} K= 50; X1 = { 5, 10, 35} X2 = {5, 10, 15, 20} … Lời giải: A = a1, a2, a3, …, an; X = X1, X2,X3,…,Xn; Quy ước: Xi = 0 => ai không thuộc dãy con Xi = 1 => ai thuộc dãy con Giải thuật: X = (X1, X2, X3, .., Xn) K = tổng giá trị ( A1X1 + A2X2+…+ AnXn)

#include<iostream>
using namespace std;

int *A,*X,n,k,OK = 1, amount = 0;

// Nhap gia tri cua A[] va khoi tao gia tri cho X , nhap k

void Init(){
cout<< "\nNhap n = "; cin>>n;
A = new int [n];
X = new int [n];
for ( int i =1; i<=n; i++){
cout<< "\n A[ " << i << "] = " ; cin >> A[i];
X[i] =0;
}

cout<<"\n Nhap k= "; cin >> k;
}

// Duyet tat ca cac chuoi con cua A duoi dang nhi phan
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; // Da duyet het tat ca cac day con     

}

// Kiem tra nhung day con thoa man

int Test(){

int S =0;

//Tinh tong cac phan tu cua day con
for ( int i =1; i<=n; i++){
S += A[i]*X[i] ;
}
if (S == k) return 1;
else return 0;

}

// In ra cac day con thoa man

void Result(void){

cout<< " Day con X [ "<< ++ amount << "]= { ";
for ( int i =1; i<=n; i++)
{
if( X[i]) 
cout << "  " << A[i] ; 
}
cout<< " };" << endl;

}

int main(){

Init();

while(1)
{
Next_Bit_String();

if(OK==0)break;
if( Test())
Result();
}

delete(A);
delete(X);

system("pause");

return 0;
}