Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 2 - Chương 2: Các hàm Next

(chiều dài 
đoạn). 
Trong các tệp, dữ liệu trên cùng dòng cách nhau qua 
dấu cách. 
Thí dụ trên cho ta đoạn không giảm dài nhất bao gồm 7 phần tử bắt đầu từ phần tử thứ tư trong dãy 
(các phần tử được gạch dưới): 
1 5 5 1 3 3 3 5 7 9 1 2 
Thuật toán 
Đây là bài dễ, ta đọc dần các phần tử từ input file và so sánh hai phần tử liên tiếp nhau là x (phần tử 
đọc trước tại bước i) và y (phần tử đọc sau tại bước i+1). Nếu y < x thì coi như kết thúc một đọan không 
giảm, ta cập nhật để ghi nhận lại đoạn không giảm dài nhất. Các biến tổng thể trong chương trình được 
dùng như sau: 
MaxLen – chiều dài của đoạn không giảm dài nhất hiện tìm được, 
imax - chỉ số đầu tiên của đoạn không giảm dài nhất hiện tìm được, 
ileft – chỉ số đầu tiên của đoạn không giảm đang xét. 
Độ phức tạp: cỡ N. 
(* Pascal *) 
(**************************************** 
 MDOAN - Doan tang dai nhat 
****************************************) 
program MDoan; 
uses crt; 
const 
 bl = #32; fn = 'MDOAN.INP'; gn = 'MDOAN.OUT'; 
var f,g: text; 
MDOAN.INP MDOAN.OUT 
12 
1 5 5 1 3 
3 3 5 7 9 
1 2 
4 7 
 83 
 n: integer; 
 a: mw1; 
 iLeft, imax: integer; 
 MaxLen: integer; 
procedure Update(i: integer); 
begin 
 if (MaxLen < i - iLeft) then 
 begin 
 MaxLen := i - iLeft; 
 imax := iLeft; ileft := i; 
 end; 
 iLeft := i; 
end; 
procedure XuLi; 
 var i, x, y: integer; 
 begin 
 assign(f,fn); reset(f); readln(f,n); 
 read(f,x); 
 iLeft := 1; MaxLen := 0; 
 for i := 2 to n do 
 begin 
 read(f,y); 
 if (y < x) then Update(i); 
 x := y; 
 end; 
 Update(n+1); 
 close(f); 
 end; 
procedure Ghi; 
begin 
 assign(g,gn); rewrite(g); 
 writeln(g,imax,bl,MaxLen); 
 close(g); 
end; 
BEGIN 
 XuLi; ghi; 
END. 
Trong phương án C# dưới đây ta đọc toàn bộ dữ liệu vào một mảng a rồi xử lý trên mảng này. 
// C# 
using System; 
using System.IO; 
using System.Collections; 
namespace SangTao2 { 
 class DoanKhongGiam { 
 const string fn = "MDoan.inp"; 
 const string gn = "MDoan.out"; 
 static public int n; // n - so phan tu 
 static public int imax; // chi so dau cua doan max 
 static public int ileft; // chi so dau cua doan dang xet 
 static public int maxlen; // chieu dai max 
 static public int [] a; 
 static void Main(string[] args) { 
 Doc(); XuLi(); Ghi(); XemKetQua(); 
 Console.WriteLine("\n Fini "); 
 Console.ReadLine(); 
 84 
 } 
 static public void XemKetQua(): tự viết 
 static public void XuLi() { 
 ileft = 0; maxlen = 0; 
 for (int i = 1; i < n; ++i) 
 if (a[i] < a[i-1]) Update(i); 
 Update(n); 
 } 
 static public void Update(int i) { 
 if (maxlen < i - ileft) 
 { maxlen = i - ileft; imax = ileft; ileft = i; } 
 } 
 static public void Doc(): tự viết 
 static public void Ghi() { 
File.WriteAllText(gn, imax.ToString() + " " + 
 maxlen.ToString()); } 
 } // DoanKhongGiam 
} // SangTao2 
Bài 2.12 Đoạn đơn điệu dài nhất 
Dijkstra E. 
Cho dãy gồm N số nguyên. Tìm đoạn đơn điệu (không giảm hoặc không tăng) có chiều dài lớn nhất. 
Dữ liệu vào: tệp văn bản DONDIEU.INP 
Dòng thứ nhất: số tự nhiên N, 1  N  20000. 
Từ dòng thứ hai trở đi: các phần tử của dãy. 
Dữ liệu ra: tệp văn bản DONDIEU.OUT 
Chứa một dòng duy nhất gồm hai số tự nhiên d – chỉ 
số đầu đoạn và L – số phần tử trong đoạn (chiều dài 
đoạn). 
Trong các tệp, dữ liệu trên cùng dòng cách nhau qua 
dấu cách. 
Thuật toán 
Edsger Wybe Dijkstra (1930-2002) 
Sinh năm 1930 tại Rotterdam, Holland. 
1948-1956 học Toán và Vật lý lý thuyết 
tại Đại học Leyden. 1952-1962 nghiên 
cứu tại Trung tâm Toán học Amsterdam. 
1962-1973 Giáo sư Toán tại Đại học Bách 
khoa Eindhoven, Holland và Đại học 
Texas Austin. Dijkstra là một trong những 
người đi tiên phong trong lĩnh vực lập 
trình, người khởi xướng và đặt nền móng 
cho nguyên lý lập trình cấu trúc. 
DONDIEU.INP DONDIEU.OUT 
12 
1 5 5 1 3 
3 3 5 7 9 
1 2 
4 7 
 85 
