Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn


II. Bài toán và việc giải bài toán trên máy tính



tải về 1.56 Mb.
trang3/29
Chuyển đổi dữ liệu30.08.2016
Kích1.56 Mb.
#28834
1   2   3   4   5   6   7   8   9   ...   29

II. Bài toán và việc giải bài toán trên máy tính

1. Phương pháp tổng quát để giải một bài toán trên máy tính


Để giải một bài toán trên máy tính cần thực hiện các bước sau:

  1. Xác định bài toán;

  2. Xác định cấu trúc dữ liệu để mô tả bài toán;

  3. Xây dựng thuật toán;

  4. Soạn thảo văn bản chương trình, kiểm tra và hoàn thiện chương trình.

2. Xác định bài toán


Khái quát về 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 nhiều bài toán đặt ra trong cuộc sống. Có thể nói 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 thì mọi bài toán đều có thể diễn đạt theo một sơ đồ chung như sau:

A => B (*)

trong đó:



  • A là giả thiết, điều kiện ban đầu, thông tin đã cho, đã biết;

  • B là kết luận, là mục tiêu cần đạt hoặc cái phải tìm, phải làm ra khi kết thúc bài toán;

  • => là suy luận, giải pháp cần xác định hoặc chuỗi các thao tác cần thực hiện để có được kết quả B từ cái đã có A.

Xác định bài toán

Theo sơ đồ trên thì việc xác định bài toán có nghĩa là xác định A, B và nếu có thể thì xác định luôn cả các bước thực hiện để “đi” được từ A đến B.



Bài toán trên máy tính

Tương tự như (*), và



  • A gọi là đầu vào (INPUT);

  • B gọi là đầu ra (OUTPUT);

  • => là CHƯƠNG TRÌNH MÁY TÍNH cho kết quả B với đầu vào A.

Khó khăn

Việc xác định một bài toán trên máy tính thường gặp khó khăn sau:



  • Thông tin về A, B thường không rõ ràng và không đầy đủ;

  • Thông báo về đ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;

Ví dụ 1: Hãy viết chương trình cho phép giải phương trình bậc 2.

A =???, B=???

Ví dụ 2: Giả sử người A có một số tiền X đem gửi tiết kiện, lãi xuất tháng là L% hỏi rằng sau T tháng thì A có bao nhiêu tiền biết rằng cứ 3 tháng thì tiền lãi được cộng vào gốc.

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

Ví dụ 4: Cho dãy số a1, a2, ..., an hãy sắp xếp dãy trên theo thứ tự giảm dần.

Ví dụ 5: Hãy xây dựng hệ thống quản lý hồ sơ và kết quả học tập của sinh viên.

...


A =???, B=???

Nhận xét quan trọng

  • Việc xác định bài toán là rất rất quan trọng, nó ảnh hưởng tới 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 chi tiết, rõ ràng vẫn nên giả định là phần lớn thông tin về A, B là tiềm ẩn trong đầu người giải. Thông tin về A hoặc B thường 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 tiếp là tìm hiểu thông tin Input A, Output B và các mối liên hệ giữa chúng;

  • Nên xét một vài trường hợp cụ thể để thông qua đó hiểu được cả bài toán , thấy rõ được các thao tác phải làm. 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ụ (như: ).

3. Cấu trúc dữ liệu và Giải thuật


Cấu trúc dữ liệu

  • Trong khoa học máy tính, cấu trúc dữ liệu là một cách tổ chức lưu trữ và truy cập dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả (và phụ thuộc cả vào công cụ lập trình).

  • Ví dụ (trong C): Mảng (Array), Con trỏ (Pointer), Xâu ký tự (String), File, Stack, Queue

  • Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn.

  • Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt.

  • Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình.

Thuật toán

  • Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.

  • Thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào.

Ví dụ 1: Giả sử có hai bình A và B đựng hai loại chất lỏng khác nhau, A chứa dung dịch Da, B chứa dung dịch Db. Giải thuật để đổi dung dịch Da vào bình B và Db vào A là:

Yêu cầu phải có thêm một bình thứ ba gọi là bình C.

Bước 1: Đổ dung dịch Db vào bình C;

Bước 2: Đổ dung dịch Da vào bình B;

Bước 3: Đổ dung dịch Db vào bình A



Ví dụ 2: Một trong những giải thuật tìm ước chung lớn nhất của hai số a và b là:

Bước 1: Nhập vào hai số a và b.

Bước 2: So sánh 2 số a,b chọn số nhỏ nhất gán cho UCLN.

Bước 3: Nếu hai số a và b chia hết cho UCLN thì



  1. Thực hiện bước 5.

Bước 4: Giảm UCLN một đơn vị và quay lại bước 3

Bước 5: In UCLN - Kết thúc.



Một thuật toán có các tính chất sau:

  • Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.

  • Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định.

  • Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau.

  • Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.

  • Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán.

Trình tự thực hiện các bước của thuật toán

Giải thuật được thiết kế theo ba cấu trúc suy luận cơ bản sau đây:



  1. Tuần tự (Sequential): Các công việc được thực hiện một cách tuần tự, công việc này nối tiếp công việc kia.

  2. Cấu trúc lựa chọn (Selection) : Lựa chọn một công việc để thực hiện căn cứ vào một điều kiện nào đó. Có một số dạng như sau:

    • Cấu trúc 1: Nếu < điều kiện> (đúng) thì thực hiện

    • Cấu trúc 2: Nếu < điều kiện> (đúng) thì thực hiện , ngược lại (điều kiện sai) thì thực hiện

    • Cấu trúc 3: Trường hợp < i> thực hiện

  1. Cấu trúc lặp (Repeating): Thực hiện lặp lại một công việc không hoặc nhiều lần căn cứ vào một điều kiện nào đó. Có hai dạng như sau:

    • Lặp xác định: là loại lặp mà khi viết chương trình, người lập trình đã xác định được công việc sẽ lặp bao nhiêu lần.

    • Lặp không xác định: là loại lặp mà khi viết chương trình người lập trình chưa xác định được công việc sẽ lặp bao nhiêu lần. Số lần lặp sẽ được xác định khi chương trình thực thi.

Biểu diễn thuật giải

Ngôn ngữ tự nhiên: Ngôn ngữ tự nhiên là ngôn ngữ của chúng ta đang sử dụng, chúng ta có thể sử dụng ngôn ngữ tự nhiên để mô tả giải thuật giống như các ví dụ ở trên.

Ví dụ: Ta có giải thuật giải phương trình bậc nhất dạng như sau:

Bước 1: Nhận giá trị của các tham số a, b

Bước 2: Xét giá trị của a xem có bằng 0 hay không?

Nếu a=0 thì làm bước 3, nếu a khác không thì làm bước 4.

Bước 3: (a bằng 0) Nếu b bằng 0 thì ta kết luận phương trình vô số nghiệm,

nếu b khác 0 thì ta kết luận phương trình vô nghiệm.

Bước 4: ( a khác 0) Ta kết luận phương trình có nghiệm x=-b/a



Lưu đồ thuật toán: Ngôn ngữ sơ đồ (lưu đồ) là một ngôn ngữ đặc biệt dùng để mô tả giải thuật bằng các sơ đồ hình khối. Mỗi khối qui định một hành động như mô tả ở hình trên. Ví dụ: So sánh 2 số.


Giả mã: (tiếng Anh: Pseudocode, xuất phát từ chữ pseudo và code) là một bản mô tả giải thuật ngắn gọn và không chính thức, trong đó sử dụng những quy ước có cấu trúc của một số ngôn ngữ lập trình (thường là Pascal) nhưng thường bỏ đi những chi tiết không cần thiết để giúp hiểu rõ giải thuật hơn.

Ví dụ: Thuật giải phương trình bậc 2

Vào: a,b,c

Ra: Kết luận về nghiệm

BEGIN


