Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 16 Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui

Giáo án ppt chuyên đề Tin học khoa học máy tính 11 kết nối tri thức: Bài 16 Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui. Bài giảng thiết kế hiện đại, sáng tạo giúp tiết học thêm phần thú vị, giúp giáo viên tiết kiệm thời gian nhưng vẫn có thể ứng dụng công nghệ vào công tác giảng dạy.

Bài khác

Tải về

Nội dung chi tiết

... Còn nữa ...

XIN CHÀO CÁC EM!

CHÀO MỪNG CÁC EM

QUAY LẠI VỚI BÀI HỌC!

KHỞI ĐỘNG

Chắc em đã nghe nói nhiều bài toán tìm đường đi trong mê cung. Nếu áp dụng kĩ thuật duyệt quay lui cho bài toán này thì làm thế nào để tìm ra các bước đi tiếp theo từ một vị trí?

BÀI 16. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT QUAY LUI

GIẢI BÀI TOÁN MÊ CUNG

Mê cung là một hình chữ nhật gồm m hàng, n cột ô được định nghĩa bằng một tệp dạng văn bản có tên maze.inp, trong đó các ô 0 là ô được đi, ô 1 tương ứng với tường và không được đi. Tại một vị trí có thể chọn một trong bốn hướng đi tiếp (lên, xuống, trái, phải). Giả sử vị trí xuất phát là ô bên trái phía trên, hãy tìm một đường đi đến ô bên phải phía dưới để thoát khỏi mê cung. Nếu tìm ra nghiệm thì in ra đường đi dưới dạng bảng trong đó vết của đường đi gồm các ô được thể hiện bằng số 1, các ô còn lại là số 0. Kết quả được thể hiện trên màn hình và ghi ra tệp maze.out. Ví dụ một thể hiện của dữ liệu đầu vào và ra như bảng bên.

Maze.inp

0 1 1 0 1

0 0 1 1 1

1 0 0 0 1

0 0 1 0 0

Maze.out

1 0 0 0 0

1 1 0 0 0

0 1 1 1 0

0 0 0 1 1

Ý tưởng thuật toán

Quá trình tìm đường được bắt đầu tại vị trí bên phải phía trên.
Tại mỗi vị trí, thuật toán thử đi tiếp một bước theo một trong các hướng lên xuống trái phải. Nếu đi được thì cập nhật đường đi, nếu không thì thử hướng khác.
Nếu không có hướng nào hợp lệ thì quay lui.
Thiết lập mảng maze để lưu dữ liệu đầu vào của mê cung.

Thiết lập mảng sol để lưu vết đường đi trong mê cung. Ban đầu mảng sol sẽ gồm toàn số 0.
Hàm quay lui để tìm đường đi chính là solveMaze(maze, m, n, x, y, sol), mê cung có m hàng, n cột, x, y là tọa độ của ô hiện thời để tìm đường đi tiếp. Hàm sẽ trả lại True nếu từ vị trí hiện thời thời (x, y) tìm được đường đi thoát khỏi mê cung, ngược lại sẽ trả về False. Sau đây là mã giả mô tả nhanh hàm solveMaze().

Mã giả mô tả nhanh hàm solveMaze()

1 def solveMaza(maze,m,n,x,y,sol):

2 if <(x,y) nằm ở vị trí đích và rỗng>:

3 đặt sol[x][y] = 1 #Thiết lập bước đi và kết thúc

4 return True

5 if <ô (x,y) nằm trong mê cung và đang rỗng>:

6 if <ô (x,y) đã từng được đi qua trước đó>:

7 return False

8 Đặt sol[x][y] = 1 #đánh dấu đã đi qua ô này

9 lần lượt thử đi tiếp sang các ô trái, phải, trên, dưới bằng cách gọi đệ quy hàm solMaze()

10 Nếu thành công thì

11 return True

12 #Tới đây quay lui vì các bước đi tiếp ở trên đều thất bại

13 sol[x][y] = 0 #Thiết lập trạng thái trước khi thực hiện Solvemaze()

14 return False

15 else # ô (x,y) nằm ngoài mê cung hoặc là tường

16 return False

11 return True

12 #Tới đây quay lui vì các bước đi tiếp ở trên đều thất bại

13 sol[x][y] = 0 #Thiết lập trạng thái trước khi thực hiện Solvemaze()

14 return False

15 else # ô (x,y) nằm ngoài mê cung hoặc là tường

16 return False

1 maze = mảng được đọc từ tệp maze.inp

