else
Try(i+1); daxet[j] = 0;
c -= matran[pa[i-1]][j];
}
}
void inmt()
{
for(int i=1; i<=n; i++)
{
puts("");
Có thể bạn quan tâm!
-
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 - 24
Xem toàn bộ 205 trang tài liệu này.
for(int j=0; j<=n; j++) printf("%3d", matran[i][j]);
}
}
int main()
{
DocDL();
daxet[1] = 1;
pa[1] = 1;
c = 0; Try(2);
getch();
}
7. Cài đặt thuật toán thiết kế theo kỹ thuật nhánh cận 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++) for(j=1; j<=n; j++)
fscanf(f, "%d", &matran[i][j]); fclose(f);
}
void InPa()
{
int j;
for(j=1; j<=n; j++) printf("%d -> ", pa[j]);
printf("%d - %d", pa[n+1], chiphi);
}
void Try(int i, int c)
{
int j;
190
int c1;
for(j=2; j<=n; j++)
{
if(!daxet[j] && matran[pa[i-1]][j])
{
c1 = c + matran[pa[i-1]][j]; if(c1<chiphi)
{
pa[i] = j; daxet[j] = 1; c = c1; if(i==n)
{
if(matran[pa[n]][1] && (c+ matran[pa[n]][1]) < chiphi)
{
pa[n+1] = 1;
chiphi = c+ matran[pa[n]][1];
}
}
else
Try(i+1, c); daxet[j] = 0;
}
}
}
}
int main()
{
DocDL();
pa[1] = 1;
daxet[1] = 1;
191
chiphi = 1000;
Try(2, 0);
InPa();
getch();
}
8.Cài đặt thuật toán thiết kế theo kỹ thuật quy hoạch động giải bài toán máy trả tiền ATM.
/* Dữ liệu lưu trong tệp DoiTien.txt: ghi mệnh giá n loại tiền, số tiền cần rút*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define max 100 int n, soTien;
int T[max]; int pa[max];
int B[max][max]; void DocDL()
{
FILE *f;
f = fopen("DoiTien.txt", "r"); if(!f)
{
puts("Loi doc tep"); getch();
exit(0);
}
fscanf(f, "%d", &n);
fscanf(f, "%d", &soTien); int i;
for(i=1; i<=n; i++) fscanf(f, "%d", &T[i]);
192
fclose(f);
}
int Min(int a, int b)
{
if(a<b)
return a; else
return b;
}
void QHD()
{
int i, j;
for(j=1; j<=soTien; j++) B[0][j] = 32767;
for(i=1; i<=n; i++) for(j=1; j<=soTien; j++)
{
if(j<T[i])
B[i][j] = B[i-1][j];
else
B[i][j] = Min(B[i-1][j], 1+ B[i][j-T[i]]);
}
}
void TruyVet()
{
int i, j;
i = n; j = soTien; int k;
k = 1;
while(i && (j>0))
{
if(B[i][j] == B[i-1][j]) i--;
if(B[i][j] == (1 + B[i][j-T[i]]))
{
j -= T[i];
pa[k] = i; k++;
}
}
}
void InPA()
{
int i; i = 1;
while(pa[i])
{
printf("%3d", T[pa[i]]); i++;
}
}
main()
{
DocDL();
QHD();
TruyVet(); InPA();
getch();
}
TÀI LIỆU THAM KHẢO
[1]. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học quốc gia Hà Nội, 2004
[2]. Nguyễn Đức Nghĩa - Nguyễn Tô Thành, Toán rời rạc, Nhà xuất bản Đại học quốc gia Hà Nội, 2003
[3]. Robert Sedgewick, Cẩm nang thuật toán, NXB Khoa học kỹ thuật, 2004.
[4]. Chủ biên Ngọc Anh Thư, Nhóm dịch Nguyễn Tiến, Nguyễn Văn Hoài, Nguyễn Hữu Bình, Đặng Xuân Hường, Ngô Quốc Việt, Trương Ngọc Vân: Giáo trình Thuật toán, NXB Thống kê, 2002
[5]. Nhóm dịch Trần Đan Thư, Vũ Mạnh Tường, Dương Vũ Diệu Trà, Nguyễn Tiến Huy: Cẩm nang Thuật toán, NXB Khoa học và Kỹ thuật, 1998
[6]. Hà Huy Khoái, Nhập môn số học thuật toán, NXB Khoa học kỹ thuật, 1997.
[7].Giải thuật và Lập trình, Lê Minh Hoàng, Đại học Sư phạm Hà Nội, 2002.
[8]. Trần Tuấn Minh, Thiết kế và đánh giá thuật toán, Đại học Đà lạt, 2002
[9]. Đinh Mạnh Tường, Cấu trúc dữ liệu & Thuật toán, Nhà xuất bản khoa học và kĩ thuật, 2001
[10]. Nguyễn Xuân Huy, Thuật toán, Nhà xuất bản thống kê, 1988
[11]. Thomas H. Cormen:Introduction to Algorithms, Second Edition, 2001
[12]. Robert Sedgewick, Algorightms 2nd Edition, ISBN: 0201066734, Addison Wesley, 1988.
[13]. Niklaus Wirth, Algorithms and Data Structures, Prentice-Hall, 1986
[14]. Donald E. Knuth, Selected papers on analysis of algorithms, LeLand Stanford Junior University, 2000
[15]. Gregory L.Heileman, Data structures, algorithms, and object – oreinted programing, McGraw – Hill, 1996