SKKN Rèn luyện kĩ năng, vân dụng và phát triển tư duy lập trình bằng cách phân tích và mở rộng các bài toán đơn giản

dãy con đơn điệu tăng của dãy A.
Yêu cầu: Hãy tìm độ dài và chỉ số dãy con liên tiếp đơn điệu tăng dài nhất.
C++
Python
#include using namespace std;
long	int	a[10001],	cs[10001], f[10001];
int dmax, i, n, j; long int k;
n=int(input("<<Nhap n=")) lap=range(0,n,1)
a=[]
for x in lap:
print("phan tu thu ",x,"=")

int main()
{
cout<<"Nhap	so	phan	tu mang:";
cin>>n;
for (i=0;i<=n-1;i++)
{
cout>a[i];
}
f[1] = 1;
dmax = 0;
k = 1;
for (i = 0; i <= n - 1;
i++) {
if (a[i+1] > a[i])
{
f[i + 1] = f[i]
+ 1;
}
else
{
f[i + 1] = 1;
}
if (f[i+1] > dmax)
{
dmax = f[i +
1];
k = 1;
cs[k] = i + 1;
}
else if (f[i+1] ==
gt=int(input()) a.append(gt)
dmax,k=0,1 f=[0,1]
cs=[]
for i in range(0,n-1): if a[i+1]>a[i]:
f.append (f[i]+1) else:
f.append (1)
if f[i+1] > dmax: dmax=f[i+1] k=1
cs.clear() cs.append(i+1)
else:
if f[i+1]==dmax: k=k+1 cs.append (i+1)
if dmax==1: print(0) else:
print(dmax,k) for j in range(k):
for	i	in	range(cs[j]- dmax+1,cs[j]+1):
print(a[i],end=" ")

dmax)
{
k++;
cs[k] = i + 1;
}
}
if (dmax == 1)
{
cout<<"0";
}
else
{
//cout<< dmax <<
" " << k << endl;
cout<<"co "<<k<<" day cong tang" <<" gom "<<dmax<<" phan tu la:";
for (j = 1; j <= k;
j++)
{
for (i = cs[j] - dmax + 1; i <= cs[j]; i++){
cout<< a[i] << " "
}
cout<<"\n";
}
}
return 0;
}

Bài toán 2: TỔNG LỚN NHẤT
Cho một dãy A gồm N (1≤N≤10000) số nguyên {a1, a2,, aN}(-106≤ai≤106). Dãy con ai, ai+1,, aj (1≤i≤j≤N) là dãy được tạo từ các phần tử liên tiếp của dãy A
bắt đầu từ phần tử i và kết thúc ở phần tử j.
Yêu cầu: Hãy tìm dãy con liên tiếp có tổng lớn nhất.
C++
Python
#include using namespace std; int n,i,j,dem;
long tmax,k;
int a[100001],s[100001],dau[10000],cuoi[1 00001];
int main()
{
cout>n;
for (i=0;i<=n-1;i++)
{
cout>a[i];
} s[0]=0;
for (i=0;i<=n-1;i++)
{
s[i]=s[i-1]+a[i];
}
tmax=a[1]; k=0;
for (i=0;i<=n-1;i++)
{
for (j=i;j<=n;j++)
{
if ((s[j]-s[i-1])>tmax)
{
tmax=s[j]-s[i-1]; k=0;
n=int(input("<<Nhap n=")) lap=range(0,n,1)
a=[]
for x in lap:
print("phan tu thu ",x,"=") gt=int(input()) a.append(gt)
a=[0]+a; s=[0]
for i in range(1,n+1): s.append(s[i-1]+a[i])
tmax=s[1] k=0 dau=[] cuoi=[]
for i in range(1,n):
for j in range(i,n+1): if s[j]-s[i-1]>tmax:
tmax=s[j]-s[i-1] k=0
dau.clear() cuoi.clear()
if s[j]-s[i-1]==tmax: k=k+1 dau.append(i) cuoi.append(j)
print(tmax,k)
for i in range(1,k+1):
for	j	in	range(dau[i-1],cuoi[i-

}
if ((s[j]-s[i-1])==tmax)
{
k++;
dau[k]=i; cuoi[k]=j;
}
}
}
cout<<tmax<<" "<<k<<"\n"; for (i=0;i<=k;i++)
{
for (j=dau[i];j<=cuoi[i];j++)
{
cout<<a[j]<<" ";
}
cout<<"\n";
}
return 0;
}
1]+1):
print(a[j],end=" ")
Đánh giá các thuật toán
Fibonaci
So sánh thời gian thực hiện của 2 chương trình qua phần mềm Themis
Test
5
20
40
C1_Đệ quy
0.1894
0.17814
Quá thời gian
C2_QHD
0.18988
0.18026
0.18375

