Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 1: Giải một bài toán tin

i := 1 to n do a[i]:=random(m); 
 exit; 
end; 
 { Khoi tri mang co tong d phan tu dau 
 bang tong cac phan tu con lai } 
 d := random(n div 2)+ 1; { diem chia } 
 t := 0; 
 for i := 1 to d do 
 begin 
 a[i] := random(n); 
 t := t + a[i]; 
 end; { t = sum(a[1..d]) } 
 for i := d+1 to n-1 do 
 begin { sum(a[d+1..i]) + t = sum(a[1..d]) } 
 a[i] := random(t); 
 t := t-a[i]; 
 end; 
 a[n] := t; { sum(a[1..d]) = sum(a[d+1..n]) } 
end; 
procedure Xem: Hiển thị mảng a, tự viết 
function Chia: integer; 
var i, t, t2, tr: integer; 
begin 
 Chia := -1; t := 0; 
 for i:=1 to n do t:=t+a[i]; {t=sum(a[1..n]} 
 if Odd(t) then exit; { vo nghiem } 
 t2 := t div 2; tr := 0; 
 for i:=1 to n do 
 begin 
Sáng tạo trong Thuật toán và Lập trình Tập I 
19 
 tr := tr + a[i]; 
 if tr > t2 then exit; {vo nghiem } 
 if tr = t2 then { co nghiem i } 
 begin Chia:= i; exit; end; 
 end; 
end; 
procedure Test; 
var i: integer; 
begin 
 repeat 
 Gen(10); Xem; i := Chia; 
 if i = -1 then writeln('Khong chia duoc') 
 else 
 begin 
 writeln('Doan thu nhat: a[1..',i,']'); 
 writeln('Doan thu hai: a[',i+1,'..',n,']'); 
 end; 
 until ReadKey=Esc; 
end; 
BEGIN 
 Test; 
END. 
Chú ý 
1. Muốn dừng chương trình hãy nhấn phím Esc có mã ASCII là #27. 
 2. Nếu mảng a có chứa một số giá trị 0 thì bài toán có thể có nhiều nghiệm 
(nhiều cách chia). 
// C# 
using System; 
namespace SangTao1 
{ 
 class ChiaMangTiLe1_1 
 { 
 static void Main() 
 { 
 do { 
 Run(20); 
 Console.Write("\n Bam phim ENTER “ + 
 “de tiep tuc, "); 
 Console.Write("\n Bam phim T de thoat: "); 
 } while (Console.ReadLine() == ""); 
 } 
 static public void Run(int n) 
 { int[] a = new int[n]; 
 Gen(a, n); // sinh ngau nhien 1 test 
 Print(a, n); 
 int t = 0, d = Chia(a, n, ref t); 
 if (d < 0) 
 Console.WriteLine("\n Khong chia duoc"); 
 else if (KiemTra(a, n, d)) 
{ Console.WriteLine("\n Doan thu nhat: 1..{0} ",d); 
 Console.WriteLine("\n Doan thu hai: {0}..{1} ", 
Sáng tạo trong Thuật toán và Lập trình Tập I 
20 
 d+1, n); 
 Console.WriteLine("\n Tong moi doan: " + t); 
 } 
else Console.WriteLine("\n Loi giai sai!"); 
 } // end Run 
// Kiem tra sum(a[1..d] == sum(a[d+1..n]) ? 
static public bool KiemTra(int[] a, int n, int d) 
{ if (d = n) return false; 
 int t = 0; 
 for (int i = 0; i < d; ++i) t += a[i]; 
 for (int i = d; i < n; ++i) t -= a[i]; 
 return (t == 0) ? true : false; 
} 
static public int Chia(int[] a, int n, ref int t) 
{ int sum = 0; // sum = tong(a[1..n]) 
 for (int i = 0; i < n; ++i) sum += a[i]; 
 if (sum % 2 != 0) return -1; 
 t = sum / 2; // tong moi doan 
 int tr = 0; // tong rieng 
 // doan 1: tr = sum a[1..i] 
 for (int i = 0; i < n; ++i) 
 { tr += a[i]; 
 if (tr == t) return i+1; 
 } 
 return -1; 
 } 
 // sinh ngau nhien n so ghi vao mang a 
 static public void Gen(int[] a, int n) 
 { 
 Random r = new Random(); 
 if (r.Next(2) == 0) 
 { // 1/2 so test la vo nghiem 
 for (int i = 0; i < n; ++i) a[i]=r.Next(n); 
 return; 
 } 
 // sinh mang a: sum(a[0..d-1])=sum(a[d..n-1]) 
 int d = r.Next(n / 2) + 1; // diem chia 
 int t = 0; 
 // sinh doan a[0..d-1] 
 for (int i = 0; i < d; ++i) 
 { a[i] = r.Next(n); t += a[i]; } 
 // sinh tiep doan a[d..n-1] 
 int n1 = n-1; 
 for (int i = d; i < n1; ++i) 
 { a[i] = r.Next(t); t -= a[i]; } 
 a[n-1] = t; // phan tu cuoi 
 } 
 static public void Print(int[] a, int n): tự viết 
 } // SoCapNhan 
} // SangTao1 
Sáng tạo trong Thuật toán và Lập trình Tập I 
21 
Bài 1.6. Chia mảng tỉ lệ 1:k 
 Tìm cách chia dãy số nguyên không âm a1, a2,...,an, n > 1 cho trước thành hai 
đoạn có tổng các phần tử trong một đoạn gấp k lần tổng các phần tử trong 
đoạn kia, k nguyên dương. 
Đặc tả 
Gọi t là tổng các phần tử của dãy a, t = sum(a[1..n]) 
Muốn chia a thành hai đoạn a[1..i] và a[i + 1..n] có tổng gấp nhau k lần ta phải có: 
1. t chia hết cho (k + 1). Đặt t1 = t div (k + 1) và tk = t - t1. 
2. (#E i: 1 <= i <= n): sum(a[1..i]) = t1 hoặc sum(a[1..i]) = tk. 
Để ý rằng nếu k = 1 thì t1 = tk; nếu k > 1 thì t1 < tk, do đó bài này là trường hợp 
riêng của bài trước khi k = 1. 
Trong chương trình dưới đây, hàm Chia(k) cho giá trị i nếu mảng a chia được 
thành hai đoạn a[1..i] và a[(i + 1)..n] có tổng gấp k lần nhau. Trong trường hợp vô 
nghiệm Chia = -1. Ta gọi i là điểm chia và dùng biến tr (tổng riêng) để tích luỹ 
tổng các phần tử của đoạn đang xét a[1..i]. Khi tr = t1 bài toán có nghiệm I, ngược lại, 
khi tr > t1 ta chưa thể kết luận là bài toán vô nghiệm. Trường hợp này ta phải tiếp tục 
tích luỹ tr để hi vọng đạt được tổng tr = tk. Nếu sau khi tích luỹ ta thu được tr = tk thì 
bài toán có nghiệm i, ngược lại, khi tr > tk ta kết luận là bài toán vô nghiệm. 
Function Chia(n,k: integer): integer; 
var i: integer; 
 t, t1, tk, tr: longint; 
begin 
 Chia := -1; 
 t := 0; { t = sum(a[1..n]) } 
 for i := 1 to n do t := t+a[i]; 
 if (t mod (k+1) 0) then exit; { vo nghiem } 
 { Xu li truong hop co nghiem } 
 t1 := t div (k+1); { doan tong nho } 
 tk := t - t1; { tk = k * t1} 
 tr := 0; { tong rieng tr = sum(a[1..i]) } 
 for i := 1 to n do 
 begin 
 tr := tr + a[i]; 
 if (tr = t1) or (tr = tk) then 
 begin { lay nghiem i } 
 Chia:= i; exit; 
 end; 
 end; 
end; 
Ta gọi thủ tục Gen để sinh dữ liệu kiểm thử. Cũng giống như bài trước, ta sẽ sinh 
ngẫu nhiên dữ liệu kiểm thử cho hai trường hợp: chắc chắn có nghiệm và có thể vô 
nghiệm. Với trường hợp có thể vô nghiệm ta sinh ngẫu nhiên như bình thường, 
for i := 1 to n do a[i] := random(n); 
Với trường hợp có nghiệm, ta sinh ngẫu nhiên mảng a gồm hai đoạn: 
Đoạn thứ nhất a[1..d] và đoạn thứ hai a[d + 1..n] trong đó d là một điểm chia được 
sinh ngẫu nhiên 
d := random(n div 2)+1; {diem chia} 
Ta lại chọn ngẫu nhiên một trong hai trường hợp: 
Sáng tạo trong Thuật toán và Lập trình Tập I 
22 
Trường hợp thứ nhất: đoạn thứ nhất gấp k lần đoạn thứ hai. 
Trường hợp thứ hai: đoạn thứ hai gấp k lần đoạn thứ nhất. 
(* Pascal *) 
(*------------------------------------------- 
 Chia mang nguyen a thanh 2 doan 
 co tong ti le 1:k 
------------------------------------------ *) 
{$B-} 
uses Crt; 
const MN = 500; 
 Esc = #27;{ dau thoat } 
 bl = #32; { dau cach } 
 nl = #13#10; { xuong dong } 
var a: array [0..MN] of integer; 
 n: integer; 
(*---------------------------------------------- 
 Sinh ngau nhien n so nguyen khong am cho mang a 
----------------------------------------------- *) 
Procedure Gen(m,k: integer); 
 var i,d: integer; t: longint; 
begin 
 n := m; t := 0; 
 if random(2) = 0 then { vo nghiem } 
 begin 
 for i := 1 to n do a[i]:= random(n); 
 exit; 
 end; 
 { co nghiem } 
 d := random(n div 2)+1; { diem chia } 
 for i := 1 to d do 
 begin 
 a[i] := random(n); t := t+a[i]; 
 end; 
 if (random(2) = 0) then 
 { doan a[1..d] gap k lan doan cuoi } 
 a[d] := a[d]+(k-1)*t 
 else { doan cuoi gap k lan doan a[1..d] } 
 t := k*t; 
 for i := d+1 to n-1 do 
 begin 
 a[i] := random(t); t := t-a[i]; 
 end; 
 a[n] := t; 
end; 
Procedure Xem; Hiển thị mảng a, tự viết 
Function Chia(n,k: integer): integer; Tự viết 
Procedure Test; 
 var j,i,k: integer; t: longint; 
 begin 
 randomize; 
 repeat 
Sáng tạo trong Thuật toán và Lập trình Tập I 
23 
 n := 10 + random(10); 
 k := random(5)+1; 
 writeln(nl,' n = ',n,' k = ',k); 
 Gen(n,k); Xem; i := Chia(n,k); 
 if i < 0 then writeln('Khong chia duoc') 
 else 
 begin 
 t := 0; 
 for j := 1 to i do t := t+a[j]; 
 write('Doan 1: a[1..',i,'].'); 
 writeln(' Tong = ',t); 
 t := 0; 
 for j:=i+1 to n do t := t+a[j]; 
 write('Doan 2: a[',i+1,'..',n,'].'); 
 writeln(' Tong = ',t); 
 end; 
 until ReadKey = Esc; 
 end; 
BEGIN 
 Test; 
END. 
// C# 
 using System; 
 using System.Collections.Generic; 
 using System.Text; 
 namespace SangTao1 
 { 
 /*------------------------------------------- 
 * Chia Mang Ti Le 1:k 
 * Chia mang nguyen khomng am a[1..] thanh 
 * hai doan ti le 1:k hoac k:1 
 * ------------------------------------------*/ 
 class ChiaMangTiLe1_k 
 { 
 static void Main(string[] args) 
 { 
 do 
 { 
 Run(10, 3); 
 Console.Write("\n Bam RETURN de tiep tuc, "); 
Console.Write("\n Bam T de thoat: "); 
 } while (Console.ReadLine() != "T"); 
 } 
 static public void Run(int n, int k) 
 { 
 if (n 1000000 || k < 1) return; 
 int[] a = Gen(n, k); 
 Print(a); 
 int d = Chia(a, k); 
 if (d < 0) 
 { 
Sáng tạo trong Thuật toán và Lập trình Tập I 
24 
 Console.WriteLine("\n Vo nghiem"); 
 return; 
 } 
 Console.WriteLine("\n “+ Test(a, d, k)); 
 } 
 // Kiem tra k*Sum(a[1..d]) = Sum(a[d+1..n]) ? 
 // hoac Sum(a[1..d]) = k*Sum(a[d+1..n]) 
 static public bool Test(int[] a, int d, int k) 
 { 
 Console.WriteLine("\n\n Test, k = " + k); 
 Console.WriteLine(" Diem Chia = " + d); 
 int t1 = 0; 
 for (int i = 0; i < d; ++i) t1 += a[i]; 
 int t2 = 0; 
 for (int i = d; i < a.Length; ++i) t2 += a[i]; 
 Console.WriteLine("Sum1 = {0}, Sum2 = {1}", 
 t1, t2); 
 return (t1 == k * t2 || t2 == k * t1); 
 } 
 static public int Chia(int[] a, int k) 
 { 
 int t = 0; 
 foreach (int x in a) t += x; 
 if (t % (k + 1) != 0) return -1; 
 int t1 = t / (k + 1); // tong 1 phan chia 
 int t2 = t - t1; // tong phan con lai 
 int tr = 0; // tong rieng 
 for (int i = 0; i < a.Length; ++i) 
 { 
 tr += a[i]; 
 if (tr == t1 || tr == t2) return i+1; 
 } 
 return -1; 
 } 
 static public int[] Gen(int n, int k) 
 { 
 Random r = new Random(); 
 int[] a = new int[n]; 
 if (r.Next(2) == 0) 
 { // khoang 1/2 so test la vo nghiem 
 for (int i = 0; i < n; ++i) 
 a[i] = r.Next(n); 
 return a; 
 } 
 int d = r.Next(n / 2) + 1; //diem chia 
 int t = 0; 
 int d1 = d - 1; 
 for (int i = 0; i < d1; ++i) 
 { a[i] = r.Next(n); t += a[i]; } 
 if (r.Next(2) == 0) 
 // doan dau a[1..d] 
 // gap k lan doan cuoi a[d+1..n] 
 a[d1] += (k - 1) * t;