TH Toán Rời Rạc  Trang 1
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
KHOA CÔNG NGHỆ THÔNG TIN

BẢN BÁO CÁO
THỰC HÀNH TOÁN RỜI RẠC

Giáo viên hướng dẫn: Thầy Nguyễn Văn Nguyên
Nhóm :
Lớp : 07T1
Sinh viên thực hiện : Nguyễn Thị Quỳnh Mai
Đà Nẵng – Tháng 8/2010
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 2
LỜI NÓI ĐẦU
Ngày nay, Công nghệ thông tin là một trong những ngành đang phát
triển rất mạnh mẽ và có ảnh hưởng sâu rộng đến mọi mặt đời sống. Nó là
nền tảng của nền kinh tế tri thức, là thước đo trình độ phát triển của một
quốc gia.Vì vậy, việc đào tạo đội ngũ kỹ sư công nghệ thông tin có chất
lượng đòi hỏi phải được chú trọng và đầu tư đúng mức.
Đại học là môi trường cơ bản cung cấp kiến thức chuyên môn, giúp sinh
viên hình thành và phát triển những kĩ năng cần thiết cho công việc. Vì vậy,
học đi đôi với hành luôn là phương châm đào tạo hàng đầu trong các trường
đại học hiện nay.
Cùng với học phần lý thuyết, học phần Thực Hành Toán Rời Rạc giúp nâng
cao khả năng tư duy của sinh viên. Trên cơ sở đề bài thực hành được nhận,
sinh viên phải biết cách phân tích và cài đặt để giải quyết các bài toán liệt
kê, lập lịch, … nhằm giải quyết những bài toán có tính ứng dụng thực tế cao.
Em xin chân thành cảm ơn giáo viên hướng dẫn – thầy Nguyễn Văn
Nguyên đã giúp đỡ và chỉ dẫn em hoàn thành bài báo cáo này.
Đà Nẵng, ngày 9 tháng 7 năm 2010

có một số chữ cái lặp. Liệt kê tất cả các cách sắp xếp n chữ cái này. Có
đếm tổng số cách sắp xếp.
4. Xét phương trình nguyên: x
1
+x
2
+ +x
n
=k với x
i
≥0 ∀i=1 k. Viết chương
trình nhập n,k và in ra tất cả các nghiệm của phương trình.Có đếm tổng số
nghiệm.
2.Thuật toán:
2.1. Đếm số xâu nhị phân độ dài n:
a. Bất kỳ: Số xâu nhị phân độ dài n chính là 2
n
.
b. Không có hai bit 0 kề nhau:
- Nếu n=1: có 2 xâu.
- Nếu n=2: có 3 xâu.
- Từ n>2 trở đi thì số xâu nhị phân độ dài n chính bằng tổng của
số xâu nhị phân độ dài n-1 và số xâu nhị phân độ dài n-2.
c. Có ít nhất 2 bit 0 gần nhau:
Số xâu cần tìm chính bằng số xâu tìm được ở câu a trừ đi số xâu tìm
được ở câu b.
2.2. Thuật toán liệt kê các xâu nhị phân:
Để giải quyết bài toán này,ta sẽ xây dựng các hàm và dùng thuật toán
quay lui để giải
 Thuật toán cụ thể được mô tả như sau:

với i=
1,1 −n
.
Trong quá trình lặp sinh xâu kế tiếp bằng cách hoán đổi vị trí 2 phần
tử a[i]
≠
a[j] cho nhau .Điều kiện của i là tất cả các phần tử của xâu ở
bên trái vị trí i được sắp xếp theo chiều tăng trừ phần tử i .Vì các phần
tử của xâu được lưu vào vị trí từ 0 đến n-1 nên với i=n chính là điều
kiện để thoát khỏi vòng lặp .Điều kiện của j là 1 trong i-1 phần tử bên
trái của phần tử i có giá trị nhỏ nhất nhưng a[j]>a[i] .Vì dãy bên trái
của phần tử thứ i là dãy tăng do đó j chính là vị trí của phần tử đầu
tiên lớn hơn a[i] nếu j=1 i-1 .Sau khi hoán vị a[i] và a[j] cho nhau ta
sắp xếp lại tất cả các phần tử bên trái i theo chiều giảm, in ra cấu hình
mới của xâu và tăng biến đếm lên.
2.4. Giải phương trình: x
1

