int k=0; while(i && j)
{
if(L[i][j] == L[i-1][j]) i--;
if(L[i][j] == L[i][j-1]) j--;
if(a[i] == b[j])
{
c[k] = a[i]; i--;
j--; k++;
}
}
Có thể bạn quan tâm!
-
Thiết kế và đánh giá thuật toán - 21 -
Thiết kế và đánh giá thuật toán - 22 -
Thiết kế và đánh giá thuật toán - 23 -
Thiết kế và đánh giá thuật toán - 25
Xem toàn bộ 205 trang tài liệu này.
c[k] = ' ';
}
void InPA()
{
int l;
l= strlen(c);
for(int i=l-1; i>=0; i--)
printf("%c", c[i]);
}
int main()
{
DocDL();
puts(a);
puts(b);
QHD();
TruyVet();
InPA();
getch();
}
5. Cài đặt thuật toán quay lui giải bài toán Mã đi tuần
#include<conio.h>
#include<stdio.h>
#include<stdlib.h> int p;
void InBanCo(int n, int *bc)
{
puts("");
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++) printf("%5d",*(bc+ i*n+j));
printf("n");
}
}
void try(int i, int n, int *bc,int *x,int *y, int *dx, int *dy)
{
for(int j=0; j<8; j++)
{
int u; int v;
u = *x + dx[j]; v = *y + dy[j];
if(u >=0 && u <8 && v>=0 && v <8 && *(bc+u*n+v)==0)
{
*(bc + u*n +v) = i; if(i == n*n)
InBanCo(n,bc);
else
{
*x = u;
*y = v; try(i+1,n,bc,x,y,dx,dy); if(p==0)
{
*x = u - dx[j];
*y = v - dy[j];
*(bc + u*n + v) = 0;
}
}
if(p==1)
{
*x = u - dx[j];
*y = v - dy[j];
*(bc + u*n + v) =0;
}
}
}
}
main()
{
int n, x, y, *bc;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
printf("BAI TOAN MA DI TUANnn"); printf("Nhap n = ");
scanf("%d",&n);
bc = (int *)calloc(n*n, sizeof(int)); printf("nIn tat ca cac truong hop (1/0): ");
scanf("%d", &p);
*bc = 1;
x = 0;
y = 0;
try(2,n,bc,&x,&y,dx,dy); getch();
}
5. Cài đặt thuật toán thiết kế theo kỹ thuật tham lam giải bài toán người bán hàng.
/* Dữ liệu lưu trong tệp NguoiBanHang.txt: ghi số thành phố và ma trận chi phí*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 100 int n;
int matran[max][max]; int daxet[max];
int pa[max]; int chiphi; void DocDL()
{
FILE *f;
f = fopen("NguoiBanHang.txt", "r"); if(!f)
{
puts("Loi mo tep"); getch();
exit(0);
}
fscanf(f, "%d", &n); int i, j;
for(i=1; i<=n; i++)
184
for(j=1; j<=n; j++)
fscanf(f, "%d", &matran[i][j]); fclose(f);
}
void InPa()
{
int i; puts("");
for(i=1; i<=n; i++) printf("%d -> ", pa[i]);
printf("%d -%3d", pa[n+1], chiphi);
}
int ChiPhiMin(int i)
{
int chiso = -1; int j;
for(j=1; j<=n; j++) if(matran[i][j] && !daxet[j])
break; if(j>n)
return -1; else
{
chiso = j;
for(j=1; j<=n; j++)
if(matran[i][chiso] > matran[i][j] && matran[i][j] && !daxet[j]) chiso = j;
return chiso;
}
}
void Greed_TSP()
185
{
int i;
for(i = 2; i<=n; i++)
{
int chiso;
chiso = ChiPhiMin(pa[i-1]); if(chiso==-1)
break; else
{
pa[i] = chiso; daxet[chiso] = 1;
chiphi += matran[pa[i-1]][chiso];
}
}
if(i!=n+1)
printf("nKhong co phuong an - Khong di qua het cac dinh"); else
{
if(matran[pa[n]][1])
{
chiphi += matran[pa[n]][1]; InPa();
}
else
printf("nKhong co phuong an - Khong quay tro lai dinh 1 duoc");
}
}
int main()
{
DocDL();
186
pa[1] = 1;
daxet[1] = 1;
chiphi = 0; Greed_TSP(); getch();
}
6. Cài đặt thuật toán thiết kế theo kỹ thuật quay lui giải bài toán người bán hàng.
/* Dữ liệu lưu trong tệp NguoiBanHang.txt: ghi số thành phố và ma trận chi phí*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 100 int n;
int matran[max][max]; int daxet[max];
int pa[max]; int chiphi; int c;
void DocDL()
{
FILE *f;
f = fopen("NguoiBanHang.txt", "r"); if(!f)
{
puts("Loi mo tep"); getch();
exit(0);
}
fscanf(f, "%d", &n); int i, j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
fscanf(f, "%d", &matran[i][j]); fclose(f);
}
void InPa()
{
int i; puts("");
for(i=1; i<=n; i++) printf("%d -> ", pa[i]);
printf("%d - %d", pa[n+1], chiphi); puts("");
}
void Try(int i)
{
for(int j=2; j<=n; j++)
if(!daxet[j] && matran[pa[i-1]][j])
{
pa[i] = j; daxet[j] = 1;
c += matran[pa[i-1]][j]; if(i==n)
{
if(matran[pa[n]][1])
{
chiphi = c;
chiphi += matran[pa[n]][1]; pa[n+1] = 1;
InPa();
}
}