ThuatToan.Net

Chủ Nhật, 5 tháng 4, 2015

thuật toán binary insertion sort - chèn nhị phân

void BInsertionSort(int a[],int n )
{
int l,r,m,i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<n ; i++)
{
x = a[i]; l = 0;
r = i-1;
while(l<=r) // tìm vị trí chèn x
{
m = (l+r)/2;
// tìm vị trí thích hợp m
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy }
}

thuật toán insertion sort - chèn trực tiếp

Giả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự.
Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a0 , a1,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i).

Bước 1: i = 1; //giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i]
Bước 4: a[pos] = x; //có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i < n : Lặp lại Bước 2
Ngược lại : Dừng

void InsertionSort(int d, int n
{ int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(i=1 ; i<n ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x; // chèn x vào dãy
}
}

Thứ Sáu, 3 tháng 4, 2015

[đệ quy c/c++] kiểm tra các phần tử của mảng

8. Sử dụng đệ quy, viết hàm kiểm tra mảng có toàn các số nguyên chia hết cho 7 hay không.

#include<iostream>
using namespace std;
int kiemtra(int a[],int n)
{
if(n==0) return 1;
if(a[n-1]%7!=0) return 0;
n--;
return kiemtra(a,n);
}
void main()
{
int a[10]={7,14,21,28,35,42,49,56,63,70},n=10;
if(kiemtra(a,n)) cout<<"ok.tat ca chia het cho 7";
else cout<<"no.khong phai tat ca chia het cho 7";
system("pause");
}

[đệ quy c/c++] đếm số phần tử phân biệt trong mảng

7. Sử dụng đệ quy, viết hàm đếm các giá trị phân biệt trong mảng các số nguyên. (các giá trị trùng nhau chỉ đếm một lần).

#include<iostream>
using namespace std;
int dem(int a[],int left,int right)
{
if(left>right) return 0;
for(int i=left+1;i<=right;i++)
if(a[left]==a[i]) return dem(a,left+1,right);
return 1+dem(a,left+1,right);
}
void main()
{
int a[10]={17,14,21,28,17,42,49,56,63,17},n=10;
cout<<dem(a,0,n-1);
system("pause");
}

[đệ quy c/c++] tìm UCLN tất cả các phần tử trong mảng

[đệ quy c/c++] tìm UCLN tất cả phần tử trong mảng

Sử dụng đệ quy, viết hàm tìm UCLN của tất cả các phần tử của mảng., tìm ước chung lớn nhất của nhiều số bằng đệ quy.

#include<iostream>
using namespace std;
int UCLN(int a[],int left,int right)
{
if(left==right-1)
{
int x=a[left],y=a[right];
while(x!=y)
if(x>y)x-=y;
else y-=x;
return x;
}
int x=a[left],y=UCLN(a,left+1,right);
while(x!=y)
if(x>y)x-=y;
else y-=x;
return x;
}
void main()
{
int a[10]={6,12,18,24,30,36,42,48,54,60},n=10;
cout<<"UCLN="<<UCLN(a,0,n-1);
system("pause");
}

[Đệ Quy C++] viết hàm xuất các số nguyên tố có trong mảng

sử dụng đệ quy , viết hàm xuất tất cả các số nguyên tố có trong mảng ra màn hình

#include<iostream>
using namespace std;
int songuyento(int n)
{
if(n<2) return 0;
if(n==2) return 1;
for(int i=2;i<n;i++)
if(n%i==0) return 0;
return 1;
}
void xuat(int a[],int n)
{
if(n==0) return;
if(songuyento(a[n])) cout<<a[n]<<" ";
n--;
xuat(a,n);
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10},n=10;
xuat(a,n);
system("pause");
}

Thứ Năm, 2 tháng 4, 2015

[Đệ Quy C/C++] tìm min và max các phần tử của mảng.

Sử dụng đệ quy, viết hai hàm để tìm phần tử lớn nhất và nhỏ nhất của mảng.

#include<iostream>

using namespace std;

int min(int a[],int left,int right)

{

if(left==right) return a[left];

int m=min(a,left+1,right);

return (a[left]<m)?a[left]:m;

}

int max(int a[],int left,int right)

{

if(left==right) return a[left];

int m=max(a,left+1,right);

return (a[left]<m)?m:a[left];

}

void main()

{

int a[10]={1,2,3,4,5,6,7,8,9,10},n=10;

int mi=min(a,0,n-1);

int ma=max(a,0,n-1);

cout<<"min="<<mi<<"\nmax="<<ma;

system("pause");

}