Factorial(){
/*
Giải thuật sử dụng stack, mỗi phần từ của Stack có 2 thành phần: N là giá trị của n ở mức hiện tại,
RETADD là địa chỉ quay về
temrec là biến trung chuyển, chứa PARA (N) và address ứng với lời gọi chính của chương trình (ĐCC)
*/
//B1
Push(S, Top, TEMREC);
//Bước 2. kiểm tra điều kiện cơ sở
if(Top.N == 0){
GIAI_THUA = 1;
goto Bước 4;
}else{//gán thông tin cho biến temrec để push
PARA = Top.N - 1;
ADDRESS = Bước 3;
}
goto Bước 1;
//Bước 3. Tính giai thừa
GIAI_THUA = GIAI_THUA * Top.N;
//Bước 4. Khôi phục địa chỉ quay về và N
TEMREC = POP(S, Top);
goto ADDRESS; //có thể là địa chỉ chính (với N đầu tiên)
//...hoặc Bước 3
return GIAI_THUA;
}
1
|
Số mức
|
Các bước thực hiện
|
Nội dung stack
|
2
|
Vào mức 1
(Lời gọi chính)
|
Bước 1:
Push(A, -1, (3, ĐCC)
Bước 2:
N != 0 -> PARA = 3 - 1 = 2
ADDRESS = Buoc 3
goto Buoc 1;
|
3 | DCC <- TOP
____________
|
3
|
Vào mức 2
(Đệ quy lần 1)
|
Bước 1:
Push(A, 0, (2, Bước 3)
Bước 2:
Top.N != 0 -> Para = 2-1 = 1
Address = Bước 3
|
2 | Bước 3 <- TOP
3 | ĐCC
______________
|
4
|
Vào mức 3
(Đệ quy lần 2)
|
Bước 1:
Push(A, 1, (1, Bươc 3)
Bước 2:
Top.N != 0 -> PARA = 1 - 1 = 0
ADDRESS = Buoc 3
goto Buoc 1;
|
1 | Bước 3 <- TOP
2 | Bước 3
3 | ĐCC
______________
|
5
|
Vào mức 4
(Đệ quy lần 3)
|
Bước 1:
Push(A, 2, (0, Bước 3)
Bước 2:
Top.N == 0 -> Giai_thua = 1
Goto Bước 4
|
0 | Bước 3 <- TOP
1 | Bước 3
2 | Bước 3
3 | ĐCC
_______________
|
6
|
Quay lại mức 3
|
Bước 4:
TEMREC = POP
Goto Address (Bước 3)
Bước 3
Giai_thua = 1* Top.N = 1*1 = 1
|
1 | Bước 3 <- TOP
2 | Bước 3
3 | ĐCC
______________
|
7
|
Quay lại mức 2
|
Bước 4 (sau Bước 3)
TEMREC = POP(S, Top)
Goto Bước 3
Bước 3:
Giai_Thua = 1 * Top.N = 1 *2 = 2
|
2 | Bước 3 <- TOP
3 | ĐCC
______________
|
8
|
Quay lại mức 1
|
Bước 4 (sau Bước 3)
TEMREC = POP(S, Top)
Goto Bước 3
Bước 3:
Giai_Thua = 2 * Top.N = 2 * 3 = 6
|
3 | DCC <- TOP
____________
|
9
|
Quay lại địa chỉ chính
|
Bước 4:
TEMREC = POP
Goto Address (ĐCC)
|
Stack trống
|
11.Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật chuyển đổi biểu thức dạng trung tố sang dạng hậu tố.
Ý tưởng:
1. khởi tạo 1 ngăn xếp (stack) rỗng
2. đọc lần lượt các thành phần trong biểu thức nếu X là toán hạng thì viết nó vào biểu thức hậu tố (in ra) nếu X là phép toán thì thực hiện:
+ nếu stack không rỗng thì: nếu phần tử ở đỉnh stack là phép toán có độ ưu tiên cao hơn hoặc bằng phép toán hiện thời (X) thì phép toán đó được kéo ra khỏi stack và viết vào biểu thức hậu tố (lặp lại bước này)
+ nếu stack rỗng hoặc phần ử ở đỉnh ngăn xếp là dấu mở ngoặc hoặc phép toán ở đỉnh ngăn xếp có quyền ưu tiên thấp hơn phép toán hiện thời (X) thì phép toán hiện thời được đẩy vào ngăn xếp
nếu X là dấu mở ngoặc thì nó được đẩy vào stack
nếu X là dấu đóng ngoặc thì thực hiện:
+ (bước lặp):loại các phép toán ở đỉnh ngăn xếp và viết vào biểu thức dạng hậu tố cho tới khi đỉnh ngăn xếp là dấu mở ngoặc
+ loại dấu mở ngoặc khỏi ngăn xếp
3. sau khi toàn bộ biểu thức dạng trung tố được đọc, loại lần lượt các phép toán ở đỉnh stack và viết vào biểu thức hậu tố cho tới khi stack rỗng
Giải thuật:
CHUYEN_TRUNG_TO_SANG_HAU_TO ()
{//Giải thuật này sử dụng 1 stact S, trỏ bởi Top, lúc đầu T = -1
// Biểu thức trung tố gồm có: số, toán tử, 2 dấu ‘(‘ và ’)’
//Các phép * / có độ ưu tiên cao hơn + - (nhân chia trước cộng trừ sau)
do{
Đọc thành phần X tiếp theo trong biểu thức;
if (X là toán hạng){
printf(X);
}else if (X là phép toán){
do
{
if ((Top>-1) && (Top là phép toán có độ ưu tiên cao hơn hay bằng X)){
printf(POP(S, Top));
}
if (Top==-1 || Top=="(" || Top là phép toán có độ ưu tiên thấp hơn X){
PUSH (S, Top, X);
}
}while (phép toán X chưa được đưa vào S);
}else if (X là dấu "("){
PUSH (S, Top, X);
}else if (X là dấu ")"){
do{
printf(POP(S, Top)); // in ra các phép toán
}while (Top != "(");
POP(S, Top); // loại dấu ‘(’ ra khỏi S
}
}while (chưa gặp dấu kết thúc biểu thức);
do{
printf(POP(S, Top)); // in ra các phép toán còn lại
}while (T>-1);}
12. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp nhanh (Quick Sort).Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử trong trường hợp tốt nhất.
GIẢI: K; mảng
trai, phai: chỉ số của phần tử bên trái và bên phải của mảng
j: chỉ số của phần tử khoá
QuickSort(K, trai, phai){
if(t>p){
j = PhanDoan(K, trai, phai);
QuickSort(K, trai, j-1);
QuickSort(K, j+1, phai);
}
}
PhanDoan(K, vtt, vtp){
i = vtt + 1; //vị trí sau khoá hiện tại
j = vtp;
do{
while(i <= j && K[i] < K[vtt]){
i++;
}
while(i <= j && K[j] > K[vtt]){
j--;
}
if(i
K[i] <-> K[j];
i++;
j--;
}
}while(i<=j); //khi ra khỏi vòng lặp là đã tìm được vị trí cho chốt
Chia sẻ với bạn bè của bạn: |