Đối với thuật toán dùng kĩ thuật đệ quy, khi thực hiện với test lớn đã chạy quá thời gian 1s, trong thi HSG cấp tỉnh thì test này học sinh sẽ bị mất điểm. Từ đó học sinh sẽ tự rút ra được phương pháp mình cần dùng cho bài toán này là quy hoạch động.
Thuật toán sắp xếp
Đánh giá 2 thuật toán sắp xếp là Bubble và Quick với 7 bộ test khác nhau, độ lớn các bộ test tăng dần. Kết quả thu được:
Thuật toán Bubble chạy quá thời gian (1s) 2 bộ test lớn. Còn thuật toán Quick vẫn đảm bảo thời gian (dưới 1s). Thời gian thực hiện từng test như sau
Test
50
1000
5000
9000
10000
50000
100000
Bubble
0.20519
0.19666
0.24707
0.30003
0.31095
x
x
Quick
0.18788
0.18013
0.19639
0.22099
0.2114
0.27961
0.32419

nhau.
Thuật toán tìm kiếm
Đánh giá 2 thuật toán tìm kiếm là Sequential và Binary với 5 bộ test khác
Thời gian thực hiện thuật toán qua từng test như sau:
Test
50
1000
5000
50000
100000
Sequential
0.18848
0.18278
0.1827
0.21825
0.23364
Binary
0.18303
0.17893
0.19089
0.21968
0.23378

Nhìn bảng thời gian thực hiện có thể thấy thời gian thực hiện của tìm kiếm nhị phân (Binary Search) nhanh hơn so với thuật toán tìm kiếm tuần tự nếu dữ liệu vào là dãy đã sắp xếp.
Bài tập về nhà
GIÁ TRỊ LỚN THỨ 2 TRONG DÃY
Cho dãy a gồm N (N<=103) số nguyên a1, a2, ..., aN, mỗi số không vượt qua
104. Viết chương trình đưa ra màn hình số lớn thứ 2 trong dãy a. Ý tưởng:
Gọi số lớn nhất là Max1, số lớn thứ 2 là Max2. So sánh phần tử a[0] với a[1]. Nếu phần tử nào lớn hơn thì gán cho Max1, còn lại gán cho Max2.
Bắt đầu từ phần tử thứ 3, với a[i]:
Nếu Max2<Max1<a[i] thì thay Max1=a[i]; Max2=Max1 Nếu Max2<a[i]<Max1 thì thay Max2=a[i]
Nếu a[i]<Max2<Max2 thì bỏ qua.
Cài đặt chương trình:
C++
Python
#include #include int a[100001];
using namespace std; int main()
{
int n,k,i,j;
int max1, max2, tg, vt1, vt2; cout >n;
for (int i=0;i<n;i++)
{
cout>a[i];
}
if (n<1) cout<<"KHONG";
n=int(input("<<Nhap n=")) lap=range(0,n,1)
a=[]
for x in lap:
print("phan tu thu",x,"=") gt=int(input()) a.append(gt)
if n<1:
print("KHONG") else:
if a[0]>a[1]: max1=a[0] max2=a[1] vt1=0 vt2=1
else:

else
{
if (a[0]>a[1])
{
max1=a[0]; max2=a[1]; vt1=0; vt2=1;
}
else
{
max1=a[0]; max2=-1000000;
vt1=0; vt2=-1;
}
for (i=2;imax1)
{
max2=max1; max1=a[i]; vt2=vt1; vt1=i;
}
else
if ((a[i]max2))
{
max2=a[i]; vt2=i;
}
if (vt2!=-1) cout<<"phan tu lon
max1=a[0] max2=-100000
vt1=0 vt2=-1
for i in lap:
if a[i]>max1: max2=max1 max1=a[i] vt2=vt1 vt1=i
else:
if (a[i]max2):
max2=a[i] vt2=i
if (vt2!=0):
print("so lon thu 2 la: ",max2, "o vi tri ", vt2)
else:
print("KHONG")

thu 2 la:"<<max2<<" o vi tri: "<<vt2;
else cout<<"KHONG";
}
return 0;
}

