TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH

tải về 2.51 Mb.

trang	17/21
Chuyển đổi dữ liệu	24.07.2016
Kích	2.51 Mb.
	#3874

1 ... 13 14 15 16 17 18 19 20 21

5.6 Chuyển tin

Bách khoa Đà Nẵng, 2001

Cần chuyển hết n gói tin trên một mạng có m kênh truyền. Biết chi phí để chuyển i gói tin trên kênh j là C(i,j). Cho biết một phương án chuyển với chi phí thấp nhất.

Dữ liệu vào: file văn bản messages.inp:

Dòng đầu tiên: 2 số n và m;

Dòng thứ i trong số n dòng tiếp theo: Dãy m số nguyên dương b₁, b₂, ..., b_m trong đó b_j là chi phí chuyển i gói tin trên kênh j.

Dữ liệu ra: file văn bản messages.out:

Dòng đầu tiên: tổng chi phí thấp nhất theo phương án tìm được;

Dòng thứ j trong số m dòng tiếp theo: số lượng gói tin chuyển trên kênh j.

messages.inp

messages.out

Ý nghĩa

Với n = 5 gói tin, m = 4 kênh và chi phí c(i,j) cho trước, trong đó i là chỉ số dòng (số gói tin), j là chỉ số cột (kênh) thì cách chuyển sau đây sẽ cho chi phí thấp nhất là 2

Kênh	Số gói tin	Chi phí
1	0	0
2	4	1
3	1	1
4	0	0

5 4

31 10 1 1

1 31 12 13

4 10 31 1

6 1 20 19

10 5 10 10

2

0

4

1

0

Thuật toán Quy hoạch động

Gọi s(i,j) là chi phí thấp nhất của phương án chuyển hết i gói tin trên mạng gồm j kênh đầu tiên 1, 2, ..., j. Ta xét kênh thứ j và thử chuyển lần lượt k = 0, 1, ..., i gói tin theo kênh này. Ta thấy, nếu chuyển k gói tin theo kênh j thì chi phí cho kênh j này sẽ là c(k,j), còn lại ik gói tin phải chuyển trên j1 kênh đầu tiên với chi phí là s(ik,j1), vậy phương án này cho chi phí là c(k,j) + s(ik,j1), k = 0, 1, 2,...,i.

Ta có

s(i,j) = max { c(k,j) + s(ik,j1) | k = 0, 1, ..., i }

Để cài đặt, ta có thể có thể dùng 1 mảng 1 chiều p với m bước lặp. Tại bước lặp thứ j ta có p[i] = s(i,j) là chi phí thấp nhất khi chuyển hết i gói tin trên mạng với j kênh đầu tiên. Vậy

p[i] = max { c(k,j) + p[ik] | k = i, i1,...,0 }; i = n..1

Chú ý rằng để khỏi ghi đè lên giá trị còn phải dùng để xử lý bước sau, với mỗi kênh j ta cần duyệt i theo chiều ngược từ n đến 1.

Điểm khó là phải giải trình cụ thể phương án chuyển tin tối ưu, nghĩa là cho biết phải chuyển theo mỗi kênh bao nhiêu gói tin. Ta sẽ sử dụng một mảng 2 chiều SoGoi, trong đó phần tử SoGoi[i][j] cho biết trong phương án tối ưu chuyển i gói tin theo j kênh đầu tiên thì riêng kênh j sẽ được phân phối bao nhiêu gói tin. Trước khi ghi kết quả ta tính ngược từ kênh m đến kênh 1 số gói tin cần chuyển theo mỗi kênh.

Độ phức tạp

Thủ tục XuLi tính m.n lần, mỗi lần lại tính tối đa m phần tử, vậy độ phức tạp là O(nm²).

Chương trình
(* messages.pas *)

const fn = 'messages.inp'; gn = 'messages.out';

mn = 101; bl = #32; nl = #13#10;

type mi1 = array[0..mn] of integer;

mi2 = array[0..mn] of mi1;

var f,g: text;

c,sogoi: mi2; { c - ma tran chi phi }

{ sogoi[i,j] - so goi tin chuyen theo kenh j }

p: mi1;

n,m: integer; { n - tong so goi tin; m - so kenh }

procedure Ghi;

var i,j: integer;

begin

assign(g,gn); rewrite(g); writeln(g,p[n]);

i := n;

for j := m downto 1 do

begin

p[j] := SoGoi[i,j]; { so goi chuyen theo kenh j }

i := i - SoGoi[i,j]; { so goi con lai }

end;

for i := 1 to m do writeln(g,p[i]);

close(g);

end;

{ Chi phi chuyen het i goi tin

theo j kenh dau tien: 1, 2, ... j }

procedure Tinhp(i,j: integer);

var k: integer;

begin

SoGoi[i,j] := 0;

for k := 1 to i do { thu chuyen k goi theo kenh j }

if (p[i] > p[i-k] + c[k][j]) then

begin

p[i] := p[i-k] + c[k][j]; { cap nhat tri min }

SoGoi[i,j] := k; { chuyen k goi theo kenh j }

end;

end;

procedure XuLi;

var i, j, k: integer;

begin

fillchar(SoGoi,sizeof(SoGoi),0);

{ Khoi tri cho kenh 1 }

{ i goi tin chi chuyen tren kenh 1 voi chi phi c[i][1] }

for i := 1 to n do

begin p[i] := c[i,1]; SoGoi[i,1] := i; end;

for j := 2 to m-1 do { xet kenh j }

for i := n downto 1 do

Tinhp(i,j); { chi phi chuyen i goi tin theo j kenh dau tien }

{ Xu li buoc cuoi, kenh m }

SoGoi[n,m] := 0;

for k := 1 to n do

if (p[n] > p[n-k] + c[k][m]) then

begin

SoGoi[n,m] := k;

p[n] := p[n-k] + c[k][m];

end;

end;

procedure Print;

var i,j: integer;

begin

writeln(nl, n, bl, m);

for i := 1 to n do

begin writeln;

for j := 1 to m do write(c[i,j],bl);

end;

end;

procedure Doc;

var i,j: integer;

begin

assign(f,fn); reset(f);

readln(f, n, m);

for i := 1 to n do

for j := 1 to m do

read(f,c[i,j]);

close(f);

end;

BEGIN

Doc; Print;

XuLi; Ghi;