+ x
2
+ x
3

+ … + x
n

= k
- Khai báo biến.
- Khai báo thêm mảng a[i] để in ra các nghiệm của phương trình.
- Nhập dữ liệu n và k.

#include<stdio.h>
#include<math.h>
int DemXau1(int n);
int DemXau2(int n);
int DemXau3(int n);
void main(){
clrscr();
int n;
printf("Enter n=");
scanf("%d",&n);
printf("\nSo xau nhi phan bat ky do dai %d: %d
xau.",n,DemXau1(n));
printf("\nSo xau nhi phan ko co 2 bit 0 ke nhau: %d
xau.",DemXau2(n));
printf("\nSo xau nhi phan co it nhat 2 bit 0 ke nhau: %d
xau.",DemXau3(n));
getch();
}
int DemXau1(int n){
return pow(2,n);
}
int DemXau2(int n){
if(n==1) return 2;
if(n==2) return 3;
else return DemXau2(n-1)+DemXau2(n-2);
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 7
}
int DemXau3(int n){
return DemXau1(n)-DemXau2(n);

i=n-1;
while(s[i]==1) i ;
s[i]++;
for(int j=i+1;j<n;j++)
s[j]=0;
printf("\n%2d/",dem);
print();
}
}
//
void Lke2(int n){
int dem=1,kt=0,k=0;
for(int i=1;i<=n;i++)
s[i]=0;
for(dem=2;dem<=pow(2,n);dem++){
kt=0;
i=n;
while(s[i]==1) i ;
s[i]++;
for(int j=i+1;j<=n;j++)
s[j]=0;
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 8
for(i=1;i<n;i++)
if(s[i]==0 && s[i+1]==0) kt=1;
if(kt==0){
k++;
printf("\n%2d/",k);
print();
}

#include<stdio.h>
#include<string.h>
void Lke(char a[],int n);
void print(char a[]);
void Daygiam(int n,char a[]);
void main(){
clrscr();
char a[100];
int n,kt=1;
do{
kt=1;
printf("\nEnter the string: ");
gets(a);
n=strlen(a) ;
for(int i=0;i<n;i++)
if(a[i]<65 || a[i]>90) kt=0;
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 9
if(kt==0 || n==0) {
printf("Error! Retry");
}
}while(kt==0 || n==0);
printf("\nXau vua nhap la: %s",a);
printf("\nCac hoan vi ko lap:\n");
Lke(a,n);
getch();
}
void Lke(char a[],int n){
int i1=1,i2,count=1;
int x;

a[i]=a[j];
a[j]=x;
}
}
}
- Câu 4:
#include<conio.h>
#include<stdio.h>
#include<math.h>
int s[50];
void Giaiptr(int n,int k);
void print(int n);
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 10
void main(){
clrscr();
int n,k;
printf("Enter n=");
scanf("%d",&n);
printf("k=");
scanf("%d",&k);
Giaiptr(n,k);
getch();
}
void Giaiptr(int n,int k){
int i,j,sum=0,c,count=0;
for(i=1;i<=n;i++) s[i]=0;
printf("\nNghiem cua ptr: ");
if(k==0) {
count++;

- Câu 4:
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 12
II. BÀI 2:BÀI TOÁN TỐI ƯU RỜI RẠC
1.Đề bài:
1. Viết chương trình nhập n là số chi tiết cần gia công và nhập thời gian
gia công trên hai máy của từng chi tiết. Tính và in thời gian hoàn thành gia
công nhanh nhất.
2. Viết chương trình nhập n là số thành phố và nhập ma trận khoảng cách
C
n
x
n
=(c
ij
)
n
x
n
. Tìm hành trình ngắn nhất cho người du lịch.
2.Thuật toán:
2.1. Bài toán lập lịch:
Mỗi một chi tiết trong số n chi tiết D
1
, D
2
,…, D
n
cần phải được lần lượt
gia công trên 2 máy A, B. Thời gian gia công chi tiết D

> b
i
, tức là min(a
i
,b
i
) đạt được tại b
i
. Các chi tiết D
i
thỏa
mãn a
i
= b
i
xếp vào nhóm nào cũng được.
- Sắp xếp các chi tiết trong N
1
theo chiều tăng của các a
i
và sắp xếp các
chi tiết trong N
2
theo chiều giảm của các b
i
.
- Nối N
2
vào N
1

gọi là rẻ nhánh gần ( ta quy ước đường đi trên cạnh (i,j) là i >j ) , như
vậy tất cả “các đường đi từ i ra” và “các đường đi tới j” đều bị loại ra
khỏi ma trận C bằng thủ tục hạ bậc ma trận .Vì đã có đường đi I > j thì
đường đi j > i sẽ bị cấm .Cũng nhu vậy nếu việc nối cạnh (i,j) làm xuất
hiện đường đi từ 2 đỉnh A đến B trong hành trình thì đường thẳng nối B
đến A sẽ bị cấm. ví dụ :A >i >j >B thì cạnh (B,A) sẽ bị cấm ,việc cấm
cạnh (B,A) được gọi là cấm hành trình con .
Phương án 2: cạnh (i,j) không thuộc hành trình tối ưu , vì vậy đường đi
i >j sẽ bị cấm ,đây là phương án rẻ nhánh xa .
Chú thích: Việc cấm cạnh được thực hiện bằng cách gán cạnh cấm có chi phí
bằng ∞.
Trong chương trình ta ưu tiên chọn rẻ nhánh cận và nhánh xa chỉ thực
hiện khi chi phí nhỏ nhất lớn hơn cận của ma trận, khi đó ta chọn cạnh (i,j)
sao cho khi loại bỏ hàng i cột j ra khỏi ma trận rút gọn C thì ma trận hạ bậc
mới được tạo thành có chi phí rút gọn lớn nhất .Ta có thể tìm được cận tiếp
theo của ma trận hạ bậc bằng cách tìm phần tử nhỏ nhất trên hàng i khác
phần tử c[i,j] và nhỏ nhất trên cột j khác phần tử c[i,j], khi đó tổng của 2
phần tử nhỏ nhất đó chính là cận mới của ma trận rút gọn C sau khi đã loại
hàng i cột j ra khỏi ma trận .
Quá trình trên được lặp cho tới khi ma trận trở thành ma trận vuông bậc 2.
Theo quy ước ở trên thì bất cứ cạnh nào có c[i][j]= ∞ thì không tồn tại
cạnh nối I > j do vậy ở đây ta lần lượt nạp vào chu trình còn thiếu 2 cạnh
còn lại được nối với nhau.Tại đây ta so sánh cận với chi phí min
- Nếu lớn hơn thì bỏ qua.
- Nếu nhỏ hơn thì cập nhật chi phí min mới, xoá bỏ hành trình cũ đã
lưu và nạp hành trình mới.
- Nếu bằng thì cập nhật trường hợp và lưu thêm hành trình mới.
3.Mã nguồn:
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 14

{
int t;
t=a;
a=b;
b=t;
}
void LapLich()
{
int A[MAX],B[MAX];
int ia,ib;
int ta,tb;
int i,j;
//Phan nhom
ia=0;ib=0;
for(i=0;i<n;i++)
{
if(x[0][i] <= x[1][i])
{
A[ia]=i;
ia++;
}
else
{
B[ib]=i;
ib++;
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 15
}
}
//Sap xep moi nhom

}
int main()
{
int s,t;
if(Read()==0)
{
printf("Ko mo duoc file!");
getch();
}
Print();
LapLich();
getch();
return 0;
}
Ma trận đầu vào:
5
3 4 6 5 6
3 3 2 7 3
- Câu 2:
#include<conio.h>
#include<math.h>
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 16
#include<stdio.h>
int c[20][20], a[20], xopt[20], chuaxet[20], n, fopt, cmin, can;
void nhapdulieu() {
int i, j;
printf("Nhap so thanh pho: ");
scanf("%d", &n);
printf("nhap ma tran chi phi c[i][j]\n");

if (chuaxet[j]) {
a[i] = j;
chuaxet[j] = 0;
can += c[a[i - 1]][a[i]];
if (i == n) ghinhan();
else
if (can + (n - i + 1) * cmin < fopt) Try(i + 1);
can -= c[a[i - 1]][a[i]];
chuaxet[j] = 1;
}
}
//==============================//
void ketqua() {
int i, j;
printf("\nhanh trinh toi uu co chi phi la :%5d \n\n", fopt);
for (i = 1; i <= n; i++)
printf("%2d >", xopt[i]);
printf("%2d", xopt[1]);
}
//===============================//
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 17
void init() {
int i, j;
cmin = 0;
for (i = 1; i <= n; i++) {
chuaxet[i] = 1;
for (j = 1; j <= n; j++)
if ((i != j) && (cmin > c[i][j])) cmin = c[i][j];
}

của đồ
thị vô hướng liên thông G gồm n đỉnh (a
ij
=a
ji
∀i,j=1 n).
a) Kiểm tra đồ thị G có phải là đồ thị Euler hay không.
b) Nhập hai đỉnh x,y và dùng thuật toán Dijkstra để tìm đường đi ngắn nhất
từ x đến y.
c) Dùng thuật toán Prim để tìm cây phủ nhỏ nhất của đồ thị G.
2.Thuật toán:
- Tạo ma trận: sử dụng bộ ngẫu nhiên khởi tạo giá trị cho ma trận của
đồ thị G.
- Chuyển ma trận về dạng có a[i][i] và các cạnh không có đường đi
bằng
∞
.
- Kiểm tra đồ thị Euler: tất cả các đỉnh của đồ thị phải có bậc chẵn.
- Thuật toán Dijkstra:
+ Đầu vào: đồ thị có hướng G=(V,E) với n đỉnh, x
∈
V là đỉnh xuất
phát, y là đỉnh đích, a[u,v], u,v
∈
V là ma trận trọng số.
+ Đầu ra: khoảng cách từ x  y.
+ Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ x v
+ Bước 1: Khởi tạo: d[v]=a[x,v]; Truoc[v]=x;
d[x]=0; T=V\{x}, T là tập các đỉnh có nhãn tạm thời.
+ Bước 2: Lặp

- Tìm min{A[1][j]}j=1 n. Sau đó gán D[1]=D[j]=1 (đánh dấu 2 đỉnh
1,j) và cho số cạnh tìm được bằng 1 (Dem=1).
- Tìm min{A[i][j]}j=1 n, i=1 n với điều kiện D[i]=1 và D[j]=0. Sau
đó gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1
(Dem++).
- Nếu Dem = n-1 thì thuật toán kết thúc.
3.Mã nguồn:
#include<math.h>
#include<string.h>
#define vc 32767
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i, j, n, x, y;
int c[20][20], tr[20], s[20], chuaxet[20];
void khoitao();
void inra1();
void euler();
void xtoy();
void cayphu();
void taomang();
void ngaunhien();
//====================//
void main() {
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 20
clrscr();
n = 0;
taomang();
if (n != 0) {

for (i = 1; i <= n; i++)
s[i] = vc;
}
void inra1() {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%5d", c[i][j]);
printf("\n");
}
}
void euler() {
int bac, kt = 1;
for (i = 1; i <= n; i++) {
bac = 0;
for (j = 1; j <= n; j++)
if (c[i][j] != vc)
bac++;
if (((bac % 2) == 1) || (bac == 0))
kt = 0;
}
if (kt == 1)
printf("\n\tDo thi tren la do thi Euler\n");
else
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 21
printf("\n\tDo thi tren khong phai la do thi Euler\n");
}
void xtoy() {
int kt, k, b[20];
chuaxet[y] = 1;

y);
}
}
void cayphu() {
int p = 1, g[20][2], k, h, dodai, kt, min, u, cl;
for (i = 1; i <= n; i++)
chuaxet[i] = 0;
chuaxet[p] = 1;
k = 1;
for (i = 1; i <= n; i++)
if (p != i) {
s[i] = c[p][i];
tr[i] = p;
}
kt = 0;
h = 0;
cl = 0;
while ((kt == 0) && (cl == 0)) {
min = vc;
for (i = 1; i <= n; i++)
if ((chuaxet[i] == 0) && (s[i] <= min)) {
min = s[i];
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 22
u = i;
}
k++;
chuaxet[u] = 1;
h++;
g[h][1] = tr[u];

tr[i] = u;
}
}
}
}
4.Demo:
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1
TH Toán Rời Rạc  Trang 23
SV: Nguyễn Thị Quỳnh Mai Lớp 07T1