Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị
tải về 418.79 Kb.
|
- Điều hướng trang này:
- Nội dung chuyên đề lý thuyết đồ thị
- 7. Bài tập theo chủ đề Chuyên đề Tìm kiếm theo chiều rộng (BFS)
- Output Gồm 1 dòng duy nhất là số nước đi tìm được Example
- Hạn chế: Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20. Gặm cỏ
- Kết quả Dòng 1: Một số nguyên là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuồng. Ví dụ
- VMUNCH.INP VMUNCH.OUT
- Kết quả Dòng 1: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng. Ví dụ
- 5 Tương đương hóa hai từ
- Ví dụ VWORDS.INP
- Output - Gồm 1 số nguyên duy nhất là số lần bấm phím ít nhất. Nếu ko có đáp án ghi ra -1 Example
| Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thuỵ Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng.
Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong khoảng vài mươi năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học v.v... Chẳng hạn như trả lời câu hỏi: Hai máy tính trong mạng có thể liên hệ được với nhau hay không?; hay vấn đề phân biệt hai hợp chất hoá học có cùng công thức phân tử nhưng lại khác nhau về công thức cấu tạo cũng được giải quyết nhờ mô hình đồ thị. Hiện nay, môn học này là một trong những kiến thức cơ sở của bộ môn khoa học máy tính. Lý thuyết đồ thị là một phần quan trọng trong nội dung chương trình chuyên của môn Tin học tại các trường chuyên. Hầu như trong các đề thi học sinh giỏi đều có các bài toán liên quan đến lý thuyết đồ thị, do đó để học sinh có được kết quả cao chúng ta cần trang bị cho các em một nền tảng tốt cũng như các kỹ thuật cài đặt các bài toán cơ bản của lý thuyết đồ thị. Tuy nhiên, lý thuyết đồ thị là một môn học cần tốn nhiều thời gian để truyền đạt, có một số vấn đề thì cần thiết cho học sinh trong các kỳ thi, một số khác không cần thiết, đặc biệt là một số vấn đề cần chứng mình, các định lý. Mặt khác một số vấn đề lại phải được trang bị sâu nhằm giúp học sinh giải quyết tốt vấn đề trong các đề thi lại không có trong nhiều tài liệu lý thuyết đồ thị cổ điển. Những vấn đề đó thường liên quan đến ứng dụng của lý thuyết đồ thị để giải quyết các bài toán thực tế.Một vấn đề khó khăn mà giáo viên gặp phải là quỹ thời gian của chúng ta rất ít mà nội dung giảng dạy nhiều. Do đó vấn đề chọn lựa những chuyên đề nào dạy và dạy đến đâu, những vấn đề nào định hướng cho học sinh tự học cần phải đặt ra cho Giáo viên giảng dạy các lớp chuyên Tin học và các đội tuyển chuẩn bị cho các kỳ thi Học sinh giỏi. Trong phạm vi một chuyên đề, không thể nói kỹ và nói hết những vấn đề của lý thuyết đồ thị mà chỉ giới thiệu các bài toán cơ bản của Lý thuyết đồ thị trong Tin học cùng với phương pháp truyền đạt cho học sinh. Tập bài giảng này sẽ xem xét lý thuyết đồ thị dưới góc độ người lập trình, tức là khảo sát những thuật toán cơ bản nhất có thể dễ dàng cài đặt trên máy tính một số ứng dụng của nó. Các khái niệm trừu tượng và các phép chứng minh sẽ được diễn giải một cách hình thức cho đơn giản và dễ hiểu chứ không phải là những chứng minh chặt chẽ dành cho người làm toán. Ngoài ra cũng cung cấp một số bài tập trên mạng đã được phân loại thành các dạng giúp giáo viên có nguồn bài tập cung cấp cho học sinh sau khi giảng dạy các chuyên đề. Lời giải của các bài tập được cung cấp dưới dạng chương trình.
Trang bị cho học sinh các kiến thức cơ bản cần thiết về đồ thị để giải quyết các bài toán thi học sinh giỏi.
Nội dung các bài giảng từ phần 1 tới phần 6 được soạn trên slide trong file đính kèm    
7. Bài tập theo chủ đềChuyên đề Tìm kiếm theo chiều rộng (BFS)
Mã bài: LUCKYNUMTrong một số nước châu Á, 8 và 6 được coi là những chữ số may mắn. Bất cứ số nguyên nào chỉ chứa chữ số 8 và 6 được coi là số may mắn, ví dụ 6, 8, 66, 668, 88, 886 …. Nguyên là một học sinh rất thích toán. Nguyên thích các số may mắn nhưng chỉ thích các số có dạng S = 8…86…6 trong đó S có ít nhất một chữ số và chữ số 6 và 8 không nhất thiết phải đồng thời xuất hiện. Ví dụ, 8, 88, 6, 66, 86, 886, 8866 … là các số có dạng S. Cho trước một số nguyên dương X (1 < X < 10 000), Nguyên muốn tìm số may mắn nhỏ nhất dạng S, có không quá 200 chữ số và chia hết cho X. Nhiệm vụ của bạn là viết một chương trình tìm số đó cho Nguyên.
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu. Trên mỗi dòng tiếp theo chứa một số nguyên X tương ứng với mỗi bộ dữ liệu.
Với mỗi bộ dữ liệu, ghi ra trên một dòng số may mắn dạng S nhỏ nhất chia hết cho X. Trường hợp không tồn tại số S có không quá 200 chữ số như vậy, ghi -1. Ví dụ
Mã bài: QBBISHOPXét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân 
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy. Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được. InputDòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t. Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i. Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
OutputGồm 1 dòng duy nhất là số nước đi tìm được Example
Hạn chế:Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.
Mã bài: VMUNCHBessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối. Bessie đã chia đồng cỏ của mình là 1 vùng hình chữ nhật thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột, đồng thời đánh dấu chỗ nào là cỏ và chỗ nào là đá. Bessie đứng ở vị trí R_b,C_b và muốn ăn cỏ theo cách của mình, từng ô vuông một và trở về chuồng ở ô 1,1 ; bên cạnh đó đường đi này phải là ngắn nhất. Bessie có thể đi từ 1 ô vuông sang 4 ô vuông khác kề cạnh. Dưới đây là một bản đồ ví dụ [với đá ('*'), cỏ ('.'), chuồng bò ('B'), và Bessie ('C') ở hàng 5, cột 6] và một bản đồ cho biết hành trình tối ưu của Bessie, đường đi được dánh dấu bằng chữ ‘m’. Bản đồ Đường đi tối ưu 1 2 3 4 5 6 <-cột 1 2 3 4 5 6 <-cột 1 B . . . * . 1 B m m m * . 2 . . * . . . 2 . . * m m m 3 . * * . * . 3 . * * . * m 4 . . * * * . 4 . . * * * m 5 * . . * . C 5 * . . * . m
Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie sẽ ăn được trên con đường ngắn nhất trở về chuồng (tất nhiên trong chuồng không có cỏ đâu nên đừng có tính nhé) Dữ liệu
Kết quả
Ví dụ
Mã bài: VBGRASSBessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột. Bessie ước gì có thể đếm được số khóm cỏ trên cánh đồng. Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự ‘#‘ hoặc là 2 ký tự ‘#’ nằm kề nhau (trên đường chéo thì không phải). Cho bản đồ của cánh đồng, hãy nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng. Ví dụ như cánh đồng dưới dây với R=5 và C=6: .#....
..#... ..#..#
...##. .#....
Cánh đồng này có 5 khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi hàng thứ 2 và thứ 3 ở cột thứ 2, một khóm là 1 ký tự nằm riêng rẽ ở hàng 3, một khóm tạo bởi cột thứ 4 và thứ 5 ở hàng 4, và một khóm cuối cùng ở hàng 5. Dữ liệu
Kết quả
Ví dụ
Mã bài: VWORDSCho hai từ x, y và một dãy hữu hạn các từ (w1, w2, ..., wk). Phép toán p * q mang ý nghĩa là phép nối từ p với từ q, hay nói cách khác p * q là một từ mới tạo thành bằng cách viết từ q phía sau từ p. Ta cần kiểm tra xem hai từ x, y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước không. Ví dụ: Từ abba và ab có thể tương đương hóa bằng cách sử dụng các từ trong dãy: baaabad aa badccaa cc. Ta cần nối vào từ abba các từ: aa và badccaa, và nối vào từ ab các từ baaabad, cc và aa theo thứ tự. Trong cả hai trường hợp, ta sẽ thu được cùng một từ: abbaaabadccaa.
Yêu cầuCho biết từ x, từ y và dãy từ w1, w2, ..., wk. Cho biết từ x và y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước được hay không? Nếu có thể, hãy tìm số lượng nhỏ nhất phép toán * cần sử dụng. Dữ liệu
Kết quả
Ví dụ
Mã bài: LEM2Một TV có N phím bấm đánh số 1..N. Trước đây TV còn tốt, khi ấn 1 phím xuống mọi phím khác đều tắt và chỉ có phím vừa ấn là bật. Bây giờ TV đã cũ, khi ấn 1 phím,chỉ có 1 số phím khác tắt(nếu nó đang bật), các phím khác không đổi Một phím dù đang bật hay tắt khi ta ấn nó thì phím này sẽ bật. Các phím bị nó tác động sẽ tắt nếu đang bật. Bạn được cho biết kết quả bấm của mỗi phím và 1 hiện trạng của các phím. Hãy tìm 1 dãy bấm liên tiếp 1 số ít nhất phím sao cho cuối cùng chỉ còn lại phím K, 1 <= K <= N, là bật các phím còn lại đều tắt.
Input- Gồm 1 test duy nhất: - Dòng đầu là 2 số nguyên N, K ( 3 ≤ N ≤ 20 ) - N dòng tiếp theo, dòng thứ i: * Đầu tiên là số S ( số phím mà phím i tác động ) . Tiếp theo S số là dãy phím mà phím i tác động khi bật nó - Dòng cuối là N số 0 or 1 mô tả hiện trạng bàn phím đang tắt or bật
Output- Gồm 1 số nguyên duy nhất là số lần bấm phím ít nhất. Nếu ko có đáp án ghi ra -1 Example
Каталог: forum -> attachment forum -> Kiểm tra kiến thức Sinh học lớp 12 forum -> Danh sách giao lưu đại học Sookmyung ( 8/1/2014) Lớp 4H12 attachment -> CHƯƠng I: LẮp ráp và CÀI ĐẶt máy tíNH attachment -> BÀi tập lớn môn: Kiến trúc máy tính Yêu cầu: Tìm hiểu kiến trúc mips attachment -> BÀI 1 : html cơ sở 1-Thành phần-Element tải về 418.79 Kb. Chia sẻ với bạn bè của bạn:
|