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 4: Các thuật toán sắp đặt

hức năng của các phím điều khiển 
 155 
Bạn cũng có thể sử dụng hệ 4 để xử lí như sau: Các phương án nhấn 9 phím biến thiên từ 
(0,0,0,0,0,0,0,0,0) đến (3,3,3,3,3,3,3,3,3) ứng với imin = 0 và imax = 49-1 = 218-1 = (1 shl 18) - 1 = 
262143. Ta cho i biến thiên từ imin đến imax. Với mỗi i ta xây dựng phương án nhấn phím bằng cách gọi 
thủ tục Split(i,p) chuyển số i sang dạng biểu diễn hệ 4 để ghi vào mảng p, trong đó p[j] sẽ là số lần nhấn 
phím j. Biết p ta dễ dàng cập nhật các đồng hồ. 
Chương trình dưới đây cài đặt 2 phương án vét cạn, Run1 – chín vòng for lồng nhau và Run2 - tính 
toán theo hệ 4. 
(* Pascal *) 
(* Dong ho *) 
const bl = #32; fn = 'DONGHO.INP'; gn = 'DONGHO.OUT'; 
type mi1 = array[1..9] of integer; 
var 
 dongHo,kq: mi1; 
 f,g: text; 
 imin, imax: longint; 
 s, tsmin: integer; 
var 
phim: array[1..9,1..4] of integer; 
procedure Split(x: longint; var a: mi1); 
var i: integer; 
begin 
 for i := 1 to 9 do 
 begin 
 a[i] := x mod 4; 
 x := x div 4; 
 end; 
end; 
procedure Doc; 
var i,j: integer; 
begin 
 assign(f,fn); reset(f); 
 for i:=1 to 9 do read(f,dongHo[i]); 
 for i:=1 to 9 do 
 for j:=1 to 4 do read(f,phim[i,j]); 
 close(f); 
end; 
procedure Ghi; 
var i,j: integer; 
begin 
 assign(g,gn); rewrite(g); 
 if tsmin = 28 then writeln(g,0) { vo nghiem } 
 else 
 begin { co nghem } 
 writeln(g,1); 
 for i := 1 to 9 do 
 for j := 1 to c[i] do write(g,i,bl); 
 writeln(g); 
 end; 
 close(g); 
end; 
procedure Init; 
var i: integer; 
begin 
 for i:=1 to 9 do dongHo[i] := (dongHo[i] div 3) mod 4; 
 imin := 0; 
 156 
 imax := 1; 
 imax := (imax shl 18 - 1); 
end; 
function KiemTra(var q: mi1): Boolean; 
var i: integer; 
begin 
 KiemTra := false; 
 for i:=1 to 9 do 
 if (dongHo[i]+q[i]) mod 4 0 then exit; 
 KiemTra := true; 
end; 
function Sum(var q: mi1): integer; 
 var i,s: integer; 
begin 
 s := 0; 
 for i:=1 to 9 do s := s+q[i]; 
 Sum := s; 
end; 
procedure XuLiFor; 
var j,k,ts: integer; 
 q,p: mi1; { p[i] – so lan nhan phim i } 
 i,ikq: longint; 
begin 
 tsmin := 28; { = 3*9+1 } 
 for p[1] := 0 to 3 do 
 for p[2] := 0 to 3 do 
 for p[3] := 0 to 3 do 
 for p[4] := 0 to 3 do 
 for p[5] := 0 to 3 do 
 for p[6] := 0 to 3 do 
 for p[7] := 0 to 3 do 
 for p[8] := 0 to 3 do 
 for p[9] := 0 to 3 do 
 begin 
 fillchar(q,sizeof(q),0); 
 for j := 1 to 9 do 
 begin 
 for k := 1 to 4 do 
 inc(q[phim[j,k]],p[j]); 
 end; 
 if KiemTra(q) then 
 begin 
 ts := Sum(p); 
 if ts < tsmin then 
 begin 
 tsmin := ts; 
 kq := p; 
 end; 
 end; 
 end; 
end; 
procedure XuLi; 
var j,k,ts: integer; 
 q,p: mi1; 
 i,ikq: longint; 
begin 
 tsmin := 28; { = 3*9+1 } 
 157 
 for i:=imin to imax do 
 begin 
 Split(i,p); { bam phim j p[j] lan } 
 fillchar(q,sizeof(q),0); 
 for j := 1 to 9 do 
 begin 
 for k := 1 to 4 do 
 inc(q[phim[j,k]],p[j]); 
 end; 
 if KiemTra(q) then 
 begin 
 ts := Sum(p); 
 if ts < tsmin then 
 begin 
 tsmin := ts; 
 ikq := i; 
 end; 
 end; 
 end; 
 Split(ikq,kq); 
end; 
procedure Run1; 
begin 
 Doc; Init; 
 XuLiFor; Ghi; 
end; 
procedure Run2; 
begin 
 Doc; Init; 
 XuLi; Ghi; 
