<

Hướng dẫn
LẬP TRÌNH CƠ BẢN

Nguyễn Hoàng Phú

ĐỌC DỮ LIỆU VÀ GHI KẾT QUẢ

(lưu ý cơ bản khi lập trình giải toán)

Các bước giải bài toán

Đọc dữ liệu

Xử lý bài toán

Ghi kết quả

ĐỌC DỮ LIỆU

Lệnh: input()

Nếu đọc nhiều giá trị: sử dụng split() để tách dữ liệu

Quan tâm đến kiểu dữ liệu là gì để ép về kiểu dữ liệu đó

Sử dụng map để ép kiểu dữ liệu nhiều giá trị cùng lúc

Ví dụ đọc dữ liệu

Đọc 1 số nguyên n


                            n = int(input())

Đọc 2 số nguyên a, b trên 1 dòng


                            a, b = map(int, input().split())

Đọc 1 dãy số nguyên trên 1 dòng vào mảng a


                            a = [int(x) for x in input().split()]

Đọc n số nguyên, mỗi số trên 1 dòng vào mảng a


                            a = []
                            for i in range(n):
                                a.append(int(input()))

GHI KẾT QUẢ

Lệnh: print()

Kết thúc lệnh print sẽ tự động xuống hàng

Giữa các tham số trong print tự động chèn dấu cách

Nếu không muốn xuống hàng kết hợp tham số end

Nếu không muốn thêm dấu cách giữa các tham số kết hợp tham số sep

Ví dụ ghi kết quả

Ghi 1 số nguyên n


                            print(n)

Ghi 2 số nguyên a, b trên 1 dòng


                            print(a, b)

Ghi 1 mảng a có n số nguyên, mỗi số trên một dòng


                            for i in range(n):
                                print(a[i])

Ghi 1 mảng a có n số nguyên trên cùng một dòng


                            for i in range(n):
                                print(a[i], end=' ')
                            print()

FINDMAX-Tìm giá trị lớn nhất

https://nhpoj.net/problem/FINDMAX

ĐỌC DỮ LIỆU

Dòng đầu tiên ghi số nguyên dương n


                            n = int(input())

n dòng tiếp theo, mỗi dòng ghi một số nguyên dương cho biết dãy số.


                            a = []
                            for i in range(n):
                                a.append(int(input()))

