Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Giới thiệu - Sơ đồ - Đào Nam Anh

Data Structure and Algorithm 1 DATA STRUCTURE AND ALGORITHM FLOWCHARTS CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Dr. Dao Nam Anh Data Structure and Algorithm 2 Resource - Reference Slides of Achmad Yani (Electrical Engineering Department, Gadjah Mada University), and Rasime Uyguroğlu (Electrical & Electronic Eng.Dept, Eastern Mediterranean University) edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. Data Structure and Algorithm 3 Symbol Bắt đầu hoặc kết thúc Dữ liệu đầu vào hoặc đầu ra Một việc Sự lựa chọn đúng sai Một việc đã được xác định trước Data Structure and Algorithm 4 The three basic control structures Các thành phần cơ bản Data Structure and Algorithm 5 1. Sequence – Nối tiếp Statemement a Statemement b Statemement c Data Structure and Algorithm 6 2. Selection – Lựa chọn Condition p? Statemement a Statemement b T F Data Structure and Algorithm 7 2. Selection – Lựa chọn Condition p? Statemement a T F Data Structure and Algorithm 8 3. Repetition – Lặp lại Condition p? Statemement block T F Data Structure and Algorithm 9 Ví dụ 1. Cộng 3 số
Một chương trình A cần đọc 3 con số, cộng chúng với nhau và in ra kết quả Data Structure and Algorithm 10 • Defining diagram – Thiết kế sơ đồ Input Đầu vào Processing Thực hiện Output Kết quả Số thứ 1 Số thứ 2 Số thứ 3 Đọc 2 con số Cộng vào In tổng Tổng Data Structure and Algorithm 11 Solution Algorithm – Giải thuật Add numbers to total Read Number1 Number2 Number3 Print total Start Stop Data Structure and Algorithm 12 Ví dụ 2. Tìm nhiệt độ trung bình • Một chương trình yêu cầu nhập trên màn hình nhiệt độ cao nhất và thấp nhất trong ngày. Sau đó tính và hiện trên màn hình nhiệt độ trung bình. • A program is required to prompt the terminal operator for the maximum and minimum temperature readings on a particular day, and calculate and display to the screen the average temperature, calculated by (maximum temperature + minimum temperature)/2. Data Structure and Algorithm 13 • Defining diagram Input Processing Output Max_temp Min_temp Prompt for temperatures Get temperatures Calculate average temperature Display average temperature Avg_temp Data Structure and Algorithm 14 Solution Algorithm Avg_temp= (Max_temp-Min_temp)/2 Read Max_temp Min_temp Print Avg_temp Start Stop Data Structure and Algorithm 15 Ví dụ 3 Tính thời gian dọn vườn • Một chương trình yêu cầu nhập chiều dài, chiều rộng mảnh đất, chiều dài, chiều rộng ngôi nhà xây trên đó. Sau đó tính và hiện trên màn hình thời gian cần thiết để cắt cỏ xung quanh ngôi nhà, theo tốc độ cắt cỏ m2/1h cho trước. • A program is required to read from the screen the lenght and widht of a rectangular house block, and the lenght and width of the rectangular house that has been built on the block. The algorithm should then compute and display the mowing time required to cut the grass around the house, at the rate of two square metres per minute. Data Structure and Algorithm 16 • Defining diagram Input Processing Output Block_lenght Block_width House_lenght House_width Prompt for block measurements Get block measurements Prompt for house measurements Get house measurements Calculate mowing area Calculate mowing time Mowing_time Data Structure and Algorithm 17 Solution Algorithm Time = Read Print Time Start Stop Data Structure and Algorithm 18 Flowchart and the selection control structure Lựa chọn Data Structure and Algorithm 19 Simple IF statement Account_ balance < $300? Service_charge = $5 Service_charge = $2 T F Data Structure and Algorithm 20 Null ELSE statement Student_ attendance = P/T? Increment part_time_count T F Data Structure and Algorithm 21 Combined IF statement Student = P/T AND Gender = F ? Increment Female_part_time_count T F Data Structure and Algorithm 22 Nested IF statement Increment Counter_A Record Code =`A‘ ? Increment Counter_B Increment Counter_C Increment Error_counter Record Code =`A‘ ? Record Code =`A‘ ? T T T F F F Data Structure and Algorithm 23 Ví dụ 4. Đọc ký tự • Một chương trình đọc trên màn hình 3 ký tự, sau đó sắp xếp theo thứ tự, và hiện lên màn hình • Design an algorithm that will prompt a terminal operator for three characters, accept those characters as input, sort them into ascending sequence and output them to the screen. Data Structure and Algorithm 24 • Defining diagram Input Processing Output Char_1 Char_2 Char_3 Prompt for characters Accept three characters Sort three characters Output three characters Char_1 Char_2 Char_3 Data Structure and Algorithm 25 Solution Algorithm ? Data Structure and Algorithm 26 Case Structure Case Of variable Statement_a Statement_b Statement_c Statement_d Value 1 Value 2 Value 3 Value 4 Data Structure and Algorithm 27 Data Structure and Algorithm 28 Flowchart and Array Mảng • Một chương trình yêu cầu nhập 18 điểm thi môn toán cao cấp, tính điểm trung bình, sau đó hiện lên màn hình tất cả các điểm, đồng thời hiện điểm trung bình • Design a program that will prompt for and receive 18 examination scores from a mathematics test, compute the class average, and display all the scores and the class average to the screen. Data Structure and Algorithm 29 • Defining diagram Input Processing Output 18 điểm thi Nhập các điểm Lưu các điểm vào mảng Tính trung bình Hiển thị các điểm Hiển thị điểm trung bình 18 điểm thi Điểm trung bình Data Structure and Algorithm 30 Control Structures required Cấu trúc mảng và vòng lặp 1. Một mảng lưu điểm - scores 2. Index – xác định vị trí các phần tử của mảng 3. Vòng lặp DO nhận điểm 4. Vòng lặp DO hiển thị điểm Data Structure and Algorithm 31 Solution Algorithm Start Total_score = zero I = 1 Add scores(I) to Total score I = I + 1 Calculate average I = I + 1 Prompt and get Scores (I) I = 1 I <= 18 ? Display Scores (I) I <= 18 ? Display average Stop T F T F Data Structure and Algorithm 32 Flowchart and Module Thiết kế chương trình, nhập 3 chữ cái, và sắp xếp, Hiển thị lên màn hình. Chương trình cư tiếp tục nếu vẫn còn tiếp tục nhập các chữ cái dạng `XXX` Design a solution algorithm that will prompt a terminal operator for three characters, accept those characters as input, sort them into ascending sequence and output them to the screen. The algorithm is to continue to read characters until ´XXX`is entered. Data Structure and Algorithm 33 • Defining diagram Input Processing Output Char_1 Char_2 Char_3 Prompt for characters Accept three characters Sort three characters Output three characters Char_1 Char_2 Char_3 Data Structure and Algorithm 34 Hierarchy chart Process_three_ characters Sort_three_ characters Data Structure and Algorithm 35 Process_three_characters Start Prompt For characters Sort_ Three_ characters Outpur characters Get characters Prompt For characters Get characters Stop Characters NOT = xxx ?F T Data Structure and Algorithm 36 Sort_three_characters Start Char_2 > Char_3 ? Char_1 > Char_2 ? Char_1 > Char_2 ? Swap Char_2, Char_3 Swap Char_1, Char_2 Swap Char_1, Char_2 Stop T F T T F F Data Structure and Algorithm 37 Bài tập: Tính lương Một chương trình yêu cầu nhập mã số nhân viên, lương giờ, số giờ đã làm trong tuần. Sau đó kiểm tra lương giờ, số giờ. Nếu đúng sẽ tính lương của tuần, và hiển thị. A program is required by a company to read an employee‘s number, pay rate and the number of hours worked in a week. The program is then to validate the pay rate and the hours worked fields and, if valid, compute the employee‘s weekly pay and print it along with the input data. Data Structure and Algorithm 38 Bài tập: Tính lương Kiểm tra: Số giờ làm việc tối đa trong 1 tuần là 60 giờ. Nếu lương giờ nằm ngoài phạm vi cho phép, chương trình báo lỗi và không tính. Tính lương tuần: Là tích của lương giờ với số giờ. Nếu số giờ lớn hơn 35: làm ngoài giờ, được tính thêm ½ mức lương giờ Data Structure and Algorithm 39 • Defining diagram Input Processing Output Emp_no Pay_rate Hrs_worked Read employee details Validate input fields Calculate employee pay Print employee details Emp_no Pay_rate Hrs_worked Emp_weekly_pay Error_message Data Structure and Algorithm 40 Hierarchy chart Compute_employee_pay Calculate_ Employee_pay Validate_input_ fields Read_employee_ details Employee_details Print_employee_ details Valid_input_ fields Data Structure and Algorithm 41 Solution Algorithm Data Structure and Algorithm 42 Compute_employee_pay Start Read_ Employee_ details More Recods? Validate_ Input: fields Stop Fields Valid? Calculate_ Employee_ pay Print_ Employee_ details Read_ Employee_ details Data Structure and Algorithm 43 Validate_input_fields Start Valid_input_ fields = T Pay_rate > $ 25 Print Error message Valid_ Input_ Fields = F Hours_ Worked > 60 Print Error message Valid_ Input_ Fields = T Stop Data Structure and Algorithm 44 Bài tập 1 Thiết kế chương trình nhập các cạnh hình chữ nhật. Tính và hiển thị diện tích hình chữ nhật Data Structure and Algorithm 45 Bài tập 2 • Viết chương trình giải phương trình bậc hai • Gợi ý: tính Delta d = sqrt ( ), và hai nghiệm là: x1 = (–b + d)/2a, x2 = (–b – d)/2a 2 0ax bx c+ + = 2 4b ac− Data Structure and Algorithm 46 Bài tập 1 Algorithm • Step 1: Input W,L • Step 2: A ← L x W • Step 3: Print A START Input W, L A ← L x W STOP Print A Data Structure and Algorithm 47 Bài tập 2 • Viết chương trình giải phương trình bậc hai • Gợi ý: tính Delta d = sqrt ( ), và hai nghiệm là: x1 = (–b + d)/2a, x2 = (–b – d)/2a 2 0ax bx c+ + = 2 4b ac− Data Structure and Algorithm 48 Bài tập 2 Pseudocode: • Input the coefficients (a, b, c) of the quadratic equation • Calculate d • Calculate x1 • Calculate x2 • Print x1 and x2 Data Structure and Algorithm 49 Bài tập 3 • Chương trình nhập 2 số, tìm số lớn nhất và hiển thị số đó • Write an algorithm that reads two values, determines the largest value and prints the largest value with an identifying message. ALGORITHM Step 1: Input VALUE1, VALUE2 Step 2: if (VALUE1 > VALUE2) then MAX ← VALUE1 else MAX ← VALUE2 endif Step 3: Print “The largest value is”, MAX Data Structure and Algorithm 50 Bài tập 2 • Algorithm: • Step 1: Input a, b, c • Step 2: d← sqrt ( ) • Step 3: x1 ← (–b + d) / (2 x a) • Step 4: x2 ← (–b – d) / (2 x a) • Step 5: Print x1, x2 START Input a, b, c d ← sqrt(b x b – 4 x a x c) STOP x1←(–b + d) / (2 x a) X2← (–b – d) / (2 x a) 4b b a c× − × × Print x1 ,x2 Data Structure and Algorithm 51 Bài tập 3 • Chương trình nhập 2 số, tìm số lớn nhất và hiển thị số đó • Write an algorithm that reads two values, determines the largest value and prints the largest value with an identifying message. ALGORITHM Step 1: Input VALUE1, VALUE2 Step 2: if (VALUE1 > VALUE2) then MAX ← VALUE1 else MAX ← VALUE2 endif Step 3: Print “The largest value is”, MAX Data Structure and Algorithm 52 Bài tập 4 • Chương trình nhập 3 số, tìm số lớn nhất và hiển thị số đó Data Structure and Algorithm 53 Bài tập 3 MAX ← VALUE1 STOP Y N START Input VALUE1,VALUE2 MAX ← VALUE2 is VALUE1>VALUE2 Print “The largest value is”, MAX Data Structure and Algorithm 54 Bài tập 4 • Chương trình nhập 3 số, tìm số lớn nhất và hiển thị số đó Data Structure and Algorithm 55 Bài tập 4 Step 1: Input N1, N2, N3 Step 2: if (N1>N2) then if (N1>N3) then MAX ← N1 [N1>N2, N1>N3] else MAX ← N3 [N3>N1>N2] endif else if (N2>N3) then MAX ← N2 [N2>N1, N2>N3] else MAX← N3 [N3>N2>N1] endif endif Step 3: Print “The largest number is”, MAX Data Structure and Algorithm 56 Bài tập 4 MAX ← VALUE1 STOP Y N START Input VALUE1,VALUE2, VALUE3 MAX ← VALUE3 is VALUE1>VALUE2 is VALUE1>VALUE3 is VALUE2>VALUE3 MAX ← VALUE3 MAX ← VALUE2 Y Y NN Print “The largest value is”, MAX Data Structure and Algorithm 57 Discussion – Câu hỏi • https://sites.google.com/site/daona manhedu/data-structure-algorithm