Lý thuyết Python cơ bản
MỤC LỤC
CHỦ ĐỀ
1: LÀM QUEN PYTHON
1. Công cụ lập trình:
Có nhiều
phần mềm giúp chúng ta viết và chạy chương trình
viết bằng Python
như:
·
Pycharm
·
Atom
·
Thony
·
Vscode
·
…
Mỗi phần mềm đều có ưu nhược điểm
riêng, cách cài đặt và viết chương trình cũng khác nhau. Pycharm hỗ trợ code rất tốt tuy nhiên lại quá nặng, khi chạy
chiếm tầm 1GB Ram nên máy tính mà 4GB ram thì rất hay Lag. Atom giao diện đẹp, thư viện tiện ích phong phú tuy nhiên công cụ debug
lại không đáp ứng được để dạy và học phần tìm và sửa lỗi. Thony thì rất nhẹ,
khi chạy chiếm chỉ tầm 40MB bộ
nhớ, tuy nhiên tiện ích rất ít và công cụ debug còn quá đơn giản.
Dễ cài đặt, dễ sử dụng, chuyên nghiệp,
hỗ trợ tốt khi code, hỗ trợ tốt debug, phù hợp với chuyên đề F và các kỳ thi HSG theo tôi vẫn là VScode.
Khi chạy chiếm tầm 300MB bộ nhớ, tạo một thư mục và code tất cả bài vào rất tiện lợi. Đặc biệt lên lớp 12 dùng vscode code luôn HTML5 và CSS.
2. Tải và cài đặt phần mềm:
a) Cài đặt Python cho Window:
·
Truy cập trang www.python.org vào mục Download, nhấn nút Download
Python để tải về
·
Chạy file vừa tải về để cài đặt
b) Cài đặt Vscode:
·
Vào google gõ vào ô tìm kiếm: vscode, chọn Download
ngay ở kết quả đầu tiên và chọn tải về
bản cho window.
·
Chạy file vừa tải để cài đặt:
|
|
|
|
Bước này chọn accept
để cài đặt |
Bước này chọn
create a desktop icon
để thêm icon
ra màn hình |
·
Mở Vscode vừa cài xong, nhấn tổ hợp phím Ctrl +
Shift + X, gõ python, sau đó chọn và cài đặt
thêm tiện ích python này. Bước này sẽ giúp: Gợi ý lệnh khi code, hỗ trợ debug,
chạy code…
3.
Chương trình Python đầu tiên
·
Nếu bạn chưa có thư mục lưu trữ code hãy tạo cho mình một thư mục để lưu. Lưu ý tạo thư
mục không
đặt tiếng Việt có
dấu.
·
Mở Vscode, vào
File chọn Open Folder và mở thư mục của bạn
vừa tạo ở bước trên.
·
Trong khung bên phải, Click chuột phải chọn New File
để tạo file mới, đặt tên vidu.py
·
Gõ chương trình
sau để thử:
·
Để chạy chương trình vừa viết xong: Nhấn vào biểu tượng
tam giác màu trắng gần góc trên bên
phải. Vscode sẽ hiển thị ra một khung mới phía dưới và chờ bạn nhập họ tên của
mình. Sau khi gõ xong thì nhấn enter để
xem kết quả.
Thông tin thêm : Để code có format đẹp thì tìm vào File, chọn Preferences, chọn Settings, chọn Text Editor, chọn Formatting và tick chọn vào Format
on Save. Sau khi tuỳ chọn này được bật, mỗi khi lưu bài thì Vscode
format lại code theo chuẩn autopep8
rất chuyên nghiệp, rõ ràng và đẹp
mắt.
CHỦ ĐỀ 2: CHƯƠNG TRÌNH GIẢI BÀI TOÁN ĐƠN GIẢN
1. Ví dụ:
Sau đây là chương trình đơn giản giải bài toán tính và thông báo diện tích hình tròn:
|
Chương trình |
Giải thích |
|
|
Khai báo thư viện
toán học
Nhập
bán kính vào từ bàn phím Tính diện
tích hình tròn Thông báo kết quả diện tích |
2. Các phần cụ thể:
a) Phần khai
báo thư viện:
Qua ví dụ trên ta thấy phần đầu tiên và
rất quan trọng trong lập trình là khai báo thư viện. Việc khai báo thư viện giúp ta khai thác được các chương trình
có sẵn trong thư viện. Hiện Python có
hệ thống thư viện khổng
lồ về rất nhiều lĩnh vực.
Sau
đây xin giới thiệu đến các bạn thư viện math,
chứa rất nhiều modul sử dụng cho các tác vụ toán học. Một số hàm toán học tiêu biểu:
|
Hàm |
Công dụng |
|
math.pi |
Hằng số pi = 3.141592653589793 |
|
math.sqrt(x) |
Trả về số thực là căn bậc hai của số thực dương x. Nếu ta gọi hàm này với số
âm sẽ báo lỗi |
|
math.trunc(x) |
Trả về phần nguyên
của số thực x. Ví dụ: math.trunc(5.6) = 5 |
|
math.floor(x) |
Làm tròn
xuống số nguyên gần nhất. Ví dụ: math.floor(5.9) = 5 |
|
math.ceil(x) |
Làm tròn lên số nguyên gần nhất. Ví dụ: math.ceil(5.3) = 6 |
|
math.fabs(x) |
Trả về
giá trị tuyệt đối của
số x. |
|
math.gcd(x,
y) |
Trả về ước chung lớn nhất
của hai số nguyên x và y. |
|
math.pow(x,
y) |
Trả về số thực là giá trị xy. Hàm này có sai số khá lớn nên hạn chế sử dụng. Nếu
muốn tính xy của hai số nguyên
thì nên dùng: x**y |
|
math.sin(x) |
Trả về giá
trị lượng giác
sin(x) |
|
math.cos(x) |
Trả về giá
trị lượng giác
cos(x) |
|
math.tan(x) |
Trả về giá trị lượng
giác tan(x) |
|
math.asin(x) |
Trả về
số đo U của góc có sin(U) = x. Dùng khi muốn
tìm số đo góc. Lưu ý đơn vị
là radian. |
|
math.degrees(x) |
Đổi đơn
vị x radian sang độ. Ví dụ: math.degrees(math.pi) = 180 độ. |
|
math.radians(x) |
Đổi đơn
vị x độ sang radian. Ví dụ:
math.radians(180) = 3.14159… |
|
math.log2(x) |
Trả về
logarit cơ số 2 của x. |
|
math.log10(x) |
Trả về
logarit cơ số 10 của x. |
|
math.comb(n,
k) |
Trả về C(k,n) là tổ hợp chập k của n. Có thể dùng để đếm số cách chọn ra k vật trong n
vật. Ví dụ: math.comb(7, 5) = 21 |
|
… |
… |
Còn rất nhiều thư viện hữu ích
khác, các bạn sẽ
lần lượt tìm hiểu theo quá trình học.
b)
Phần xử lý chính:
Phần xử lý của bài toán tính
toán đơn giản thông thường có ba bước như trong ví dụ trên.
·
Nhập thông tin cần thiết vào cho máy tính
·
Tính toán
giải quyết bài toán
·
Thông báo
kết quả của bài
|
Phần |
Nội dung cơ bản |
||||||
|
Nhập thông tin |
- Để nhập
thông tin vào từ bàn phím Python hỗ trợ cho ta hàm input() - Hàm input() mặc định trả về một chuỗi kí tự được
nhập vào từ bàn phím.
Sau đây là một số ví dụ: |
||||||
|
|
Thao tác nhập |
Lệnh Python |
|
||||
|
Một chuỗi
kí tự |
hoten
= input() |
||||||
|
một số nguyên |
x = int(input()) - Lệnh trên
dùng hàm int() để chuyển
xâu số nguyên được nhập vào bởi hàm input() thành số |
||||||
|
một số thực |
x = float(input()) |
||||||
|
hai số nguyên trên
hai dòng |
x = int(input()) y = int(input()) |
||||||
|
Hai số nguyên cách
nhau dấu cách |
x,y = map(int, input().split()) Trong lệnh trên: input().split() sẽ tách chuỗi
nhập thành hai xâu số
nguyên dựa vào dấu cách. map(int, ..) sẽ chuyển hai xâu số thành 2 số |
||||||
|
Hai số thực cách nhau dấu cách |
x,y
= map(float, input().split()) |
||||||
|
Ba số
nguyên |
x,y,z
= map(int, input().split()) |
||||||
|
Tính
toán |
- Python cung
cấp lệnh gán để
tính toán: tên biến = biểu thức - Ví dụ tính diện
tích hình chữ nhật: s = a*b - Để viết
được các biểu
thức tính toán,
Python cung cấp một số
loại phép toán: 1. Phép toán số học: Các ví dụ dưới đây thì
ta coi a = 5 và b = 7. |
||||||
|
|
Phép toán |
Mô Tả |
Ví
Dụ |
|
|||
|
+ |
Phép toán cộng các giá trị lại với nhau |
a + b = 12 |
|||||
|
- |
Phép toán trừ các giá trị lại với nhau |
a - b = -2 |
|||||
|
* |
Phép toán nhân các giá trị lại với nhau |
a * b = 42 |
|||||
|
/ |
Phép toán chia cho ra số thực |
a / b = 0.71428… |
|||||
|
// |
Phép toán chia lấy phần
nguyên |
a // b = 0 |
|||||
|
% |
Phép toán chia lấy phần
dư |
a % b = 5 |
|||||
|
** |
Phép toán mũ. a**b = ab |
a ** b = 78125 |
|||||
|
|
|
2, Phép toán Quan
hệ. Dạng phép toán
này dùng để so sánh
các giá trị
với nhau kết quả của
nó sẽ trả về là True nếu đúng và False nếu sai. Và nó thường được
dùng trong các câu lệnh
điều kiện. Trong
Python thì nó cũng tồn tại 6 dạng phép toán quan hệ cơ bản như sau: (trong các ví dụ dưới đây thì ta coi a có giá trị là
5 và b có giá trị
là 7). Phép Chú Thích Ví
Dụ toán
So sánh giá trị của các đối số xem có bằng nhau == hay không.Nếu bằng nhau thì
kết quả trả
về sẽ a == b // False là True và ngược lại sẽ là False.
So
sánh giá trị của các đối số xem có khác nhau != hay không. a != b //True Nếu
khác nhau thì kết quả trả về sẽ là True và ngược lại sẽ
là False.
Dấu < đại diện cho phép toán nhỏ hơn, nếu đối < số 1 nhỏ hơn đối số 2 thì
kết quả sẽ trả về là True a
< b //True và ngược
lại sẽ là False.
Dấu >
đại diện cho phép toán
lớn hơn, nếu đối số > 1 lớn hơn đối
số 2 thì kết quả sẽ trả về là True và a >
b //False ngược lại sẽ
là False.
Dấu > đại diện cho phép
toán nhỏ hơn hoặc bằng, <= nếu đối số 1 nhỏ hơn hoặc bằng đối số 2 thì kết a <= b //True quả sẽ trả về là
True và ngược lại sẽ là False.
Dấu >
đại diện cho phép toán
lớn hơn hoặc
bằng, >= nếu đối số 1 lớn hơn hoặc bằng đối số 2 thì kết a>= b //False quả sẽ trả
về là True và ngược lại
sẽ là False. 3, Phép toán gán. Phép toán gán là phép
toán dùng đế gán giá trị của
một đối tượng
cho một đối tượng khác.
Và trong Python
thì nó cũng được thể hiện giống
như các ngôn ngữ khác.
Và dưới đây
là 8 phép toán nằm trong dạng
này mà Python
hỗ trợ. |
||||
|
|
Phép toán |
Chú Thích |
Ví Dụ |
|
|
|
= |
Phép
toán này dùng để gán giá trị của một
đối tượng cho một giá trị |
c = a (lúc này c sẽ có giá trị = 5) |
|
||
|
+= |
Phép toán
này cộng rồi gắn giá
trị cho đối tượng |
c += a (giống với c = c + a) |
|
||
|
-= |
Phép toán này trừ rồi gắn giá trị cho
đối tượng |
c -= a (giống với c
= c - a) |
|
||
|
||||||||||||||||
|
||||||||||||||||
|
|
|
*= |
Phép toán này trừ rồi gắn giá trị cho
đối tượng |
c *= a (giống với c = c * a) |
|
|
/= |
Phép toán
này chia rồi gắn giá trị cho đối tượng |
c /= a (giống với c
= c / a) |
|
||
|
% |
Phép toán này chia
hết rồi gắn
giá trị cho đối tượng |
c %= a (giống với c = c
% a) |
|
||
|
**= |
Phép toán
này lũy thừa
rồi gắn giá
trị cho đối tượng |
c **= a (giống
với c = c ** a) |
|
||
|
//= |
Phép toán này chia làm tròn rồi gắn giá trị cho đối tượng |
c //=
a (giống với c = c //
a) |
|
||
|
4, Phép toán logic. Phép toán logic
trong Python hoàn
toàn giống như các ngôn
ngữ khác. Nó gồm có 3
kiểu cơ bản như sau: Phép Chú
Thích toán
and Nếu 2 vế của phép toán này đều là True thì kết quả sẽ là True và ngược lại nếu 1 trong 2 vế là False thì kết quả trả về sẽ là False.
or Nếu 1 trong 2 vế là True thì kết quả trả về sẽ là True và ngược
lại nếu cả 2
vế là False thì
kết quả trả về sẽ là False.
not Đây là dạng
phủ định, nếu
biểu thức là True thì nó
sẽ trả về là False
và ngược lại. 5, Phép
toán bitwise. Phép toán này
thực hiện trên các bit
của các giá trị. Hãy tưởng tượng
mình có 2 biến a = 12 và b = 15 nhưng nếu chúng ta convert chúng
sang hệ nhị
phân thì 2 biến này sẽ có giá trị như
sau: a = 00001100 và b = 00001111. Phép toán Ví Dụ
& (a &
b) = 12 (00001100)
| (a | b) = 14 (00001111)
^ (a ^ b) = 2 (00000010)
~ (-a) = -13 (00001101)
<< a<<a
= 49152
>> a>>a
= 0 6, Phép toán khai thác. Phép toán này thường được dùng để kiểm tra xem 1 đối số có nằm trong 1 tập hợp đối số hay không (list). Trong
Python hỗ trợ chúng ta 2 dạng phép toán như sau: Giả sử: a = 4, b = [1,5,7,6,9] |
|||||
|
|
|
Phép toán |
Chú
Thích |
Ví
Dụ |
|
||
|
in |
Nếu 1 đối số thuộc một tập đối số nó sẽ trả
về True và ngược
lại/ |
a in b //False |
|
||||
|
not in |
Nếu 1 đối số
không thuộc một tập đối số nó sẽ trả về True
và ngược lại/ |
a not in b //True |
|
||||
|
Thông báo kết quả |
- Để in thông tin Python cung cấp lệnh print() - Lệnh này cho phép in
một hoặc nhiều giá trị ra màn hình. Các giá trị trong một lệnh
in sẽ được in cách
nhau một dấu
cách. - Một số ví dụ: |
||||||
|
|
Lệnh
in |
Ý nghĩa |
|
||||
|
print(12) |
in số 12 ra
màn hình |
||||||
|
print(15, “hoà bình”) |
in số 15
và chuỗi kí tự “hoà bình” kết quả trên
màn hình: 15 hoà bình |
||||||
|
print(“số chẵn:”, 2) |
số
chẵn: 2 |
||||||
|
print(format(s, ‘.3f’)) |
in kết quả s ra màn hình, làm tròn 3 chữ số thập phân |
||||||
|
print(‘chào’
+ ‘bạn’) |
chàobạn |
||||||
|
print(‘chào’,
‘bạn’) |
chào bạn |
||||||
|
print(‘chào’, end = ‘ ‘) print(‘bạn’) |
- end = ‘ ‘ là để in xong
nhưng không xuống dòng mà chỉ in thêm một dấu cách - kết quả: chào bạn |
||||||
|
print(‘chào’) print(‘bạn’) |
in ra hai dòng:
chào bạn |
||||||
3.
Ví dụ:
- VD1: Chương trình nhập vào hai cạnh hình
chữ nhập cách nhau dấu cách
và tính diện tích
a, b
= map(int, input().split()) s = a*b
print(s)
- VD2: Chương trình nhập vào bán kính, tính và thông báo diện tích hình tròn. Kết quả làm tròn 5 chữ số thập phân:
import math
r = int(input())
s = math.pi * r * r print(format(s, '.5f'))
CHỦ ĐỀ 3: CÂU LỆNH RẼ NHÁNH
1. Câu lệnh if –
else
-
 |