end; 
BEGIN 
 Run1; 
END. 
Chương trình C# 
// C# 
using System; 
using System.Collections.Generic; 
using System.Text; 
using System.IO; 
namespace SangTao2 { 
 class DongHo { 
 const string fn = "DONGHO.INP"; 
 const string gn = "DONGHO.OUT"; 
 const int cc = 9; 
 static int[,] phim = new int [9,4]; 
 static int[] dongHo = new int[cc]; 
 static int [] kq = new int [cc]; 
 static int smin = 0; // Tong so lan nhan phim 
 static void Main(string[] args) { 
 Run2(); 
 Console.ReadLine(); 
 } 
 static void Run1(){ 
 158 
 Doc(); Init(); XuLi(); Ghi(); XemKq(); 
 } 
 static void Run2(){ 
 Doc(); Init(); 
 XuLiFor(); Ghi(); XemKq(); 
 } 
 static void XuLiFor(){ 
 int [] p = new int [cc];// 9 phim 
 int[] dh = new int[cc];//so lan nhay kim cua 9 DH 
 int s = 0; 
 smin = 28; 
 for (p[0]=0; p[0] < 4; ++p[0]) 
 for (p[1]=0; p[1] < 4; ++p[1]) 
 for (p[2]=0; p[2] < 4; ++p[2]) 
 for (p[3]=0; p[3] < 4; ++p[3]) 
 for (p[4]=0; p[4] < 4; ++p[4]) 
 for (p[5]=0; p[5] < 4; ++p[5]) 
 for (p[6]=0; p[6] < 4; ++p[6]) 
 for (p[7]=0; p[7] < 4; ++p[7]) 
 for (p[8]=0; p[8] < 4; ++p[8]){ 
 Array.Clear(dh,0,dh.Length); 
 for (int j = 0; j < cc; ++j) 
 //phim j nhan p[j] lan 
 for (int k = 0; k < 4; ++k) 
 // 4 DH chuyen kim 
 dh[phim[j, k]] += p[j]; 
 if (KiemTra(dh)){ 
 s = Sum(p); 
 if (s < smin){ 
 smin = s; 
 p.CopyTo(kq,0); 
 } 
 } 
 } 
 } 
 static int Sum(int []p){ // Tong so lan nhan phim 
 int s = 0; 
 for (int i = 0; i < cc; ++i) s += p[i]; 
 return s; 
 } 
 static void Doc() { // Doc du lieu tu input file 
 int[] v = 
 Array.ConvertAll((File.ReadAllText(fn)).Split( 
 new char[] { '\0', '\n', '\t', '\r', ' ' }, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 int k = 0; 
 for (int j = 0; j < cc; ++j) dongHo[j] = v[k++]; 
 for (int i = 0; i < cc; ++i) 
 for (int j = 0; j < 4; ++j) 
 phim[i, j] = v[k++]; 
 } 
 static void Init() { // Khoi tri 
 for (int j = 0; j < cc; ++j) 
 dongHo[j] = (dongHo[j] / 3) % 4; 
 for (int i = 0; i < cc; ++i) 
 for (int k = 0; k < 4; ++k) 
 159 
 --phim[i, k]; 
 } 
 static void XuLi(){ 
 int imax = ((int)1 << 18) - 1; 
 int[] p = new int[cc]; smin = 28; 
 int[] q = new int[cc]; 
 for (int i = 0; i <= imax; ++i){ 
 int s = Split(i, p); 
 Array.Clear(q, 0, q.Length); 
 for (int j = 0; j < cc; ++j) 
 for (int k = 0; k < 4; ++k) 
 q[phim[j, k]] += p[j]; 
 if (KiemTra(q)) 
 if (s < smin){ smin = s; p.CopyTo(kq,0); } 
 } 
 } 
 static void Ghi(){ 
 StreamWriter g = File.CreateText(gn); 
 if (smin < 28) { // co nghiem 
 g.WriteLine(1); 
 for (int i = 0; i < cc; ++i) 
 for (int j = 1; j <= c[i]; ++j) 
 g.Write((i + 1) + " "); 
 } 
 else g.WriteLine(0); // vo nghiem 
 g.Close(); 
 } 
 static bool KiemTra(int[] q)// Kiem tra ca 9 DH tro ve 0? 
 { 
 for (int i = 0; i < cc; ++i) 
 if ((dongHo[i] + q[i]) % 4 > 0) return false; 
 return true; 
 } 
 // Tach x thanh cac chu so he 4 va tinh tong 
 static int Split(int x, int[] p){ 
 int s = 0; 
 for (int i = 0; i < cc; ++i) 
 { p[i] = x % 4; s += p[i]; x /= 4; } 
 return s; 
 } 
 static void XemKq(){ 
 Console.WriteLine("\n Input file " + fn); 
 Console.WriteLine(File.ReadAllText(fn)); 
 Console.WriteLine("\n Output file " + gn); 
 Console.WriteLine(File.ReadAllText(gn)); 
 } 
 } // DongHo 
} // SangTao2 
4.10 Số duy nhất 
Olimpic Baltics 
Tệp văn bản UNIQUE.INP chứa dãy số, mỗi số chiếm một dòng dài không quá 20 chữ số. Trong 
dãy này có duy nhất một số xuất hiện đúng một lần, các số còn lại đều xuất hiện đúng k lần. Hãy tìm số duy 
nhất đó. Số k không cho trước, nhưng biết rằng đó là một số chẵn khác 0. Kết quả hiển thị trên màn hình. 
 160 
Thuật toán 
Ta dựa vào một kiến thức có từ hàng ngàn năm trước, đó là biểu diễn số theo vị trí. Ta lần lượt đọc 
từng dòng vào một biến string sau đó ghi vào một mảng a số lần xuất hiện của từng chữ số tại từng vị trí, 
a[c,i] cho biết số lần xuất hiện của chữ số c tại cột i tính từ trái qua phải. 
Với thí dụ đã cho, trên cột 1 ta tính được a[„1‟,1] = 5, a[„2‟,1] = 4, a[„3‟,1] = 0,... , a[„8‟,1] = 4... 
Như vậy mảng a có kích thước 10 hàng đủ chứa 10 chữ số „0‟..‟9‟ và 20 cột đủ chứa các chữ số dài nhất. 
Sau khi đọc xong dữ liệu, ta thấy mọi phần tử của mảng a hoặc là chia hết cho k do đó là số chẵn, hoặc là 
số lẻ có dạng m.k + 1, m = 0, 1, 2,... Nếu a[c,i] là số lẻ thì c sẽ là chữ số xuất hiện tại cột i của số duy nhất 
cần tìm. 
Chương trình Pascal 
(* Pascal *) 
procedure XuLi; 
const mn = 20; 
 ChuSo = ['0'..'9']; 
 fn = 'unique.inp'; 
var a: array['0'..'9',1..mn] of integer; 
 f: text; 
 i: integer; 
 s: string; 
 cs: char; 
begin 
 fillchar(a,sizeof(a),0); 
 assign(f,fn); reset(f); 
 while not seekeof(f) do 
 begin 
 readln(f,s); 
 for i:=1 to length(s) do 
 if s[i] in ChuSo then inc(a[s[i],i]); 
 end; 
 close(f); 
 s := ''; { Ket qua } 
 for i := 1 to mn do 
 for cs := '0' to '9' do 
 if Odd(a[cs,i]) then s := s+cs; 
 writeln(s); 
end; 
BEGIN 
 XuLi; 
 readln; 
END. 
Chương trình C# 
// C# 
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.IO; 
UNIQUE.IN
P 
MÀN HÌNH 
1357 
2008 
80 
1357 
2008 
80 
2008 
1357 
10203040 
80 
2008 
80 
1357 
10203040 
Giải thích: Số duy nhất cần tìm 
là 10203040. Các số còn lại 
đều xuất hiện 4 lần. 
 161 
namespace SangTao2 { 
 class Unique { 
 const string fn = "UNIQUE.INP"; 
 static void Main(string[] args){ 
 Console.WriteLine(XuLi()); 
 Console.ReadLine(); 
 } 
 static string XuLi(){ 
 string s; 
 StreamReader f = File.OpenText(fn); 
 int mn = 20; 
 int [,] a = new int[10,mn]; 
 Array.Clear(a, 0, a.Length); 
 while (true){ 
 s = f.ReadLine().Trim(); 
 if (s.Length == 0) break; 
 for (int i = 0; i < s.Length;++i) 
 if (s[i] >= '0' && s[i] <= '9') 
 ++a[s[i]-'0',i]; 
 } 
 f.Close(); 
 string kq = ""; 
 for (int i = 0; i < mn; ++i) 
 for (int cs = 0; cs <= 9; ++cs) 
 if (a[cs, i] % 2 == 1) 
 kq += cs; 
 return kq; 
 } 
 } // Unique 
} // SangTao2 
Độ phức tạp 
Nếu có n số dài tối đa m chữ số thì ta cần xét mỗi chữ số 1 lần, nghĩa là tổng cộng cần n.m thao tác. 
Duyệt mảng a cần 10.m thao tác là số rất nhỏ so với n.m. 
Các biến thể của bài UNIQUE 
1. Nếu đầu bài cho biết số k thì không cần đòi hỏi k là số chẵn. 
2. Biết duy nhất một số xuất hiện đúng m lần, các số còn lại đều xuất hiện k lần như nhau, k  m và 
k và m nguyên tố cùng nhau. Bạn thử suy nghĩ xem có cần biết cụ thể các giá trị của m và k không? Bạn 
thử tìm một số điều kiện của k và m? 
3. Thay các số bằng các dãy kí tự A..Z dài tối đa m. 
________________________ 
21.01.2010 
NXH