Edsger Wybe Dijkstra 
(photo ©2002 Hamilton 
Richards) 
Nhận xét: 
Đoạn có 1 phần tử là đoạn đơn điệu (tăng, giảm), 
Đoạn gồm một dãy liên tiếp các phần tử bằng nhau là đoạn đơn điệu (tăng, giảm). 
Ta dùng hai biến đếm các phần tử tăng hoặc bằng nhau liên tiếp, dt và đếm các phần tử giảm hoặc 
bằng nhau liên tiếp, dg. Nếu ai = ai1 ta tăng đồng thời dt và dg 1 đơn vị. Nếu ai > ai1 ta tăng dt thêm 1 đơn 
vị và đặt lại dg = 1. Nếu ai < ai1 ta tăng dg thêm 1 đơn vị và chỉnh lại dt = 1. Sau mỗi bước ta cập nhật đoạn 
đơn điệu dài nhất tìm được. Chương trình Pascal đọc và xử lí trực tiếp file input, chương trình C# đọc toàn 
bộ dữ liệu vào mảng rồi xử lí trên mảng. 
Độ phức tạp: cỡ N. 
Các biến tổng thể: 
n: số lượng phần tử, 
dt: đếm số phần tử trong dãy tăng, 
dg: đếm số phần tử trong dãy giảm. 
iMax: chỉ số đầu của đoạn đơn điệu dài nhất, 
MaxLen: chiều dài (số phần tử) của đoạn đơn điệu dài nhất. 
(* Pascal *) 
program DonDieu; 
uses crt; 
const 
 bl = #32; fn = 'DONDIEU.INP'; gn = 'DONDIEU.OUT'; 
var f,g: text; 
 n: integer; 
 dt,dg: integer; 
 iMax, MaxLen: integer; 
function Max(a,b,c: integer): integer; 
begin 
 if (a < b) then a := b; { a = Max(a,b) } 
 if (a > c) then Max := a 
 else Max := c; 
end; 
procedure XuLi; 
 var i,m,x,y: integer; 
 begin 
 assign(f,fn); reset(f); 
 readln(f,n); read(f,x); 
 dt := 1; dg := 1; 
 MaxLen := 1; iMax := 1; 
 for i := 2 to n do 
 begin 
 read(f,y); 
 if (y = x) then 
 begin dt := dt + 1; dg := dg + 1; end 
 else if (y > x) then 
 begin dt := dt + 1; dg := 1; end 
 else { y < x } 
 begin dg := dg + 1; dt := 1; end; 
 86 
 m := Max(MaxLen, dt, dg); 
 if (m > MaxLen) then 
 begin MaxLen := m; iMax := i - MaxLen + 1; end; 
 x := y; 
 end; 
 close(f); 
 end; 
procedure Ghi; 
begin 
 assign(g,gn); rewrite(g); 
 writeln(g, iMax, bl, MaxLen); close(g); 
end; 
BEGIN 
 XuLi; Ghi; 
END. 
// C# 
using System; 
using System.IO; 
using System.Collections; 
namespace SangTao2 { 
 class DonDieu { 
 const string fn = "DonDieu.inp"; 
 const string gn = "DonDieu.out"; 
 static public int n; // n - so phan tu 
 static public int imax; // chi so dau tien cua doan max 
 static public int maxlen; // chieu dai max 
 static public int [] a; 
 static void Main(string[] args) { 
 Doc(); XuLi(); Ghi(); XemKetQua(); 
 Console.WriteLine("\n Fini "); 
 Console.ReadLine(); 
 } 
 static public void XemKetQua(): tự viết 
 static public void XuLi(){ 
 imax = 0; maxlen = 1; 
 int dt = 1, dg = 1; 
 int m; 
 for (int i = 1; i < n; ++i){ 
 if (a[i] == a[i - 1]) { ++dt; ++dg; } 
 else if (a[i] < a[i - 1]) { dt = 1; ++dg; } 
 else /* a[i] > a[i-1] */ { ++dt; dg = 1; } 
 m = Max(maxlen, dt, dg); 
 if (maxlen < m) 
 { maxlen = m; imax = i - maxlen + 1; } 
 } 
 } 
 static public int Max(int a, int b, int c){ 
 if (a < b) a = b; // a = Max(a,b) 
 return (a > c) ? a : c; 
 } 
 static public void Doc(): tự viết 
 static public void Ghi(): tự viết 
 } // DonDieu 
} // SangTao2 
 87 