Cú pháp cơ bản:
- Nếu điều kiện
đúng thì thực hiện câu lệnh 1 còn không sẽ thực hiện câu
lệnh 2.
-
 |
Trường hợp sau: Nếu điều kiện đúng thì thực hiện hai câu lệnh. Python sử dụng thụt lề để xác định
lệnh cùng khối với
nhau. Nên lệnh 1 và lệnh
2 phải cùng thụt lề như nhau.
- Trường hợp sau điều kiện đúng chỉ thực hiện câu lệnh
1 do hai lệnh này không cùng khối lệnh:
-
 |
Lệnh sau sẽ
báo lỗi IndentationError do cấp độ thụt lề không
xác định
2. Một số ví dụ:
|
Ví dụ |
Ý nghĩa,
kết quả |
|
a = 33 b = 45 if b > a: print("b lớn hơn a") |
b
lớn hơn a |
|
a,b = 68, 33 if b >
a: print("b lớn hơn
a") else: print("b không
lớn hơn a") |
a
= 68 và b = 33 nên sẽ in ra: b không lớn hơn a |
|
a = 200 b = 33 if b >
a: print("b lớn hơn
a") elif a == b: print("b bằng
a") else: print("b bé hơn a") |
Sử dụng elif để kiểm tra điều kiện |
|
a = 34 b = 68 print("A") if a > b else print("B") |
Lệnh in
kết hợp if then để kiểm tra |
|
if a >
b and c > a: print("Thử hai điều
kiện") |
Biểu thức điều kiện với phép toán và |
|
if a >
b or a > c: print("Chỉ cần một trong hai đúng") |
Biểu thức điều kiện với phép toán hoặc |
|
if x >
10: print("Lớn hơn 10,") if x > 20: print("và lớn
hơn 20!") |
Sử dụng if lồng nhau |
|
else: print("Nhưng không lớn
hơn 20.") |
|
|
a, b = 33, 45 if b >
a: print("b lớn hơn
a") print("Chào bạn") |
Lệnh
in thứ hai cùng khối với lệnh if nên sau khi thực
hiện xong lệnh if sẽ thực hiện lệnh print(“Chào bạn) |
|
a = int(input()) if a >=
0: if a == 0: print("Zero") else: print("Số dương") else: print("Số âm") |
- Nhập số nguyên a vào từ bàn phím - Sử
dụng if lồng nhau để kiểm tra thuộc loại
số nào. |
|
a = int(input()) if a == 0: print("Zero") elif a > 0: print("Số dương") else: print("Số âm") |
Tương đương ví dụ
trên |
CHỦ ĐỀ
4 –
CÂU LỆNH LẶP
1.
Lặp với số lần biết trước:
- Khác với C++ hay Pascal, Python xác định lặp lại lần lượt từng đối tượng của một danh sách theo thứ tự của chúng trong danh sách.
for x in danhsach:
Lệnh xử lý
- Python 3 cung cấp hàm range() để tạo
ra danh sách các số nằm
trong một phạm vi:
·
range(u, v) sẽ tạo ra một danh sách
các số từ u đến v-1
·
range(u, v, w) sẽ tạo
ra một
danh sách các số từ
u đến v-1, số sau cách số trước w đơn
vị
- Một số ví
dụ về lệnh lặp for:
|
Ví dụ |
Ý nghĩa,
kết quả |
|
for x in [0,
1, 2]: print(x) |
- Lặp lại 3
lần - x lần lượt nhận
giá trị 0, 1, 2. |
|
for x in range(2, 6): print(x) |
- range(2,6) trả về một đoạn gồm các
số nguyên từ 2 đến 5. - x lần lượt
nhận giá trị 2, 3, 4, 5 |
|
for x in range(2, 10, 2): print(x) |
range(2,10,2) trả về một đoạn gồm các số nguyên
[2, 4, 6, 8] |
|
s = 0 for i in range(7, 3, -1): s += i print(s) |
- i lần
lượt nhận giá trị 7, 6, 5, 4 (Lặp lùi) |
|
fruits = ["Táo", "Chuối",
"Đào"] for x in fruits: print(x) |
x lần lượt nhận giá trị trong
một danh sách
cho trước |
|
for x in "banana": print(x) |
Duyệt qua lần
lượt các chữ cái của chuỗi “banana” |
|
L = ["a", "b", "c"] for x in L: print(x) if
x == "b": break |
Lệnh break giúp dừng vòng lặp sau khi in a và b ra màn hình. |
|
L = ["a", "b", "c"] for x in L: if x == "b": break print(x) |
Chỉ
in a, không in b. Vì nếu x = ‘b’ thì đã ngắt
vòng lặp |
|
L = ["a",
"b", "c"] for x in L: if x == "b": continue print(x) s = s
+ x |
Lệnh continue
giúp bỏ qua 2 lệnh phía dưới và chuyển sang
lần lặp tiếp
theo. Kết quả
sẽ in ra a và c |
2.
Lặp với số lần chưa biết trước:
- Cú pháp lệnh while:
While điều kiện:
Khối lệnh lặp
- Ý nghĩa:
Khi nào điều kiện còn đúng
thì khối lệnh lặp vȁn còn được
thực hiện
|
Ví dụ |
Ý nghĩa,
kết quả |
|
i = 1 while i < 6: print(i) i +=
1 |
Sẽ
in ra màn hình 5 dòng lần lượt 5 số: 1 2 3 4 5 |
|
x = 1 while x <= 10: print(x, end = “ “) x += 3 |
-
sẽ in ra màn hình 4 số cách nhau dấu cách:
1 4 7 10 |
|
i = 1 while i < 6: print(i) if i == 3: break i += 1 |
In ra màn hình
ba số 1, 2, 3 trên
ba dòng. Vì khi i = 3 thì đã
ngắt vòng lặp |
|
i = 0 while i < 6: i += 1 if i == 3: continue print(i) |
- Chỉ in ra màn hình các số 1, 2, 4, 5, 6. - Không
in số 3 vì khi i = 3 thì thực hiện lệnh continue
để bỏ qua các lệnh còn lại cùng khối lặp |
CHỦ ĐỀ
5: KIỂU DANH SÁCH – LIST
1. Khái niệm,
khai báo:
- Ở Pascal hay
C/C++ ta đã làm quen với khái niệm mảng một chiều,
ở Python không còn khái niệm
này mà thay vào đó
là kiểu list mạnh mẽ hơn.
-
List là một danh sách các phần tử có cùng kiểu hoặc khác kiểu được đánh số. Phần tử đầu tiên
được đánh chỉ
số là 0. Mục tiêu dùng một biến duy nhất để lưu nhiều
đối tượng.
- Ví
dụ: a = [7, 4, 9.8, ‘Chào’, ‘Phú’] dùng một biến
a để quản lý và lưu trữ 5 đối tượng.
Phần tử đầu tiên có thể truy cập
thông qua chỉ số:
a[0] = 7. Phần tử thứ 5: a[4] = ‘Phú’
2.
Một số thao tác với List:
|
Công việc
cần thực hiện |
Lệnh tương ứng |
|
Khởi tạo a là một list trống chưa có phần tử |
a = [] |
|
Khởi tạo list gồm 5 phần
tử: a = [0, 0, 0, 0, 0] |
a = [0]*5 |
|
Khởi tạo list
gồm 6 phần tử: b = [1, 2, 3, 4, 5, 6] |
b = [i for i in range(1,7)] |
|
Nhập vào list gồm các số nguyên
cách nhau dấu cách trên cùng một dòng |
a = [int(x) for x in
input().split()] |
|
Nhập vào list gồm các số nguyên cách nhau dấu cách trên cùng một dòng (Cách 2) |
a = list(map(int, input().split())) |
|
Nhập một list gồm các số thực trên
một dòng |
a = list(map(float, input().split())) |
|
Nhập một list gồm n số nguyên,
mỗi số trên
một dòng. |
a = [] for
i in range(n): a.append(int(input())) |
|
in list a, mỗi phần tử một dòng |
for
x in a: print(x) |
|
in list a trên
một dòng, các phần tử cách nhau một dấu cách |
for
x in a: print(x, end='
') |
|
in list
a gồm các số nguyên
trên một dòng,
các phần tử cách
nhau một dấu cách (cách 2 nhanh hơn) |
print(' '.join(str(x) for x in a)) |
|
in list a gồm các chuỗi kí tự trên một dòng, các phần tử cách nhau
một dấu cách |
print(' '.join(x for x in a)) |
|
Sao
chép list a từ phần tử a[2]
đến hết |
b = a[2:] |
|
Sao
chép list a từ phần tử a[0] đến phần tử a[3] |
b = a[:4] |
|
Sao chép list a
từ phần tử a[3] đến a[6] |
b = a[3:7] |
|
Sao
chép list a chỉ
lấy a[2], a[4], a[6] |
b = a[2:7:2] |
|
Số lượng
phần tử trong
list |
n = len(a) |
|
Duyệt các phần tử trong list từ
đầu đến cuối |
for x in a: print(x) |
|
Thêm một phần tử vào list |
a.append(x) |
|
Thêm phần
tử x vào vị trí u |
a.insert(u, x) |
|
Xoá phần
tử cuối cùng khỏi list |
a.pop() |
|
Xoá phần tử đầu tiên
trong list có giá trị
là x |
a.remove(x) |
|
Xoá hết toàn bộ list |
a.clear() |
|
Đếm có bao nhiêu phần tử có giá trị là x có mặt trong list |
a.count(x) |
|
Trả về True
nếu x có mặt trong list a |
x in a |
|
Trả về giá trị phần tử lớn nhất trong list |
a.max() |
|
Trả về giá trị
phần tử nhỏ nhất trong list |
a.min() |
|
Đảo ngược toàn
bộ list |
a.reverse() |
|
Sắp xếp list tăng dần |
a.sort() |
|
Sắp xếp list giảm
dần |
a.sort(reverse=True) |
3. Ví dụ minh hoạ:
|
Bài
tập |
Code
minh hoạ |
|||
|
Lập trình nhập vào một số nguyên dương N và dãy số nguyên A gồm N phần tử. Tìm phần tử lớn nhất của dãy số nguyên
cùng vị trí của nó.
(0 < n < 10000;
|Ai| < 10^9).
Nếu có nhiều phần tử cùng có giá trị lớn nhất thì đáp án là phần
tử có vị trí bé nhất. |
n = int(input()) a = list(map(int,
input().split())) amax = max(a) print(amax, end=' ') for i in
range(n): if a[i] == amax: print(i+1) break |
|||
|
|
Dữ liệu nhập |
Kết quả |
|
|
|
|
5 1 12 -4 -3 12 |
12 2 |
||
|
Lập trình nhập vào N và dãy số A |
n = int(input()) a = [int(x) for x in input().split()] a.sort() print(*a)
Hoặc cách 2: nhanh hơn
ở thao tác in:
n = int(input()) a = list(map(int, input().split())) a.sort() print(' '.join(str(x) for x in
a)) |
|||
|
gồm N phần
tử (5 < N < 1000). Em hãy sắp |
||||
|
xếp dãy A thành
dãy số không
giảm và |
||||
|
thông báo dãy A ra màn hình sau khi đã sắp |
||||
|
xếp. |
||||
|
|
Dữ liệu nhập |
Kết quả |
|
|
|
|
5 |
1 2 3 4 5 |
||
|
1 3 2 5 4 |
|
|||
4.
Mảng hai chiều:
- Ta có thể tạo list mà
mỗi phần tử là một list
để thành ra tương đương mảng hai chiều
- Sau đây minh hoạ thao tác nhập
và in:
m, n
= map(int, input().split())
a = [[]*n for i in range(m)]
for x in range(m):
a[x] = list(map(int, input().split()))
#in mảng hai chiều
print(m,
n)
for x in range(m): print(*a[x])
- Một số ví dụ:
|
Bài tập |
Code minh hoạ |
|||
|
Cho mảng hai chiều kích thước NxN (N dòng và N cột). Lập trình nhập vào mảng này, tìm và thông báo ra màn hình các số lớn nhất
trên mỗi hàng. (1 < N <
15) |
n = int(input()) a = [] for i in range(n): u = list(map(int,input().split())) a.append(u) for i in range(n): print(max(a[i])) |
|||
|
|
Dữ liệu
nhập |
Kết quả |
|
|
|
|
3 1 2 3 4 5 6 7 8 9 |
3 6 9 |
||
|
Lập trình nhập vào mảng hai chiều gồm m dòng n cột chỉ gồm các số nguyên. Tính tổng các phần
tử trên mỗi
cột và thông
báo các tổng này
ra màn hình. (1 <
m, n < 100) |
m,
n = map(int,
input().split()) a = [[]*n
for i in range(m)] for i in
range(m): a[i]
= list(map(int, input().split())) for j in range(n): sum
= 0 for i in range(m): sum
+= a[i][j] print(sum) |
|||
|
|
Dữ liệu
nhập |
Kết quả |
|
|
|
|
2 3 1 2 3 4 5 6 |
5 7 9 |
||
CHỦ ĐỀ
5: KIỂU DỮ LIỆU XÂU
1. Khái niệm:
- Kiểu xâu trong
Python là một dãy
kí tự nằm giữa hai dấu
ngoặc đơn hoặc ngoặc kép. Ví dụ: “Chào
bạn”, ‘Ban oi’,
‘QuangTri2022’ …
- Có thể xem xâu kí tự là một danh sách kí tự liên tiếp nhau được đánh số thứ tự bắt đầu từ 0. Ví dụ: với s = ‘THPTVinhDinh’ thì s[0] = ‘T’, s[4] = ‘V’, s[7] = ‘h’.
- Nhập vào một xâu kí tự dùng hàm input(). Ví dụ: s
= input()
- Để in một
xâu kí tự ra màn hình ra dùng hàm print(). Ví dụ: print(s)
- Duyệt qua từng kí tự trong chuỗi lần lượt
từ đầu đến hết ta có thể
sử dụng vòng lặp for:
for x in s:
print(s)
Hoặc duyệt theo chỉ số:
for i in range(len(s)): print(s[i])
- Để tìm kiếm một xâu kí tự có xuất
hiện trong xâu khác hay không: dùng toán
tử in
if 'quang' in 'quangtri': print('có xuất hiện')
- Để tìm vị trí xuất hiện một xâu kí tự trong xâu khác dùng hàm find().
Hàm này trả về vị trí xuất hiện
đầu tiên,
nếu không xuất hiện sẽ
trả về -1. Ví dụ
sau cho ra đáp án: Co xuat hien tai vi tri 5
s = 'QuangTri_2022'
if s.find('Tri') > -1:
print('Co xuat hien tai vi tri', s.find('Tri'))
- Lệnh tách xâu
con dựa vào kí tự quy định. Ví dụ sau sẽ tách xâu
s = ‘Quang Tri 2022’ ra
thành một danh sách: a = ['Quang', 'Tri',
'2022']
s =
'Quang Tri 2022' a = s.split(' ')
- Ví dụ sau tương tự nhưng tách
căn cứ vào dấu phẩy:
s =
'Quang,Tri,2022' a = s.split(',')
2.
Một số thao tác khác trên xâu kí tự:
Các thao tác sau minh
hoạ trên xâu s = ‘chao’
|
Thao
tác |
Ý nghĩa |
|
s = ‘ban’
+ ‘Toi’ |
Thao tác nối
hai xâu thành 1. S = ‘banToi’ |
|
s = s*3 |
Lặp lại xâu s
3 lần. s = ‘chaochaochao’ |
|
s = s.capitalize() |
In hoa kí tự đầu
tiên của S, các kí tự khác
giữ nguyên. |
|
s = s.title() |
In hoa kí
tự đầu tiên mỗi từ.
s = ‘chao ban’ à ‘Chao
Ban’ |
|
s = s.lower() |
Chuyển toàn bộ
xâu s về thành kí tự thường |
|
s = s.upper() |
Chuyển toàn bộ xâu
s về thành kí tự in hoa |
|
x = s.count(‘p’) |
Đếm xem trong xâu
s có bao nhiêu kí tự ‘p’ |
|
s.isalnum() |
Trả về True nếu xâu s chỉ chứa
kí tự chữ cái và chữ số |
|
s.isalpha() |
Trả về True nếu xâu s chỉ chứa
kí tự chữ cái và không
rỗng |
|
s.isdecimal() |
Trả về True nếu xâu s chỉ chứa
kí tự số và không rỗng |
|
s.islower() |
Trả về True nếu xâu s chứa ít nhất 1 kí tự thường
và không chứa kí tự in
HOA |
|
s.isupper() |
Tương tự hàm trên |
|
s.find(x) s.rfind(x) |
Trả về vị trí đầu tiên/cuối cùng
xuất hiện xâu x. Nếu không xuất hiện thì trả về
-1. |
|
s = s.lstrip() s = s.rstrip() s = s.trip() |
Xoá hết kí tự trắng bên trái/phải/cả hai bên xâu s Ví dụ: s = s.lstrip() sẽ xoá kí tự
trắng có bên trái xâu s |
|
s = s.zfill(x) |
Thêm vào
kí tự không bên trái để xâu
s có độ dài x s = ‘15’, s = s.zfill(4) às = ‘0015’ |
|
s = s.swapcase() |
Đổi kí tự hoa thành
thường và thường
thành hoa. |
|
x = int(s) |
int() giúp chuyển xâu số sang thành
số |
|
s = str(x) |
str() chuyển số x sang thành một xâu |
|
ord(s[i]) |
Lấy ra
mã ascii của kí tự s[i] |
|
chr(x) |
Lấy ra kí tự
có mã ascii là x |
|
r = s[:x] |
Sao chép x kí tự đầu
tiên của xâu s |
|
r = s[x:] |
Sao chép xâu s từ
vị trí x đến hết xâu |
|
r = s[3:6] |
Sao chép các kí tự từ
vị trí 3 đến 5 của xâu s |
|
s = s[:x] + s[x+1:] |
Xoá kí tự ở
vị trí x của xâu s |
|
s = s.replace('h', '') |
Xoá hết kí tự
‘h’ của xâu s |
3.
Một số ví dụ vận dụng:
|
Bài
tập |
Code tương
ứng |
|||
|
Lập trình
nhập vào một xâu kí tự, đếm và thông báo ra màn hình số lượng kí tự A có mặt
trong xâu. |
s = input() print(s.count('A')) |
|||
|
Một xâu được gọi là xâu chuẩn nếu:
không có kí tự trắng dư thừa đầu và cuối xâu; không có hai kí tự trắng liền nhau. Em hãy lập trình
nhập vào một xâu và in ra màn hình xâu sau khi đã chuẩn hóa |
s = input() while s.find(' ') >
-1: s = s.replace(' ', ' ')
s = s.strip() print(s) |
|||
|
|
Dữ liệu nhập |
Kết quả |
|
|
|
|
Chao ban |
Chao ban |
||
|
Lập trình nhập vào một xâu họ tên chuẩn
và thông báo ra màn
hình tên của xâu vừa nhập. |
a = input().split(' ') print(a[len(a) - 1])
Hoặc:
a = input().split('
') a.reverse() print(a[0]) |
|||
|
|
Dữ liệu nhập |
Kết quả |
|
|
|
|
Le Thanh Huy |
Huy |
||
CHỦ ĐỀ 6: KIỂU
DỮ LIỆU TỆP
1.
Một số khái niệm:
Về cơ bản, cũng như trong hầu hết các ngôn ngữ lập trình, quá trình làm việc với tệp tin
thường bao gồm 3 giai
đoạn sau:
·
Mở tệp tin
·
Thực hiện các hoạt động đọc,
ghi dữ liệu
·
Đóng tệp tin để đảm bảo dữ liệu không bị hỏng hóc,
mất mát
* Mở tệp:
- Để mở một
file, chúng ta sử dụng hàm open
với cú pháp:
Biến tệp = open("tên tệp","chế độ mở", encoding="kiểu mã hóa")
- Trong đó:
·
Chế độ mở: ‘r’ để đọc, ‘w’ để
ghi, ‘a’ mở để ghi thêm dữ liệu vào
cuối
·
Kiểu mã
hoá: Nếu
đọc ghi tệp văn bản tiếng Việt
không dấu thì không cần tham số này.
Nếu
đọc ghi tệp tiếng
Việt có dấu thì dùng ‘utf-8’
- Ví dụ 1: Mở tệp
Baitap1.inp để đọc dữ liệu
f = open("Baitap1.inp", "r")
- Ví dụ 2: Mở tệp baitap2.inp để đọc văn bản
tiếng Việt có dấu
f = open("Baitap2.inp", "r", encoding="utf-8")
- Ví dụ 3: Mở tệp baitap2.out để ghi kết quả
g = open("Baitap2.out", "w")
* Đọc/ghi dữ liệu:
- Đọc dữ liệu: Biếntệp.readline() để đọc một dòng
- Ghi
dữ liệu: Biếntệp.write(x) để ghi x
vào tệp
* Đóng tệp:
- Cú pháp: Biếntệp.close()
2. Làm việc với tệp trong các kỳ thi HSG:
- Khi vào ra tệp trong các kỳ thi, thao tác trên biến tệp rất dễ nhầm lȁn. Thay vào đó ta có thể sử dụng tệp vào ra chuẩn. Để mở tệp thì trong phần đầu chương trình
ta khai báo như
sau:
import
sys
sys.stdin
= open("Baitap1.inp", "r")
sys.stdout = open("Baitap1.out", "w")
- Lệnh này chuyển hướng vào ra chuẩn thành
vào ra tệp. Khi sử dụng tệp chuẩn này thì mọi thao tác nhập, xuất thông tin giống như vào ra bàn phím màn hình mà ta
đã học từ trước đến giờ.
- Python đọc dữ liệu từ tệp khá chậm, để đọc dữ liệu từ tệp nhanh ta chỉ cần khai báo thêm lệnh sau:
input = sys.stdin.readline
3.
Một số ví dụ:
|
Bài
tập |
Code tương
ứng |
|
Dòng họ Tula vốn giàu có thịnh vượng
nhưng do nội chiến xảy ra họ phải chia ly. Các vị tiền bối cất châu báu vào một mật thất. Họ giao cho K (1 ≤ K ≤ 1000) người
con mỗi người
cất giữ một phần của mã số bí mật của kho báu. Người thứ i giữ mã khoá x[i] (1 ≤ x[i] ≤ 109). Yêu cầu: Khi nội chiến kết thúc, hãy giúp K người con
tìm mã khoá
để mở kho báu biết |
import sys import math sys.stdin = open("Timkhoa.inp", "r") sys.stdout
= open("Timkhoa.out",
"w") input = sys.stdin.readline k = int(input()) a =
list(map(int, input().split())) uc = a[0] for x in a: uc = math.gcd(uc,
x) print(uc) |
|
|
rằng mã khoá là một số nguyên dương
lớn nhất M mà tất cả mã số của K người
con đều chia hết. |
|
|||
|
|
TIMKHOA.INP |
TIMKHOA.OUT |
|
|
|
|
6 48 54 6 36 6 12 |
6 |
||
|
Ở vương quốc
NONAME người ta đưa |
import sys sys.stdin = open("HOHANG.inp", "r") sys.stdout = open("HOHANG.out", "w") input = sys.stdin.readline T = int(input()) for i in
range(T): n = int(input()) s = input().rstrip() r = input().rstrip() if sorted(s)
== sorted(r): print(1) else: print(0)
Code trên sử dụng đọc dữ liệu theo dòng nên sẽ đọc cả dấu ‘\n’
ở cuối dòng. Nếu dữ liệu là xâu kí tự thì thêm lệnh
rstrip() để loại kí tự này trước
khi xử lý: s = input().rstrip() |
|||
|
ra một quy tắc đặt tên kỳ lạ: Mỗi dòng họ |
||||
|
chọn một
dãy kí tự độ dài n
chỉ gồm các kí |
||||
|
tự in hoa trong
bảng chữ cái tiếng Anh.
Khi |
||||
|
đó để đặt tên cho một người trong
dòng |
||||
|
họ thì chỉ cần thay đổi thứ tự
của các kí tự |
||||
|
với nhau. |
||||
|
Yêu cầu: Cho biết hai xâu tên của hai |
||||
|
người trong
vương quốc, hãy
kiểm tra xem |
||||
|
hai người
này có cùng
dòng họ hay không. |
||||
|
|
HOHANG.INP |
HOHANG.OUT |
|
|
|
|
3 |
0 |
||
|
3 |
0 |
|||
|
LLQ |
1 |
|||
|
KHQ |
|
|||
|
3 |
|
|||
|
FDF |
|
|||
|
GDD |
|
|||
|
3 |
|
|||
|
KWE |
|
|||
|
EKW |
|
|||
|
Cho tệp danh sách gồm nhiều dòng, mỗi dòng là một dãy số nguyên dương gồm 3 số. Em hãy lập trình đọc thông tin từ
danh sách này, tính tổng của mỗi dãy số và in kết
quả ra màn
hình. TEPSO.INP TEPSO.OUT 5 3 5 13 2 3 4 9 5 4 3 12 |
import sys |
|||
|
sys.stdin = open("TEPSO.inp", "r") |
||||
|
sys.stdout = open("TEPSO2.out", "w") |
||||
|
while True: |
||||
|
try: |
||||
|
x,y,z = map(int,input().split()) |
||||
|
print(x + y + z) |
||||
|
except: |
||||
|
break |
||||
|
Do tệp không biết bao nhiêu
dòng nên |
||||
|
dùng while để đọc. Lệnh try giúp bắt lỗi khi đọc |
||||
|
hết tệp để break kết thúc vòng lặp. |
||||
CHỦ ĐỀ 7: CHƯƠNG TRÌNH CON
1.
Lý thuyết:
- Kỹ
thuật lập trình dȁn đến việc tổ chức chương trình kiểu cấu trúc modul hóa, tức
là chia chương trình thành nhiều
modul hay gọi là các chương trình con nhỏ hơn. Nó đem lại cho người lập trình các lợi
ích:
·
Thay các đoạn trình giống nhau bằng một chương trình
con, làm cho mã chương trình ngắn hơn, sáng sủa và dễ bảo dưỡng.
·
Đưa các chương trình con đã kiểm
tra vào thư viện (library) để khi lập trình mới thì chỉ cần liên kết tới thư viện đó.
·
Những chương trình lớn được thiết kế dạng cấu trúc tốt có thể trao cho các nhóm và người lập trình khác nhau lập trình, đôi
khi có thể thuê người làm thêm viết các chương trình con không quá phức tạp.
- Python hỗ trợ hai loại chương
trình con:
·
Hàm trả về giá trị
·
Hàm không trả về giá trị
- Cú pháp:
def <tên hàm>(<danh sách tham số>):
Dãy lệnh của hàm
Return [giá trị trả về]
- Trong đó:
·
Danh sách tham số: có thể có hoặc không
·
Giá trị trả về : Tuỳ theo chương trình con, nếu không cần trả về giá trị thì không cần cái
này.
- Lời
gọi chương trình con: Một chương trình con có thể được thực hiện với nhiều giá
trị khác nhau do chương trình truyền
vào thông qua lời gọi hàm.
2.
Một số ví dụ:
|
Bài
tập |
Code tương
ứng |
|||
|
Xây
dựng hàm yêu cầu người dùng nhập họ tên rồi
đưa ra lời chào. Hàm này không có tham số, nên muốn
sử dụng hàm này sẽ gọi: chaomung() |
def chaomung(): ten = input("Bạn tên gì: ") print("Chào
bạn", ten) return |
|||
|
Xây
dựng hàm trả về giá trị là tổng hai số nguyên. Hàm này có tham số nên khi gọi phải
đầy đủ hai tham số như
khai báo. Ví dụ: s = tong(3,
5) Hoặc print(tong(a, b)) |
def tong(u, v): s = u + v return s |
|||
|
Hãy mô tả hàm Fact(n) để tính giá
trị n giai thừa. (0 < N < 200) Cho một danh sách có dòng đầu
tiên là số M, m dòng
tiếp theo mỗi dòng là một số nguyên
dương N. Lập trình đọc dữ liệu từ danh sách,
tính giai thừa
của m số đó và thông báo
kết quả. |
import sys sys.stdin = open("Fact.inp", "r") sys.stdout
= open("Fact.out",
"w") input = sys.stdin.readline
def Fact(n): gt = 1 for i in range(1,
n+1): gt *= i return gt |
|||
|
|
Fact.INP |
Fact.OUT |
|
|
|
|
3 |
2 |
||
|
||||||
|
|
|
2 4 |
24 |
|
m = int(input()) for i in range(m): n = int(input()) print(Fact(n)) |
|
|
||||
|
Viết chương trình con Prime(x) để
kiểm tra x có phải là số nguyên
tố hay không. Vận dụng chương trình con vừa viết
lập trình nhập vào dãy số nguyên
a[1], a[2]…, a[n], đếm có bao nhiêu
cặp thoả mãn điều kiện a[i]
+ a[j] (𝑖 ≤ 𝑗) là một số nguyên
tố. NTO.INP NTO.OUT 4 5 1 2 3 4 |
import sys sys.stdin = open("NTO.inp", "r") sys.stdout
= open("NTO.out", "w") input = sys.stdin.readline
def Prime(x): if x <=
1: return 0 for i in range(2,
int(x**0.5)+1): if x % i == 0: return 0 return 1
n = int(input()) a = list(map(int,
input().split())) dem = 0 for i in range(n): for j in range(i, n): if Prime(a[i]+a[j])
== 1: dem += 1 print(dem) |
|||
|
Viết chương trình con chuanHoa(s)
có nhiệm vụ xoá đi các kí tự trắng
dư thừa có mặt trong
xâu s. Vận dụng chương trình con vừa viết
để đọc thông tin của các bạn học sinh,
tách lấy và in ra màn hình họ đệm cùng tên của
các bạn học sinh này đã chuẩn hoá
và in hoa mỗi đầu
từ. CHUAN.INP CHUAN.OUT Le thanh phu Thanh Phu Tran HUNG son Hung Son |
import sys sys.stdin = open("CHUAN.inp",
"r") sys.stdout = open("CHUAN.out", "w")
def chuanHoa(s): while s.find(' ') > -1: s = s.replace(' ', ' ')
s = s.strip() return s
while True: try: s = input() s = chuanHoa(s) vt = s.find('
') s = s[vt+1:] s = s.lower() s = s.title() print(s) except: break |
|||
CHỦ ĐỀ
8: MỘT SỐ THỨ CĂN BẢN
KHÁC KHI BỒI DƯỠNG HSG
1. Số nguyên tố:
|
Bài
toán |
Chương trình
tương ứng |
|
Kiểm tra số nguyên tố - Thuật toán duyệt căn |
def Prime(x): if x <=
1: return 0 for i in range(2,
int(x**0.5)+1): if x % i == 0: return 0 return 1 |
|
Kiểm tra số nguyên tố - Thuật toán 6k |
def Prime6k(x): if x <= 1: return 0 if (x == 2) or (x == 3): return 1 if (x % 2 == 0)
or (x % 3 == 0): return 0 k,
can = 5, int(math.sqrt(x)) for k in
range(5, can,
6): if (x % k == 0) or (x % (k+2) == 0): return 0 return 1 |
|
Kiểm tra số nguyên tố - Thuật toán
Rabin Miller - Thuật này phức tạp chỉ dành
cho các bạn đam mê tìm
hiểu |
|
|
Sàng eratos: - Tạo sàng
eratos có giới
hạn m |
def eratos(m): e = [0, 0] + [1]*m can = int(math.sqrt(m)) for i in range(2, can): if e[i] == 1: for j in range(i*i,
m, i): e[j] = 0 return e |
2. Ước/ Bội:
|
Ước chung lớn nhất: - Tìm UCLN của hai số a và b |
import math a, b = map(int, input().split()) uc = math.gcd(a, b) |
|
Bội chung nhỏ nhất - Tìm
BCNN của hai số a, b |
import math a, b = map(int, input().split()) bc = (a // math.gcd(a, b)) * b |
|
Ước chung lớn nhất: - Tìm UCLN
của a[1..n] |
import math a = list(map(int,
input().split())) uc = 0 for x in a: uc = math.gcd(uc, x) print(uc) |
|
Bội chung nhỏ nhất: - Tìm
BCNN của a[1..n] |
import math a = list(map(int, input().split())) bc = 1 for x in a: bc = (bc
// math.gcd(bc, x)) * x print(bc) |
3. Sắp xếp:
|
Thao
tác |
Lệnh tương
ứng |
|||
|
Sắp xếp list tăng dần theo
giá trị - List xâu thì tăng
dần theo thứ tự từ điển |
a.sort() |
|||
|
Giảm dần |
a.sort(reverse=True) |
|||
|
Sắp xếp xâu tăng dần |
s = ''.join(sorted(s)) - Vì xâu
không có hàm sort
nên dùng sorted(s) sẽ tạo ra
một list kí tự tăng dần. - ‘’.join() giúp
nối list kí tự này lại thành
xâu |
|||
|
Sắp xếp xâu
giảm dần |
s = ''.join(sorted(s, reverse=True)) |
|||
|
Sắp xếp list tăng
dần theo một điều kiện đặc biệt: Ví dụ ·
theo tổng chữ
số tăng dần ·
Cùng tổng chữ số thì giá trị tăng dần [12,
20, 4, 21]à[20, 12, 21,4] |
def tongcs(u): sum = 0 while u >
0: sum += (u % 10) u //= 10 return sum
def cmp(u): return (tongcs(u), u)
a.sort(key=cmp) |
|||
|
Cho một dãy số nguyên gồm n phần tử A[1]..A[n]. Hãy Sắp xếp dãy số theo thứ tự không giảm rồi in dãy số ra màn hình. Ràng buộc: ·
1 <= n <= 100000 ·
1 <= A[i] <=
10^25 |
n = int(input()) a = list(input().split())
def cmp(u): return
(len(u), u)
a.sort(key=cmp) print(' '.join(x for x in
a))
- Do a[i] <=
10^25 nên phải dùng xâu để lưu trữ. Tức mỗi
phần tử của list là một xâu. Vậy phải viết hàm so sánh, vì sort
mặc định sẽ theo thứ tự
từ điển. - Hàm này trước hết sẽ so sánh theo độ dài, ngắn hơn là số bé hơn (Vì không có số 0 ở đầu), nếu
dài bằng nhau
thì số nào bé hơn
sẽ bé hơn. |
|||
|
Có n con virut,
con thứ i có sức phá hoại
là a[i] và khả năng phát tán là b[i]. Hãy sắp xếp các con virut theo thứ tự sức phá hoại bằng hoặc tăng dần. Nếu cùng sức phá hoại thì sắp xếp theo khả năng phát tán tăng dần. |
n = int(input()) a = [] for i in range(n): u, v = map(int, input().split()) a.append([u, v])
def cmp(u): return (u[0],
u[1])
a.sort(key=cmp) for x in a: print(x[0], x[1]) |
|||
|
|
Nhập |
Xuất |
|
|
|
|
4 5 1 1 1 1 3 |
1 1 1 3 1 7 5 1 |
||
|
|
1 7 |
|
|
|
|
Có n con virut, con thứ i có sức
phá hoại là a[i] và khả năng
phát tán là b[i] và khả năng bị tiêu diệt là c[i]. Hãy sắp xếp
các con virut theo thứ tự khả năng
bị tiêu diệt không giảm. Nếu cùng
khả năng bị tiêu diệt thì sắp xếp
theo khả năng phát tán không
tăng. Nếu giống nhau cả khả năng bị
tiêu diệt và khả năng phát tán thì sắp xếp theo khả năng phá hoại không tăng. Ví dụ: con
virut (2, 5, 1) sẽ xếp trước
con virut (2, 4, 1); con virut (2, 4, 1) sẽ xếp trước con virut (1, 4, 1). |
n = int(input()) a = [] for i in range(n): u,v,z = map(int,input().split()) a.append([u, v, z])
def cmp(u): return (u[2],
-u[1], -u[0])
a.sort(key=cmp) for x in a: print(x[0], x[1],
x[2])
Hàm so sánh
cmp(u): - Đầu
tiên so sánh theo u[2] là khả năng bị tiêu diệt bé hơn đứng trước tức
không giảm - Nếu cùng u[2] thì
so sánh theo -u[1] là khả năng phát tán
bé hơn đứng trước, mà -u[1] bé hơn trước tương đương với u[1]
lớn hơn xếp trước,
tức là không giảm. - Nếu cùng hai cái đầu
thì sẽ so sánh theo -u[0] bé hơn xếp trước. |
|||
|
|
Nhập |
Xuất |
|
|
|
|
4 1 1 1 7 9 9 3 1 1 6 7 1 |
6 7 1 3 1 1 1 1 1 7 9 9 |
||
|
Tèo đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Tí về thành
quả vừa đạt được.
Tuy nhiên, khi Tèo vừa ra khỏi phòng
để gọi anh trai thì cô em Mì chạy
vào phòng và xé rách cuộn giấy thành
một số mảnh. Kết quả là trên mỗi mảnh
có một hoặc
vài kí số theo thứ
tự đã viết. Bây giờ Tèo không thể nhớ chính xác mình đã viết số gì. Tèo chỉ nhớ rằng đó là một số rất lớn. Để làm hài lòng cậu em trai, Tí quyết định truy tìm số nào là lớn nhất mà Tèo đã có thể viết lên cuộn giây
trước khi bị xé. Bạn hãy giúp
Tí làm việc này. Ràng buộc: ·
0 < n < 5050 ·
Số chữ số trên mỗi mảnh giấy
không quá 100. |
import functools
n = int(input()) a = [] for i in range(n): s = input() a.append(s)
def cmp(u, v): if u+v > v+u: return
-1 if u+v == v+u: return 0 return 1
a.sort(key=functools.cmp_to_key(cmp)) print(''.join(x for x in a))
-
Theo quy định: Hàm so sánh cmp(u,v) phải trả về -1, 0, 1: ·
-1: Nếu
u sắp xếp trước v ·
1: Nếu u sắp
xếp sau v ·
0 thì sếp
đâu cũng giống nhau - Hàm trên so sánh để quyết định xâu u xếp trước xâu v khi nào: ·
u xếp trước tạo ra
xâu số: u+v ·
u xếp sau tạo ra xâu
số: v+u |
|||
|
|
Nhập |
Xuất |
|
|
|
|
|
4 2 20 004 66 |
66220004 |
|
- Hai xâu u+v và v+u có cùng
độ dài nên xâu nào bé hơn
theo thứ tự từ điển
thì số tạo thành bé hơn. |
4. Tìm kiếm nhị phân:
- Có thư viện bisect cung cấp hai hàm tìm
kiếm nhị phân rất hay:
·
u = bisect.bisect_left(a, x) : Trả về vị trí bé nhất trong
a thoả mãn 𝑎[𝑢] ≥ 𝑥. Nếu tất cả phần tử trong a
đều bé hơn x thì sẽ trả về u =
len(a) + 1.
·
u = bisect.bisect_right(a, x) : Trả về vị trí bé nhất trong a thoả mãn 𝑎[𝑢] > 𝑥. Nếu tất cả phần tử trong
a đều bé hơn x thì sẽ trả về u =
len(a) + 1.
|
Thao
tác |
Lệnh tương
ứng |
|||
|
Bạn được cho
hai dãy số nguyên A và
B, mỗi dãy có N phần tử.
Nhiệm vụ của bạn là đếm xem
có bao nhiêu
phần tử của
dãy A xuất hiện trong dãy B. (𝑁 ≤ 105)
Nhập Xuất 5 4 2 3 1 4
5 1 2 3 4
8 |
import bisect n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) b.sort() dem = 0 for x in a: u = bisect.bisect_left(b,
x) if u < len(b) and b[u] == x: dem += 1 print(dem) |
|||
|
Nhân dịp tết trung thu, Nam được bố mẹ cho đi dự lễ hội đêm trăng rằm. Tại lễ hội này nam đã tích cực tham gia các trò
chơi và giành
được X điểm
thưởng. Nam dùng X điểm thưởng này để đổi quà. Ban tổ chức có N món quà khác nhau, món thứ i có giá
trị A[i] điểm. Với số điểm X Nam
quyết định sẽ đổi hai món quà khác nhau
có tổng giá trị lớn nhất có
thể nhưng không vượt quá X. Bạn hãy
xác định giúp Nam tổng giá
trị quà Nam
đổi được là bao
nhiêu. (𝑁 ≤ 105) |
import bisect n, x = map(int, input().split()) a = list(map(int, input().split())) a.sort() #a[i] + a[j]
<= X --> a[j] <=
X - a[i] qua = 0 for i in range(n): j = bisect.bisect_right(a, x - a[i]) - 1 if i
< j and j < n: qua = max(qua, a[i] + a[j]) print(qua) |
|||
|
|
Nhập |
Xuất |
|
|
|
|
6 18 5 3 10 2 4 9 |
15 |
||
5.
Heap:
- Heap
là loại cấu trúc dữ liệu dạng cây, và tất cả các node trong cây đó được sắp xếp
theo một thứ tự nhất định, có thể là theo chiều tăng dần hoặc giảm dần.
- Python cung cấp thư viện heapq
để thao tác với heap:
Mặc định là heap min
·
heapq.heapify(a) Chuyển list a
thành heap
·
u = heapq.heappop(hp) Lấy phần tử nhỏ nhất ra khỏi heap
·
heapq.heappush(hp, u) Đưa phần tử u vào heap
- Ví dụ:
|
Bài
tập |
Chương trình |
|||
|
Có n đống sỏi được đánh số từ 1 đến n, đống thứ i có a[i] viên sỏi. Ta có
thể ghép hai đống sỏi với nhau
thành một đống với chi phí là tổng
số sỏi của hai đống đó. Yêu cầu: Tìm cách
ghép n đống
sỏi thành
1 đống duy nhất với tổng chi phí ghép nhỏ nhất. |
import heapq n = int(input()) a = list(map(int, input().split())) hp = [] for x in a: heapq.heappush(hp,
x) chiphi = 0 while len(hp) > 1: u = heapq.heappop(hp) v = heapq.heappop(hp) chiphi
+= (u + v) heapq.heappush(hp,
u+v) print(chiphi) |
|||
|
|
Nhập |
Xuất |
|
|
|
|
3 2 8 2 |
16 |
||
6.
Dict – Python:
- Nếu
từng dùng mảng đánh dấu trong Pascal thì thấy rằng đây là cách làm tuyệt vời
giúp ta kiểm tra sự tồn tại của một số
rất nhanh trong O(1). Tuy nhiên mảng đánh dấu lại hạn chế bởi vì giới hạn khai báo
của mảng.
-
Trong Python cung cấp kiểu Dictionary giúp ta lưu trữ nhiều phần tử, mỗi phần tử là một cặp [key
: value] tức giúp
đánh dấu giá trị của key là value.
- Ví dụ: c
= {1: 'Phu', ‘ab’: 5} giúp ta đánh dấu
c[1] = ‘Phu’ và c[‘ab’] = 5.
- Kiểu Dict này trong Python linh động
và mạnh hơn mảng đánh dấu rất nhiều.
- Một số thao tác:
·
Khởi tạo một Dict rỗng: c = {}
·
Thêm phần tử (Đánh dấu) c[1] = ‘Phú’
·
Truy cập phần tử
x trong dict c.get(x)
·
Loại bỏ phần tử x khỏi dict del c[x]
·
Xoá hết, làm rỗng
dict c.clear()
·
Lấy ra
giá trị và xoá x khỏi dict u = c.pop(x)
-
|
Bài tập ví dụ:
|
Bài tập |
Chương trình |
|
Cho danh sách n số nguyên
dương có giá
trị không quá
một triệu. Lập trình tìm số nguyên
dương nhỏ nhất
chưa có mặt trong danh
sách trên. Nhập Xuất |
n = int(input()) a = list(map(int,
input().split())) c = {} for x in a: c[x] = 1 lim = max(a) + 1 for i in range(1, lim + 1): if c.get(i) == None: |
|
|
5 5 3 1 6 4 |
2 |
|
print(i) break |
|
Cho số nguyên dương n và dãy A gồm n số nguyên dương. Ta gọi một số a[i] là có bạn nếu tồn tại một vị trí j khác i và a[j]
= a[i]. Hãy
đếm số lượng
số có bạn trong dãy số
trên. Nhập Xuất 9 3 12 5 1 7 10 6 1 1 3 |
n = int(input()) a = list(map(int, input().split())) c = {} for x in a: if c.get(x) != None: c[x] += 1 else: c[x] = 1 dem = 0 for x in c: if
c.get(x) > 1: dem += c.get(x) print(dem) |
|||
7. 
Set – Python:
|
- Set trong Python là một tập các giá trị không có thứ tự. Mỗi giá trị trong set là duy nhất, không
thể lặp lại và bất biến (tức
bạn không thể thay đổi giá trị các phần tử trong set). Tuy nhiên chúng ta có thể thêm, xóa các phần tử
trong set.
- Sử dụng set khi nào:
·
Khi muốn quản lý một tập
các đối tượng phân biệt, không lưu trùng lặp
·
Thêm một phần tử tập nhanh:
O(1)
·
Xoá phần tử khỏi tập nhanh: O(1)
·
Kiểm tra nhanh một đối tượng có thuộc tập đang lưu hay không:
O(1)
- Một số thao tác
|
Thao
tác |
Ví dụ |
|
Khởi tạo
set: - Sử dụng
dấu {} hoặc
set() - Nếu có phần tử trùng nhau thì sẽ bị loại
bỏ chỉ giữ lại
một |
#set rỗng: S = set() #một set kiểu numbers S1 = {5,7,8,6}
#một set kiểu
string s2 = {"hello", "hi", "xin chao"}
#set với kiểu dữ liệu hỗn hợp s3 = {"hello", 5, (1,5,7)} |
|
Thêm phần tử - <tên set>.add(phần tử) |
S.add(5) |
|
Xoá phần tử: khuyên dùng discard để nếu xoá mà không
có x trong set sẽ không bị lỗi. - remove(x) - discard(x) |
S.discard(x) |
|
Xoá toàn bộ set - clear() |
S.clear() |
|
Kiểm tra phần
tử có trong set: - in - not in |
if x in S: print(‘Có’) |
- Ví dụ:
|
Bài
tập |
Chương trình |
|||
|
Sắn nhận được một vài tin nhắn từ những
người bạn. Một người có thể nhắn nhiều tin.
Hãy giúp Sắn liệt kê danh sách những người bạn đã gửi tin, mỗi người
chỉ một lần và theo
thứ tự thời gian gửi sớm nhất |
n = int(input()) a = list(input().split()) s = set() kq = [] for x in a: if x not in s: kq.append(x) s.add(x) print(' '.join(x for x in
kq)) |
|||
|
|
Nhập |
Xuất |
|
|
|
|
5 mi hue mi cuc duc |
mi hue cuc duc |
||
8. Một số Trick khác:
|
Bài
tập |
Chương trình |
|
- Cho một List, lấy
ra 4 số bé nhất,
3 số lớn nhất - Độ phức
tạp: O(nlogn) |
import heapq a = list(map(int, input().split())) print(heapq.nsmallest(4, a)) print(heapq.nlargest(3, a))
Kết
quả: [1, 2, 4, 4] [9, 8, 8] |
|
- Cho một list, lấy ra 3 phần tử có số lần
xuất hiện nhiều nhất - Độ phức
tạp: O(nlogn) |
import collections a = list(map(int, input().split())) b
= collections.Counter(a) print(b.most_common(3))
Kết quả: [(5, 6), (1, 5), (2, 4)] |
|
-
Sinh hoán vị độ dài 3: (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) |
import
itertools a = [1,2,3] b = list(itertools.permutations(a)) for x in b: print(x) |
|
-
Sinh tổ hợp chập 2 của 3: (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) |
import
itertools a = [1, 2, 3] b = list(itertools.permutations(a,
2)) for x in b: print(x) |
CHỦ ĐỀ
9: TĂNG TỐC CHƯƠNG TRÌNH PYTHON
- Bản
Python dành cho Window và phần mềm chấm Themis mới nhất 1.98 là bản Python 3.x
đang sử dụng chế độ thông dịch nên việc
thực hiện chương trình là rất chậm so với ngôn ngữ khác như Pascal
hay C++.
- Tuy nhiên ta có thể tăng tốc chương
trình bằng một số trick để chương
trình chạy nhanh
hơn, tránh quá giới
hạn thời gian.
- Các
ví dụ sau được thực hiện trên máy tính có cấu hình: CPU i3 10105f, DDRAM4 8GB,
SSD 256. Tính thời gian bằng thư viện time của
Python.
- Bài tập: Đọc từ tệp
input 106 số nguyên dương có giá trị không quá 109. Lọc
ra danh sách số chẵn và ghi vào
tệp output, các số cách nhau dấu cách.
1. Sử dụng chương trình con và biến cục bộ:
- Sử dụng chương trình con làm chương trình chạy nhanh hơn
- 
Sử dụng biến cục bộ cho
tốc độ xử lý nhanh hơn
|
Chương trình
chậm |
Chương trình nhanh hơn |
||
|
import sys, time
sys.stdin
= open("vidu.inp",
"r") sys.stdout = open("vidu.out",
"w") n = int(input()) a = [] for i in range(n): a.append(int(input())) for x in a: if x % 2 ==
0: print(x, end=' ') |
|
import sys, time
def xuly(): sys.stdin
= open("vidu.inp",
"r") sys.stdout = open("vidu.out",
"w") n = int(input()) a = [] for i in range(n): a.append(int(input())) for x in a: if x % 2 ==
0: print(x, end=' ') xuly() |
|
|
Time xử lý (xấp
xỉ): 1.19s |
Time xử lý: 1.07s |
||
2. Nhập mảng nhanh hơn:
- Khi đã biết kích thước mảng thì nên khai báo sẵn
thay vì dùng append
|
Chương trình nhanh hơn |
||
|
|
import sys, time
def xuly(): sys.stdin
= open("vidu.inp", "r") sys.stdout = open("vidu.out", "w") n =
int(input()) a = [0]*n for i in range(n): a[i] = int(input()) for x in a: if x % 2 == 0: print(x, end=' ') xuly() |
|
|
Time xử lý: 1.05s |
||
3. Đọc ghi dữ liệu nhanh hơn:
- Để đọc dữ liệu nhanh hơn: Ta nên sử dụng sys.stdin.readline thay vì sử
dụng hàm input() mặc định. Để sử dụng ta chỉ cần thêm vào lệnh
input = sys.stdin.readline sau khi mở tệp. Lưu ý: Khi thêm lệnh này cần hết sức cẩn thận vì sẽ
đọc nguyên dòng và đọc cả kí tự xuống dòng là
‘\n’ ở cuối. Nếu đọc số thì không
sao, đọc xâu thì cần
loại nó đi bằng cách input().replace('\n', '').
- Để ghi dữ liệu nhanh hơn: Hạn chế
ghi nhiều lần: bằng cách nối thành một xâu rồi
ghi một lần.
|
Chương trình nhanh hơn |
|
||
|
|
import sys, time
def xuly(): sys.stdin
= open("vidu.inp", "r") sys.stdout = open("vidu.out", "w") input = sys.stdin.readline n = int(input()) a = [0]*n for i in range(n): a[i] = int(input()) b = [] for x in a: if x % 2 == 0: b.append(x) s = ' '.join(str(x) for x in b) print(s)
xuly() |
|
Lệnh thêm vào để đọc nhanh hơn
Nối
thành xâu để hạn chế lệnh in nhiều
lần |
|
Time xử lý: 0.38s |
|
||
- Chỉ với 3 thao tác tối ưu như trên, từ một chương trình bị quá thời gian (1.19s) đã giảm xuống trong
thời gian cho phép (0.38s) và
giành trọn vẹn điểm của bài.
4.
Một số trick khác:
- Bạn có thể google
với từ khoá: Python performance
- Để đọc thêm một
số kỹ thuật tối ưu code
Python
5.
Bàn thêm:
- Bạn phải chấp nhận thực tế rằng dù tối ưu đi chăng nữa thì nó vȁn còn quá chậm so với các ngôn ngữ khác. Nên có
thể sẽ chấp nhận TLE ở một số bài tập
khi tham gia thi
HSG.
- Các bạn khác nếu muốn mục tiêu đạt giải Nhất hoặc
tham gia các kỳ thi cao hơn thì lời khuyên của tôi
là các bạn nên học thêm C++.
CHỦ ĐỀ 10: TẠO TEST VỚI
PYTHON
1. Thư viện random:
- Python có thư viện random mà bạn
có thể sử dụng để tạo ra
các số ngȁu nhiên.
- Một số thao tác:
·
random.randint(u, v) Trả về một số nguyên ngȁu nhiên trong đoạn [u, v]
·
random.random() Trả về một số thực
thuộc đoạn [0, 1]
·
random.uniform(2, 6) Trả về số
thực thuộc đoạn [2, 6]
·
random.choice(a) Lấy ngȁu nhiên một phần
tử thuộc list a
·
random.sample(a,
k=3) Tạo một list gồm 3 phần tử
ngȁu nhiên từ list a
·
random.shuffle(a) Xáo trộn ngȁu
nhiên list a
·
random.getrandbits(2) Tạo một số ngȁu nhiên
có 2 bit
·
…
2.
 |
Template tạo test:
3. Ví dụ minh hoạ:
- Bài tập: TONG.*
Viết
chương trình tính tổng hai số nguyên a và b được đọc từ tệp tong.inp. Kết quả lưu vào tệp tong.out.
Ràng buộc: 60% test có: 0 ≤ 𝑎, 𝑏 ≤ 105; 40% test có: 0 ≤ 𝑎, 𝑏 ≤ 1012
import sys,
random, os, shutil name = 'Tong'
def ghiinput(gioihan):
a = random.randint(0,
gioihan) b = random.randint(0,
gioihan) print(a, b)
def taoinput(itest):
sys.stdout
= open(name + '.inp', 'w') if itest
<= 12:
ghiinput(10**5) else:
ghiinput(10**12) sys.stdout.close()
def xuli(itest):
sys.stdin
= open(name + '.inp') sys.stdout = open(name
+ '.out', 'w') a, b = map(int,
input().split()) print(a + b)
sys.stdin.close() sys.stdout.close()
# Di chuyển 2 tệp vào đúng thư mục test
def movefile(itest):
num
= '0' * (3 - len(str(itest)))
+ str(itest) newpath
= name + '/Test' + num shutil.rmtree(newpath, ignore_errors=True) os.makedirs(newpath)
shutil.move(name
+ '.inp', newpath + "/"
+ name + '.inp') shutil.move(name + '.out', newpath
+ "/" + name + '.out')
# Phần chính: gọi tạo ra 20 test
for itest in range(1, 21): taoinput(itest) xuli(itest) movefile(itest)
0 Nhận xét