Student Ktlt Chapter1 Intro

Nh?p môn m ? â Nh Nh<04B1>p ô

Nhập môn KTLT 1. Các nguyên tắc lập trình 1. 2. 3. 4.

Thiết kế chương trình Phong cách lập trình Cài đặt, kiểm thử và tinh chỉnh Bảo trì chương trình

2. Hàm và biến 3. Đệ quy 4. Giới thiệu về lập trình hướng đối tượng 1. 2. 3. 4.

Thế nào là OOP. Object và Class Constructor, Destructor Operator

1. Các nguyên tắc lập trình (Kruse, Chương 1) Reading: C++ Programming Style Guide

1. 1. Thiết kế chương trình

Giới thiệu • Mục đích: – Giới thiệu phương pháp và công cụ lập trình cho những chương trình thực tế – Đi theo một tiếp cận logic, thống nhất – Nguyên tắc thiết kế chương trình

Xác định mục tiêu của bài toán • Quyết định mục đích chung • Chỉ rõ những mục đích cụ thể • Chia công việc thành các bài toán con cho đến khi có kích thước cô đọng

Thiết kế chương trình • • • •

Tổ chức tốt từng phần Mã lệnh phải viết rõ ràng, dễ hiểu. Lựa chọn cấu trúc dữ liệu phù hợp Phân tích thuật toán

1. 2. Phong cách lập trình

Đặt tên • Mục đích của tên: – Lớp và biến: đại diện cho cái gì – Hàm: thực hiện công việc gì – Giải thích chi tiết

Một số chú ý khi đặt tên 1. Lựa chọn cẩn thận tên hàm, lớp, hằng, biến toàn cục 2. Tên biến cục bộ đơn giản 3. Sử dụng tiền tố/hậu tố cho các tên có cùng kiểu 4. Tránh đặt tên dễ nhầm lẫn, hoặc thêm phần đuôi không có ý nghĩa

Chuẩn bị tài liệu hướng dẫn • Mục đích: – chương trình nhỏ: giải thích cho những người khác. – chương trình lớn: cho cả người lập trình và người khác.

Một số chú ý khi viết TLHD 1. Viết một đoạn mở đầu trước mỗi hàm 2. Khi khai báo biến, lớp, hằng, giải thích ý nghĩa và cách sử dụng của nó

Một số chú ý khi viết TLHD 3. Giới thiệu mỗi đoạn chương trình (hàm, khối) với chú thích ngắn gọn về mục đích và ý nghĩa 4. Chỉ rõ kết thúc của mỗi phần 5. Tránh chú thích quá kỹ không cần thiết 6. Giải thích những câu lệnh không rõ ràng 7. Phần mã lệnh: cách chương trình hoạt động, TLHD: tại sao chương trình hoạt động, thực hiện công việc gì 8. Chú ý: Khi chương trình thay đổi, cần đảm bảo TLHD sẽ thay đổi tương ứng.

Ví dụ int main( ) // Program to play Conway’s game of Life. /* Pre : The user supplies an initial configuration of living cells. Post : The program prints a sequence of pictures showing the changes in the configuration of living cells according to the rules for the game of Life. Uses: The class Life and its methods initialize( ), print( ), and update( ). The functions instructions( ), user_says_yes( ). */

Định dạng chương trình • Canh lề giúp chương trình dễ hiểu

Thời gian đọc chương trình lớn hơn rất nhiều so với viết chương trình. Làm chương trình dễ đọc nhất có thể.

Tinh chỉnh và module hóa • Tinh chỉnh top-down: – Bắt đầu bằng viết chương trình chính – Quyết định việc chia các công việc (cho lớp, hàm, CTDL) – Tiếp tục với các hàm, lớp, CTDL

