Bài tập Kĩ thuật lập trình

Tiêu đề: Bài tập Kĩ thuật lập trình Fri Sep 17, 2010 8:15 am

Bài 1: Liệt kê mọi tập con của tập 1,2,...,n với n nhập từ bàn phím
Bài 2: Liệt kê tất cả các cách xếp 8 quân Hậu trên bàn cờ 8x8 sao cho chúng không ăn đc nhau.

Làm theo 2 cách: đệ quy,ko đệ quy.

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Fri Sep 17, 2010 8:16 am

Bài 1: TH đệ quy

#include<iostream>
#include<conio.h>
#include<iomanip>
using namespace std;

int *a,n,k;
void Nhap()
{
cout<<"\n Nhap so phan tu n= ";
cin>>n;
a=new int[n+1];
a[0]=0;
}
void Ketqua(int *a,int k)
{
cout<<"\n";
for(int i=1;i<=k;i++)
{
cout<<setw(3)<<a[i];
}
}
void Backtrack(int i,int *a,int n,int k)
{
for(int j=a[i-1]+1;j<=n-k+i;j++)
{
a[i]=j;
if(i==k)
Ketqua(a,k);
else Backtrack(i+1,a,n,k);
}
}
int main()
{
Nhap();
for(k=1;k<=n;k++)
Backtrack(1,a,n,k);
_getch();
}

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Fri Sep 17, 2010 8:26 am

Bài 2: TH đệ quy

#include<iostream>
#include<conio.h>
#define MAX 100
using namespace std;
int n,x[MAX],a[MAX],b[MAX],c[MAX],d=0;

void Try(int j)
{
for(int i=1;i<=n;i++)
if(a[i]==0&&b[i+j]==0&&c[i-j]==0)
{
x[j]=x[i];
a[i]=1;b[i+j]=1;c[i-j]=1;
if(j< 8 ) Try(j+1);
else
{
cout<<" +Cach xep: "<<++d<<":\n";
for(int i=1;i<=n;i++)
cout<<" ("<<i<<" ; "<<x[i]<<" ) ";
cout<<"\n";
}
a[i]=0;b[i+j]=0;c[i-j]=0;
}
}

int main()
{
cout<<"\n Kich thuoc ban co: n= ";
cin>>n;
for(int i=1;i<=n;i++)
{
x[i]=i;
a[i]=0;
}
for(int i=2;i<=2*n;i++)
b[i]=0;
for(int i=-n;i<=n;i++)
c[i]=0;
Try(1);
_getch();
}

/*a[i]=0 khong co quan hau nao chiem hang i;
b[i+j]=0 --------------------------- duong cheo i+j;
c[i-j]=0 ---------------------------------------i-j;*/

Còn TH không đệ quy ae giúp với !

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Fri Sep 17, 2010 8:59 am

đây là bài tập toán rời rạc phần bài toán liệt kê

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Sat Sep 18, 2010 10:41 pm

Copy đc đoạn code về 8 hậu nhưng không hiểu
Ae vào giúp

#include <iostream>
#include <algorithm>
#include<math.h>
using namespace std;

int main(){

const int size = 8;
int Q[size];
for(int i = 0; i < size; ++i)
Q[i] = i;
do{
for(int x = 1 ;x < size ; ++x){
for( int y = 0 ; y < x; ++y){
if(abs(Q[x] - Q[y]) == (x - y))
goto not_a_solution;
}
}
for(int x = 0; x < size; ++x){
for(int y = 0; y < size ; ++y){
cout << "_Q"[Q[x] == y] << ' ';
}
cout << '\n';
}
cout <<endl;
not_a_solution:;
}
while(next_permutation(Q, Q + size));
}

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Sun Sep 19, 2010 1:21 am

goto la lenh khuyen khong nen dung.vi thang nay no tro lung tung gay roi ram chuong trinh

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Thu Sep 23, 2010 10:14 am

#include<conio.h>
#include<iostream.>
#include<iomanip.h>
int n,count;
int *x;
bool *a,*b,*c;
void Init()
{
int i;
cout<<"Nhap vao kich thuoc ban co(n*n) voi n= ";
cin>>n;

x=new int[n+1];

a=new bool[n+1];
for(i=1;i<=n;i++)
a[i]=true;

b=new bool[2*n+1];
for(i=2;i<=2*n;i++)
b[i]=true;

c=new bool[2*n+1];
for(i=1-n;i<=n+1;i++)
c[i]=true;

count=1;
}
void Return()
{
cout.setf(ios::left);
cout<<"Cach "<<setw(4)<<count<<": ";
for(int i=1;i<=n;i++) cout<<setw(3)<<x[i];
cout<<"\n";
count++;
}
void Try(int i)
{
int j;
for(j=1;j<=n;j++)
if(a[j]&&b[i+j]&&c[j-i])
{
x[i]=j;
a[j]=false; b[i+j]=false; c[j-i]=false;
if(i==n) Return();
else Try(i+1);
a[j]=true; b[i+j]=true; c[j-i]=true;
}
}
int main()
{
Init();
Try(1);
getch();
}

Baì hậu thì nên làm thế này(theo sách thầy nghĩa chỉnh sang C++)

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Thu Sep 23, 2010 5:38 pm

Bài toán Đặt hậu
TH K
ko đệ quy

#include<iostream>
#include<conio.h>
#include<math.h>
#define N 8
using namespace std;

int main()
{
int x[N];
int k = 0,d=1;
x[0] = -1;
while(k>=0)
{
x[k]++;
if(x[k]<=7)
{
int Test = 0;
for(int i=0; i<k; i++)
{
if((x[k]==x[i]) || (abs(i-k) == abs(x[k]-x[i])))
/* Hai hậu ở dòng k,i cùng nằm trên một cột
và 2 hậu ở ô (x[k],k),(x[i],i) nằm trên cùng 1 đường chéo*/
{
Test = 1;
break;
}
}
if(Test)
{
continue;
}
if(k==7)
{
cout << "\n +Cach xep: "<<d++<< endl;
for(int i=0; i<=k; i++)
{
cout <<"("<<i+1<<";"<< x[i]+1 <<") ";
}
cout << endl;
}

else
{
k++;
x[k] = -1;
}
}
else k--;
}
_getch();
}

Tiêu đề: Re: Bài tập Kĩ thuật lập trình Fri Sep 24, 2010 2:43 am

bai1 khu de quy
dung thuat toan sinh xau nhi phan

#include<conio.h>
#include<stdio.h>
#include<iostream.h>
void Inkq(int n,int*);
int main(void)
{
int n,j;
int *prtA = NULL;

//khoi tao
cout<<"nhap n= "<<endl;
cin>>n;
prtA = new [n + 1];
for(int i = 0 ; i <= n ; i ++ )
prtA[i] = 0;

//sinh xau nhi phan
do
{
i = n;
while( prtA[i] == 1 ) i -- ;
if (i == 0) break;
prtA[i] = 1;
for(j = n ; j>i ;j -- )
prtA[j] = 0;
Inkq(n,prtA);
}
while(1);

//giai phong
delete []prtA;
getch();
return(0);
}
void Inkq(int n,int* Temp)
{
for (int i = 1 ; i <= n ; i ++ )
if (Temp[i] == 1)
cout<<i<<" ";
cout<<endl;
}

» Giáo trình C++ của thầy Phạm Văn Ất
» Tối ưu hóa thuật toán