CNTT4A2 COMMUNITY

Thảo luận học tập


You are not connected. Please login or register

Go downThông điệp [Trang 1 trong tổng số 1 trang]

25/9/2011, 5:23 pm
whatsltd4us
whatsltd4us

Bài viết này whatsltd4us dựa vào cuốn sách của thầy Trần Đức Huyên, bổ sung thêm các minh họa bằng NNLT C/C++

Bài viết được chia làm 4 phần :
1. Xác định bài toán
2. Tìm cấu trúc dữ liệu để biểu diễn bài toán
3. TÌm thuật toán
4. Lập trình
5. Chạy thử, sửa đổi chương trình


Phần I. XÁC ĐỊNH BÀI TOÁN

1. Khái niệm bài toán
Trong quá trình tồn tại và phát triển, mọi cá nhân luôn phải giải quyết các bài toán. Cuộc sống là một chuỗi các bài toán mà ta phải đối đầu để giải quyết
Theo nhiều nhà nghiên cứu thi mọi bài toán đều có thể diễn đạt theo một sơ đồ chung
A----->B
Trong đó:
A là giả thiết, điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đàu giải bài toán
B là kết luận, mục tiêu cần đạt hoặc là cái phải tìm, phải làm ra khi bài toán kết thúc
-----> là suy luân, giải pháp cần xác định hoặc là một chuỗi các thao tác cần thực hiện, cần thi hành để có được cái phải tìm B từ cái đã có A

2. Xác định bài toán
Theo sơ đò trên thì xác định bài toán có nghĩa là xác định A, B nếu có thể thì xác định luôn các thao tác được phép sử dụng để đi từ A đến B ( Điều này rất quan trọng nhưng lại thường được hiểu ngầm )

3. Bài toán trên máy tính
Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán tổng quát đã nói ở trên nhưng có thể được diễn đạt theo một cách nói khác.
• A : là input hay còn gọi là thông tin vào
• B : là output hay còn gọi là thông tin ra
• -----> : là chương trình tạo ra từ các lệnh cơ bản của máy cho phép biến đổi từ A thành Bư

4. Những khó khăn
Để xác đinh một bài toán trên máy tính ta thường gặp 2 khó khăn sau :
• Thông báo về A hay B không đầy đủ và không rõ rang
• Thông báo về các điều kiên đặt ra cho cách giải (----->) thường không được nêu ra một cách minh bạch

5. Một số ví dụ

Bài toán 1 :
Cho 2 số tự nhiên a,b. TÌm UCLN của chúng


Xác định bài toán:
A. Xác định thông tin vào (INPUT)
- 2 số tự nhiên a,b
B. Xác định thông tin ra
- Số tự nhiên d thỏa mãn
+ d là ước của a và là ước của b
+ a lớn nhất trong tập các ước chung của a và b
Xác định các thao tác chế biến thông tin
- Xây dựng một dãy hữu hạn các thao tác cho phép tính được từ a và b
- VD :
a = 16 ; b = 24
d = 8

Bài toán 2:
Hãy tìm các cách đặt 8 quân hậu trên một bàn cờ vua sao cho không có quân hậy nào có thể ăn quân hậu khác

Xác định bài toán
A.Thông tin vào (INPUT)
-Bàn cờ vua hình vuông gồm 8 hàng và 8 cột
-Quân hậu là quân cờ có thể ăn được bất kỳ quân nào nằm ở cùng một hàng, cùng một cột hay cùng một đường chéo.
-Ta có tất cả 8 quân hậu
[You must be registered and logged in to see this image.]

B.Thông tin ra (OUTPUT)
-Các bảng vuông trên đó đã có đánh dấu vị trí của 8 quân hậu sao cho không có quân hậu nào có thể ăn quân hậu khác, nghĩa là trên mỗi hàng, mỗi cột, mỗi đường chéo chỉ có một quân hậu.
Ví dụ:
[You must be registered and logged in to see this image.]

-Chỉ ra tất cả các bảng vuông khác nhau thỏa mãn điều kiện của bài như bảng vuông ở trên.

Xác định các thao tác chế biến thông tin:
-Lần lượt xác định vị trí của một trong 8 quân hậu trên bàn cờ ( một ô trong số 64 ô ) sao cho :
+Đặt đủ 8 quân hậu
+Tất cả đều thỏa mãn các điều kiện đã nêu.

Một số nhận xét :

- Việc xác định bài toán là rất quan trọng, nó ảnh hưởng rất lớn đến cách thức và chất lượng của việc giải quyết bài toán
- Một bài toán cho dù được diễn đạt bằng thông báo chính xác đến đâu đi chăng nữa cũng phải giả định là phần lớn thông tin về A và B là tiềm ẩn trong đầu người giải. Thông báo về A hoặc B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó
- Bước đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách chính xác theo ngôn ngữ của riêng mình vì đó chính là cách tiếp cận bài toán, hiểu bài toán
- Bước kế tiếp là tìm hiểu các thông tin Input A và Output B, tìm các mối liên hệ giữa chúng.
- Nhận xét một vài trường hợp cụ thể để thông qua đó hiểu được cả bài toán và cũng thông qua đó thấy được các thao tác cần phải tiến hành. Thực tế cho thấy có những bài toán trong tin học chỉ có thể mô tả được thông qua các ví dụ.

( Do thời gian hạn chế nên các phần sau sẽ post vào ngày hôm sau ^^ )

http://vdvinh-nd.blogspot.com

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà whatsltd4us
25/9/2011, 6:01 pm
kienhl
kienhl

he. tìm hiểu thêm trong toán rời rạc, năm sau đc học nhé!
http://tin4a2uneti.tk

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà kienhl

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

« Xem bài trước | Xem bài kế tiếp »

Bài viết mới cùng chuyên mục

      Quyền hạn của bạn:

      Bạn không có quyền trả lời bài viết