Tinh chỉnh Top-down – Hướng dẫn 1. Sử dụng lớp để mô hình hóa những khái niệm cơ bản của chương trình int main( ) { Life iConfig; iConfig . initialize( ); iConfig . print( ); cout << “Xem tiep the he sau? " << endl; while (user_says_yes( )) { iConfig . update( ); iCconfig . print( ); cout << “Xem tiep the he sau?” <<endl; } }

Tinh chỉnh Top-down – Hướng dẫn 2. Mỗi hàm chỉ thực hiện một công việc duy nhất 3. Mỗi hàm/lớp nên che giấu thông tin 4. Tham số của hàm cần được chỉ rõ

5. Các dữ liệu mà hàm sử dụng: Æ Giữ cho các mỗi liên hệ càng đơn giản càng tốt. Tránh sử dụng biến toàn cục càng nhiều càng tốt. Æ Nếu sử dụng biến toàn cục, viết hướng dẫn chi tiết.

1. 3. Cài đặt, kiểm thử, tinh chỉnh

Hàm giả void instructions() { } bool user_says_yes() { return(true); }

Định nghĩa lớp Life const int maxrow = 20, maxcol = 60; class Life { public: void initialize( ); void print( ); void update( ); private: int grid[maxrow + 2][maxcol + 2]; // allows for two extra rows and columns int neighbor_count(int row, int col); };

int Life :: neighbor_count(int row, int col) /* Pre: The Life object contains a configuration, and the coordinates row and col define a cell inside its hedge. Post: The number of living neighbors of the specified cell is returned. */ { int i, j; int count = 0; for (i = row − 1; i <= row + 1; i++) for (j = col − 1; j <= col + 1; j++) count += grid[i][j]; /* Increase the count if neighbor is alive. */ count −= grid[row][col]; /* Reduce count, since cell is not its own neighbor. */ return count; }

void Life :: update( ) /* Pre: The Life object contains a configuration. Post: The Life object contains the next generation of configuration. */ { int row, col; int new_grid[maxrow . 2][maxcol . 2]; for (row = 1; row <= maxrow; row..) for (col = 1; col <= maxcol; col..) switch (neighbor_count(row, col)) { case 2: new_grid[row][col] = grid[row][col]; // Status stays the same. break; case 3: new_grid[row][col] = 1; // Cell is now alive. break; default: new_grid[row][col] = 0; // Cell is now dead. } for (row = 1; row <= maxrow; row..) for (col = 1; col <= maxcol; col..) grid[row][col] = new_grid[row][col]; }

void Life :: initialize( ) /* Pre: None. Post: The Life object contains a configuration specified by the user. */ { int row, col; for (row = 0; row <= maxrow . 1; row..) for (col = 0; col <= maxcol . 1; col..) grid[row][col] = 0; cout << "List the coordinates for living cells." << endl; cout << "Terminate the list with the the special pair -1 -1" << endl; cin >> row >> col; while (row != -1 || col != -1) { if (row >= 1 && row <= maxrow) if (col >= 1 && col <= maxcol) grid[row][col] = 1; else cout << "Column " << col << " is out of range.“; else cout << "Row " << row << " is out of range." << endl; cin >> row >> col; } }

print() void Life :: print( ) /* Pre: The Life object contains a configuration. Post: The configuration is written for the user. */ { int row, col; cout << "\nThe current Life configuration is:" << endl; for (row = 1; row <= maxrow; row..) { for (col = 1; col <= maxcol; col..) if (grid[row][col] == 1) cout << ‘*’; else cout << ‘ ‘; cout << endl; } cout << endl; }

Driver •

Driver: đoạn chương trình cung cấp dữ liệu cho hàm và đánh giá kết quả. int main ( ) // driver for neighbor_count( ) { Life iConfig; iConfig.initialize( ); for (row = 1; row <= maxrow; row..){ for (col = 1; col <= maxrow; col..) cout << iConfig.neighbor_count(row, col) ; cout << endl; } }

Dò vết chương trình • Duyệt lại cấu trúc chương trình • Sử dụng công cụ dò vết • Scaffolding: thêm những đoạn code để gỡ lỗi • Lập trình phòng ngự • Sử dụng bộ phân tích tĩnh (static analyzer)

Nguyên tắc kiểm thử chương trình • Chọn dữ liệu kiểm thử: chất lượng quan trọng hơn số lượng • 3 phương pháp kiểm thử: – Hộp đen (Black-box) – Hộp kính (Glass-box) – Hộp tíc tắc (Ticking-box)

1. 4. Bảo trì chương trình

Bảo trì • Sau khi chương trình đã đưa vào sử dụng. • Sửa đổi và phân tích chương trình để đáp ứng yêu cầu mới. • Bảo trì chiếm >50% tổng số công việc.

Đánh giá chương trình 1. Chương trình đã giải quyết được bài toán đặt ra? 2. Chương trình cho kết quả đúng ở mọi trường hợp? 3. Giao diện thân thiện? Đầu vào/ra? Nhiều chức năng thay thế? Trợ giúp rõ ràng? 4. Chương trình viết rõ ràng, logic? Cấu trúc dữ liệu hợp lý? 5. Tài liệu hướng dẫn rõ ràng? (tên, đầu vào, đầu ra, giải thích) 6. Thời gian chạy và bộ nhớ hiệu quả?

2. Hàm và biến (Deitel, Chương 6)

Hàm • Gọi hàm – Cung cấp tên hàm và các tham số – Hàm thực hiện các thao tác và các phép toán – Hàm trả lại giá trị kết quả

• Định nghĩa hàm: Kiểu_trả_về tên_hàm (danh_sách_biến_hình_thức) { Thân_hàm: khai_báo + các_lệnh }

Phạm vi biến • Phạm vi biến: là vùng chương trình hoạt động của biến – Không thể truy cập biến ngoài vùng phạm vi này

Biến cục bộ và toàn cục • Phạm vi biến là vùng (block) chương trình mà biến được khai báo. Không thể truy cập biến địa phương ngoài vùng chương trình này • Biến toàn cục: phạm vi biến từ vị trí khai báo đến hết chương trình

Sự khác nhau giữa biến cục bộ và toàn cục

Biến static • Được khởi tạo ở lần chạy đầu tiên. Phạm vi sử dụng: – Khai báo trong hàm: phạm vi là hàm mà nó khai báo. Nhưng được giữ nguyên khi ra khỏi hàm và có thể sử dụng lại khi hàm được thực hiện trở lại – Khai báo ngoài hàm: phạm vi là từ khi khai báo đến cuối file chương trình

1 /* Fig. 5.12: fig05_12.c 2 A scoping example */ 3 #include <stdio.h> 4 5 void useLocal( void ); /* function prototype */ 6 void useStaticLocal( void ); /* function prototype */ 7 void useGlobal( void ); /* function prototype */ 8 9 int x = 1; /* global variable */ 10 11 /* function main begins program execution */

Global variable with file scope

12 int main( void ) 13 { 14 int x = 5; /* local variable to main */ 15 16 17

printf("local x in outer scope of main is %d\n", x );

18

{ /* start new scope */

19 20 21 22 23

int x = 7; /* local variable to new scope */ printf( "local x in inner scope of main is %d\n", x ); } /* end new scope */

Variable with block scope

Variable with block scope

24 25 26 27 28 29 30

printf( "local x in outer scope of main is %d\n", x ); useLocal(); /* useLocal has automatic local x */ useStaticLocal(); /* useStaticLocal has static local x */ useGlobal(); /* useGlobal uses global x */ useLocal(); /* useLocal reinitializes automatic local x */ useStaticLocal(); /* static local x retains its prior value */

31 32

useGlobal();

33 34

printf( "\nlocal x in main is %d\n", x );

/* global x also retains its value */

35 return 0; /* indicates successful termination */ 36 37 } /* end main */ 38 39 /* useLocal reinitializes local variable x during each call */ 40 void useLocal( void ) 41 { 42 43

int x = 25; /* initialized each time useLocal is called */

44 45

printf( "\nlocal x in useLocal is %d after entering useLocal\n", x ); x++; printf( "local x in useLocal is %d before exiting useLocal\n", x );

46 47 } /* end function useLocal */ 48

Variable with block scope

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

/* useStaticLocal initializes static local variable x only the first time the function is called; value of x is saved between calls to this function */ void useStaticLocal( void ) { /* initialized only first time useStaticLocal is called */ static int x = 50; Static variable with block scope

printf( "\nlocal static x is %d on entering useStaticLocal\n", x ); x++; printf( "local static x is %d on exiting useStaticLocal\n", x ); } /* end function useStaticLocal */ /* function useGlobal modifies global variable x during each call */ void useGlobal( void ) { printf( "\nglobal x is %d on entering useGlobal\n", x ); x *= 10; printf( "global x is %d on exiting useGlobal\n", x ); } /* end function useGlobal */

Global variable

local x in outer scope of main is 5 local x in inner scope of main is 7 local x in outer scope of main is 5 local x in useLocal is 25 after entering useLocal local x in useLocal is 26 before exiting useLocal local static x is 50 on entering useStaticLocal local static x is 51 on exiting useStaticLocal global x is 1 on entering useGlobal global x is 10 on exiting useGlobal local x in useLocal is 25 after entering useLocal local x in useLocal is 26 before exiting useLocal local static x is 51 on entering useStaticLocal local static x is 52 on exiting useStaticLocal global x is 10 on entering useGlobal global x is 100 on exiting useGlobal local x in main is 5

2. 3. Kiểu tham chiếu

Kiểu tham chiếu (reference) • Tham chiếu là một tên khác của biến • Được xem như một con trỏ hằng – không được tham chiếu tới một biến khác int ival = 1024; int &refVal = ival; // ok int &refVal; // error: tham chiếu phải được khởi tạo // tới một biến nào đó refVal += 2; refVal = someVal; int *p = &refVal; // khởi tạo p là địa chỉ của refVal

Ví dụ int a[ ] = { 3, 8, -4, 6 }; int &b = a[0]; int *c = &(a[3]); int *&d = c; int **e = &d; Dữ liệu của mảng a[ ] sau khi thực hiện những câu lệnh sau? b--; *d += b + a[1]; c = &(a[1]); **e -= a[2]; c[0] = *d + **e + b; d[1] = 2 * (**e);

2. 4. Truyền tham số

Truyền tham số • Có 2 cách truyền tham số: – Truyền theo giá trị (call/pass by value) – Truyền theo tham chiếu (call/pass by reference)

Truyền theo giá trị và truyền theo tham chiếu Truyền theo giá trị: • Một bản copy của biến được truyền vào tham số của hàm Truyền theo tham chiếu: • làm việc với tham số gốc của lời gọi hàm

void SwapWrong(short, short); void main() { short x = 10, y = 2; SwapWrong (x, y); cout << x << endl; cout << y << endl; } void SwapWrong(short u,short v ) { short stemp; stemp = v; v = u; u = stemp; }

Truyền theo tham chiếu void SwapRef(short &,short & ); void main() { short x = 10, y = 2; SwapRef (x, y); cout << x << endl; cout << y << endl; } void SwapRef(short &u,short &v ) { short stemp; stemp = v; v = u; u = stemp; }

Tham biến là kiểu con trỏ • Cung cấp địa chỉ của biến void getDimensions(int*, int*);

• Cho phép thay đổi giá trị của tham số

Ví dụ The code

void doubleIt(int x, int * p)Box diagram main { *p = 2 * x; 16 a } int main() { int a = 16; doubleIt(9, &a); doubleIt return 0; } x 9 p

a = 18

Memory Layout

p (8200)

8192 doubleIt

x (8196)

9

a (8192)

16

main

Tham biến là con trỏ void SwapPtr(short *,short * ); void main() { short x = 10, y = 2; SwapWrong (&x, &y); cout << x << endl; cout << y << endl; } void SwapPtr(short *u,short *v ) { short stemp; stemp = *v; *v = *u; *u = *stemp; }

Tham số mặc định được chỉ ra trong hàm mẫu

Tham số mặc định int getSum(int, int=0, int=0); // OK int getSum(int, int=0, int); // NO sum = getSum(num1, num2); // OK sum = getSum(num1, , num3); // NO

Ví dụ

void modifyArray( int [], int ); int main() { const int arraySize = 5; // size of array a int a[ arraySize ] = { 0, 1, 2, 3, 4 }; // initialize array a // pass array a to modifyArray by reference modifyArray( a, arraySize ); } // end function main // in function modifyArray, "b" points to the original array "a" void modifyArray( int b[], int sizeOfArray ) { // multiply each array element by 2 for ( int k = 0; k < sizeOfArray; k++ ) b[ k ] *= 2; } // end function modifyArray

// In function tryToModifyArray, "b" cannot be used // to modify the original array "a" in main. void tryToModifyArray( const int b[] ) { b[ 0 ] /= 2; // error b[ 1 ] /= 2; // error b[ 2 ] /= 2; // error } // end function tryToModifyArray

Hàm trả lại giá trị con trỏ int main() { int *p, bar=10; p = foo(bar); } int* foo(int bar){ int x = bar * 2; return &x; } Chưong trình trên có lỗi không?

Chồng hàm – Ví dụ • Các hàm được chồng: void void void void

getDimensions(int); getDimensions(int, int); getDimensions(int, double); getDimensions(double, double);

// // // //

1 2 3 4

• CTD sẽ gọi hàm như sau: int length, width; double base, height; getDimensions(length); getDimensions(length, width); getDimensions(length, height); getDimensions(height, base);

// // // //

1 2 3 4

3. Đệ quy (Kruse, Chương 5, Sedgewick, Chương 5)

3.1. Tổng quan về đệ quy

Kỹ thuật Đệ quy • Là một kỹ thuật giải quyết bài toán quan trọng trong đó: – Phân tích đối tượng thành các thành phần nhỏ hơn mang tính chất của chính đối tượng đó.

• Ứng dụng: – – – –

Cú pháp của ngôn ngữ lập trình Các thuật toán tìm kiếm và sắp xếp Lý thuyết trò chơi (Game theory) …

Gọi hàm và Bộ nhớ Stack

Activation Record

Biến địa phương Địa chỉ trở về Các tham số

Activation Frame

Khung stack cho các lời gọi hàm

D B C C C D A A A A A A A D D M M M M M M M M M M M Thời gian

D D D D D D M M M M

Stack được cấp phát cho dữ liệu

Cây lời gọi hàm Bắt đầu

Kết thúc

M

Cây gọi hàm tương đương

D

A B

C

D

D D Đệ quy là trường hợp khi: • Một hàm gọi chính nó, hoặc • Một hàm gọi một chuỗi các hàm khác trong đó một/ một vài trong số đó gọi lại hàm đầu tiên

Bài toán Tính giai thừa • Hàm tính giai thừa cho một số nguyên: n! = n * ( n - 1 ) * … * 1

• Định nghĩa đệ quy: 1

if n = 0

// điều kiện dừng

n * ( n - 1)!

if n > 0

// bước đệ quy

n! =

Chương trình tính giai thừa // Sử dụng đệ quy long Factorial (long n) { // điều kiện dừng n == 0 if (n == 0) return 1; else // bước đệ quy return n * Factorial (n-1); }

Điều kiện của đệ quy • Giải thuật đệ quy phải thỏa mãn 2 điều kiện: – Phải có điểm dừng – Phải làm cho kích thước bài toán thu nhỏ hơn

Có dừng hay không? int puzzle( int N) { if (N==1) return 1; if (N%2 == 0) return puzzle(N/2); else return puzzle (3*N+1); }

Thiết kế giải thuật đệ quy 1. 2. 3. 4. 5.

Tìm cách phân rã bài toán Tìm điều kiện dừng Viết sơ bộ thuật toán Kiểm tra sự kết thúc Vẽ cây đệ quy

Cài đặt đệ quy • Một processor. • Đồng bộ trên nhiều processor:

Chia để trị • Giải quyết một bài toán: – chia công việc thành các phần nhỏ hơn, – mỗi phần phải dễ giải quyết hơn bài toán ban đầu.

Thông số hóa bài toán void move(int n, int start, int finish, int temp); /* Pre: There are at least n disks on the tower start. The top disk (if any) on each of towers temp and finish is larger than any of the top n disks on tower start. Post: The top n disks on start have been moved to finish; temp (used for temporary storage) has been returned to its starting position. */

Chương trình void move(int n, int start, int finish, int temp) { if (n > 0) { move(n-1, start, temp, finish); cout << “ Move disk “ << n << “from ”<<start << “to ”<
Số lần chuyển đĩa Gọi f(n) là số lần chuyển đĩa cần thiết để chuyển n đĩa từ cột 1 sang cột 3. f(1) = 1; f(n) = 2 * f(n – 1) + 1, if n > 1 Do đó

f(n) = 2 * f(n – 1) + 1 = 2 2* f(n – 2) + 2 + 1 = … n-1 = 2 n-1 * f(1)n-2+ … + 2 + 1 = 2 + 2 +…+2+1 n = 2–1

Các nhà sư phải chuyển 64 đĩa. Giả sử mỗi lần chuyển mất 1 11 giây, các nhà sư sẽ phải mất 5 * 1011 năm = 25 lần tuổi của vũ trụ. Khi chuyển xong chồng đĩa thì đã đến ngày tận thế!

Dãy số Fibonacci • Dãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

trong đó mỗi số là tổng của 2 số đứng trước nó. • Định nghĩa theo đệ quy: – F(0) = 0; – F(1) = 1; – F(n) = F(n-1)+ F(n-2);

Chia để trị int fib(int number) { if (number == 0) return 0; if (number == 1) return 1; return fib(number-1) + fib(number-2); }

Tìm phần tử lớn nhất int max(int a[], int l, int r) { if(l==r) return a[l]; int m = (l+r)/2; int u = max(a, l, m); int v = max(a, m+1, r); if (u>v) return u; else return v; }

Tìm kiếm nhị phân // Tìm kiếm trên một mảng có thứ tự int bsearchr(const int data[], // input: mảng int first, // input: chỉ số đầu int last, // input: chỉ số cuối int value) // input: giá trị cần tìm // output: chỉ số của phẩn tử tìm được, nếu không trả lại –1

{

}

int middle = (first + last) / 2; if (data[middle] == value) return middle; else if (first >= last) return -1; else if (value < data[middle]) return bsearchr(data, first, middle-1, value); else return bsearchr(data, middle+1, last, value);

3.4. Đệ quy đuôi

Đệ quy đuôi • Hành động cuối cùng của hàm là lời gọi đệ quy tới chính nó

Đệ quy đuôi

Xóa đệ quy đuôi void move(int n, int start, int finish, int temp) { int swap; // temporary storage to swap towers while (n > 0) { // Replace the if statement with a loop. move(n − 1, start, temp, finish); // first recursive call cout << "Move disk " << n << " from " << start << " to " << finish << endl; n−−; // Change parameters to mimic the // second recursive call.

swap = start; start = temp; temp = swap; } }

Giúp tăng tốc độ ? tiết kiệm bộ nhớ?

3.5. Khử đệ quy

Khử đệ quy • Hàm tính giai thừa không đệ quy // Sử dụng vòng lặp long Factorial (long n) { long prod = 1; // 0! = 1 // tính tích = 1*2* … * n for (i = 1; i < n+1; i++) prod * = i; return prod; }

Hàm tính Fibonacci không đệ quy //Fibonacci sử dụng vòng lặp

int fib(int n) { int f[LARGE_NUMBER]; f[0] = 0; f[1] = 1; for (int i=2; i<= n; i++) f[i] = f[i-1] + f[i-2]; return f[n]; }

Đệ quy và Vòng lặp • Hàm đệ quy chỉ có một lời gọi đệ quy tới chính nó: • Nhiều lời gọi đệ quy chồng nhau: • Mọi giải thuật đệ quy đều có thể thay thế bằng một giải thuật không đệ quy • Khử đệ quy:

3.6. Kỹ thuật quy hoạch động

Quy hoạch động – Dynamic Programming • Là một kỹ thuật để tránh phải tính toán lại cho các giải thuật đệ quy. • Giải pháp:

Quy hoạch động từ dưới lên int fib(int n) { int f[LARGE_NUMBER]; f[0] = 0; f[1] = 1; for (int i=2; i<= n; i++) f[i] = f[i-1] + f[i-2]; return f[n]; }

Quy hoạch động từ trên xuống // Note: knownF is a global array initialized all zero int Fib (int i) { if (knownF[i]!=0) return knownF[i]; // First action if (i < 0) return i; // parameter error else if (i==0) return knownF[0] = 0; else if (i==1) return knownF[1] = 1; else return known[i] = Fib(i-1) + Fib(i-2); // last action }

Ví dụ • Tính các hệ số nhị thức: – Số các tập con gồm k phần tử từ tập gồm N phần tử.

Bottom-up int Choose(int N, int k) { int i, j, M[MAX_N][MAX_N]; for (i = 1; i <= N; i++) { M[i][0] = M[i][i] = 1; for (j = 1; j < i; j++) M[i][j] = M[i-1][j-1] + M[i-1][j]; } return M[N][k]; }

Top-down int Choose(int N, int k) { // Check if this is an easy case if (N == k || k == 0) return 1; // Or a previously examined case if (choices[N][k] > 0) return choices[N][k]; // If neither of the above helps, use recursion choices[N][k] = Choose(N – 1, k - 1) + Choose(N – 1, k); return choices[N][k]; }

Bài tập • Viết chương trình tính toán cho công thức đệ quy sau (theo hai phương pháp Bottom-up và Top-down)

3.7. Đệ quy quay lui

Trò chơi Tic-tac-toe

Yêu cầu của bài toán • Tìm bước di chuyển tốt nhất cho máy • 4 trạng thái: – HUMAN_WIN – COMPUTER_WIN – DRAW – UNCLEAR (HUMAN_WIN < DRAW < COMPUTER_WIN)

Chương trình

int Choose(int N, int k) { static int valid = 0, choices[MAX_N][MAX_N], i, j; // Check if we need to initialize data if (valid == 0) { for (i = 0; i < MAX_N; i++) for (j = 0; j < MAX_N; j++) choices[i][j] = 0; valid = 1; } // Check if this is an easy case if (N == k || k == 0) return 1; // Or a previously examined case if (choices[N][k] > 0) return choices[N][k]; // If neither of the above helps, use recursion choices[N][k] = Choose(N – 1, k - 1) + Choose(N – 1, k); return choices[N][k]; }

C++ (.h file)

C++ (.cpp file)