Phần trước: [C++ Cơ bản] Phần 13: Vòng lặp
Tương tự, ta cũng không thể tự tay tạo ra từng biến để lưu trữ thông tin của người dân Hà Nội được - ta sẽ phải tạo tới hơn 7 triệu biến, ai có tưng đấy thời gian cơ chứ? Bài viết này sẽ đề cập tới mảng - một cách để khai báo nhiều biến có cùng kiểu giá trị.
Mảng (array) là một cấu trúc dữ liệu có kích cỡ cố định, dùng để lưu trữ nhiều đối tượng có cùng kiểu dữ liệu. Thay vì phải tạo ra từng biến person1
, person2
, person3
, vân vân, ta chỉ cần tạo ra một mảng people
và truy cập vào từng phần tử people[0]
, people[1]
, people[2]
,…
Các biến trong array được lưu trữ tại các địa chỉ ô nhớ liên tiếp - phần tử đầu tiên ở vị trí đầu tiên, phần tử thứ hai ở vị trí thứ hai,… Thông tin này sẽ có ích khi ta học tới con trỏ bộ nhớ, còn giờ tạm thời hãy ghi nhớ lại điều đó đã.
Việc khai báo mảng cũng giống như việc khai báo biến, tuy nhiên ta cần phải cung cấp thêm kích cỡ các chiều (số lượng phần tử) của mảng vào trong ngoặc vuông đặt sau tên mảng.
Ví dụ:
Chiều của mảng là gì? Ta có thể hình dung mảng nhiều chiều là mảng chứa các mảng - mảng hai chiều là mảng với các phần tử là mảng 1 chiều, mảng 3 chiều là mảng với các phần tử là mảng 2 chiều, vân vân… Ví dụ thực tế của mảng nhiều chiều là một bảng dữ liệu, bao gồm các hàng và cột giống như mảng hai chiều.
Để có thể truy cập vào phần tử của mảng, ta gọi tên của mảng kèm theo với chỉ số nằm trong ngoặc nhọn đặt sau tên của mảng.
Ví dụ
Chỉ số của các phần tử trong mảng bắt đầu từ số 0 - một mảng có n
phần tử sẽ có các chỉ số 0, 1, 2,… tới n - 1
. Để thuận tiện hơn, ta sẽ hình dung chỉ số của phần tử là số phần tử nằm giữa phần tử đó, với phần tử đầu tiên.
Khi khai báo mảng, các phần tử của mảng chưa được khởi tạo giá trị.
Để khai báo mảng với giá trị khởi tạo cho các phần tử, ta gán mảng bằng các giá trị khởi tạo trong ngoặc nhọn, phân cách bởi dấu phẩy. Ví dụ
Ta cũng có thể khai báo mảng mà không có số lượng phần tử, nếu như ta đã khởi tạo giá trị cho các phần tử trong mảng. Khi đó số lượng phần tử của mảng sẽ bằng số lượng giá trị đã được khởi tạo.
Để khởi tạo giá trị cho mảng nhiều chiều, ta cũng đặt mảng giá trị khởi tạo của các phần tử trong ngoặc nhọn. Ví dụ về việc khởi tạo mảng 2 chiều:
Quy hoạch động (Dynamic Programming, gọi tắt là DP) là một phương pháp giải quyết các vấn đề trong toán học, tin học và kinh tế, bằng cách chia nhỏ vấn đề ra và tính toán các kết quả của trường hợp lớn hơn bằng kết quả của các trường hợp nhỏ hơn. Mảng là một công cụ đắc lực để giải các bài toán DP, và ta sẽ áp dụng nó ở trong ví dụ kế tiếp.
Các bạn cũng có thể tìm kiếm các bài toán quy hoạch động khác thông qua tag dp trên trang Cowboy Coder.
Cho một dãy số nguyên AA có nn phần tử (n<=1000n<=1000). Hãy tìm số lượng phần tử lớn nhất trên dãy AA, sao cho khi giữ nguyên thứ tự của các phần tử này như trên dãy số gốc, thì phần tử sau lớn hơn phần tử trước. Các phần tử không nhất thiết phải kề nhau.
Bài toán này còn được gọi là bài toán dãy con tăng dài nhất (Longest Increasing Subsequence - LIS)
Input
Đọc từ file INPUT.TXT
. Dòng đầu tiên của file là một số nn - số lượng phần tử của dãy số AA. Dòng tiếp theo có nn số nguyên là các phần tử của dãy số AA. n≤103n≤103, các số thuộc dãy AA thuộc kiểu int
.
Output
Viết ra file OUTPUT.TXT
một số nguyên duy nhất là số lượng phần tử lớn nhất tìm được.
Ví dụ
INPUT.TXT
5
1 3 2 4 5
OUTPUT.TXT
4
Ta định nghĩa hàm số f(i)f(i) là số lượng phần tử lớn nhất có thể lựa chọn được, nếu ta lấy phần tử thứ ii là phần tử cuối cùng được chọn. Kết quả của bài toán sẽ là giá trị lớn nhất của các f(x)f(x) từ 1 tới n.
Khi ta lấy phần tử thứ xx làm phần tử cuối cùng, có hai trường hợp xảy ra
Vậy với mỗi phần tử xx, ta đặt f(x)=1f(x)=1, và duyệt qua các phần tử ii từ 1 tới x−1x−1. Nếu a[i]<a[x]a[i]<a[x] và f(i)+1>f(x)f(i)+1>f(x), ta cập nhật giá trị của f(x)f(x) bằng giá trị mới.
Bài toán này còn có cách giải nhanh hơn, nhưng trong khuôn khổ của bài viết này, chúng ta sẽ chỉ tìm hiểu cách làm này.
Phần sau: [C++ Cơ bản] Phần 15: Các giá trị kiểu số. Thư viện toán học cmath.
Tác giả bài viết: Thanh Sơn
Nguồn tin: cowboycoder.tech
Ý kiến bạn đọc
Những tin mới hơn
Những tin cũ hơn