Bài 2.13 Lũy thừa 2, 3 và 5 
Dijkstra E. 
Với mỗi giá trị N cho trước hãy sinh N số đầu tiên theo trật tự tăng dần là tích các lũy thừa của 2, 3 
và 5. 
Dữ liệu vào: tệp văn bản LUYTHUA.INP 
Chứa số tự nhiên N, 1  N  1000. 
Dữ liệu ra: tệp văn bản LUYTHUA.OUT 
N số tìm được, mỗi dòng một số. 
Thuật toán 
Gọi S là tập các số cần tìm. Ta có 
 (i) 1  S 
 (ii) Nếu x  S thì 2x, 3x, 5x  S. 
Giả sử các phần tử trong S được sắp tăng và ta đã 
tìm được phần tử thứ i. Ta kí hiệu S(i) = { a1, a2,…,ai }. Để 
tìm phần tử thứ i+1 ta nhận xét 
ai+1 = Min { 2x, 3y, 5z | x, y, z  S(i), 2x > ai, 3y > 
ai, 5z > ai } 
Ta sử dụng 3 biến i2, i3, i5 để ghi nhận các chỉ số 
trong S sao cho ai2 = x, ai3 = y và ai5 = z. Các biến a[1], i2, 
i3 và i5 được khởi trị 1. 
Khi đó hàm Next(i) sinh phần tử sát sau phần tử A[i] sẽ như sau: 
function Next(i: integer): integer; 
begin 
 while (a[i2] * 2 <= a[i]) do i2 := i2 + 1; 
 while (a[i3] * 3 <= a[i]) do i3 := i3 + 1; 
 while (a[i5] * 5 <= a[i]) do i5 := i5 + 1; 
 Next := Min(a[i2]*2, a[i3]*3, a[i5]*5); 
end; 
(* Pascal *) 
(*************************************** 
 LUY THUA cua 2, 3, 5 
 *************************************) 
program LuyThua; 
uses crt; 
const bl = #32; mn = 1001; fn = 'LUYTHUA.INP'; gn = 'LUYTHUA.OUT'; 
type ml1 = array[0..mn] of longint; 
var f,g: text; 
n: integer; 
a: ml1; 
procedure Doc: tự viết; 
function Min(a,b,c: longint): tự viết; 
function Next(i: integer): tự viết; 
procedure Sinh; 
 var i: longint; 
begin 
 assign(g,gn); rewrite(g); 
LUYTHUA.INP LUYTHUA.OUT 
12 
1 
2 
3 
4 
5 
6 
8 
9 
10 
12 
15 
16 
 88 
 a[1] := 1; writeln(g,1); 
 i2 := 1; i3 := 1; i5 := 1; 
 for i := 2 to n do 
 begin 
 a[i] := Next(i-1); 
 writeln(g,a[i]); 
 end; 
 close(g); 
end; 
BEGIN 
 Doc; Sinh; 
END. 
// C# 
using System; 
using System.IO; 
namespace SangTao2 { 
 /*-------------------------------------------* 
 Luy thua 2, 3, 5 
 * ------------------------------------------*/ 
 class LuyThua235 { 
 const string fn = "LuyThua.inp"; 
 const string gn = "LuyThua.out"; 
 static public int n; // so luong phan tu 
 static public int[] a; 
 static void Main(){ 
 Doc(); Sinh(); Ghi(); XemKetQua(); 
 Console.WriteLine("\n fini"); 
 Console.ReadLine(); 
 } // Main 
 static public void Doc() 
 { n = int.Parse(File.ReadAllText(fn).Trim()); } 
 static public void Sinh(){ 
 a = new int[n]; 
 int i2 = 0, i3 = 0, i5 = 0; a[0] = 1; 
 int n1 = n-1; 
 for (int i = 0; i < n1; ++i){ // Next 
 while (a[i2] * 2 <= a[i]) ++i2; 
 while (a[i3] * 3 <= a[i]) ++i3; 
 while (a[i5] * 5 <= a[i]) ++i5; 
 a[i + 1] = Min(a[i2] * 2, a[i3] * 3, a[i5] * 5); 
 } 
 } 
 static public int Min(int x, int y, int z) : tự viết 
 static public void Ghi(){ 
 StreamWriter g = new StreamWriter(gn); 
 for (int i = 0; i < n; ++i) g.WriteLine(a[i]); 
 g.Close(); 
 } 
 static void XemKetQua(): tự viết 
 } // LuyThua235 
} // space