Bài 1 – Dãy Fibonacci với nhiều cách cài đặt
Cho số nguyên dương N, hãy in ra N số đầu tiên của dãy Fibonacci.
-
F(0) = 1
-
F(1) = 1
-
F(n) = F(n – 1) + F(n – 2) (n ≥ 2)
Thực hiện bằng 4 cách khác nhau:
-
Dùng 3 biến (không dùng mảng)
-
Dùng mảng để lưu toàn bộ dãy
-
Dùng đệ quy thuần
-
Dùng đệ quy có nhớ (memoization) để tối ưu tốc độ
Bài 2 – Tính toán với số nguyên
Ví dụ đầu bài
Cho N = 6
-
Tổng từ 1 → 6: 1+2+3+4+5+6 = 21
-
Giai thừa 6! = 720
Cho số nguyên dương N, hãy thực hiện các yêu cầu sau theo nhiều cách:
2.1. Tính tổng N số nguyên liên tiếp từ 1 đến N
Viết lời giải theo các cách:
-
Dùng vòng lặp for
-
Không dùng vòng lặp, sử dụng công thức toán học:
→S = N * (N + 1) / 2
2.2. Tính giai thừa của số N (N!)
Thực hiện theo các cách:
-
Dùng vòng lặp for
-
Dùng đệ quy
-
Dùng kiểu công thức để xử lý số lớn
Bài 3 – Đếm số lần xuất hiện trong mảng
🔷 Ví dụ đầu bài
Input:
[1, 2, 2, 3, 3, 3]
| Số | - Số lần xuất hiện |
|---|---|
| 1 | - 1 |
| 2 | - 2 |
| 3 | - 3 |
Cho một mảng số nguyên bất kỳ.
Hãy đếm số lần xuất hiện của từng giá trị trong mảng và in ra kết quả.
(Yêu cầu sử dụng: HashMap hoặc TreeMap)
Bài 4 – Gộp 2 mảng đã sắp xếp thành 1 mảng cũng đã sắp xếp
🔷 Ví dụ đầu bài
Input:
-
A =
[1, 3, 5] -
B =
[2, 4, 6]
Output:
[1, 2, 3, 4, 5, 6]
Cho 2 mảng đã được sắp xếp tăng dần.
Hãy ghép chúng lại thành 1 mảng mới cũng theo thứ tự tăng dần.
(Yêu cầu: thực hiện bằng thuật toán 2 con trỏ)
Bài 5 – Tách số chẵn và số lẻ trong mảng
🔷 Ví dụ đầu bài
Input: [1, 4, 7, 2, 8, 5]
Output (chẵn trước, lẻ sau):
[4, 2, 8, 1, 7, 5]
Cho một mảng số nguyên.
Hãy đưa số chẵn lên đầu, số lẻ xuống cuối theo 3 cách khác nhau:
Cách 1: Dùng vòng lặp for và so sánh bình thường
-
Duyệt mảng và in ra chẵn trước, lẻ sau.
Cách 2: Dùng mảng mới
-
Tạo mảng mới để lưu chẵn, sau đó thêm lẻ.
Cách 3: Không dùng thêm mảng (in-place)
-
Thuật toán phân vùng (partition) tương tự QuickSort
-
Hoán đổi phần tử trong chính mảng ban đầu