XỬ LÝ BÀI TOÁN

  • Giả sử phần tử lớn nhất là phần tử đầu tiên a[0]
    • 
                                mx = a[0]
  • Lần lượt duyệt từng phần tử bắt đầu từ phần tử thứ 2 đến phần tử cuối (từ a[1] đến a[n-1], khi gặp phần tử nào có giá trị lớn hơn mx ta cập nhật lại giá trị mx
    
                                for i in range(1, n):
                                    if a[i] > mx:
                                        mx = a[i]

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
3

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
3

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
3

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
5

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
5

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
5

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
6

Mô phỏng thuật toán

i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
1
6
9
7
mx =
9

GHI KẾT QUẢ

Một số là kết quả tìm được


                            print(mx)

CHƯƠNG TRÌNH HOÀN CHỈNH


                            n = int(input())
                            a = []
                            for i in range(n):
                                a.append(int(input()))
                            mx = a[0]
                            for i in range(1, n):
                                if a[i] > mx:
                                    mx = a[i]
                            print(mx)
Input Output
4
3
2
5
1
 5

P287-Đếm số phần tử có giá trị bằng x

https://nhpoj.net/problem/P287

ĐỌC DỮ LIỆU

Dòng đầu ghi hai số nguyên dương n và x


                            n, x = map(int, input().split())

Dòng thứ hai ghi n số nguyên dương cho biết dãy số.


                            a = [int(x) for x in input().split()]

XỬ LÝ BÀI TOÁN

  • Khởi tạo biến đếm ban đầu bằng 0 (chưa có giá trị nào bằng x)
    • 
                                cnt = 0
  • Lần lượt duyệt từng phần tử bắt đầu từ phần tử thứ nhất đến phần tử cuối (từ a[0] đến a[n-1], khi gặp phần tử nào có giá trị bằng x ta tăng biến cnt lên 1 đơn vị
    
                                for i in range(0, n):
                                    if a[i] == x:
                                        cnt = cnt + 1

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
0

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
0

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
0

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
1

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
1

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
2

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
3

Mô phỏng thuật toán

n = 8, x = 5
i
0
1
2
3
4
5
6
7
a[i]
3
2
5
4
5
5
9
7
cnt =
3

GHI KẾT QUẢ

Một số là kết quả tìm được


                            print(cnt)

CHƯƠNG TRÌNH HOÀN CHỈNH


                            n, x = map(int, input().split())
                            a = [int(x) for x in input().split()]
                            cnt = 0
                            for i in range(n):
                                if a[i] == x:
                                    cnt += 1
                            print(cnt)
Input Output
8 5
3 2 5 4 5 5 9 7		 3

TRÁO BÀI

https://nhpoj.net/problem/P293

Tráo bài

  1. Cho một tập bài gồm 𝑛 lá bài đánh số 1…𝑛 theo thứ tự trái→phải. Đầu tiên người ta viết vào mỗi lá bài một số nguyên là số thứ tự lá bài đó.
  2. Phép tráo 𝑆(i, j): Rút ra lá bài ghi số nguyên i và chèn lên trên lá bài mang số nguyên j (i ≠ j).
  3. Yêu cầu: Xác định trạng thái của bộ bài sau 𝑥 phép tráo cho trước.

Ví dụ

1
2
3
4
5
6
7
8
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
2
3
4
5
6
7
8
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9
S(4, 7)

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9
S(4, 7)
1
8
2
3
4
5
6
7
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9
S(4, 7)
1
8
2
3
5
6
4
7
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9
S(4, 7)
1
8
2
3
5
6
4
7
9
S(1, 9)
1
8
2
3
5
6
4
7
9

Ví dụ

1
2
3
4
5
6
7
8
9
S(8, 2)
1
8
2
3
4
5
6
7
9
S(4, 7)
1
8
2
3
5
6
4
7
9
S(1, 9)
8
2
3
5
6
4
7
1
9
8
2
3
5
6
4
7
1
9

Cài đặt bằng danh sách mốc nối kép

  1. Lá bài i được mô tả là số nguyên i.
  2. Sử dụng 2 mảng prv để lưu vị trí trước và nxt để lưu vị trí sau của một lá bài.
  3. Phép tráo S(i, j) là thao tác xóa số i ra khỏi danh sách và chèn số i vào trước số j.

Cài đặt bằng danh sách mốc nối kép

nxt[0]=1 nxt[1]=2 nxt[2]=3 nxt[3]=4 nxt[4]=5 nxt[5]=6 nxt[6]=7 nxt[7]=8 nxt[8]=9
0
1
2
3
4
5
6
7
8
9
prv[1]=0 prv[2]=1 prv[3]=2 prv[4]=3 prv[5]=4 prv[6]=5 prv[7]=6 prv[8]=7 prv[9]=8

Cài đặt bằng danh sách mốc nối kép

nxt[0]=1 nxt[1]=2 nxt[2]=3 nxt[3]=4 nxt[4]=5 nxt[5]=6 nxt[6]=7 nxt[7]=8 nxt[8]=9
0
1
2
3
4
5
6
7
8
9
prv[1]=0 prv[2]=1 prv[3]=2 prv[4]=3 prv[5]=4 prv[6]=5 prv[7]=6 prv[8]=7 prv[9]=8
S(8, 4)

Cài đặt bằng danh sách mốc nối kép

nxt[0]=1 nxt[1]=2 nxt[2]=3 nxt[3]=4 nxt[4]=5 nxt[5]=6 nxt[6]=7 nxt[7]=9
0
1
2
3
4
5
6
7
8
9
prv[1]=0 prv[2]=1 prv[3]=2 prv[4]=3 prv[5]=4 prv[6]=5 prv[7]=6 prv[9]=7
S(8, 4)

Cài đặt bằng danh sách mốc nối kép

nxt[0]=1 nxt[1]=2 nxt[2]=3 nxt[3]=8 nxt[8]=4 nxt[4]=5 nxt[5]=6 nxt[6]=7 nxt[7]=9
0
1
2
3
8
4
5
6
7
9
prv[1]=0 prv[2]=1 prv[3]=2 prv[8]=3 prv[4]=8 prv[5]=4 prv[6]=5 prv[7]=6 prv[9]=7
S(8, 4)

Cài đặt bằng danh sách mốc nối kép

Liên kết lá bài thứ i và lá bài thứ j

nxt[i] = j
i
j
prv[j] = i 

    						void link(int i, int j) {
    						    nxt[i] = j;
    						    prv[j] = i;
    						}

Cài đặt bằng danh sách mốc nối kép

Xóa lá bài i

nxt[i]
0
...
...
i
...
...
prv[i]
S(i, j) 

    						void S(int i, int j) {
    						    ...
    						}

Cài đặt bằng danh sách mốc nối kép

Xóa lá bài i

0
...
prv[i]
i
nxt[i]
...
S(i, j) 

    						void S(int i, int j) {
    						    ...
    						}

Cài đặt bằng danh sách mốc nối kép

Xóa lá bài i

0
...
prv[i]
i
nxt[i]
...
S(i, j) 

    						void S(int i, int j) {
    						    link(prv[i], nxt[i]);
    						    ...
    						}

Cài đặt bằng danh sách mốc nối kép

Chèn lá bài i vào trước lá bài j

0
...
prv[j]
j
...
...
i
S(i, j) 

    						void S(int i, int j) {
    						    link(prv[i], nxt[i]);
    						    ...
    						}

Cài đặt bằng danh sách mốc nối kép

Chèn lá bài i vào trước lá bài j

0
...
prv[j]
i
j
...
S(i, j) 

    						void S(int i, int j) {
    						    link(prv[i], nxt[i]);
    						    link(prv[j], i);
    						    link(i, j);
    						}