Chủ đề về xâu
Bài toán cơ bản
Bài toán 1: XÂU ĐẢO NGƯỢC
Nhập vào từ bàn phím xâu kí tự S. Viết chương trình đưa ra màn hình xâu đó nhưng viết theo thứ tự ngược lại (Ví dụ 3 SGK Tin học 11- trang 71)
Nhận xét: Đây là bài toán cơ bản, học sinh có thể thực hiện được ngay sau phần kiến thức về bài kiểu xâu.
Ý tưởng của thuật toán đã được giới thiệu trong SGK tin học 11. Chương trình như sau:
C++
Python
#include using namespace std; string s;
int main()
{
cout >s;
string s1=""; int l=s.length();
for (int i=0;i<=l-1;i++) s1=s[i]+s1;
cout<<"xau nguoc la:"<<s1; return 0;
}
s=input(">>nhap xau=") s1=''
for i in s: s1=i+s1
print(s1)
Bài toán 2: XÓA CÁCH TRỐNG
Nhập vào từ bàn phím xâu kí tự S. Viết chương trình đưa ra màn hình xâu
thu được sau khi loại bỏ các dấu cách nếu có. (Ví dụ 4 SGK Tin học 11 – Trang 72).
Nhận xét: Đây là bài toán cơ bản, học sinh có thể thực hiện được ngay sau phần kiến thức về bài kiểu xâu.
Ý tưởng của thuật toán đã được giới thiệu trong SGK tin học 11. Chương trình như sau:
C++
Python
#include using namespace std; string s,s1;
int main()
{
cout << "Nhap xau="; getline(cin,s);
s1="";
int l=s.length();
for (int i=0;i<=l-1;i++) if (s[i]!=' ')
{
s1=s1+s[i];
}
cout<<"xau ket qua:"<<s1; return 0;
}
s=input("<<nhap xau: ") s1=''
for i in s: if i!=' ':
s1=s1+i
print("xau thu duoc la: ",s1)
3.2.1.3. Bài toán 3: REPLACE
Viết chương trình nhập vào từ bàn phím xâu ký tự S, tìm và thay thế tất cả cụm ký tự s1 thành s2 (Bài 3-SGK tin học 11 trang 73)
Nhận xét: Đây là bài toán cơ bản, học sinh có thể thực hiện được ngay sau phần kiến thức về bài kiểu xâu.
Ý tưởng của thuật toán là dùng hàm replace để thay thế. Chương trình cụ thể như sau:
C++
Python
#include #include using namespace std; string s,s1,s2;
int main()
{
getline(cin,s); getline(cin,s1); getline(cin,s2); int l=s.length();
int l1=s1.length();
for (int i=0;i<=l-l1;i++) if (s.substr(i,l1)==s1) s.replace(i,l1,s2);
cout<<"xau thu duoc la: "<<s; return 0;
}
s=input("nhap xau goc!") s1=input("nhap cum tu can thay!") s2=input("nhap cum tu thay the!") kq=s.replace(s1,s2)
print(kq)
Bài toán nâng cao cấp độ 1
Bài toán 1: XÂU ĐỐI XỨNG
Viết chương trình kiểm tra xâu S có phải là xâu đối xứng không?
Xâu đối xứng là xâu đọc từ trái qua phải cũng giống như đọc từ phải qua trái Ví dụ: S=”22022022” là xâu đối xứng
S=”12345678” không phải là xâu đối xứng Cách 1: Sử dụng cách làm được giới thiệu trong SGK
B1: Tạo xâu mới là xâu đảo ngược của xâu đã cho (Thuật toán tạo xâu đảo ngược đã được thực hiện ở bài toán 1 phần cơ bản).
B2: So sánh xâu đã cho với xâu đảo ngược vừa tìm được B2.1: Nếu 2 xâu bằng nhau thì kết luận xâu đối xứng B2.2: Ngược lại thì xâu không đối xứng
Cài đặt chương trình:
C++
Python
#include using namespace std; string s;
int main()
{
cout >s;
string s1=""; int l=s.length();
for (int i=0;i<=l-1;i++) s1=s[i]+s1;
if (s==s1)
{
cout<<"True";
}
else{ cout<<"Flase";} return 0;
}
s=input(">>nhap xau=") s1=''
for i in s: s1=i+s1
if s==s1: print("True")
else:
print("False")
Cách 2: Từ tính chất của xâu đối xứng là các cặp kí tự đối xứng nhau thì bằng nhau, vậy chỉ cần tìm trong các cặp đối xứng nhau 1 cặp không bằng nhau thì kết luận luôn là xâu không đối xứng.
Với cách này thời gian thực hiện thuật toán sẽ nhanh hơn rất nhiều so với cách 1 vì không cần phải duyệt hết tất cả các phần từ trong xâu. Trường hợp xấu nhất chỉ duyệt đến ½ độ dài của xâu.
Chương trình cụ thể như sau:
C++
Python
using namespace std; string s;
bool check(string s)
{
def palin(s:str)->bool: l=len(s)
for i in range(0,int(l/2)):
if s[i]!=s[l-i-1]:

int n=s.length();
for(int i=0;i<=n/2;i++)
{
if(s[i]!=s[n-1-i]) return false;
}
return true;
}
int main()
{
cout >s;
if (check(s))
{
cout<<"True";
}
else {cout<<"False";} return 0;
}
return False return True
s=input(">>nh