Bài toán dãy số toàn số 0 và số 1
Cho trước một dãy số bao gồm toàn các số 0 và 1. Dãy này có độ dài nhỏ hơn 255.
a) Viết chương trình nhập dãy số trên từ bàn phím. Các số được nhập liên tiếp từ bàn phím, quá trình nhập dữ liệu kết thúc nhấn phím <Enter>. Nếu việc nhập dữ liệu sai trên màn hình kết quả “Bạn đã nhập sai, đề nghị nhập lại” và cho phép nhập lại ngay dữ liệu.
b) Một dãy con đúng của dãy trên được gọi là một dãy con liên tục bất kỳ của dãy trên bao gồm các số hạng giống nhau. Hãy tính độ dài lớn nhất của một dãy con đúng của dãy trên.
c) Một dãy con đúng bậc 1 của dãy trên được coi là một dãy con liên tục bất kỳ của dãy trên bao gồm toàn các số hạng giống nhau ngoại trừ 1 phần tử. Hãy tính độ dài lớn nhất của một dãy con đúng bậc 1 của dãy trên.
Lời giải bài toán dãy số toàn số 0 và số 1
Để giải quyết bài toán này, ta có thể thực hiện theo các bước sau:
a. Viết chương trình nhập dãy số trên từ bàn phím. Các số được nhập liên tiếp từ bàn phím, quá trình nhập dữ liệu kết thúc nhấn phím <Enter>. Nếu việc nhập dữ liệu sai trên màn hình kết quả “Bạn đã nhập sai, đề nghị nhập lại” và cho phép nhập lại ngay dữ liệu.
Để nhập dãy số từ bàn phím, ta có thể sử dụng hàm input() để lấy dữ liệu nhập vào từ bàn phím. Sau đó, ta kiểm tra tính đúng đắn của dữ liệu nhập vào bằng cách kiểm tra xem dãy số chỉ gồm các ký tự ‘0’ và ‘1’ hay không. Nếu dữ liệu nhập vào không đúng đắn, ta yêu cầu người dùng nhập lại. Nếu đúng, ta trả về dãy số.
b. Một dãy con đúng của dãy trên được gọi là một dãy con liên tục bất kỳ của dãy trên bao gồm các số hạng giống nhau. Hãy tính độ dài lớn nhất của một dãy con đúng của dãy trên.
Để tính độ dài lớn nhất của một dãy con đúng của dãy trên, ta có thể duyệt từ đầu đến cuối dãy số, và lưu lại độ dài của dãy con hiện tại đang xét. Nếu gặp phần tử khác phần tử trước đó của dãy con, ta cập nhật độ dài của dãy con và tiếp tục duyệt từ vị trí hiện tại. Trong quá trình duyệt, ta cập nhật độ dài lớn nhất của dãy con tìm được.
c. Một dãy con đúng bậc 1 của dãy trên được coi là một dãy con liên tục bất kỳ của dãy trên bao gồm toàn các số hạng giống nhau ngoại trừ 1 phần tử. Hãy tính độ dài lớn nhất của một dãy con đúng bậc 1 của dãy trên.
Để tính độ dài lớn nhất của một dãy con đúng bậc 1 của dãy trên, ta có thể duyệt từ đầu đến cuối dãy số, và lưu lại độ dài của dãy con hiện tại đang xét. Nếu gặp phần tử khác phần tử trước đó của dãy con, ta kiểm tra xem phần tử trước đó và phần tử hiện tại có khác phần tử thứ hai của dãy con không. Nếu khác, ta cập nhật độ dài của dãy con và tiếp tục duyệt từ vị trí hiện tại. Trong quá trình duyệt, ta cập nhật độ dài lớn nhất của dãy con tìm được.
Cài đặt bài toán dãy số toàn số 0 và số 1 với Python
def nhap_day_so():
while True:
day_so = input("Nhập dãy số (chỉ gồm các số 0 và 1, độ dài nhỏ hơn 255): ")
if len(day_so) < 1 or len(day_so) >= 255 or not all(s in ['0', '1'] for s in day_so):
print("Bạn đã nhập sai, đề nghị nhập lại")
else:
return [int(s) for s in day_so]
def do_dai_day_con_dung(day_so):
do_dai_max = 0
do_dai_hien_tai = 1
for i in range(1, len(day_so)):
if day_so[i] == day_so[i-1]:
do_dai_hien_tai += 1
else:
do_dai_max = max(do_dai_max, do_dai_hien_tai)
do_dai_hien_tai = 1
do_dai_max = max(do_dai_max, do_dai_hien_tai)
return do_dai_max
def do_dai_day_con_dung_bac_1(day_so):
do_dai_max = 0
do_dai_hien_tai = 1
for i in range(1, len(day_so)):
if day_so[i] == day_so[i-1]:
do_dai_hien_tai += 1
else:
if i > 1 and day_so[i] == day_so[i-2]:
do_dai_hien_tai += 1
do_dai_max = max(do_dai_max, do_dai_hien_tai)
do_dai_hien_tai = 1
if len(day_so) > 1 and day_so[-1] == day_so[-2]:
do_dai_max = max(do_dai_max, do_dai_hien_tai)
return do_dai_max
day_so = nhap_day_so()
do_dai_max = do_dai_day_con_dung(day_so)
print("Độ dài lớn nhất của một dãy con đúng của dãy trên là:", do_dai_max)
do_dai_max_bac_1 = do_dai_day_con_dung_bac_1(day_so)
print("Độ dài lớn nhất của một dãy con đúng bậc 1 của dãy trên là:", do_dai_max_bac_1)
Cài đặt bài toán dãy số toàn số 0 và số 1 với C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> nhap_day_so() {
while (true) {
string day_so;
cout << "Nhap day so (chi gom cac so 0 va 1, do dai nho hon 255): ";
getline(cin, day_so);
if (day_so.size() < 1 || day_so.size() >= 255) {
cout << "Ban da nhap sai, de nghi nhap lai" << endl;
continue;
}
bool hop_le = true;
for (char c : day_so) {
if (c != '0' && c != '1') {
hop_le = false;
break;
}
}
if (!hop_le) {
cout << "Ban da nhap sai, de nghi nhap lai" << endl;
continue;
}
vector<int> result;
for (char c : day_so) {
result.push_back(c - '0');
}
return result;
}
}
int do_dai_day_con_dung(vector<int> day_so) {
int do_dai_max = 0;
int do_dai_hien_tai = 1;
for (int i = 1; i < day_so.size(); i++) {
if (day_so[i] == day_so[i-1]) {
do_dai_hien_tai += 1;
} else {
do_dai_max = max(do_dai_max, do_dai_hien_tai);
do_dai_hien_tai = 1;
}
}
do_dai_max = max(do_dai_max, do_dai_hien_tai);
return do_dai_max;
}
int do_dai_day_con_dung_bac_1(vector<int> day_so) {
int do_dai_max = 0;
int do_dai_hien_tai = 1;
for (int i = 1; i < day_so.size(); i++) {
if (day_so[i] == day_so[i-1]) {
do_dai_hien_tai += 1;
} else {
if (i > 1 && day_so[i] == day_so[i-2]) {
do_dai_hien_tai += 1;
}
do_dai_max = max(do_dai_max, do_dai_hien_tai);
do_dai_hien_tai = 1;
}
}
if (day_so.size() > 1 && day_so.back() == day_so[day_so.size()-2]) {
do_dai_max = max(do_dai_max, do_dai_hien_tai);
}
return do_dai_max;
}
int main() {
vector<int> day_so = nhap_day_so();
int do_dai_max = do_dai_day_con_dung(day_so);
cout << "Do dai lon nhat cua mot day con dung cua day tren la: " << do_dai_max << endl;
int do_dai_max_bac_1 = do_dai_day_con_dung_bac_1(day_so);
cout << "Do dai lon nhat cua mot day con dung bac 1 cua day tren la: " << do_dai_max_bac_1 << endl;
return 0;
}