Delta: = b*b – 4*a*c;

If Delta=0 Then

Phương trình có nghiệm kép x=-b/(2*a);

else


begin

if Delta<0 then

Phương trình Vô nghiệm

Else


Begin

Phương trình có 2 nghiệm

x1=(-b+sqrt(Delte))/(2*a)

x2=(-b+sqrt(Delte))/(2*a)



end

end


END.

Một số ví dụ khác về thuật toán và biểu diễn thuật toán

Ví dụ 1: Cần viết chương trình cho máy tính sao cho khi thực hiện chương trình đó, máy tính yêu cầu người sử dụng chương trình nhập vào các số hạng của tổng (n); nhập vào dãy các số hạng ai của tổng. Sau đó, máy tính sẽ thực hiện việc tính tổng các số ai này và in kết quả của tổng tính được.

Yêu cầu: Tính tổng n số S=a1+ a2+a3+......+an .

Chi tiết giải thuật được mô tả bằng ngôn ngữ tự nhiên như sau:

- Bước 1: Nhập số các số hạng n.

- Bước 2: Cho S=0 (lưu trữ số 0 trong S)

- Bước 3: Cho i=1 (lưu trữ số 1 trong i)

- Bước 4: Kiểm tra nếu i<=n thì thực hiện bước 5, ngược lại thực hiện bước 8.

- Bước 5: Nhập ai

- Bước 6: Cho S=S+ai (lưu trữ giá trị S + ai trong S)

- Bước 7: Tăng i lên 1 đơn vị và quay lại bước 4.

- Bước 8: In S và kết thúc chương trình.

Ví dụ 2: Viết chương trình cho phép nhập vào 2 giá trị a, b mang ý nghĩa là các hệ số a, b của phương trình bậc nhất. Dựa vào các giá trị a, b đó cho biết nghiệm của phương trình bậc nhất ax + b = 0.

Mô tả giải thuật bằng ngôn ngữ tự nhiên:

- Bước 1: Nhập 2 số a và b

- Bước 2: Nếu a = 0 thì thực hiện bước 3, ngược lại thực hiện bước 4

- Bước 3: Nếu b=0 thì thông báo phương trình vô số nghiệm và kết thúc chương trình, ngược lại thông báo phương trình vô nghiệm và kết thúc chương trình.

- Bước 4: Thông báo nghiệm của phương trình là –b/a và kết thúc.

Ví dụ 3: Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt nhập vào n giá trị a1, a2,…,an. Hãy tìm và in ra giá trị lớn nhất trong n số a1, a2, …, an.

Mô tả giải thuật bằng ngôn ngữ tự nhiên:

- Bước 1: Nhập số n

- Bước 2: Nhập số thứ nhất a1

- Bước 3: Gán max=a1

- Bước 4: Gán i=2

- Bước 5: Nếu i<=n thì thực hiện bước 6, ngược lại thực hiện bước 9

- Bước 6: Nhập ai

- Bước 7: Nếu max < ai thì gán max=ai.

- Bước 8: Tăng i lên một đơn vị và quay lại bước 5

- Bước 9: In max - kết thúc

Ví dụ 4: Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt nhập vào n giá trị a1, a2,…,an. Sắp theo thứ tự tăng dần một dãy n số a1, a2,...an nói trên. Có rất nhiều giải thuật để giải quyết bài toán này. Phần trình bày dưới đây là một phương pháp.

