intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Thuật toán - ThS. Hoàng Thị Thanh Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
8
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc - Thuật toán được biên soạn gồm các nội dung chính sau: Khái niệm; Các đặc trưng của thuật toán; Các cách biểu diễn thuật toán; Thuật toán tìm kiếm; Thuật toán xử lý số; Thuật toán sắp xếp. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Thuật toán - ThS. Hoàng Thị Thanh Hà

  1. Toán rời rạc (1): THUẬT TOÁN Ts. Hoàng Thị Thanh Hà Ha.htt@due.edu.vn 0905 238 835 Khoa Thống kê –Tin học Trường Đại học Kinh tế Đại học Đà Nẵng 21 August 2018 1
  2. Nội dung 1. Khái niệm 2. Các đặc trưng của thuật toán 3. Các cách biểu diễn thuật toán 4. Thuật toán tìm kiếm 5. Thuật toán xử lý số 6. Thuật toán sắp xếp 21 August 2018 2
  3. Khái niệm thuật toán  Ví dụ : bài toán hoán đổi 2 số nguyên a,b – Cách 1:  tam=a;  a=b;  b= tam; – Cách 2:  a= a+b;  b= a-b;  a=a-b; 21 August 2018 3
  4. Khái niệm thuật toán  Định nghĩa: – Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho. 21 August 2018 4
  5. Các đặc trưng của thuật toán  Đầu vào: Thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ  Đầu ra: Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra  Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng.  Tính xác định: Các bước thao tác phải hết sức rõ ràng, không nhập nhằng  Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn  Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định 21 August 2018 5
  6. Các cách biểu diễn thuật toán  Dùng ngôn ngữ tự nhiên (biểu diễn bằng lời) hay còn gọi là giả lệnh  Dùng sơ đồ khối  Dùng mã giả (pseudocode) 21 August 2018 6
  7. Các cách biểu diễn thuật toán  Dùng ngôn ngữ tự nhiên – Ví dụ 2 : xây dựng thuật toán tính tổng s=1+2+…n  Bước 1: Nhập giá trị n  Bước 2: Cho s = 0, i = 0 (i là biến đếm)  Bước 3: Trong khi i còn nhỏ hơn n thì thực hiện – Bước 3.1: tăng i lên một đơn vị (i = i + 1) – Bước 3.2: cộng i vào s (s = s + i) – Bước 3.3: lặp lại bước 3  Bước 4: Xuất ra giá trị của s 21 August 2018 7
  8. Các cách biểu diễn thuật toán  Dùng ngôn ngữ tự nhiên – Ví dụ 3: xây dựng thuật toán tính giai thừa p = n! = 1.2.3…n  Bước 1: Nhập giá trị n  Bước 2: Cho p = 1, i = 1 (i là biến đếm)  Bước 3: Trong khi i còn nhỏ hơn n thì thực hiện – Bước 3.1: tăng i lên một đơn vị (i = i + 1) – Bước 3.2: nhân i vào p (p = p * i) – Bước 3.2: lặp lại bước 3  Bước 4: Xuất ra giá trị của p 21 August 2018 8
  9. Các cách biểu diễn thuật toán  Sơ đồ khối gồm các kí hiệu sau: begin end Bắt đầu Kết thúc Nhập/xuất dữ liệu điều kiện đúng sai Thực hiện công việc Kiểm tra rẽ nhánh Gọi chương trình con 21 August 2018 9
  10. Các cách biểu diễn thuật toán  Ví dụ: vẽ sơ đồ khối tính n!, p = 1.2.3. …. n Begin Nhap n i=1 p=1 S i
  11. Các cách biểu diễn thuật toán  Ví dụ: dùng mã giả để biểu diễn thuật toán tính n!  Main{ – Scanf (“%d”,n); – P=1; – For (i= 1;i
  12. Thuật toán tìm kiếm  Tìm kiếm phần tử x trong mảng a gồm n phần tử – Tìm kiếm tuần tự – Tìm kiếm nhị phân (mảng a đã được sắp xếp) 21 August 2018 12
  13. Thuật toán tìm kiếm  Tìm kiếm phần tử x trong mảng a gồm n phần tử: – Tìm kiếm tuần tự : duyệt từ đầu đến cuối danh sách, khi gặp x thì dừng, hoặc dừng khi đã duyệt đến cuối danh sách. 21 August 2018 13
  14. Thuật toán tìm kiếm  Tìm kiếm tuần tự : duyệt từ đầu đến cuối danh sách, khi gặp x thì dừng, hoặc dừng khi đã duyệt đến cuối danh sách  Dùng mã giả: int main(){ int n,i,x, vitri=0, found=0; int a[100]; printf("nhap so phan tu cua mang "); scanf ("%d",&n); for (i= 1; i
  15. Thuật toán tìm kiếm  Tìm kiếm nhị phân (mảng a đã được sắp xếp tăng dần) – Thuật toán này chỉ áp dụng trong trường hợp bảng được sắp xếp theo thứ tự tăng dần. – Phần tử x được so sánh với số hạng ở giữa bảng. – Sau đó bảng được tách thành 2 bảng con. – Quá trình tìm kiếm được tiếp tục trên một trong 2 bảng con dựa trên kết quả so sánh x với phần tử ở giữa bảng ban đầu. 21 August 2018 15
  16. Thuật toán tìm kiếm  Tìm kiếm nhị phân: mã giả (NN C) Int BinarySearch(int x, int a1, a2, …, an) { int i = 1, j = n, m; while (i < j) { m = (i + j)/2; (nếu m lẻ thì phải làm tròn) if (x>am) i=m+1; else j=m; } if (x==ai) return(i); else return(0) } 21 August 2018 16
  17. Một số thuật toán xử lý số  Tìm ước chung lớn nhất của 2 số nguyên dương  Kiểm tra số nguyên tố  Kiểm tra số chính phương 21 August 2018 17
  18. Một số thuật toán xử lý số  Thuật toán tìm ước số chung lớn nhất Int UCLN(int a, int b) { While (a!=0 && b!=0) if (a>b) a = a – b; else b = b – a; if (a==0) return(b); else return(a); } 21 August 2018 18
  19. Một số thuật toán xử lý số  Kiểm tra số nguyên tố int ktnt(int n) { int i, kt=1; for(i=2; i
  20. Một số thuật toán xử lý số  Kiểm tra số chính phương int ktcp(int n) { int i = 1, kt = 0; while (n>i*i) i = i + 1; if (i*i == n) kt = 1; return(kt); } 21 August 2018 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0