Sáng kiến kinh nghiệm Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi

++)
{
if ((a[i+1]-a[i])==d)
{
s[i+1]=s[i]+1;
}
else s[i+1]=1;
if (s[i+1]>dmax)
import sys
fi	=	open	("dayconcsc.inp", encoding = "utf-8")
fo = open("dayconcsc.out","w", encoding = "utf-8")
sys.stdin=fi sys.stdout=fo
#đọc dữ liệu từ tệp inp a=str.split(input()) n=int(a[0])
d=int(a[1]) a=str.split(input()) for i in range(n):
a[i]=int(a[i])
# Tìm đoạn con csc dài nhất có công sai d
dmax,k=0,0 s =[]
cs=[] s.append (1)
for i in range(n-1):
if a[i+1]-a[i]==d:
s.append (s[i]+1)

{
dmax=s[i+1]; k=1;
cs[k]=i+1;
}
else
{
if (s[i+1]==dmax)
{
k++;
cs[k]=i+1;
}
}
}
if (dmax==1)
{
fo<<"0";
}
else
{
fo<<dmax<<" "<<k<<"\n"; for (int j=1;j<=k;j++)
{
for(int i=(cs[j]-dmax+1);i<=cs[j]; i++)
{
fo<<a[i]<<" ";
}
fo<<"\n";
}
}
fi.close();fo.close(); return 0;}
else:
s.append (1)
if s[i+1] > dmax: dmax=s[i+1] k=1
cs.clear() cs.append(i+1)
else:
if s[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=" ") print()
fi.close() fo.close()