2 m, n = số hàng và số cột của maze

3 khởi tạo ma trận sol khích thước giống maze với các phần tử đều bằng 0 để chứa đường đi cần tìm

Solvemaze(maze, m, n, 0, 0, solve) #gọi hàm solve tìm đường từ vị trí góc trái bên trên
Thông báo kết quả

Dạng của chương trình chính

GIẢI THÍCH

Hàm readmaze() dùng để đọc dữ liệu từ tệp maze.inp, kết quả thông tin mê cung đưa vào mảng 2 chiều maze.
Hàm writemaze(outmaze) ghi mảng kết quả outmaze ra tệp maze.out.
Nếu ô hiện tại chưa là đích, tại dòng 25 kiểm tra xem ô này có được phép đi không, nếu có thì gán 1 tại ô hiện thời (dòng 28) và thử đi tiếp một bước theo một trong các hướng (lên, xuống, trái, phải). Nếu không đi được hoặc ô hiện tại không hợp lệ, trả lại giá trị False và quay lui về bước đi trước đó. Trước khi quay lui thì gán 0 tại ô hiện thời tại dòng 37.
Từ dòng 46, khởi tạo biển sol để lưu nghiệm và gọi hàm solveMaze để giải.

LUYỆN TẬP

Bài 1.

Nếu sửa yêu cầu đề bài đặt vị trí xuất phát tại ô giữa của mê cung (ví dụ vị trí m//2, n//2), vị trí thoát của mê cung là ô trái trên hoặc phải dưới của mê cung thì cần sửa chương trình như thế nào?

Bài 2.

Trên dữ liệu đầu ra của bài toán chưa thể hiện thông tin của các ô là tường. Hãy sửa lại chương trình đề trên dữ liệu đầu ra các ô là tường sẽ được đánh dấu bằng "x".

Để đặt vị trí xuất phát tại ô giữa của mê cung cần chỉnh giá trị tham số x, y khi gọi hàm solveMaze, cụ thể tại dòng 47 sửa thành:

Bài 1

Vị trí thoát của mê cung được thiết lập ở dòng 21. Theo yêu cầu vị trí thoát có thể là một trong hai trường hợp trái trên hoặc phải dưới thì chúng ta có thể sửa như sau:

Để đánh dấu “x” vào các ô là tường, có thể thêm một đoạn mã trước khi in ra ma trận sol để duyệt qua các ô của maze, nếu là tường thì sửa ô tương ứng của sol thành x. Tham khảo mã nguồn sau trong đó đoạn sửa ma trận sol ở dòng 50 đến 53.

Bài 2

1 #Hàm readmaze/writemaze để đọc/ghi mê cung

2 def readmaze():

3 file = open(“maze.inp”)

4 maze = []

5 for row in file:

6 h = [int(x) for x in row.split()]

7 maze.append(h)

8 file.close()

9 return maze

10 def writemaze(outmaze):

11 f = open(“maze.out”, “w”)

12 for i in outmaze:

13 for j in i:

14 print(j,file = f,end=“”)

15 print(file=f)

16 f.close()

18 #Hàm đệ quy tìm đường đi trong mê cung theo phương pháp quay lui

19 def solveMaze (maze, m, n, x, y, sol):

20 #Nếu đã đến ô bên phải phía dưới thì đã tìm được đường và kết thúc

21 if x == n – 1 and y == m – 1 and maze [x][y] == 0:

22 sol[x][y] = 1

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

8 file.close()

9 return maze

10 def writemaze(outmaze):

11 f = open(“maze.out”, “w”)

12 for i in outmaze:

13 for j in i:

14 print(j,file = f,end=“”)

15 print(file=f)

16 f.close()

18 #Hàm đệ quy tìm đường đi trong mê cung theo phương pháp quay lui

19 def solveMaze (maze, m, n, x, y, sol):

20 #Nếu đã đến ô bên phải phía dưới thì đã tìm được đường và kết thúc

21 if x == n – 1 and y == m – 1 and maze [x][y] == 0:

22 sol[x][y] = 1

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

VẬN DỤNG

--------------- Còn tiếp ---------------

Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 16 Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui

Nội dung chi tiết

Đầy đủ Giáo án ppt chuyên đề tin học khoa học máy tính 11 kết nối tri thức

Tài liệu cùng môn học

Tài liệu khác

Xem thêm nội dung

CHUYÊN ĐỀ 1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

CHUYÊN ĐỀ 3. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT