#include "baitap.h"
//ham tim kiem nhi phan lap
int TIM_KIEM::timKiemNPL(int a[],int l,int r,int k)
{
int m;
while(l<=r) //trong khi trai <= phai
{
m=(l+r)/2; //phan tu giua mang
if(a[m]>k) //so sanh voi k, neu > k thi loai bo khoi phep so sanh tu giua ve sau
r=m-1;
else
if(a[m]<k) //neu be hon k thi loai bo khoi phep so sanh tu giua ve truoc
l=m+1;
else
return m; //neu khong thi tra ve m
}
return -1; //neu khong thi tra ve -1
}
//tim kiem nhi phan de quy
int TIM_KIEM::timKiemNPDQ(int a[],int l,int r,int k)
{
int m;
if(l>r) //neu trai lon hon phai tra ve -1
return -1;
m=(l+r)/2; //vi tri giua mang
if(a[m]>k) //so sanh phan tu giua mang voi k
return timKiemNPDQ(a,l,m-1,k); //neu lon hon thi goi lai ham
else
if(a[m]<k) //so sanh
return timKiemNPDQ(a,m+1,r,k);//neu be hon thi goi lai
else return m; //tra ve m
}
//sap xep tang dan
void SAP_XEP::chonTrucTiep(int a[], int n){
int posMin;
int temp;
for(int i=0;i<n-1;i++){
//tim vi tri cua phan tu nho nhat tu a[i] den a[n-1]
posMin=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[posMin])
posMin=j;
// Hoan vi a[i] va a[posMin]
temp=a[i];
a[i]=a[posMin];
a[posMin]=temp;
};
};
//sap xep giam dan
void SAP_XEP::bubbleSort(int a[],int n){
int temp;
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(a[j]>a[j-1]){
temp=a[j-1];
a[j-1]=a[j];
a[j]=a[j-1];
};
};
void SAP_XEP::chenTrucTiep(int a[], int n){
int j;
int x;
for(int i=1;i<n;i++){
x=a[i];
j=i-1;
while(a[j]>x&&j>0){
a[j+1]=a[j];
j--;
};
a[j+1]=x;
};
};
void THOI_GIAN::batDau(){
start=clock();
};
void THOI_GIAN::ketThuc(){
end=clock();
};
DOC_GHI_FILE::DOC_GHI_FILE(){
ofstream f("C:\\OUT.TXT",ios::trunc);
f<<"\nTinh Thoi gian chay cac thuat toan:"<<endl;
f.close();
};
void DOC_GHI_FILE::docFileData(){
ifstream f("C:\\DATA.TXT",ios::in);
if(f.bad()){
cout<<"\nKhong the mo file"<<endl
; getch();
exit(1);
};
f.seekg(0,ios::beg);
f>>n;
a=new int[n];
for(int i=0;i<n;i++)
f>>a[i];
f.close();
};
void DOC_GHI_FILE::ghiFileData(){
ofstream f("C:\\DATA.TXT",ios::out);
if(f.bad()){
cout<<"\nKhong the mo file"<<endl
; getch();
exit(1);
};
cout<<"\nNhap vao so phan tu mang: "; f<<n<<endl;
srand(time(0));
for(int i=0;i<n;i++){
int m=rand()%n+1;
f<<m<<endl;
};
f.close();
n=0;
};
void DOC_GHI_FILE::ghiFileOut(char c[]){
ofstream f("C:\\OUT.TXT",ios::ate);
if(vt==0){
f<<"\nThoi gian chay thuat toan "<<c<<" la: ";
f<<thoiGian<<endl;
f.close();
}
else if(vt==-1){
f<<"\nKhong tim thay khoa "<<k;
f<<"\nThoi gian chay thuat toan "<<c<<" la: ";
f<<thoiGian<<endl;
f.close();
}
else {
f<<"\nVi tri tim thay la: "<<vt;
f<<"\nThoi gian chay thuat toan "<<c<<" la: ";
f<<thoiGian<<endl;
f.close();
};
};