writeln(nl,' Fini ');

readln;

END.
// DevC++ messages.cpp

#include

#include

#include

#include

using namespace std;

// D A T A A N D V A R I A B L E

const char * fn = "messages.inp";

const char * gn = "messages.out";

const int mn = 101;

int c[mn][mn]; // ma tran chi phi

int SoGoi[mn][mn];//SoGoi[i][j]-so goi tin chuyen theo kenh j

int n, m;

int p[mn];

// P R O T O T Y P E S

void Doc();

void Print();

void XuLi();

void Tinhp(int, int);

void Ghi();

// I M P L E M E N T A T I O N

int main() {

Doc(); Print();

XuLi(); Ghi();

cout << endl; system("PAUSE");

return EXIT_SUCCESS;

}

void Ghi(){

ofstream g(gn);

g << p[n]; // chi phi min

int i = n, j;

for (j = m; j > 0; --j) {

p[j] = SoGoi[i][j];

i = i - SoGoi[i][j];// so goi con lai

}

for (i = 1; i <= m; ++i) g << endl << p[i];

g.close();

}

// Chi phi chuyen het i goi tin

// theo j kenh dau tien: 1, 2, ... j

void Tinhp(int i, int j) {

int k;

SoGoi[i][j] = 0;

for (k = 1; k <= i; ++k) // thu chuyen k goi theo kenh j

if (p[i] > p[i-k] + c[k][j]) {

p[i] = p[i-k] + c[k][j]; // cap nhat tri min

SoGoi[i][j] = k; // so goi can chuyen theo kenh j

}

}

void XuLi(){

int i, j, k;

memset(SoGoi, 0,sizeof(SoGoi));

// Khoi tri cho kenh 1

// i goi tin chi chuyen tren kenh 1 voi chi phi c[i][1]

p[0] = 0; // chuyen 0 goi tin tren kenh 1

for (i = 1; i <= n; ++i) {

p[i] = c[i][1]; SoGoi[i][1] = i;

}

for (j = 2; j < m; ++j) // xet kenh j = 2..m-1

for (i = n; i > 0; --i) // chuyen i goi tin tren kenh j

Tinhp(i,j);

// Xu li buoc cuoi, kenh m

SoGoi[n][m] = 0;

for (k = 1; k <= n; ++k) // thu chuyen k goi theo kenh m

if (p[n] > p[n-k] + c[k][m]) {

p[n] = p[n-k] + c[k][m];

SoGoi[n][m] = k;

}

}

void Print(){

int i,j;

cout << endl << n << " goi tin, " << m << " kenh";

for (i = 1; i <= n; ++i) {

cout << endl;

for (j = 1; j <= m; ++j)

cout << " " << c[i][j];

}

}

void Doc(){

ifstream f(fn);

memset(c,0,sizeof(c));

f >> n >> m; // n goi tin, m kenh

int i,j;

for (i = 1; i <= n; ++i)

for (j = 1; j <= m; ++j)

f >> c[i][j];

f.close();

}

5.7 Mã BW

Olimpic Quốc tế (Bài dự tuyển)

Mã BW do Michael Burrows and David Wheeler đề xuất dùng để mã hóa xâu kí tự s thành cặp (u,d) như sau.

1. Quay xâu s qua trái mỗi lần 1 vị trí để thu được n xâu tính cả bản thân xâu s,

2. Sắp tăng các xâu thu được theo trật tự từ điển,

3. Lấy các kí cuối của các xâu được sắp ghép thành từ u,

4. Xác định d là vị trí xuất hiện của xâu s trong dãy được sắp.

Thí dụ, với s = "panama" ta có kết quả tại các bước như sau:

1. Sinh các xâu theo cách quay: "panama", "anamap", "namapa", "amapan", "mapana", "apanam".

2. Sắp các xâu: "amapan", "anamap", "apanam", "mapana", "namapa","panama".

3. u = "npmaaa",

4. d = 6.

Kết quả: "panama" được mã BW thành: ("npmaaa", 6).

Cho s, hãy tính (u,d) và biết (u,d), hãy xác định s. Chiều dài tối đa của s là 200.

Thuật toán

Ta gọi BW là thuật toán mã hóa và WB là thuật toán giải mã. Như vậy, với thí dụ đã cho ta có,

BW("panama") = ("npmaaa",6) và WB("npmaaa",6) = "panama".

Bài toán xuôi BW chỉ có một điểm khó là sinh ra n xâu, tính cả xâu nguồn và sắp tăng các xâu đó. Với xâu nguồn s có chiều dài tối đa là 200 thì sẽ đòi hỏi miền nhớ 40000 byte để có thể lưu trữ các xâu. Ta sẽ triển khai thuật toán với chỉ 1 xâu nguồn s duy nhất. Giả sử chiều dài của xâu s là n. Với mỗi i = 1..n ta kí hiệu [i] là "xâu vòng" bắt đầu tính từ kí tự s[i] đến hết xâu, tức là đến kí tự s[n] rồi lại tính tiếp đến s[1] và kết thúc tại s[i1]. Tóm lại, xâu vòng [i] là xâu sinh ra khi ta duyệt xâu nguồn s theo vòng tròn kể từ vị trí i qua phải. Mỗi xâu dài n sẽ có đúng n xâu vòng và mỗi xâu vòng có đúng n kí tự. Thí dụ, với s[1..6] = "panama" thì [2] = "anamap" là một xâu vòng. Ta dễ dàng sắp xếp các xâu vòng và ghi nhận trật tự trong một mảng chỉ dẫn id. Với xâu đã cho, sau khi sắp tăng theo chỉ dẫn ta thu được:

id[1] = 4 – xâu vòng [4] = "amapan" đứng đầu tiên trong dãy sắp tăng,

id[2] = 2  xâu vòng [2] = "anamap" đứng thứ hai trong dãy sắp tăng,

id[3] = 6  xâu vòng [6] = "apanam" đứng thứ ba trong dãy sắp tăng,

id[4] = 5  xâu vòng [5] = "mapana" đứng thứ tư trong dãy sắp tăng.

id[5] = 3  xâu vòng [3] = "namapa" đứng thứ năm trong dãy sắp tăng.

id[6] = 1  xâu vòng [1] = "panama" đứng cuối cùng, thứ sáu, trong dãy sắp tăng.

