Bài toán khoa học kỹ thuật và kinh tế bằng ngôn ngữ Pascal - 101 thuật toán và chương trình: Phần 1

Chia sẻ: Lê Thị Na | Ngày: | Loại File: PDF | Số trang:140

Thêm vào BST

Báo xấu

122
lượt xem 35
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 Tài liệu 101 thuật toán và chương trình - Bài toán khoa học kỹ thuật và kinh tế bằng ngôn ngữ Pascal gồm nội dung 3 chương đầu Tài liệu, trình bày những khái niệm chung về thuật toán, cách mô tả bài toán bằng ngôn ngữ máy tính; 101 bài toán; phân tích các thuật toán và lưu đồ của 101 bài toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán khoa học kỹ thuật và kinh tế bằng ngôn ngữ Pascal - 101 thuật toán và chương trình: Phần 1

ĐẠI HỌC VINH THI VIÊN DC NH - T R Ầ N KHẮC TUẤN 005.133 LE-D/93 DT. 007690 ƯÂT TOÁN i/À CHƯƠNG TRÌNH BÀI TOÁN KHOA HỌC KỸ THUẬT VÀ KINH T Ể BẰNG NGÔN NGỮ P A S C A L
LÈ VẰ N DOANH T R Â N K H Ắ C TUẤN 101 T H U Ậ T T O Á N V À CHƯƠNG TRÌNH Bài toán khoa học kỹ thuật và kinh tễ BẰNG N G Ô N NGỮ P A S C A L NHÀ XUẤT BẤN KHOA HỌC VÀ KỸ THUẬT HÀ NỘI - 1993
Chịu trách nhiệm xuất bàn: Pgs, Pts T Ồ D Ă N G HÀI Biển tập: TIP.N K H A N G - K I M A N H Trình bày: M I N H TÚNG Sửa bản in: THÌN ì l i ' N i Vẽ bìa: HUY TI'ẤN In 2 500 b ả n k h ổ 14.5 X 20,5 em. t ạ i N h à in s á c h K H K ' 1 S ố X B : 2 1 1 K H / K H K T do C ụ c X B c ấ p n g à y Vò- 3 - ^ 9 9 3 I n x o n g và nộp lưu chiểu t h á n g 4 n ă m 1993.
MÚC LỤC Trang Lòi l ự a 5 Lòi giòi thiêu 7 Chuưtiịi ì. Những khái n i ệ m c h u n g v ề t h u ậ t toán. c á c h m ô t ả b à i t o á n b ằ n g ngôn ngữ m á y tính 11 1.1. Thuật toán 11 1.2. Mô tá thuật t o á n b ằ n g lưu đ ồ 13 1.3. M ộ t s ố ví d ụ v ê xây dựng lưu đ ồ 14 ( hưư/iy 2. 101 bài t o á n 27 2.1 Dại s ố (từ bài 10 đến bài 28) 27 2.2 V e c t ơ , ma trận. hệ phương trình đại s ố (từ bài 29 đ ế n bài 37) 28 2.3 H à m số (tứ bài 38 đ ế n 48) 29 2.4 Đa thúc và nội suy đ a thức (từ bài 49 đ ế n bài 59) 29 2.5 Đ ạ o hàm số (tu bài 6 0 đ ế n bài 65) 30 2.6 Tích phân s ố (từ bài 6 6 đ ế n bài 69) 30 2.7 Giải phương trình phi t u y ế n (từ bài 70 đ ế n bài 72) 31 2.8 Tối ưu hóa (từ bài 73 đ ế n bài 75) 31 2.9 Giải phương trình vi phân (từ bài 76 đ ế n bài 79) 31 210 X á c suất thống kê (từ bài 8 0 đ ế n bài 83) 31 2.11 Một s ổ bài t o á n quản lý v à x ù lý v ă n b ả n (từ bài 84 đ ế n 91) 32 2 12 M ộ t s ố bài t o á n k t h u ậ t (từ bài 92 đ ế n bài 101) 32 Chtrmnj .i. Phân tích các t h u ậ t t o á n v à lưu đ ồ của 101 bài t o á n 39 3.1 Dại s ố 39 3.2 V e c t đ , ma trận, hệ phương trình đ ạ i s ố 57 3.3 H à m s ổ 66 3.4 Đa thức và nội suy đ a thức 75 3.5 Đạo h à m s ố 89 3.6 Tích phân s ố 94 3.7 Giải phương trình phi t u y ế n 99 3.8 Tối ưu hóa 102 3.9 Giải phương trinh vi phân 108
3.10 X á c s u ấ t t h ố n g k ê lít 3.11 M ộ t s ố b à i t o á n q u ả n l ý v à x ử l ý v ă n b ả n 121 3.12 M ộ t s á b à i t o á n k ỹ t h u ậ t ->24 Chương -í. 101 c h ư ơ n g t r ì n h 139 M ộ t s ố ví dụ 139 Oại s ố 147 V e c t đ , m a t r ậ n , h ệ p h ư o n g trình đ ạ i s ố t u y ế n tính 162 Hàm số 174 Đ a thức 186 Đạo hàm sổ 203 Tích phân sá 208 Giải phương trình phi t u y ế n 214 T ố i ưu h ó a 219 Ọ hương t r ì n h vi p h â n 223 Xác suất thống kê 230 X ơ lý v ă n b ả n q u á n l ý 235 M ộ t s ố bài toán k ỹ thuật 254 T à i liệu t h a m k h ả o 268 4
LÒI TỰA Ngày nay tin học đã thâm nhập vào tất cả mọi hoạt động của xã hội loài người và máy tính diện tủ trỏ thành một công cụ dắc lực không chỉ giảm nhẹ lao động (kề cả lao dộng có trí tuệ) mà còn giúp thêm cho con người những năng lực mặi mà trưặc dãy chúng ta khó hỉnh dung được. Ỏ Việt Nam máy tính, đặc biệt máy ui tính trong những năm gần đây dã quen thuộc vặi mọi người. Bưặc đàu tin học dã được dưa vào các trường trung học, các trường đại học nhầm di tói phổ cập tin học cho toàn xã hội. Số lượng máy tính ngày một nhiề u và ta có thể gặp khắp mọi nơi. Do vậy một vấn dè lán được đặt ra là làm thế nào dể khai thác hét công suất các máy tính và làm thế nào để tin học thực sự hữu ích cho mọi người. Dề làm được diêu này trưặc hết phải phổ cập việc đào tạo tin học, không những trong nhà trường mà cả toàn xã hội. Quyến sách "loi thuật toán và chương trình" là một trong những tài liệu tối giúp cho bạn đọc mái bắt đàu làm quen vặi tin học. Mặt khác dây là một bộ bài tập tương đói đầy đủ tạo cơ sà ban đầu cho những ai muốn di sâu vào giải các bài toán ve khoa học kỹ thuật và kinh tế trong quá trinh công tác của minh. Các lời giải cùa các bài tập trong quyển sách này khá phong phú L Ờ chuẩn xác đòng thời đáy là những bài tập máu rất tốt cho những ai gặp các bài toán tương tự. Chúng tôi xin trăn trọng giặi thiệu bạn đọc cuốn sách này vặi mong muốn góp phàn thúc dầy quá trình tin học hóa và phổ cập tin học ỏ Việt Nam. Gs. Ts. NfỊU\ễn Xuân Quỳnh 5
L Ờ I G I Ớ I THIỆU Ván dề quan trọng nhất của tin học ứng dụng là biết cách sử dụng máy tính trong các lỉnh vực chuyên môn khác nhau. Để làm được việc dó ngoài việc nấm vững các ngôn ngữ lập trình thông dụng, người sử dụng phải biết cách chuyề n các bài toán thuộc linh vực chuyên môn của mình sang các ngôn ngữ thuật toán, nghía là cỹn nắm vững cách phân tích các thuật toán, các phương pháp số. Cuốn sách "loi thuật toán và chương trình các bài toán khoa học kỹ thuật và kinh tế bàng ngôn ngữ TURBO-PASCAL" nhỹm đáp ứng các yêu càu dó, giúp cho bạn đọc có thể dễ dàng lập trình rúc bài toán thuộc lỉnh vực chuyên môn cụ thể. Cuốn sách cũng có ích cho sinh viên các trường dại học và cao dâng, các cán bộ kỹ thuật và kinh tế, để nâng cao trình độ lập trình. Có thể coi đây là tài liệu thực hành về kỹ thuật lập trình, đòng thời nhiề u bài trong tài liệu này có thể coi là cẩm nang lập trình bàng ngôn ngữ PASCAL. Nội dung của cuốn sách gôm bón chương. Chương Ì là phỹn mở đàu, giói thiệu sơ lược vẽ thuật toán, cách chuyển các bài toán cụ thể sang ngôn ngữ máy tính. Chương 2 gôm loi bài toán xép theo loại bai toán cụ thề : dại số, hàm'số, vectơ, ma trận và hệ phương trình tuyến tính, đa thức, đạo hàm số, tích phân số, các bài toán phi tuyến, bài toán tối ưu, xác suất, bài toán kinh tế và cuối cùng là một số bài toán khoa học và kỹ thuật cụ thể. Chương 3 là phỹn chủ yếu, phân tích, giới thiệu các thuật toán, các phương pháp số đề giải loi bài toán trong chương 2. Chương 4 là loi chương trình viết bàng ngôn ngữ TƯRBO-PASCAL và đã chạy thủ có kết quả tại phòng tính toán KHOA THỈÉT BỊ DIỆN TRƯỜNG DẠI HỌC BÁCH KHOA HÀ NỘI. 7
Cuốn sách này là phàn đàu của bộ sách gồm các ứng dụng cùa tin học trong khoa học kỹ thuật. Chúng tôi hy vọng sắp tới sẽ cho ra mắt độc giả phần tiếp theo với các bài toán cụ thề thông dụng hiện nay. VÌ trình độ và thời gian có hạn cuốn sách không tránh khợi sai sót. Rất mong bạn đọc góp ý dể tài liệu được hoàn chỉnh, chúng tôi xin chăn thành cảm ơn. Nếu bạn dọc có yêu cầu vè dúi mèm chứa chương trình xin liên hệ với PHÒNG TÍNH TOÁN KHOA THIẾT BỊ ĐIỆN TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI. Các tác giả 8
C Á C H S ử DỤNG QUYỂN SÁCH NÀY B E ữ l N ( ) Bạn háy dọc kỹ chương 1 và các bài toán chương 2 Bạn thú tìm cách giải và vẽ .lưu dò tính toán Dùng Sai Bạn tìm lời giải ở chương 3 ĩ Bạn thử viết chương trình cho bài toán Bạn hãy tìm chương trình mẫu trong chương 4 Bạn hãy chạy chương trình trên máy vi tính 3 ( END )
CHƯƠNG Ì NHỮNG KHÁI NIỆM C H U N G VỀ THUẬT TOÁN, CÁCH MÔ TÀ BÀI TOÁN BẰNG NGÔN NGỮ MÁY TÍNH §1.1. Thuật toán Ta đã làm quen với khái niệm về thuật toán trong giáo trình toán học và các giáo trinh khác. Thuật toán giải phương trình bậc hai, giải hệ phương trình đã quen biết trong giáo trình toán phổ thông trung học T h u â t toán được hiểu là tập hợp các quy tắc dùng cho một lớp bà' toán nào đó để từ các số liệu ban đầu qua một quá trình thao tác dẫn đến kết quả xác định. Khái n i ệ m về t h u ậ t t o á n đ ầ u tiên do n h à toán học À Rập Kharezmi nêu ra từ cuối t h ế kỷ thủ 8 đàu thê ký thủ 9 khi đưa ra các quy tác đầu tiên về tính số học. Con người trong các hoạt động của mình thường phải sử 'dụng những thuật toán để giải quyết các công việc cụ thể. Bất kỳ một hình thủc lao động chân tay nào cũng gồm một số thao tác cụ t h ể theo một t r ậ t tự nhất định, ta gọi lao động chân tay là hoạt động theo thuật toán. Lao động trí óc là lao động sáng tạo, tuy vậy cũng có t h ể thuật toán hóa lao động trí óc. Ví dụ người ta có t h ể xây dựng thuật toán sáng tác nhạc, làm thơ trên máy tính v.v. Tuy nhiên nhiều người phủ nhận tính thuật toán của lao động nghệ thuật. Ta hiểu quá trinh thuật toán hóa lao động s á n g tạo là một quá trình t i ệ m cận. Những đặc t r ư n g cơ bản của thuật toán là: 1) Tính tống quát: thuật toán không đề cập chỉ một bài toán riêng lẻ mà bao hàm một lớp bài toán cùng một kiểu; 2) Có giới hạn: quá trinh biến đổi từ thông t i n ban đ ầ u đến k ế t quả cuối cùng qua một số giới hạn các biến đổi; li
3) Tỉnh duy nhất: t o à n bộ q u á t r ì n h b i ế n đ ổ i , c ũ n g n h ư t r ậ t t ự t h ự c h i ệ n p h ả i được x á c đ ị n h v à là duy n h ấ t . N h ư v ậ y k h i d ù n g t h u ậ t t o á n c ù n g m ộ t t i n t ứ c ban đ ầ u p h ả i cho c ù n g m ộ t k ế t quả. T r o n g t h u ậ t t o á n ở m ỗ i g i a i đ o ạ n p h ả i n ê u c h í n h x á c c á c bước t i ế p theo, có nghĩa là t h ứ t ự t h ự c h i ệ n , c á c thao t á c v à q u y ế t đ ị n h p h ả i được quy đ ị n h r õ r à n g . Theo c ấ u t r ú c ta có t h ể p h â n l o ạ i t h u ậ t t o á n n h ư sau: - thuật toán không phân nhánh; - t h u ậ t t o á n có p h â n n h á n h ; - t h u ậ t t o á n theo chu t r ì n h c ó bước l ủ p x á c đ ị n h v à c ó bước l ậ p k h ô n g xác định. T h u ậ t t o á n k h ô n g p h â n n h á n h là t h u ậ t t o á n đ ơ n g i ả n n h ấ t . T r o n g t h ự c t ế t h ư ờ n g gủp t h u ậ t t o á n p h â n n h á n h theo c á c đ i ề u k i ệ n so s á n h đ ú n g hoủc sai. P h ổ b i ế n n h ấ t t r o n g c á c b à i t o á n t h ự c t ế là t h u ậ t t o á n g ồ m n h i ề u chu t r ì n h , theo n h i ề u n h á n h , đ ó là đủc t r ư n g của t h u ậ t t o á n g i ả i c á c bài t o á n khoa học k ỹ t h u ậ t . T r ì n h t ự g i ả i bài t o á n t r ê n m á y t í n h t h ư ờ n g theo c á c bước sau: Ì - D ủ t b à i t o á n và x â y d ự n g m ô h ì n h t o á n của b à i t o á n t h ự c t ế . Giai đ o ạ n n à y bao g ồ m v i ệ c b i ế u d i ễ n b à i t o á n t h ự c t ế b à n g c á c b i ể u t h ứ c t o á n học, x á c đ ị n h c á c r à n g buộc, c á c đ i ề u k i ệ n ban đ ầ u , g i ớ i h ạ n của nghiệm; 2- C h ọ n p h ư ơ n g p h á p số t h í c h hợp. D ể g i ả i c á c m ô h ỉ n h t o á n x â y d ự n g t r o n g bước Ì c ầ n chọn m ộ t t r o n g c á c p h ư ơ n g p h á p số theo c á c t i ê u c h u ẩ n sau đ â y : đ ộ c h í n h x á c cao, t ố c đ ộ t í n h n h a n h , q u á t r ì n h tính đơn giản V . V . ; 3- D i ễ n t ả t h u ậ t t o á n b à n g lưu đ ồ . L ư u đĩ h ể h i ệ n rõ r à n g các bước t í n h q u a n t r ọ n g v à c á c đ i ề u k i ệ n đ ể t h u được k ế t q u ả c u ố i c ù n g . L ư u đ ồ là c á c h b i ể u d i ễ n b ằ n g đ ồ t h ị t o à n bộ t h u ậ t t o á n . X â y d ự n g l ư u đ ò c h í n h x á c l à đ ả m bảo 90% k ế t q u ả t í n h t o á n ; 4- V i ế t c h ư ơ n g t r ì n h : l à h ệ t h ố n g c á c c â u l ệ n h có cấu t r ú c theo l ư u đ ò . N g ô n n g ữ l ậ p t r ì n h P A S C A L là n g ô n n g ữ c ó c ấ u t r ú c rõ r à n g đ á p ứ n g được c á c đ ò i h ỏ i phức t ạ p của c á c bài t o á n khoa học k ỹ t h u ậ t v à q u ả n lý k i n h t ế ; 5- Chạy c h ư ơ n g t r ì n h v à p h â n t í c h k ế t q u ả . 12
§1.2. MÔ tả thuật toán bằng lưu đồ Trước khi viết chương trình cần phân tích một cách cặn kẽ các tình huống co' thế xảy ra trong quá trình tính toán. Dể mô tả quá trình tính toán một cách hệ thống và rõ ràng người ta thường thể hiện thuật toán bằng lưu đồ, đó là sự biểu diễn bằng đò thị của toàn bộ quá trình tính toán. Việc vẽ lưu đồ không nhứng giúp cho quá trình thảo chương dể dàng mà còn giúp ta phát hiện sai sót trong chương trình. Trong các bài toán đơn giản có thể bỏ qua giai đoạn này, nhưng trong các bài toán phức tạp nhất thiết phải lập lưu đô tính toán. Các ký hiệu thường dùng trong lưu đò cho trong bảng 1.1. Bàng LI. C á c ký hiệu t r i n lưu d í TT Tên khối Ì Ký hiệu Ý nghĩa ỉ c 3, 1 Khối mỏ đầu hoặc Dùng mờ đầu hoặc kết thúc kết thúc chương trình Đưa s ố liệu vào hoặc 2 Khái vào - - r a in kết quả Biểu diễn các công thức 3 Khối tính toán tính toán và thay dổi giá tri cùa các biến 4 5 Khối điều kiện Chưcng trình con o < > Dùng để phân nhánh chương trình Dùng để gọi các chư ng trình con C h ỉ hư ng truyền thông 6 Mũi tên tin, liên hệ các khái 13
§ 1 . 3 . Một SỐ vi dụ về xây dựng lưu đồ 13.1. Thuật toán không phân nhánh Để làm ví dụ cho thuật toán không phân n h á n h ta nêu sơ đồ tính toán một số biểu thức sau: Ví dụ 1. Cho A = X + ỵ 2 z B = X + y + A c = xy + A - B 2 X, y € R. Xác định thuật t o á n và lưu đồ tính A, B, c. Giải. Thông tin ban đầu là X, ỵ đã cho, còn thông t i n cuối cùng cần tỉm là giá trị A, B, c. Ta thấy rằng đ ể tính A chỉ càn số liệu ban đ ầ u là X và y, t i ế p theo đ ể t í n h B c ầ n sử dụng X và ỵ và cợ kết quợ tính V. BEGIN 0 A. Còn để tính c cần cợ X, y Dọc X, ỵ v à A, B. T h ứ t ự t í n h t o á n không phợi là bất kỳ mà đầu A :- X 2 + y 2 tiên phợi tính A, sau đó mới tính B và c. Lưu đồ được vẽ t r ẽ n hình 1.1. Tính tổng q u á t B := X + y + A của thuật toán t h ể hiện ở chỗ nó dùng đ ể tính với bất kỳ giá trị của X, y e R. Tính có giới c := xy + A - hạn t h ể hiện ở chỗ qua một số ị hữu hạn biến đổi ta nhận được In A, B, c kết quợ A, B, c. Còn tính duy nhất là với hai giá trị X và ỵ END nhất định thì kết quợ A, B, c là duy nhất. Hình 1.1 1.3.2. Thuật toán có phân nhánh Thuật toán có phân nhánh được đặc t r ư n g bằng các quyết định của khối điều kiện. Tùy theo kết quợ đúng hoặc sai của khối điêu 14
kiện chương trình được phân chia theo các nhánh khác nhau. Ta xét thuật t o á n phân n h á n h qua một số ví dụ đơn giản. Vi dụ 2. T ỉ m giá trị MAX trong ba giá trị của số thực A, B, c. Giải. T h ô n g t i n ban đ ầ u là giá trị của A, B, c, rõ r à n g rằng bất. kỳ số A hoặc B, c có t h ọ là sò lớn nhất. Đê* t ì m số lớn nhất trong các số A, B, c đàu tiên ta so sánh các số với nhau. Nếu A >B và A >c thì MAX := A. N ế u A>B còn A á c thì M A X := c. N ế u A < B và B < c ta có MAX := c. Nếu A < B và B > c thì MAX : = B. Lưu đồ của thuật toán so sánh này cho t r ê n hình 1.2. ( BEGIN ) ị Dọc A, B, c J ( ) i/ìn/i /.2 15
Ví dụ 3. T í n h g i á t r ị c ủ a h à m số: 'x 3 + y v ớ i 0 < X - y < 10 i 1 /Ky) = X 2 + ý v ớ i X - y < 0, y > 0 Oe - ;y) v ớ i c á c t r ư ờ n g hợp còn l ạ i X, y e R Giải. G i á t r ị h à m s ố f(x, y) n h ậ n đ ư ợ c 3 b i ể u t h ứ c g i ả i t í c h t ù y t h e o c á c đ i ề u k i ệ n c ủ a X v à y. Đ ầ u t i ê n t a so s á n h X - ỵ < 0 t i ế p t h e o n ế u y > 0 đ ú n g t h ì /Xx, = X + 7 , n g ư ợ c l ạ i f(x, y) = (x - 2 y) . T r o n g t r ư ờ n g h ợ p X - y > 0 c ầ n so s á n h t i ế p đ i ề u k i ệ n X - y < 10, n ế u đ ú n g t h ì f(x, y) = * 3 3 + y , n g ư ợ c l ạ i /•(*, y) = ịx - 2 y) . L ư u đ ồ c ủ a t h u ậ t t o á n t r ê n cho t r ê n h ỉ n h 1.3. > fr, 4 < 1 2 f : = ( x - y) C END Hình 1.3 16
Ví dụ 4. Tìm nghiệm của phương trình bậc hai ax2 + bx + c = 0, a, 6, c E R . Già/. Thông tin ban đầu là các hệ số a, ờ, c còn kết quả là nghiệm jCj, x Nếu a * 0 là phương trình bậc 2, còn a = 0 là phương trình 1 bậc n h ấ t X ~-clb. Đ ể tìm nghiệm đầu tiên ta tính biệt thức A = b - 4ac. 2 - b + VÃ - b - \TK Nếu A > 0 có 2 nghiệm thực Xj = *2 = 2a " 2a còn ngược lại cố 2 nghiệm phức liên hợp là phần thực b V^~Ẵ Re(x) = - — và phần ào Im(x) = - 2a 2a Lưu đồ của bài toán cho trên hỉnh 1.4. (BEGIN) Ị>c ạ, ồ, c y sai In hai nghiệm f In hai nghiêm Ì* phương trình t h ự c X j , x-ị phức ReCxJ, Im(x) bác nhất X Hình 1.4 17
1.3.3. Chu trình có bước lặp xác định Trong nhiều bài toán khoa học kỹ thuật t h ư ờ n g gặp các thuật toán tính lặp theo một chu trình có bước xác định, sau ra l ầ n t h ự c hiện quá trình lặp kết thúc. D ể thực h i ệ n q u á t r i n h tính lặp Hình l.Sa t h ư ờ n g d ù n g bộ đếm. Giá trị ban đầu của biến đếm nguyên ì := Ì và sau mỗi l ầ n lặp biến đếm được t ă n g thêm một đơn vị í = í + 1. Sơ đồ chu trình có bước lặp xác định cho t r ê n hình Lòa. Trong nhiều bài toán có t h ể gặp nhiều chu t r ì n h lồng vào nhau. Chú ý rạng các chu trình có t h ể lồng vào nhau n h ư n g không được giao nhau. Hình 1.5.b minh họa một số chu trình lòng vào nhau. / É • >