Bài toán 2 - Dãy con không giảm
Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai≤ai+1≤≤ aj (1≤i≤j≤N) được gọi là dãy con không giảm của dãy A. Lưu ý các phần tử của dãy con có thể chọn liên tiếp hoặc không liên tiếp từ các phần tử dãy A nhưng phải theo đúng thứ tự. Độ dài của dãy con là số lượng phần tử của dãy con đó.
Yêu cầu: Tìm độ dài lớn nhất của dãy con không giảm.
Dữ liệu vào: File văn bản dayconkogiam.inp gồm 2 dòng:
Dòng đầu chứa một số nguyên dương N (1≤ N ≤ 104).
Dòng thứ hai chứa N số nguyên dương ai ((-105≤ai ≤ 105), giữa hai số cách nhau bởi một dấu cách.
Dữ liệu ra: File văn bản dayconkogiam.out gồm một số nguyên dương là kết quả bài toán.
Ví dụ:
Dayconkogiam.inp
Dayconkogiam.out
8
5 1 6 4 5 2 1 7
4
Ý tưởng thuật toán
Cũng như ở bài toán 1, ở bài này ta dùng mảng một chiều L để lưu độ dài của các đoạn con không giảm dài nhất kể từ đầu dãy đến vị trí đang xét. Nghĩa là: L[i] là độ dài của dãy con không giảm dài nhất có thể tìm thấy được mà phần tử thứ a[i] là phần tử cuối cùng trong dãy con không giảm đó. Chẳng hạn, với ví dụ trên ta có:
Dãy a:
5
1
6
4
5
2
1
7
Mảng L:
1
1
2
2
3
2
1
4
Vậy L[8]=4 là lớn nhất trong mảng L nên dãy con không giảm dài nhất tìm được sẽ có độ dài bằng 4, đó là dãy con có phần tử a[8] =7 là phần tử cuối cùng trong dãy con. Vậy dãy con không giảm dài nhất là (1, 4, 5, 7) tương ứng với các phần tử trong mảng L là đoạn con (1, 2, 3, 4) được duy trì sắp xếp.
Cài đặt chương trình
C++
Python
#include 
#include #include 
import sys # Đọc tệp
fi=open("dayconkhonggiam.inp",enco

using namespace std; int n;
int a[10001]; int L[10001];
int main()
{
ifstream fi("dayconkogiam.inp"); ofstream fo("dayconkogiam.out"); fi>>n;
for (int i=0;i>a[i];
L[0]=1;
int lmax;
for (int i=1;i<n;i++)
{
lmax=0;
for (int j=0;j<i;j++)
{
if (a[i]>=a[j]) if (lmax<L[j])
lmax=L[j];
}
L[i]=lmax+1;
}
int lengmax=0;
for (int i=0;ilengmax)
lengmax=L[i];
fo<<lengmax<<endl; fi.close();fi.close();
return 0;}
ding="utf-8") sys.stdin=fi n=int(input()) a=str.split((input())) for i in range(n):
a[i]=int(a[i]) fi.close()
# xử lí l=[0]
for i in range(1,n): lmax=0
for j in range(i): if a[i]>=a[j]:
if lmax<l[j]: lmax=l[j] l.append(lmax+1)
lengmax=0
for i in range(n):
if l[i]>lengmax: lengmax=l[i] # Ghi kết quả
fo=open("dayconkhonggiam.out","w", encoding="utf-8")
sys.stdout=fo print(lengmax) fo.close()

Đánh giá:
Kỹ thuật duy trì mảng sắp xếp là một kỹ thuật khá hay, chỉ cần duy trì được mảng sắp xếp kết hợp vời dò tìm tuyến tính hoặc tìm kiếm nhị phân chúng ta đã có ngay một thuật toán hiệu quả trong thời gian cho phép. Tuy vậy, trong trường hợp tập hợp nhớ luôn biến động luôn phá vỡ tính được sắp thì kỹ thuật này không hiệu quả. Trong những trường hợp như vậy, người ta thường sử dụng các kỹ thuật lưu trữ dữ liệu cao cấp hơn như cây tìm kiếm nhị phân, mảng băm...
Đánh giá các kĩ thuật
Đánh giá các kĩ thuật
Để đánh giá các kĩ thuật, chúng tôi thực hiện 1 bài toán với 2 kĩ thuật khác nhau. Sau đó đánh giá bằng phần mềm Themis để đưa ra kết luận cuối cùng.
Bài toán 1. Tìm số Fibonaci thứ N.
Với bài toán này chúng ta có thể áp dụng kĩ thuật đệ quy như đã trình bày ở mục 2.3.4.2 . Tuy nhiên bài này cũng có thể áp dụng kĩ thuật nhớ như đã trình bày ở mục 2.3.3.1 bằng cách tính và lưu dãy fibonaci vừa tính được vào mảng F. Cuối cùng chỉ cần đưa ra phần tử F[N] là xong. Vậy với bài này nên dùng kĩ thuật nào thì sẽ tối ưu hơn?
Đây là chương trình C++ giải bài tìm số Fibonaci thứ N với hai kĩ thuật đệ quy và kĩ thuật nhớ:
Chương trình sử dụng đệ quy
Chương trình sử dụng kĩ thuật nhớ
#include #include 
using namespace std; long long n;
void doctep()
{ ifstream fi("fibo.inp"); fi>>n; fi.close();	}
long long fibonaci(long long x)
{if (x == 0) return 1;
if (x == 1) return 1;
return fibonaci(x - 1) + fibonaci(x- 2);
}
#include #include
using namespace std;
const long long maxn=50000; long long n,i,a[maxn];
void doctep()
{ ifstream fi ("fibo.inp"); fi>>n; fi.close();}
void xuli()
{ a[0]=1;a[1]=1;
for	(i=2;i<=n;i++)	a[i]=a[i-1]+a[i- 2];}
void ghitep()

int main()
{	doctep();
ofstream fo("fibo.out"); fo<<fibonaci(n); fo.close(); return 0;
}
{ofstream fo ("fibo.out"); fo<<a[n]; fo.close();} int main()
{
doctep();xuli(); ghitep();return 0;
}
Lập bảng so sánh thời gian thực hiện 2 chương trình trên với bộ test lớn bằng phần mềm Themis ta có kết quả sau:

Kĩ thuật đệ quy
Kĩ thuật nhớ
N=40
≈ 0.5099445
≈ 0.0268591
N=45
≈ 5.3174084
≈ 0.0272185
N=100
> 1 phút
≈ 0.0287061
Qua bảng so sánh trên, ta thấy đối với bài toán 1 nếu dùng kĩ thuật đệ quy với dữ liệu test lớn sẽ không đáp ứng yêu cầu khi đi thi HSG Tỉnh là không quá 1 (s). Với dữ liệu test lớn thì kĩ thuật đệ quy phải thực hiện một số lượng phép tính là rất lớn. Dó đó trong trường hợp không cần thiết sử dụng đệ quy thì nên sử dụng kĩ thuật nhớ, sẽ tối ưu hơn rất nhiều.
Bài toán 2.
Tìm giá trị lớn nhất của một dãy gồm N số nguyên cho trước. Cho biết trong dãy có bao nhiêu phần tử có giá trị lớn nhất.
Với bài này, chúng ta có thể dùng kĩ thuật lính canh như ở mục 2.3.1.1. Tuy nhiên cũng có thể dùng kĩ thuật chia để trị để giải quyết bài toán. Đó là tiến hành sắp xếp dãy tăng dần (hoặc giảm dần), khi đó phần tử có giá trị lớn nhất sẽ nằm cuối dãy (hoặc đầu dãy). Chương trình được cài đặt trong C++ như sau:
Chương trình sử dụng lính canh
Chương trình sử dụng chia để trị
#include #include using namespace std;
long long i, n, dem, a[50000]; int main()
{
ifstream fi ("max.inp.out");
#include #include using namespace std;
long long dem,n,i,a[1000000+1]; void swap(int &x,int &y)
{int tg=x;x=y;y=tg;}
void QuickSort(int left, int right)

fi>>n;
for (i=0;i>a[i];
long long max=a[0];//dat linh canh for(i=1;i<n;i++)
if (max<a[i]) max=a[i]; dem=0; for(i=0;i<n;i++)
if (a[i]==max) dem++; ofstream fo ("max.out"); fo<<max<<" "<<dem; fo.close();fi.close(); return 0;
}
{
int i=left; int j=right;
int pivot=a[(left+right)/2]; while (i<=j)
{while (a[i]pivot) j--; if (i<=j)
{swap(a[i],a[j]);i++;j--;}} if (left<j) QuickSort(left,j);
if (i<right) QuickSort(i,right);
}
int main()
{
freopen("max.inp","r",stdin);
freopen("max.out","w",stdout); ios::sync_with_stdio(0); cin>>n;
for (i=1;i>a[i]; QuickSort(1,n); dem=0; i=n; while (a[i]==a[n]) {dem++;i--;} cout<<a[n]<<" "<<dem;
return 0;
}
Lập bảng so sánh thời gian thực hiện 2 chương trình trên với bộ test lớn bằng phần mềm Themis ta có kết quả sau:

Kĩ thuật lính canh
Kĩ thuật chia để trị
N=500000
≈ 0.0798972
≈ 0.120688
N=1000000
≈ 0.1323613
≈ 0.2085602
Với bài toán 2, ta thấy sử dụng kĩ thuật lính canh lại thích hợp, tối ưu hơn so với kĩ thuật chia để trị. Việc sắp xếp các phần tử với số lượng lớn sẽ làm cho kĩ thuật chia để trị chạy càng chậm hơn.
Bài toán 3.
Cho dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, , aN và một số nguyên K. Hãy cho biết có hay không chỉ số i mà ai =K. Nếu có thì hãy tìm chỉ số i mà ai =K. Ngược lại nếu không có thì ghi -1.
Đối với bài toán này, có thể sử dụng kĩ thuật lính canh như đã trình bày ở mục 2.3.1.2. Tuy nhiên cũng có thể dùng kĩ thuật chia để trị để giải quyết tối ưu hơn. Chương trình cài đặt trong NNLT C++ như sau:
Chương trình sử dụng lính canh
Chương trình sử dụng chia để trị
#include #include
using namespace std;
const long long maxn=10000000; long long k,i,n,cs;
long long a[maxn]; void doctep()
{
ifstream fi ("TK.inp"); fi>>n>>k;
for (i=0;i>a[i]; fi.close();
}
int main()
{
doctep();
ofstream fo ("TK.out"); a[n]=k;
for (i=0;i<n;i++)
{
if (a[i]==k)
{
cs=i; break;
}
}
if (i==n) fo #include #include using namespace std; int arr[10000000]; int n,x;
int BinarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid=l+(r-l)/2;
if (arr[mid]==x) return mid; if (arr[mid]>x)
return BinarySearch(arr,l,mid-1,x); return BinarySearch(arr,mid+1,r,x);
}
return -1;
}
int main()
{
ifstream fi("TK.inp"); ofstream fo("TK.out"); fi>>n>>x;
for (int i=0;i>arr[i];
int result=BinarySearch(arr,0,n-1,x); fo<<result<<"\n";

fo.close(); return 0;
}
fi.close();
fo.close(); return 0;
}
Lập bảng so sánh thời gian thực hiện của hai chương trình trên được kết quả như sau:

Chương trình dùng lính canh
Chương trình dùng chia để trị
N=6000000
≈ 0.8329733
≈ 0.6768452
N=500000
≈ 0.0954796
≈ 0.0771862
Nhận xét: Khác hẳn với bài toán 2 , đối với bài toán 3 việc lựa chọn áp dụng kĩ thuật chia để trị lại tối ưu hơn hẳn so với việc áp dụng kĩ thuật lính canh. Do đó chúng ta phải căn cứ cụ thể vào từng bài toán để lựa chọn kĩ thuật thích hợp, tối ưu nhất có thể.
Bài toán 4.
Cho số nguyên dương N. Hãy cho biết có bao nhiêu số nguyên tố nhỏ hơn i với mọi i thỏa mãn 1≤i≤N.
Với bài toán này chúng ta