Dễ thầy, nếu [i] là xâu vòng thì kí tự cuối của xâu này sẽ là kí tự sát trái kí tự thứ i trong s, cụ thể là s[(i+(n1)) % n] nếu s biểu diễn trong C++ với chỉ số tính từ 0 và là s[(i1+(n1)) mod n + 1] nếu s biểu diễn trong Pascal với chỉ số tính từ 1.

Khi sắp xếp ta gọi hàm Sanh(s,i,j) để so sánh hai xâu vòng [i] và [j] của s. Hàm cho ra giá trị 0 nếu hai xâu bằng nhau, và 1 nếu xâu vòng [i] lớn hơn xâu vòng [j], 1 nếu xâu vòng [i] nhỏ thua xâu vòng [j].

Hoạt động của hàm Sanh 2 xâu vòng [i] và [j]

1. Duyệt n lần các phần tử s[i] và s[j] theo vòng tròn.

Xét:

- Nếu s[i] > s[j]: return 1;

- Nếu s[i] < s[j]: return -1;

2. return 0;

3. end.

Bài toán ngược, WB khôi phục xâu nguồn s từ xâu mã u và giá trị d được triển khai như sau. Trước hết ta để ý rằng xâu u là một hoán vị của các kí tự trong xâu s. Cũng do các xâu vòng được sắp tăng nên sau khi gọi hàm BS để sắp tăng xâu u theo chỉ dẫn id ta dễ dàng tính được xâu s như sau. Ta coi u như là cột chứa các kí tự cuối cùng của các xâu vòng trong dãy được sắp và u' là xâu sắp tăng của xâu u. Do dãy các xâu vòng được sắp tăng nên cột đầu tiên của dãy các xâu này cũng phải được sắp tăng. Vậy cột đó chính là u'. Xét kí tự u[i]. Đây là kí tự cuối của một xâu vòng v nào đó trong dãy được sắp. Vậy trước khi quay, xâu v sẽ nhận u[i] làm kí tự đầu tiên, nghĩa là kí tự u[i] sẽ thuộc và là kí tự j nào đó trong xâu được sắp u', ta có u[i] = u'[j], hay là i được đặt tương ứng với j. Nhờ tương ứng này ta có thể khôi phục xâu s Kí tự này thuộc cả xâu u'. Nếu kí tự cuối trong dãy này là u[j] thi trước khi quay trái một vị trí, kí tự u[j] phải nằm trong cột đầu tiên được sắp.

(* Pascal *)

procedure WB(var u: string; d: integer; var s: string);

var i: integer;

begin

n := length(u);

BS(u); { sắp tẵng xâu u theo chỉ dẫn }

s := ''; d := id[d];

for i := 1 to n do

begin

s := s + u[d]; d := id[d];

end;

end;
// DevC++

void WB(char *u, int d, char * s) { // (u,d) ==> v

n = int(strlen(u));

BS(u); // sắp tẵng xâu u theo chỉ dẫn

int i;

d = id[d-1];

for (i = 0; i < n; ++i) {

s[i] = u[d]; d = id[d];

}

s[n] = '\0';

}

Bạn phải chọn phương thức sắp xếp không xáo trộn các phần tử bằng nhau mà chỉ tịnh tiến các phần tử đó. Các phương pháp sắp xếp như quick sort, min sort đều vi phạm tiêu chí này. Chương trình dưới đây sử dụng phương pháp sắp nổi bọt (bubble sort).

(* BW.PAS *)

uses crt;

const bl = #32; nl = #13#10;

var

n: integer;

id: array[0..256] of integer;

procedure iswap(i, j: integer);

var t: integer;

begin

t := id[i]; id[i] := id[j]; id[j] := t;

end;

function Sanh(var s: string; i,j: integer): integer;

var k: integer;

begin

for k := 1 to n do

begin

if s[i] <> s[j] then

begin

if s[i] < s[j] then Sanh := -1 else Sanh := 1;

exit;

end;

i := (i mod n) + 1;

j := (j mod n) + 1;

end;

Sanh := 0;

end;

// sap tang cac xau vong cua s theo chi dan

procedure BubbleSort(var s: string);

var i,j: integer;

begin

for i := 1 to n do id[i] := i;

for i := 1 to n-1 do

for j := n downto i+1 do

if Sanh(s,id[j],id[j-1]) < 0 then iswap(j,j-1);

end;

procedure BW(var s: string; var u: string; var d: integer);

var i: integer;

begin

n := length(s);

BubbleSort(s);

u := '';

for i := 1 to n do

begin

u := u + s[(id[i]-1+n-1) mod n + 1];

if id[i] = 1 then d := i;

end;

end;

procedure BS(var u: string);

var i,j: integer;

begin

for i := 1 to n do id[i] := i;

for i := 1 to n-1 do

for j := n downto i+1 do

if u[id[j]] < u[id[j-1]] then iswap(j,j-1);

end;

procedure WB(var u: string; d: integer; var s: string);

var i: integer;

begin

n := length(u);

BS(u);

s := ''; d := id[d];

for i := 1 to n do

begin

s := s + u[d]; d := id[d];

end;

end;

procedure Test;

var s, u, v: string;

d: integer;

begin

s := 'panama';

BW(s,u,d);

writeln(s,' => (',u,',',d,')');

WB(u,d,v);

writeln('(',u,',',d,') => ',v);

end;

BEGIN

Test;

readln;

END.
// DevC++: Bw.cpp

#include

using namespace std;

// D A T A A N D V A R I A B L E

const char * fn = "bw.inp";

const char * gn = "bw.out";

const int mn = 256;

char s[mn];

char u[mn];

char v[mn];

int id[mn];

int n,d; // n = len(s); d: vi tri cua s trong day duoc sap

// P R O T O T Y P E S

// BW(s) = (u,d)

// WB(u,d) = v ( = x)

void BW(char * s, char * u, int & d);

void WB(char * u, int d, char * s);

int Sanh(char * s, int i, int j);

void BubbleSort(char * s);

void BS(char * u); // BubbleSort tren u

void iswap(int i , int j ); // doi cho id[i], id[j]

// I M P L E M E N T A T I O N

