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 NextTrong hầu hết các bài của Chương, khi trình bày tham biến kiểu mảng trong các hàm và thủ tục ta giả thiết là các kiểu này đã được khai báo trước. Thí dụ, kiểu mảng nguyên một chiều được khai báo như sau:
Nội dung trích xuất từ tài liệu:
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 h ươ ng 2 C á c h àm Ne xt Trong hầu hết các bài của Chương, khi trình bày tham biến kiểu mảng trong các hàm và thủ tục tagiả thiết là các kiểu này đã được khai báo trước. Thí dụ, kiểu mảng nguyên một chiều được khai báo nhưsau: (* Pascal *) type mi1 = array[0..MN] of integer;trong đó MN là hằng số đủ lớn cho kích thước mỗi bài toán, thí dụ const MN = 2000; Trong C# mảng được khai báo trực tiếp hoặc thông qua class, thí dụ, int [] a = new int [2000]; Class Array { … }; Tùy theo bài toán và ngôn ngữ lập trình đã chọn, ta có thể hoặc không sử dụng phần tử đầu tiên vàcuối cùng của mảng. Như vậy, mảng x gồm n phần tử sẽ được kí hiệu là x [1..n] trong Pascal hoặc x[0..n1]trong C#. Trong Pascal khai báo tham biến kiểu var (truyền theo biến hay địa chỉ) cho mảng thì thủ tục sẽđược gọi nhanh hơn, trong C# các mảng được ngầm định là truyền theo biến / địa chỉ.Bài 2.1 Số sát sau cùng độ cao Chiều dài của một số tự nhiên là số chữ số của số đó. Độ cao của một số tự nhiên là tổng các chữ sốcủa số đó. Cho số tự nhiên x ghi trong hệ đếm b, có chiều dài N. Tìm số tự nhiên y sát sau x có cùng chiềudài, cùng độ cao và cùng hệ đếm với x. Dữ liệu vào: tệp văn bản DOCAO.INP DOCAO.INP DOCAO.OUT Dòng đầu tiên: hai số tự nhiên b và N cách nhau qua dấu cách, 2  b  100, 2  N  1000. 10 5 1 Dòng thứ hai: số x với các chữ số ghi cách nhau qua 23990 24089 dấu cách. Dữ liệu ra: tệp văn bản DOCAO.OUT Dòng đầu tiên: ghi 1 nếu có nghiệm, 0: nếu vô nghiệm. Dòng thứ hai: số y với các chữ số ghi cách nhau qua dấu cách.Thuật toán Độ cao của số x sẽ không đổi nếu ta đồng thời tăng và giảm hai chữ số của x cùng một đơn vị. Taduyệt lần lượt các chữ số của x từ phải qua trái, trước hết tìm chữ số xj > 0 đầu tiên để có thể giảm 1 đơnvị. Tiếp đến ta duyệt tiếp từ j1 qua trái tìm một chữ số xi < (b1) đầu tên sau j để có thể tăng thêm 1 đơn 52vị. Nếu không tìm được xj hoặc xi thì x không có số sát sau. Nếu tìm được đồng thời hai chữ số xj và xi nhưtrên thì ta sửa x như sau:  Giảm xj 1 đơn vị,  Tăng thêm xi 1 đơn vị,  Lật lại đoạn x[i+1..n]. Với thí dụ x[1..5] = (2,3,9,9,0) trong hệ đếm thập phân (b = 10) ta tìm được j = 4, x[j] = 9, i = 2, x[i]= 3. Sau khi giảm x[4] và tăng x[2] 1 đơn vị ta thu được x[1..5] = (2,4,9,8,0). Số này còn lớn, nếu lật lạiđoạn x[3..5] sẽ thu được x[1..5] = (2, 4,0,8,9). Đây là số cần tìm. Vì sao lại làm như vậy? Giải thích điều này khá dễ nếu để ý rằng x[j+1..n] chứa toàn 0 (chữ số nhỏnhất trong hệ đếm b) và x[i+1..j 1] chứa toàn (b1) (chữ số lớn nhất trong hệ đếm b). Từ đó suy ra rằngđoạn x[i+1..n] được sắp tăng. Lật lại đoạn đó ta sẽ thu được dãy các chữ số giảm dần. Vì x[i] đã được thêm1 đơn vị nên nó lớn hơn số ban đầu. Khi lật lại ta sẽ thu được số sát sau số ban đầu. Hàm Next dưới đây biến đổi trực tiếp x[1..n] để thu được số sát sau. Ta sử dụng phần tử x[0] = blàm giới hạn cho quá trình duyệt ngược. Phần tử x[0] này được gọi là lính canh. Nó có nhiệm vụ làm chovòng lặp dừng một cách tự nhiên mà không cần phải kiểm tra giới hạn chỉ số của mảng (rang check). Độ phức tạp: cỡ N, do mỗi chữ số của x được thăm và xử lí không quá 2 lần.(* Pascal *) function Next(var x: mi1; n,b: integer): Boolean; var i,j,t,b1: integer; begin Next := FALSE; x[0] := b; j := n; while (x[j] = 0) do j := j - 1; if (j = 0) then exit; { ko co so sat sau } i := j - 1; b1 := b - 1 ; while (x[i] = b1) do i := i - 1; if (i = 0) then exit; { Ko co so sat sau } x[j] := x[j] - 1; x[i] := x[i] + 1; i := i + 1; j := n; { Lat doan x[i..n] } while (i < j) do begin t := x[i]; x[i] := x[j]; x[j] := t; i := i + 1; j := j - 1; end; Next := TRUE; end;// C# static bool Next(int[] x, int n, int b) { int i, j , b1 = b - 1; for (j = n - 1; j >= 0; --j) if (x[j] > 0) break; if (j < 0) return false; for (i = j - 1; i >= 0; --i) if (x[i] < b1) break; if (i < 0) return false; --x[j]; ++x[i]; ++i; j ...