Please enable JavaScript.

Coggle requires JavaScript to display documents.

(Huy Pháp) CHƯƠNG 8: GIẢI THUẬT - Coggle Diagram

- - - - B1: Nếu a=b thì dừng, thông báo UCLN=a; nếu a≠b thì sang B2
      - Input: a,b nguyên dương | Output: UCLN(a,b)
      - B2: Nếu a>b thì a=a-b, nếu a<b thì b=b-a; quay lại B1
  - - - Các khối: Bắt đầu, Kết thúc, Input, Output, Điều kiện, Thao tác
    - - Ví dụ giả mã tìm UCLN (kiểu Pascal):
        Nhập a,b
        While a≠b do
        If a>b then a := a-b
        else b := b-a
        Thông báo UCLN = b
  - - - Ngôn ngữ tự nhiên -> Giả ngôn ngữ -> Ngôn ngữ lập trình
    - - Ý tưởng: chọn phần tử nhỏ nhất còn lại, xếp vào đúng vị trí, lặp lại
      - Giả mã Pascal:
        
        For i:=1 to n-1 do
        Begin
        - Chọn phần tử nhỏ nhất aj trong ai..an - Đổi chỗ aj và ai End;
  - - - Quy tắc cộng: T1=O(f(n)), T2=O(g(n)) => T1+T2 = O(max{f(n),g(n)})
      - Quy tắc nhân: T1=O(f(n)), T2=O(g(n)) => T1.T2 = O(f(n).g(n))
      - Quy tắc bỏ hằng số: O(c.f(n)) = O(f(n))
  - - - procedure Selection_Sort;
        begin
        for i:=1 to n-1 do
        begin
        m:=i
        for j:=i+1 to n do if aj<am then m:=j
        if m≠i then đổi chỗ ai và am
        end
        end
    - - procedure Insertion_Sort
        begin
        for i:=2 to n do
        begin
        k:=ai; j:=i
        while aj-1>k do begin aj:=aj-1; j:=j-1 end
        aj:=k
        end
        end
    - - procedure Bubble_Sort
        begin
        for i:=1 to n-1 do
        for j:=n downto i+1 do
        if aj<aj-1 then đổi chỗ aj và aj-1
        end
    - - procedure Sequential_Searching
        begin
        i:=1
        while ai≠X do i:=i+1
        if i=n+1 then không tìm thấy
        else vị trí tìm thấy là i
        end
    - - procedure Binary_Searching
        begin
        left:=1; right:=n
        repeat
        mid:=(left+right)/2
        if X<amid then right:=mid-1 else left:=mid+1 until (X=amid) or (left>right)
        if X=amid then vị trí là mid
        else không tìm thấy
        end
    - - Định nghĩa đệ quy gồm 2 phần:
      - Phần đệ quy (qui nạp)