int main() {

strcpy(s,"panama");

BW(s,u,d);

cout << endl << "BW(" << s << ") = (" << u

<< ", " << d << ")" << endl;

WB(u,d,v);

cout << endl << "WB(" << u << ", " << d << ") = " << v;

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

void BW(char * s, char * u, int & d) { // s ==> (u,d)

n = int(strlen(s));

BubbleSort(s);

for (int i = 0; i < n; ++i) {

u[i] = s[(id[i] + n - 1) % n];

if (id[i] == 0) d = i+1;

}

u[n] = '\0';

}

void BubbleSort(char * s){

// sap tang cac xau vong cua s theo chi dan

int i,j, n1 = n - 1;

for (i = 0; i < n; ++i) id[i] = i;

for (i = 0; i < n1; ++i) {

for (j = n1; j > i; --j)

if (Sanh(s,id[j],id[j-1]) < 0) iswap(j,j-1);

}

}

int Sanh(char * s, int i, int j) { // sanh 2 xau vong [i] va [j]

int k;

for (k = 0; k < n; ++k, i = (i+1)%n, j = (j+1)%n)

if (s[i] != s[j]) return (s[i] > s[j]) ? 1 : -1;

return 0;

}

void iswap(int i, int j) { int t = id[i]; id[i]= id[j]; id[j] = t; }

void WB(char *u, int d, char * s) { // (u,d) ==> v

n = int(strlen(u));

BS(u);

int i;

d = id[d-1];

for (i = 0; i < n; ++i) {

s[i] = u[d]; d = id[d];

}

s[n] = '\0';

}

void BS(char *u){ // sap tang xau u theo chi dan

int i,j,n1 = n-1;

for (i = 0; i < n; ++i) id[i] = i;

for (i = 0; i < n1 ; ++i) {

for (j = n1; j > i; --j)

if (u[id[j]] < u[id[j-1]]) iswap(j,j-1);

}

}

5.8 Tam giác Pascal

Tam giác Pascal bậc n là một bảng gồm n dòng, dòng thứ i là một dãy gồm i+1 số tự nhiên được xây dựng như sau.

Dòng i = 1 chứa hai số 1, 1.

Gọi x = (x₁, x₂, ..., x_i+1) là dòng thứ i, thì dòng thứ i+1, y = (y₁, y₂, ..., y_i+2) được xây dựng như sau:

y₁ = y_i+2 = 1,

y_j = x_j-1+x_j , j = 2, 3, ..., i+1.

Các phần tử của dãy được gọi là hệ số. Hai phần tử đầu và cuối của mỗi dãy luôn luôn mang giá trị 1 và được gọi là hai hệ số ngoài. Các phần tử còn lại được gọi là các hệ số trong.

Blaise Pascal

Nhà vật lý học, toán học và triết gia người Pháp. Ông được tiếp thu nền giáo dục từ người cha. Ngay từ thời trẻ Pascal đã nổi tiếng là thần đồng. Các tác phẩm đầu tiên của Pascal là về tự nhiên và các khoa học ứng dụng, nơi ông đã có những đóng góp quan trọng vào việc xây dựng một máy tính cơ khí, các nghiên cứu về chất lỏng, trình bày các khái niệm về áp suất và chân không bằng việc khái quát tác phẩm của Evangelista Torricelli.

Pascal là một trong những người đặt nền móng cho hai lĩnh vực nghiên cứu mới của toán học. Ông đã viết một luận án quan trọng về hình học xạ ảnh ở độ tuổi 16. Cùng với Pierre de Fermat xây dựng lý thuyết xác suất. Đây là công trình có ảnh hưởng lớn tới sự phát triển của kinh tế học hiện đại và các khoa học xã hội.

Sau đó ông dành tâm sức vào triết học và thần học với hai tác phẩm nổi tiếng trong thời kỳ đó.

Nguồn: Wikipedia

Blaise Pascal

19/6/1623-19/8/1662

Tam giác Pascal (PT – Pascal's Triangle ) có nhiều ứng dụng nổi tiếng. Dòng thứ n trong PT chính là các hệ số trong dạng khai triển của đa thức (a+b)ⁿ. Định lý sau đây cho ta một dấu hiệu nhận biết số nguyên tố dựa trên PT.

Định lý: n là số nguyên tố khi và chỉ khi mọi hệ số trong của dòng n trong tam giác Pascal chia hết cho n.

Chúng ta thử giải hai bài toán sau đây liên quan đến tam giác Pascal.

PT1: Với mỗi số tự nhiên n hãy tính các hệ số của tam giác Pascal và tổng của chúng.

PT2: Kí hiệu a(i,n) là hệ số thứ i trên dòng thứ n của m giác Pascal. Hãy tính tổng

(n) = sum { a(i, i/2+1) | i = 1..n } = a(1,1) + a(2,2) + a(3,2)+ ... + a(i, i/2+1) + ... + a(n, n/2+1)

trong dó x/y cho ta phần nguyên của thương trong phép chia số tự nhiên x cho số tự nhiên y. Giới hạn của n là 1  n  20.

Thí dụ, với n = 6 ta có

PT1: Dòng 6 của tam giác Pascal: (1, 6, 15, 20, 15, 1); Tổng là: 64.

PT2: (6) = 1 + 2 + 3 + 6 + 10 + 20 = 42 (các số gạch dưới trong bảng).

n

Ứng dụng

1

2

3

4

5

6 1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

. . .

Dòng 4:

(a+b)⁴=1a⁴+4a³b+6a²b²+4ab³+1b⁴.

Dòng 5: Mọi hệ số trong chia hết cho 5, vậy n = 5 nguyên tố.

Dòng 6: Hệ số 15 không chia hết cho 6, vậy 6 không phải nguyên tố.

Thuật toán

Hệ số thứ i trên dòng n, p(n, i) của PT chính là tổ hợp chặp i1 của n phần tử do đó được tính theo công thức:

p(n,i) = C_n ⁱ^¹ = n!/(i1)!(ni+1)! = (ni+2)...n/(i1)!, i = 1.. n+1.

Ta qui ước 0! = 1, do đó

p(n, 1) = p(n, n+1) = C_n⁰ = C_nⁿ = 1

Biết p(n, i) ta tính được p(n, i+1) theo công thức sau:

p(n, i+1) = p(n, i).(ni+1)/i (*)

Ta khởi trị a[1] = 1 ứng với p(n, 1). Ngoài ra ta sử dụng hai biến phụ tu và mau với giá trị khởi đầu là tu = n, mau = 1. Sau đó, với mỗi i = 2..n+1 ta tính p(n, i) = a[i] = a[i-1]*tu/mau và giảm tu, tăng mau 1 đơn vị.

Thủ tục PT dưới đây tính và hiển thị dòng thứ n trong tam giác Pascal:

(* Passcal *)

procedure PT(n: integer);

var x: longint;

i, tu, mau: integer;

begin

x := 1; tu := n; mau := 1;

for i := 2 to n+1 do

begin

write(x,bl); { bl là dấu cách, bl = #32 }

x := (x * tu) div mau;

dec(tu); inc(mau);

end;

write(1);

end;
// DevC++

void PT(int n) {

int x = 1;

int i, n1 = n+1, tu = n, mau = 1;

for (i = 2 ; i <= n1; ++i, --tu, ++mau) {

cout << x << " ";

x = x*tu/mau;

}

cout << 1;

}

Để tính tổng các hệ số trên dòng thứ n của PT, T(n), ta xét dạng khai triển của đa thức (a+b)ⁿ:

(a+b)ⁿ = p(n, 1)aⁿ + p(n, 2)a^n-1b + ... + p(n, i)a^n-i+1b^i-1 + ... + p(n, n+1)bⁿ

Thay a = b = 1 vào biểu thức trên ta thu được:

T(n) = (1+1)ⁿ = 2ⁿ = p(n, 1) + p(n, 2) + ... + p(n, i) + ... + p(n, n+1)

Vậy T(n) = 2ⁿ. Do các số nguyên trong máy tính được biểu diễn dưới dạng nhị phân nên hàm T(n) nhận giá trị là số 1 dịch qua trái n bit:

(* Passcal *)

function T(n: integer): longint;

begin T := longint(1) shl n; end;
// DevCPP

int T(int n) { return (1 << n); }

Để tính hàm (n) trước hết ta cần tính được p(i, j) với i = 1..n và j = i/2 + 1. Ta gọi x là giá trị của p(i,i/2+1) tính được tại bước i. Ta có nhận xét sau đây:

Khi i = 1 ta có x = p(1,1) = 1;
Nếu i là số chẵn thì giá trị của x được tăng gấp đôi: x = 2 *x.
Nếu i là số lẻ thì x = x + x', trong đó x là giá trị tính được ở bước sát trước, bước i1, x = p(i1,v), v = (i1)/2; x' là giá trị sát sau x tại bước i1, x' = p(i1, v+1). Sử dụng công thức (*) ta dễ dàng tính được x' từ x. Khi cài đặt ta sử dụng biến v để ghi nhận chỉ số của hệ số cần tính tại bước i. v được khởi trị 1, sau đó tăng thêm 1 nếu gặp dòng chẵn. Ta cũng sử dụng biến bool even để xác định dòng chẵn.

Thủ tục Test trong các chương trình dưới đây tính đồng thời với mỗi giá trị n = 1..20 các đại lượng sau đây:

Dòng thứ n trong tam giác Pascal và tổng các hệ số trên dòng;
Hàm .

Để kết thúc chương trình bạn hãy bấm dấu chấm (.).

Độ phức tạp: O(n) cho cả hai thủ tục PT và Alpha.

Chương trình

(* Triangle.pas *)

uses crt;

const bl = #32; nl = #13#10;

procedure PT(n: integer);

var x: longint;

i, tu, mau: integer;

begin

x := 1; tu := n; mau := 1;

for i := 2 to n+1 do

begin

write(x,bl);

x := (x * tu) div mau;

dec(tu); inc(mau);

end;

write(1);

end;

function Alpha(n: integer): longint;

var x, sum, i, v: integer;

even: Boolean;

begin

x := 1; sum := 1; even := false; v := 1;

for i := 2 to n do

begin

even := not even;

if (even) then

begin

inc(v); x := x * 2;

end

else x := x + x * (i-v) div v;

sum := sum + x;

end;

Alpha := sum;

end;

procedure Test;

var n: integer;

begin

for n := 1 to 20 do

begin

writeln(nl, ' n = ',n);

write(' a = '); PT(n);

writeln(nl, ' Tong = ', longint(1) shl n);

writeln(' Alpha = ',Alpha(n));

write(nl,' Bam . de ket thuc: ');

if readkey = '.' then exit;

end;

end;

BEGIN

Test;

END.
// DevC++: Triangle.cpp

#include

using namespace std;

// P R O T O T Y P E S

void PT(int);

int Alpha(int );

void Test();

// I M P L E M E N T A T I O N

int main() {

Test();

return 0;

}

void Test(){

int n;

for (n = 1; n <= 20; ++n) {

cout << endl << " n = " << n << ":";

cout << endl << "a = "; PT(n);

cout << endl << " Tong = " << (1 << n);

cout << endl << " Alpha = " << Alpha(n) << " ";

cout << endl << endl << " Bam . de ket thuc: ";

if (cin.get() == '.') return;

}

}

// p(i, v+1) = p(i, v).(i-v+1)/v, v = i/2 + 1

int Alpha(int n) {

int sum = 1, x = 1, v = 1, i;

bool even = false;

for (i = 2 ; i <= n; ++i) {

even = !even;

if (even) { // i chan

v++; x *= 2;

} else x += x*(i-v)/v;

sum += x;

}

return sum;

}

void PT(int n) {

int x = 1;

int i, n1 = n+1, tu = n, mau = 1;

for (i = 2 ; i <= n1; ++i, --tu, ++mau) {

cout << x << " ";

x = x*tu/mau;

}

cout << 1;

}

5.9 Sơn mô hình

Moscow

Bạn Minh làm một mô hình như sau: Trên một tấm bảng nhựa hình chữ nhật chia lưới kích thước n  m đơn vị Minh dùng keo gắn tại một số ô của bảng một cột gỗ vuông cạnh đáy 1 đơn vị, chiều cao là một số nguyên. Các cột gỗ kề nhau cũng được gắn keo giữa hai mặt tiếp giáp. Sau đó Minh sơn các mặt gỗ tiếp xúc với không khí. Tính diện tích cần sơn.

son.inp	son.out	Giải thích file son.inp: dòng đầu tiên: 2 số nguyên dương n và m. Phần tử thứ j trên dòng i trong số n dòng tiếp theo là chiều cao của cột đặt tại ô (i, j). file son.out: diện tích cần sơn.
2 3 1 2 0 5 4 5	49

Thuật toán

Bài này khá dễ nhưng hầu hết các bạn đều qnuên sơn mặt trên. Với mỗi cột ta tính diện tích cần sơn trên 4 mặt cột đó nếu tại mặt đó phần tường cao hơn cột bên cạnh. Ta viết hàm Hieu(x,y) cho ra hiệu xy nếu x > y, ngược lại hàm cho ra giá trị 0. Như vậy hàm này cho ra diện tích cần sơn trên phần lộ của bức tường cao x và bức tường cao y kề nó (x > y). Sau đó, nếu ô nào có cột (độ cao lớn hơn 0) bạn nhớ cộng thêm diện tích sơn mái là 1 đơn vị. Khi đọc dữ liệu vào mảng bạn nên điền các ô viền phia ngoài bảng giá trị 0.

Độ phức tạp: O(n.m) vì ta duyệt mỗi ô 1 lần.

Chương trình
(* son.pas *)

uses crt;

const mn = 101; bl = #32; nl = #13#10;

fn = 'son.inp'; gn = 'son.out';

var n, m: integer;

a: array[0..mn,0..mn] of integer;

procedure Doc;

var i,j: integer;

f: text;

begin

assign(f,fn); reset(f);

readln(f, n, m);

fillchar(a, sizeof(a), 0);

for i := 1 to n do

for j := 1 to m do

read(f,a[i,j]);

close(f);

end;

procedure Ghi(d: longint);

var g: text;

begin

assign(g,gn); rewrite(g);

writeln(g,d); close(g);

end;

procedure Print;

var i,j: integer;

begin

writeln(nl,n, bl, m);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j], bl);

writeln;

end;

end;

function Hieu(x, y: integer): integer;

begin

if x > y then Hieu := x - y else Hieu := 0;

end;

function Son: longint;

var d: longint;

i, j: integer;

begin

d := 0;

for i := 1 to n do

for j := 1 to m do

begin

d := d + Hieu(a[i,j], a[i+1,j]) + Hieu(a[i,j], a[i-1,j]) +

Hieu(a[i,j], a[i,j+1]) + Hieu(a[i,j], a[i,j-1]);

if a[i,j] > 0 then inc(d);

end;

Son := d;

end;

BEGIN

Doc; Print; Ghi(Son);

readln;

END.
// DevC++: son.cpp

#include

#include

using namespace std;

// D A T A A N D V A R I A B L E S

const char * fn = "son.inp";

const char * gn = "son.out";

const int mn = 102;

int a[mn][mn];

int n,m;

// P R O T O T Y P E S

void Doc();

int Son();

int Hieu(int, int);

void Print(); // xem du lieu

void Ghi(int);

// I M P L E M E N T A T I O N

int main() {

Doc(); Ghi(Son());

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

void Print() { // Hiển thị bảng a

int i,j;

cout << endl << " n = " << n << " m = " << m;

for (i = 0; i <= n+1; ++i) {

cout << endl;

for (j = 0; j <= m+1; ++j)

cout << a[i][j] << " ";

}

}

void Doc() {

memset(a,0,sizeof(a));

ifstream f(fn);

f >> n >> m;

int i,j;

for (i = 1; i <= n; ++i)

for (j = 1; j <= m; ++j)

f >> a[i][j];

f.close();

Print();

}

void Ghi(int d) {

ofstream g(gn);

g << d;

g.close();

}

int Son() {

int i,j, d = 0; // d: dien tich can son

for (i = 1; i <= n; ++i)

for (j = 1; j <= m;++j) {

d += Hieu(a[i][j],a[i][j+1])+Hieu(a[i][j],a[i][j-1])

+ Hieu(a[i][j],a[i-1][j]) + Hieu(a[i][j],a[i+1][j]);

if (a[i][j] > 0) ++d;

}

return d;

}

int Hieu(int x, int y) { return (x > y) ? (x - y) : 0; }

5.10 Nhúng mô hình

Bạn Minh làm một mô hình như sau: Trên một tấm bảng nhựa hình chữ nhật chia lưới kích thước n  m đơn vị Minh dùng keo gắn tại một số ô của bảng một cột nhựa vuông cạnh đáy 1 đơn vị, chiều cao là một số nguyên. Các cột kề nhau cũng được gắn keo giữa hai mặt và hai cạnh tiếp giáp. Sau đó Minh nhúng mô hình ngập vào nước rồi cẩn thận nhấc lên. Tính thể tích của khối nước đọng trong mô hình.

model.inp	model.out	Giải thích file model.inp: dòng đầu tiên: 2 số nguyên dương n và m. Phần tử thứ j trên dòng i trong số n dòng tiếp theo là chiều cao của cột đặt tại ô (i, j). file model.out: thể tích nước đọng trong mô hình.
4 5 5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5	8

Thuật toán

Gọi a là tấm bảng nền mô hình với kích thước nm và a(i,j) là chiều cao của cột nhựa vuông đặt trên ô (i,j). Thoạt tiên ta giả sử chiều cao tối đa của các cột là 1, như vậy các ô trên nền nhà chỉ chứa các giá trị 0 hoặc 1.

Nền tầng 1 với các ô đặc mang giá trị 1, ô chứa nước đọng màu trắng (0) và ô thoát nước màu xám (0).

Có 5 ô trắng bị giam nên thể tích nước đọng sẽ là 5.

0

ô thoát nước

0

ô nước đọng

1

ô đặc

Các ô liên thông với ô trống trên biên sẽ tạo thành nột cống thoát nước ra ngoài mô hình.

Ô mang giá trị 0 chính là mặt sàn, còn ô mang giá trị 1 chính là cột. Bây giờ bạn thử rót nước vào mô hình đơn giản này cho ngập các ô và quan sát điều gì sẽ xảy ra. Dễ thấy là chỉ có các ô trống bị giam tại giữa mô hình là còn chứa nước. Có 5 ô trống bị giam nên thể tích nước đọng sẽ là 5. Các ô trống (mang giá trị 0) liên thông cạnh với một ô trống trên biên sẽ tạo thành một cống thoát nưởc ra ngoài mô hình. Nhận xét này cho ta thuật toán tính lượng nước đọng tại tầng nền (tầng 0) của mô hình như sau:

Duỵệt đường biên, nếu gặp ô trống (trên biên và chứa trị 0) thì gọi thủ tục loang đánh dấu các ô này bằng giá trị 1.

Duyệt các ô lọt trong mô hình, đếm các ô trống (chứa giá trị 0) và đồng thời đánh dấu các ô này bằng giá trị 1. Đó là thể tich nước đọng.

Tiếp theo, sau khi đã duyệt và tính lượng nước đọng tại tầng nền (tầng 0), bạn dễ dàng suy ra cách tính lượng nước đọng tại tầng 1 nếu như coi các ô trống đã duyệt tại tầng 0 đã được lấp bằng các khối nhựa chiều cao 1. Ta gọi phương thức này là đóng băng các ô đã xử lí. Tổng quát, tại tầng h ta thực hiện thủ tục tương tự như tại tầng nền với chút điều chỉnh là thay giá trị đánh dấu bằng h+1 thay vì bằng 1. Gọi chiều cao tối đa của các cột là hmax, cho h biến thiên từ 0 đến hmax1 ta tính được tổng khối nước đọng của mô hình.

Để thực hiên thuật toán loang bạn nhớ khởi trị mọi ô của nền nhà là 1.

Thủ tục Loang(i,j,h)

1. Xét trị của ô (i,j):

Nếu a(i,j) = h thì

1.1 Thay a(i,j) bằng h+1;

1.2 Loang tiếp sang 4 ô kề: (i,j+1), (i,j-1), (i+1,j) và (i-1,j)

2. end.

Độ phức tạp

Mỗi tầng ta duyệt n.m ô vậy tổng số ô phải duyệt vào cỡ hmax.n.m.

Chương trình
(* Model.Pas *)

uses crt;

const mn = 101; bl = #32; nl = #13#10;

fn = 'model.inp'; gn ='model.out';

var

n, m: integer;

a: array[0..mn, 0..mn] of integer;

hmax: integer;

procedure Doc;

var f: text;

i,j: integer;

begin

assign(f,fn); reset(f);

fillchar(a,sizeof(a),255); // gan -1

readln(f,n,m); hmax := 0;

for i := 1 to n do

for j := 1 to m do

begin

read(f,a[i,j]);

if hmax < a[i,j] then hmax := a[i,j];

end;

close(f);

end;

procedure Ghi(v: integer);

var g: text;

begin

assign(g,gn); rewrite(g);

writeln(g,v); close(g);

end;

procedure Loang(i,j,h: integer);

begin

if a[i,j] <> h then exit;

a[i,j] := h+1;

Loang(i+1,j,h); Loang(i-1,j,h);

Loang(i,j+1,h); Loang(i,j-1,h);

end;

function Tang(h: integer): longint;

var i, j: integer;

v: longint;

begin

for i := 1 to n do { canh trai, phai }

begin

Loang(i,1,h); Loang(i,m,h);

end;

for j := 2 to m-1 do { canh tren, duoi }

begin

Loang(1,j,h); Loang(n,j,h);

end;

v := 0; { Duyet trong }

for i := 2 to n-1 do

for j := 2 to m-1 do

if a[i,j] = h then

begin

inc(v);

a[i,j] := h+1;

end;

Tang := v;

end;

function TheTich: longint;

var h: integer;

v: longint;

begin

v := 0;

for h := 0 to hmax-1 do v := v + Tang(h);

TheTich := v;

end;

BEGIN

Doc; Ghi(TheTich);

readln;

END.
// DevC++: Model.cpp

#include

#include

using namespace std;

// D A T A A N D V A R I A B L E S

const char * fn = "model.inp";

const char * gn = "model.out";

const int mn= 102;

int a[mn][mn];

int n,m;

int hmax;

// P R O T O T Y P E S

void Doc();

void Ghi(int);

int TheTich();

int Tang(int);

void Loang(int, int, int);

// I M P L E M E N T A T I O N

int main(){

Doc(); Ghi(TheTich());

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

void Doc(){

memset(a,0xff,sizeof(a));

ifstream f(fn);

f >> n >> m; hmax = 0;

int i,j;

for (i = 1; i <= n; ++i)

for (j = 1; j <= m; ++j){

f >> a[i][j];

if (a[i][j] > hmax) hmax = a[i][j];

}

f.close();

}

void Ghi(int v) {

ofstream g(gn);

g << v;

g.close();

}

void Loang(int i, int j, int h){

if (a[i][j] != h) return;

++a[i][j];

Loang(i,j+1,h);

Loang(i,j-1,h);

Loang(i+1,j,h);

Loang(i-1,j,h);

}

int Tang(int h){ // The tich nuoc bi giam tai tang h

// Loang ngoai

int i,j;

for (i = 1; i <= n; ++i){

Loang(i,1,h); // bien trai

Loang(i,m,h); // bien phai

}

for (j = 2; j < m; ++j){

Loang(1,j,h); // bien tren

Loang(n,j,h); // bien duoi

}

// Tong khoi nuoc bi giam ben trong

int v = 0;

for (i = 2; i < n; ++i)

for (j = 2; j < m; ++j)

if (a[i][j] == h) {

v++; ++a[i][j];

}

return v;

}

int TheTich(){

int h, v = 0; // v: The tich nuoc bi giam

for (h = 0; h < hmax; ++h)

v += Tang(h);

return v;

} // end

5.11 Số sát sau nhị phân

Каталог: tailieu
tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning
tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm
tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI
tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1
tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng
tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp
tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam

tải về 2.51 Mb.

Chia sẻ với bạn bè của bạn:

1 ... 13 14 15 16 17 18 19 20 21

TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH

5.6 Chuyển tin

5.7 Mã BW

5.8 Tam giác Pascal

Tam giác Pascal bậc n là một bảng gồm n dòng, dòng thứ i là một dãy gồm i+1 số tự nhiên được xây dựng như sau.

Dòng i = 1 chứa hai số 1, 1.

Gọi x = (x1, x2, ..., xi+1) là dòng thứ i, thì dòng thứ i+1, y = (y1, y2, ..., yi+2) được xây dựng như sau:

y1 = yi+2 = 1,

yj = xj-1+xj , j = 2, 3, ..., i+1.

Các phần tử của dãy được gọi là hệ số. Hai phần tử đầu và cuối của mỗi dãy luôn luôn mang giá trị 1 và được gọi là hai hệ số ngoài. Các phần tử còn lại được gọi là các hệ số trong.

Blaise Pascal

Sau đó ông dành tâm sức vào triết học và thần học với hai tác phẩm nổi tiếng trong thời kỳ đó.

Nguồn: Wikipedia

Blaise Pascal

Tam giác Pascal (PT – Pascal's Triangle ) có nhiều ứng dụng nổi tiếng. Dòng thứ n trong PT chính là các hệ số trong dạng khai triển của đa thức (a+b)n. Định lý sau đây cho ta một dấu hiệu nhận biết số nguyên tố dựa trên PT.

Chúng ta thử giải hai bài toán sau đây liên quan đến tam giác Pascal.

PT1: Với mỗi số tự nhiên n hãy tính các hệ số của tam giác Pascal và tổng của chúng.

PT2: Kí hiệu a(i,n) là hệ số thứ i trên dòng thứ n của m giác Pascal. Hãy tính tổng

(n) = sum { a(i, i/2+1) | i = 1..n } = a(1,1) + a(2,2) + a(3,2)+ ... + a(i, i/2+1) + ... + a(n, n/2+1)

trong dó x/y cho ta phần nguyên của thương trong phép chia số tự nhiên x cho số tự nhiên y. Giới hạn của n là 1  n  20.

Thí dụ, với n = 6 ta có

PT1: Dòng 6 của tam giác Pascal: (1, 6, 15, 20, 15, 1); Tổng là: 64.

PT2: (6) = 1 + 2 + 3 + 6 + 10 + 20 = 42 (các số gạch dưới trong bảng).

n

Ứng dụng

1

2

3

4

5

6

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

. . .

Dòng 4:

(a+b)4=1a4+4a3b+6a2b2+4ab3+1b4.

Dòng 5: Mọi hệ số trong chia hết cho 5, vậy n = 5 nguyên tố.

Dòng 6: Hệ số 15 không chia hết cho 6, vậy 6 không phải nguyên tố.

Hệ số thứ i trên dòng n, p(n, i) của PT chính là tổ hợp chặp i1 của n phần tử do đó được tính theo công thức:

p(n,i) = Cn i1 = n!/(i1)!(ni+1)! = (ni+2)...n/(i1)!, i = 1.. n+1.

Ta qui ước 0! = 1, do đó

p(n, 1) = p(n, n+1) = Cn0 = Cnn = 1

Biết p(n, i) ta tính được p(n, i+1) theo công thức sau:

p(n, i+1) = p(n, i).(ni+1)/i (*)

Ta khởi trị a[1] = 1 ứng với p(n, 1). Ngoài ra ta sử dụng hai biến phụ tu và mau với giá trị khởi đầu là tu = n, mau = 1. Sau đó, với mỗi i = 2..n+1 ta tính p(n, i) = a[i] = a[i-1]*tu/mau và giảm tu, tăng mau 1 đơn vị.

Thủ tục PT dưới đây tính và hiển thị dòng thứ n trong tam giác Pascal:

}

Để tính tổng các hệ số trên dòng thứ n của PT, T(n), ta xét dạng khai triển của đa thức (a+b)n:

(a+b)n = p(n, 1)an + p(n, 2)an-1b + ... + p(n, i)an-i+1bi-1 + ... + p(n, n+1)bn

Thay a = b = 1 vào biểu thức trên ta thu được:

T(n) = (1+1)n = 2n = p(n, 1) + p(n, 2) + ... + p(n, i) + ... + p(n, n+1)

Vậy T(n) = 2n. Do các số nguyên trong máy tính được biểu diễn dưới dạng nhị phân nên hàm T(n) nhận giá trị là số 1 dịch qua trái n bit:

Để tính hàm (n) trước hết ta cần tính được p(i, j) với i = 1..n và j = i/2 + 1. Ta gọi x là giá trị của p(i,i/2+1) tính được tại bước i. Ta có nhận xét sau đây:

Khi i = 1 ta có x = p(1,1) = 1;

Nếu i là số chẵn thì giá trị của x được tăng gấp đôi: x = 2 *x.

Thủ tục Test trong các chương trình dưới đây tính đồng thời với mỗi giá trị n = 1..20 các đại lượng sau đây:

Dòng thứ n trong tam giác Pascal và tổng các hệ số trên dòng;

Hàm .

Để kết thúc chương trình bạn hãy bấm dấu chấm (.).

Độ phức tạp: O(n) cho cả hai thủ tục PT và Alpha.

5.9 Sơn mô hình

5.10 Nhúng mô hình

5.11 Số sát sau nhị phân

Gọi x = (x₁, x₂, ..., x_i+1) là dòng thứ i, thì dòng thứ i+1, y = (y₁, y₂, ..., y_i+2) được xây dựng như sau:

y₁ = y_i+2 = 1,

y_j = x_j-1+x_j , j = 2, 3, ..., i+1.

Tam giác Pascal (PT – Pascal's Triangle ) có nhiều ứng dụng nổi tiếng. Dòng thứ n trong PT chính là các hệ số trong dạng khai triển của đa thức (a+b)ⁿ. Định lý sau đây cho ta một dấu hiệu nhận biết số nguyên tố dựa trên PT.

(a+b)⁴=1a⁴+4a³b+6a²b²+4ab³+1b⁴.

p(n,i) = C_n ⁱ^¹ = n!/(i1)!(ni+1)! = (ni+2)...n/(i1)!, i = 1.. n+1.

p(n, 1) = p(n, n+1) = C_n⁰ = C_nⁿ = 1

Để tính tổng các hệ số trên dòng thứ n của PT, T(n), ta xét dạng khai triển của đa thức (a+b)ⁿ:

(a+b)ⁿ = p(n, 1)aⁿ + p(n, 2)a^n-1b + ... + p(n, i)a^n-i+1b^i-1 + ... + p(n, n+1)bⁿ

T(n) = (1+1)ⁿ = 2ⁿ = p(n, 1) + p(n, 2) + ... + p(n, i) + ... + p(n, n+1)

Vậy T(n) = 2ⁿ. Do các số nguyên trong máy tính được biểu diễn dưới dạng nhị phân nên hàm T(n) nhận giá trị là số 1 dịch qua trái n bit: