Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 12 Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

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 12 Thực hành kĩ thuật duyệt cho bài toán tìm kiếm. 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 MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Có lẽ em đã biết đến tính năng liệt kê danh sách bạn chung giữa những người dùng khác nhau để đề xuất kết bạn của Facebook. Nếu cần lập danh sách bạn chung của em và của một bạn khác trên Facebook thì em sẽ làm như thế nào?

BÀI 12. THỰC HÀNH KĨ THUẬT DUYỆT CHO BÀI TOÁN TÌM KIẾM

NHIỆM VỤ 1

Cho tên các tài khoản Facebook và danh sách bạn bè của tài khoản Facebook đó được lưu trong tệp. Mỗi dòng bao gồm tên tài khoản Facebook được ngăn cách với tên bạn bè bằng dấu hai chấm, tên bạn bè được ngăn cách nhau bởi dấu phẩy như sau:

Viết chương trình đọc dữ liệu danh sách bạn bè từ tệp, sau đó cho phép người dùng nhập tên hai tài khoản Facebook từ bàn phím và in ra số bạn chung của hai tài khoản đó.

Hướng dẫn thực hiện

Xác định danh sách bạn bè của hai tài khoản Facebook đó.

Xác định số phần tử chung của hai danh sách vừa tìm được ở bước 1.

Có thể thực hiện bằng cách duyệt từng phần tử trong một danh sách xem phần tử này có xuất hiện trong danh sách còn lại hay không.

1 def banchung(A,B): #tính số phần tử chun có trong 2 danh sách

2 kq = 0

3 for i in range(len(A)):

4 if A[i] in B:

5 kq= kq + 1

6 return kq

8 input_file = open(“ban_fb.inp”,encoding = “utf-8”)

9 ten_fb=[]

10 ban_fb=[]

11 for line in input_file.readlines():

12 ten, ban=line.split(“:”)

13 ten_fb.append(ten)

14 ban = ban.strip().split(“,”)

15 for i in range(len(ban)):

16 ban[i] = ban[i].strip()

17 ban_fb.append(ban)

18 input_string = input(“Nhập tên 2 tài khoản Facebook cần kiểm tra:”)

19 ten1,ten2 = input_string.split()

20 index1= index2 = -1

21 for i in range(0,len(ten_fb)): #tìm vị trí của tài khoản thứ nhất trong danh sách

22 if ten1==ten_fb[i]:

index1 = i

23 for i in range(0,len(ten_fb)): #tìm vị trí của tài khoản thứ hai trong danh sách

24 if ten2==ten_fb[i]:

25 index2 = i

26 if (index1==-1) or (index2==-1)

27 print(“Không tồn tại tài khoản cần tìm trong danh sách”

28 else:

29 print(“Số bạn chung của cả hai tài khoản Facebook là:”, banchung(ban_fb[index1],ban_fb[index2]))

NHIỆM VỤ 2

Cho trước tên các tài khoản Facebook và danh sách nhóm mà tài khoản đó tham gia, được lưu trong tệp. Mỗi dòng bao gồm tên tài khoản Facebook được ngăn cách với tên các nhóm bằng dấu hai chấm, tên các nhóm được ngăn cách nhau bởi dấu phẩy như sau:

Viết chương trình gợi ý kết bạn cho các tài khoản Facebook để gợi ý các bạn có cùng sở thích với tài khoản này. Hai tài khoản được coi là có chung sở thích nếu tham gia ít nhất 3 nhóm chung. In ra màn hình danh sách kết bạn đề xuất cho từng tài khoản.

Hướng dẫn thực hiện

1 def nhomchung(A,B): #Tính số phần tử chung có trong hai danh sách

2 kq = 0

3 for i in range(len(A)):

4 if A[i] in B:

5 kq= kq + 1

6 return kq

8 input_file = open(“group_fb.inp”, encoding = “utf-8”)

9 ten_fb=[]

10 group_fb=[]

11 for line in input_file.readlines():

12 ten, group=line.split(“:”)

13 ten_fb.append(ten)

14 group = group.strip().split(“,”)

15 for i in range(len(group)):

16 group[i] = group[i].strip()

17 group_fb.append(group)

18 print(“Danh sách đề xuất kết bạn cho các tài khoản như sau:”)

19 for i in range(len(ten_fb)):

20 dexuat=[]

21 for j in range(len(ten_fb)):

22 if i! = j: #Không đề xuất kết bạn với chính mình

23 if nhomchung(group_fb[i], group_fb[j] >=3:

24 dexuat.append(ten_fb[j])

25 print(“Đề xuất kết bạn cho”, ten_fb[i], “là”, dexuat)

LUYỆN TẬP

Sửa chương trình trong Nhiệm vụ 1 để in ra được danh sách bạn chung của hai tài khoản.

Để in ra danh sách bạn chung của hai tài khoản, trong hàm tính số bạn chung của hai tài khoản, ngoài số bạn chung, chúng ta cần trả về thêm một mảng chứa danh sách bạn chung của hai tài khoản đó. Chương trình trong Nhiệm vụ 1 có thể được sửa lại như sau:

1 def banchung (A,B): #tính số phần tử chung có trong hai danh sách

2 kq = 0

3 banchung=[]

4 for i in range(len(A)):

5 if A[i] in B:

6 kq = kq+1

7 banchung.append(A[i])

8 return kq,banchung

9 kq, ban_list = banchung(ban_fb[index1],ban_fb[index2])

10 print(“Số bạn chung của hai tài khoản facebook là: “, kq,ban_list)

Sau khi tìm được hai tài khoản Facebook cần kiểm tra, chúng ta có thể sử dụng hàm tính số bạn chung như sau:

9 kq, ban_list = banchung(ban_fb[index1],ban_fb[index2])

10 print(“Số bạn chung của hai tài khoản facebook là: “, kq,ban_list)

VẬN DỤNG

Bài 1. Trong bài toán đề xuất danh sách kết bạn, không tìm thấy đối tượng phù hợp cho hai bạn Hà, Hùng. Hãy viết chương trình tìm nhóm gợi ý cho một bạn bất kì (được nhập vào từ bàn phím). Nhóm được gợi ý là nhóm các bạn này chưa tham gia và đang có nhiều thành viên nhất.
Bài 2. Viết chương trình để tìm ra hai bạn có nhiều bạn chung nhất, hai bạn có nhiều nhóm chung nhất.

Bài 1

Để giải quyết được bài toán này, chúng ta phải lần lượt thực hiện các bước sau:

Thống kê được danh sách các nhóm.
Viết chương trình tính số thành viên hiện có trong nhóm.
Sau khi nhập tên người dùng cần gợi ý, duyệt lần lượt các nhóm có trong danh sách nhóm, kiểm tra xem người dùng đã có trong nhóm hay chưa. Trong các nhóm người dùng chưa tham gia, tìm ra nhóm hiện đang có nhiều thành viên nhất.

Bài toán này có thể được thực hiện như sau:

1 def member(ten_fb,group_fb,group): #tính số thành viên trong group

2 kq = 0

3 for i in range(len(ten_fb)):

4 if group in group_fb[i]:

5 Kq = kq + 1

6 return kq

8 input_file = open(“group_fb.inp”, encoding=“utf8”)

9 ten_fb=[]

10 group_fb=[]

11 for line in input_file.readlines():

12 ten, group_line.split(“:”)

14 group=group.strip().split(“:”)

15 for i in range(len(group)):

16 group[i]=group[i].strip()

17 group_fb.append(group)

18 all_group = [] #Danh sách các nhóm

19 for i in range(0,len(group_fb)):

20 for j in range(0,len(group_fb[i])):

21 if group_fb[i][j] not in all_group:

22 all_group.append(group_fb[i][j])

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

Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 12 Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

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