Thuật toán sắp xếp tuần tự

Bài toán đặt ra

Cho mảng A gồm n phần tử. Sắp xếp lại dãy A theo chiều giảm dần

Nhập vào: số nguyên dương n và dãy A.

8
9 7 6 15 16 5 10 11
Xuất ra: dãy A sau khi đã được sắp xếp
5 6 7 9 10 11 15 16

Ý tưởng

Tư duy đơn giản như cách chúng ta xếp bài

sap-xep-1-yeulaptrinhHình trên là thao tác xếp cây bài 7 bằng cách rút nó ra và đặt vào vị trí của phù hợp.

Giải sử bài trên tay đang là:

2 5 7 10 4

ta thấy dãy 2,5,7,10 đã tăng dần chỉ còn cây 4 đứng chưa đúng chỗ nên ta đẩy 4 lên trước 10, rồi lên trước 7 cứ như vậy đến khi gặp cây 2 đứng trước. 2 < 4 suy ra thì dừng. Dãy trở thành

2 4 5 7 10

Dãy đã được sắp xếp.

Ý tưởng: duyệt lần lượt từng cây bài, nếu cây bài nhỏ thì ta đẩy dần lên đầu đến khi nào không chuyển lên được nữa

Ví dụ khác:

sap-xep-yeulaptrinh.pwCode:

#include <bits/stdc++.h>

using namespace std;

int n, a[10000];

void doi_cho(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<i; j++)
            if (a[j] > a[i])
            {
                doi_cho(&a[i], &a[j]);
            }
    }
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}
Ví dụ:

Với dãy A = {12, 11, 13, 5, 6}

Cho i chạy từ 1 đến 4

i=1. không làm gì cả

12, 11, 13, 5, 6

i = 2. Vì 11 nhỏ hơn 12 nên chuyển 11 lên trước 12
11, 12, 13, 5, 6

i = 3. 13 không cần chuyển lên đầu nữa
11, 12, 13, 5, 6

i = 4. 5 được chuyển chỗ với 13 rồi chuyển chố tiếp lần lượt với 12, 11.
5, 11, 12, 13, 6

i = 5. 6 cũng giông như 5 được chuyển dần lên đến khi gặp 5 nhỏ hơn thì dừng lại
5, 6, 11, 12, 13

Độ phức tạp:

  • O(n^2)

 

Quý bạn đọc có ý kiến, thắc mắc xin comment bên dưới <3

Tìm kiếm nhị phân (chặt nhị phân) toàn tập

Đã lâu rồi mình chưa viết bài mới, hôm nay mình xin chia sẻ với các bạn cách code thuật toán tìm kiếm phân mà mình thường sử dụng.

Chắc mọi người cũng biết, cùng một thuật toán tìm kiếm nhị phân nhưng có rất nhiều cách code khác nhau, tất cả đều chính xác, tốc độ nhanh như nhau. Và cách mình chia sẻ dưới đây là một trong những cách dễ hiểu nhất, linh hoạt nhất mà tốc độ chạy cũng khá tốt (cách này của anh Kiên – HCB Olympic Tin học Quốc tế)

Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)

// day con tang – tim phan tu lon nhat nho hon x ( chi so lon nhat);

function tim2(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>=x then c:=g else d:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto  d do

      if b[g]<x then exit(g);

   end;

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)

// day con tang – so be nhat lon hon hoac bang x (chi so be nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do

if a[i]>=k then return a[i];

print “Not found”

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)

// day con tang – so be nhat lon hon hoac bang x ( chi so lon nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = right to left do

if a[i]<=k then return a[i];

print “Not found”

Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x

//day con giam – tim phan tu cuoi cung lon hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto d do

      if b[g]>x then exit(g);

  end;

Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x

//day con giam – tim phan tu dau tien nho hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=d to c do

      if b[g]>x then exit(g);

  end;

Các bài khác nhau với các yêu cầu tìm kiếm khác nhau bạn có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.

Mọi thắc mắc rất mong nhận được từ quý bạn đọc <3

Tổng hợp tài liệu Java cơ bản

Hưởng dẫn dịch chương trình Java: http://uet.vnu.edu.vn/~chauttm/guides/BuildingFirstJavaProgram.pdf

Head First Java: https://zimslifeintcs.files.wordpress.com/2011/12/head-first-java-2nd-edition.pdf

How to Program Java: http://mobile.skku.ac.kr/lecture/2017_1/CEL/how%20to%20program%20Java.pdf

Tổng hợp đề thi HSGQG môn Tin học các năm

YeuLapTrinh xin được tổng hợp lại đề thi HSGQG các năm để các bạn tiện tham khảo:

 

 

++++++++++++++

(đang tiếp tục cập nhập)

Tài liệu chuyên đề thuật toán duyệt

Hiện nay chưa có tài liệu chính thức dành cho lớp Chuyên Tin khối THPT. Mà chỉ tồn tại ở dưới dạng tên chuyên đề của Bộ Giáo dục gửi về cho các trường. Do vậy việc dạy và học gặp nhiều khó khăn trong việc thống nhất về nội dung cũng như mức độ về kiến thức chuyên môn. Nên việc nghiên cứu và xây dựng chuyên đề này là thực sự cần thiết.

Mục đích của chuyên đề là truyền tải một cách tổng quát, chi tiết và sự thống nhất về mặt nội dung để người đọc dễ hiểu và thấy được tầm quan trọng của bài toán liệt kê tổ hợp và một số bài tập ứng dụng trong Tin học dành cho học sinh chuyên tin ở trường THPT.

Nội dung của chuyên đề đã được các tác giả chọn lọc qua chương trình đã thực dạy tại trường và tham khảo của một số đồng nghiệp khác trong nước.

Kiến thức là vô hạn, trong chuyên đề này chúng tôi đã có gắng sáng  tạo, sưu tầm và trao đổi một cách tốt nhất có thể về mặt lý thuyết, các bài tập ứng dụng và các bài tập trong các kỳ thi trong nước để tạo thành cuốn tài liệu hiệu quả dành cho giáo viên và các em học sinh đam mê tin học chính thức làm tài liệu cho mình trong quá trình học tập và nghiên cứu.

THPT Chuyên Bắc Giang.

TẢI VỀ: CHUYEN-DE-DUYET-CAU-HINH-TO-HOP-YEULAPTRINH.PW

Thuật toán duyệt phân tập

Bài toán cơ bản:

Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

  • Inp: n, S, mảng A.
  • Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

  • Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
  • Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

  • Chia mảng A làm 2 mảng nhỏ độ dài n/2
  • Khi đó max(n/2)=20 => duyệt
  • Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
  • Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
  • res là kết quả bài toán

Các bài tập luyện tập thêm:

COIN34 – SPOJ

VECTOR – spoj

DTTUI1 – spoj

Tổng hợp tài liệu về thuật toán cặp ghép

Tài liệu của thầy Lê Minh Hoàng: http://yeulaptrinh.pw/wp-content/uploads/2016/05/BipartiteMatching.pdf