Giả sử ta đã nhập vào máy dãy n số a1, a2,..., an. Việc sắp xếp dãy số này trải qua (n-1) lần:

  • Lần 1: So sánh phần tử đầu tiên với tất cả các phần tử đứng sau phần tử đầu tiên. Nếu có phần tử nào nhỏ hơn phần tử đầu tiên thì đổi chỗ phần tử đầu tiên với phần tử nhỏ hơn đó. Sau lần 1, ta được phần tử đầu tiên là phần tử nhỏ nhất.

  • Lần 2: So sánh phần tử thứ 2 với tất cả các phần tử đứng sau phần tử thứ 2. Nếu có phần tử nào nhỏ hơn phần tử thứ 2 thì đổi chỗ phần tử thứ 2 với phần tử nhỏ hơn đó. Sau lần 2, ta được phần tử đầu tiên và phần tử thứ 2 là đúng vị trí của nó khi sắp xếp.

  • …

  • Lần (n-1): So sánh phần tử thứ (n-1) với phần tử đứng sau phần tử (n-1) là phần tử thứ n. Nếu phần tử thứ n nhỏ hơn phần tử thứ (n-1) thì đổi chỗ 2 phần tử này. Sau lần thứ (n-1), ta được danh sách gồm n phần tử được sắp thứ tự.

Mô tả giải thuật bằng ngôn ngữ tự nhiên:

- Bước 1: Gán i=1

- Bước 2: Gán j=i+1

- Bước 3: Nếu i <=n-1 thì thực hiện bước 4, ngược lại thực hiện bước 8

- Bước 4: Nếu j <=n thì thực hiện bước 5, ngược lại thì thực hiện bước 7.

- Bước 5: Nếu ai > aj thì hoán đổi ai và aj cho nhau (nếu không thì thôi).

- Bước 6: Tăng j lên một đơn vị và quay lại bước 4

- Bước 7: Tăng i lên một đơn vị và quay lại bước 3

- Bước 8: In dãy số a1, a2,..., an - Kết thúc.

Giải thuật + Cấu trúc dữ liệu = Chương trình

Algorithms + Data Structures = Programs
Niklaus Emil Wirth

In 1975 he wrote the book "Algorithms + Data Structures = Programs", which gained wide recognition and is still useful today.



Biography

Wirth was born in Winterthur, Switzerland, in 1934. In 1959 he earned a degree in Electronics Engineering from the Swiss Federal Institute of Technology Zürich (ETH Zürich). In 1960 he earned an M.Sc. from Université Laval, Canada. Then in 1963 he was awarded a Ph.D.in EECS from the University of California, Berkeley, supervised by the computer designer pioneer Harry Huskey.

From 1963 to 1967 he served as assistant professor of Computer Science at Stanford University and again at the University of Zurich. Then in 1968 he became Professor of Informatics at ETH Zürich, taking two one-year sabbaticals at Xerox PARC in California (1976–1977 and 1984–1985). Wirth retired in 1999.

Programming languages

Wirth was the chief designer of the programming languages Euler, Algol W, Pascal, Modula, Modula-2, Oberon, Oberon-2, and Oberon-07 . He was also a major part of the design and implementation team for the Lilith and Oberon operating systems, and for the Lola digital hardware design and simulation system. He received the ACM Turing Award for the development of these languages and in 1994 he was inducted as a Fellow of the ACM. He designed the simple programming language PL/0 to illustrate compiler design. It has formed the basis for many university compiler design classes.


4. Chương trình


Định nghĩa

  • Chương trình máy tính: là một tập hợp những câu lệnh được viết bằng một ngôn ngữ lập trình theo một trật tự xác định nhằm tự động thực hiện một số nhiệm vụ hoặc chức năng hoặc giải quyết một bài toán nào đó.

  • Là một biểu hiển cụ thể của một giải thuật trên một ngôn ngữ lập trình nào đó cùng với những mô tả về cấu trúc dữ liệu mô tả đầu vào, đầu ra của bài toán cần giải quyết.

Ví dụ 1: Chương trình giải phương trình bậc 2 bằng Pascal

Ví dụ 2: Chương trình giải phương trình bậc 2 bằng C

Tạo ra chương trình máy tính bằng cách nào???

Каталог: files -> FileMonHoc
FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM
FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số
FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC
FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn
FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG
FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG
FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon
FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam

tải về 1.56 Mb.

Chia sẻ với bạn bè của bạn:
1   2   3   4   5   6   7   8   9   ...   29



Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý
    Quê hương
BÁO CÁO
Tài liệu