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


Chương 4 Các phép lật và chuyển vị



tải về 2.51 Mb.
trang8/21
Chuyển đổi dữ liệu24.07.2016
Kích2.51 Mb.
#3874
1   ...   4   5   6   7   8   9   10   11   ...   21

Chương 4 Các phép lật và chuyển vị




4.1 Lật xâu

Cho xâu kí tự s. Hãy lật xâu s, tức là sắp các kí tự của xâu s theo trật tự ngược lại. Thí dụ, với s = "abcd", thì sau khi đảo ta thu được s = "dcba".

Thuật toán

Để lật một đoạn s[d..c] trong dãy s bất kì ta thực hiện liên tiếp các phép đổi chỗ hai phần tử cách đều đầu và cuối tính dần từ ngoài vào giữa dãy.



Độ phức tạp

Nếu đoạn cần lật có chiều dài n, mỗi lần đổi chố hai phần tử ta cần 3 phép gán. Tổng cộng có n/2 cặp phần tử do đó số phép gán sẽ là 3n/2.



Chương trình

Hàm Rev trong các chương trình sau đây nhận vào một xâu s và hai chỉ số đầu d và cuối c, sau đó thực hiện phép đảo đoạn s[d..c] rồi cho ra chính xâu s đó.


(* Reverse.pas *)

uses crt;

const nl = #13#10;

var s: string;

function Rev(var s: string; d,c: integer): string;

var ch: char;

begin

while (d < c) do

begin

ch := s[d]; s[d] := s[c]; s[c] := ch;

inc(d); dec(c);

end;

Rev := s;

end;

BEGIN

s := 'I have a dream';

write(nl,'Given: ',s);

Rev(s,1,length(s));

writeln(' => ',s);

writeln(nl,' Now, the source string is: ', Rev(s,1,length(s)));

readln;

END.
// DevC++: Reverse.cpp

#include

#include

using namespace std;

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

int main();

char * Rev(char *s, int d, int c);

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

int main() {

char * s = strdup("I have a dream");

cout << endl << " Given: " << s;

cout << " => " << Rev(s,0,strlen(s)-1);

cout << endl << " Now, the source string is => "

<< Rev(s,0,strlen(s)-1);

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

char * Rev(char * s, int d, int c) {

char ch;

while (d < c) {

ch = s[d]; s[d] = s[c]; s[c] = ch;

++d; --c;

}

return s;

}

Giải thích

Hàm s = strdup("I have a dream") cấp phát miền nhớ cho xâu s và khởi trị xâu này bằng dãy kí tự "I have a dream".


4.2 Lật số nguyên

Viết hàm Rev(x) cho ra số nguyên dạng lật của số nguyên x. Thí dụ, Rev(1234) =  4321.

Thuật toán

Gọi y là kết quả. Ta khởi trị y = 0 sau đó lấy lần lượt các chữ số đầu phải của x ghép vào bên phải số y.



Độ phức tạp

Nếu số đã cho có n chữ số, mỗi lần chuyển một chữ số ta cần thực hiện một phép chia dư và hai phép nhân. Nếu ta coi thời gian thực hiện phép nhân, chia và chia dư là xấp xỉ bằng nhau thì thuật toán lật số nguyên cần thời gian 3n. Mỗi số nguyên x có lg(x) + 1 chữ số dạng thập phân. Vậy độ phức tạp cỡ lg(x).


(* RevInt.pas *)

uses crt;

var x,y: integer;

function Rev(x: longint): longint;

var y: longint;

begin

y := 0;

while x <> 0 do

begin

y := y*10 + (x mod 10);

x := x div 10;

end;

Rev := y;

end;

BEGIN

x := -1234;

y := Rev(x);

writeln(' Given: ',x,' => ' ,y);

writeln(' Now, the source number is ', Rev(y));

readln;

END.
// DevC++: RevInt.cpp

#include

#include

using namespace std;

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

int main();

int Rev(int x);

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

int main() {

int y, x = -1234;

cout << endl << " Given: " << x;

cout << " => " << (y = Rev(x));

cout << endl << " Now, the source number is => " << Rev(y);

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

int Rev(int x) {

int y = 0;

while (x) {

y = y*10 + (x % 10);

x /= 10;

}

return y;

}

4.3 Sân bay vũ trụ

Muốn đưa các con tàu vũ trụ vào đúng quỹ đạo trên không gian người ta cần chọn địa điểm thich hợp để xây dựng đường băng. Nếu đường băng đặt tại vị trí thuận lợi, phù hợp với hướng vận hành của các hành tinh thì sẽ tiết kiệm được nhiều nhiên liệu. Người đã ta xây dựng xong một đường băng tại sân bay vũ trụ. Đường băng gồm n tấm bê tông lớn được đặt tại một vị trí cố định. Trong các tấm bê tông chứa nhiều linh kiện và đường nối tinh vi do đó sơ đồ liên kết rất phức tạp. Tuy nhiên, lúc kiểm tra người ta đã phát hiện ra sự nhầm lẫn lớn: i tấm bê tông đầu đường băng đặt sai vị trí: chúng cần được chuyển về phia cuối đường băng. Rất may là trên công trường lúc này còn một xe đặc chủng có sức chở 1 tấm bê tông và một cần trục có sức nâng 1 tấm bê tông. Xe chạy trên đường ray song song với đường băng. Mỗi tấm bê tông cần chuyển được tháo các khớp nối và được cần trục cẩu lên đặt trên xe rồi được xe chuyển đến vị trí cần đặt lại. Tại vị trí đó cần trục lại cẩu tấm bê tông khỏi xe và đặt vào vị trí thích hợp. Cần trục cũng có thể cẩu trực tiếp 1 tấm bê tông từ một vị trí đến vị trí còn trống nào đó. Thời gian cẩu và vận chuyển một tấm bê tông là đáng kể. Hãy đề xuất một phương án khắc phục sự cố với thời gian ngắn nhất, cụ thể là cần giảm tối đa số lần cẩu bê tông.

Thí dụ









Đường băng gồm 7 tấm bê tông mã số lần lượt từ 1 đến 7. 3 tấm bê tông đầu tiên là 1, 2 và 3 bị đặt sai vị trí. Sau khi chuyển lại 3 tấm này ta thu được đường băng đặt đúng là (4, 5, 6, 7, 1, 2, 3).

1
2
3
4
5
6
7











4
5
6
7
1
2
3












Thuật toán
Phương án 1. Ta gọi mỗi lần cẩu một tấm bê tông là một thao tác. Để chuyển i tấm bê tông từ đầu đường băng về cuối đường băng ta chuyển dần từng tấm. Để chuyển một tấm t từ đầu về cuối đường băng ta thực hiện n+1 thao tác sau đây:
  • 1 thao tác: Chuyển tấm t ra xe x;
  • n1 thao tác: dịch dần n1 tấm trên đường băng lên 1 vị trí;
  • 1 thao tác: Chuỷen tấm t từ xe vào vị trí cuối đường băng.
Tổng hợp lại, để chuyển i tấm từ đầu về cuối đường băng ta cần T1 = i(n+1) thao tác.
Giả sử đường băng có 1000 tấm bê tông và ta cần chuyển 500 tấm bê tông từ đầu về cuối đường băng thì ta cần T = 500(1000+1) = 500.1001 = 500500 thao tác. Lại giả sử mỗi ngày ta có thể thực hiện được 100 thao tác thì thời gian cần thiết để khắc phục sự cố sẽ là:
500500/(100365(ngày))  13 năm
Phương án 2. Ta vận dụng phép đối xứng (phép lật) để giải bài toán này. Kí hiệu u' là dãy lật của dãy u. Thí dụ, u = 1234 thì u' = (1234)' = 4321.
Phép lật có các tính chất sau:
1. Tính khả nghịch hay lũy đẳng: u'' = u. Lật đi lật rồi lật lại một dãy sẽ cho ta dãy ban đầu;
2. Cộng tính ngược: (uv)' = v'u'. Lật một dãy gồm hai khúc u và v sẽ cho kết qủa là một dãy gồm hai khúc lật riêng rẽ: khúc lật thứ hai v' kết nối với khúc lật thứ nhất u'.
Gọi u là khúc đầu gồm i tấm bê tông đầu đường băng, v là khúc cuối gồm ni tấm bê tông còn lại. Bài toán đặt ra là biến đổi uv thành vu: uv vu. Vận dụng hai tính chất của phép lật ta có:
(u'v')' = v''u'' = vu (*)
Ta xét lại thí dụ đường băng gồm 7 tấm bê tông và cần chuyển i = 3 tấm bê tông từ đầu về cuối đường băng. Ta có u = 123; v = 4567.
Nhiệm vụ: uv = 1234567 vu = 4567123.
Vận dụng đẳng thức (*) ta có
(u'v')' = ((123)'(4567)')' = (3217654)' = 4567123 = vu
Nếu Rev(s,d,c) là thủ tục lật đoạn từ chỉ số d đến chỉ số c trong dãy s(1..n) thì biểu thức (*) nói trên được cài đặt qua ba phép gọi thủ tục Rev như sau:

Rev(s, 1, i); { u' }

Rev(s, i+1, n); { v' }

Rev(s, 1, n); { s' = (u'v')' = vu }
Ta đã biết, để lật một khúc gồm m phần tử ta cần đổi chỗ lần lượt mỗi cặp phần tử cách đều đầu và cuối. Tổng cộng có m/2 cặp. Mỗi lần đổi chỗ hai phần tử trong một cặp ta cần thực hiện 3 phép gán tương ứng với 3 thao tác cẩu. Vậy thuật tóan chuyển vị theo công thức (*) sẽ đòi hỏi:
  • 3i/2 thao tác cho u';
  • 3(ni)/2 thao tác cho v';
  • 3n/2 thao tác cho s';
Tổng cộng ta cần T2 = 3/2. (i+(ni)+n) = 3n thao tác.
Với thí dụ đã cho, n = 1000, i = 500 ta tính được T2 = 3.1000 = 3000, tức là 3000/100 = 30 ngày.
Phương án 1 đòi hỏi 13 năm trong khi phương án 2 chỉ cần 1 tháng!
Chú ý Nếu m là số lẻ thì khi lật đoạn gồm m phần tử sẽ chỉ cần 3(m1)/2 phép gán, do đó công thức tính T2 có thể còn nhỏ hơn 3n tối đa là 6 phép gán.

Phương án 3. Có thể vận dụng phép lấy tích các hoán vị để giải bài toán với n+d phép chuyển, trong đó d là ước chung lớn nhất của n và i. Giả sử đường băng a gồm n = 15 tấm bê tông, a = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) và ta cần chuyển i = 6 tấm từ đầu về cuối đường băng theo yêu cầu của đầu bài. Kết quả cuối cùng phải thu được là b = (7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6). Như vậy ta có phép hoán vị a  b như sau:


a

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

b

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6


Ba hoán vị vòng quanh

  • xe  1  7  13  4  10  1 (xe);

  • xe  2  8  14  5  11  2 (xe);

  • xe  3  9  15  6  12  3 (xe).






Ta sẽ cố gắng mỗi lần chuyển 1 tấm vào đúng vị trí cần thiết. So sánh hai dòng a và b của bảng ta có thể thực hiện như sau:



Pha thứ nhất

1. Cẩu tấm 1 ra xe; vị trí 1 trở thành trống,

2. Cẩu tấm 7 vào vị trí 1; vị trí 7 trở thành trống,

3. Cẩu tấm 13 vào vị trí 7; vị trí 13 trở thành trống,

4. Cẩu tấm 4 vào vị trí 13; vị trí 4 trở thành trống,

5. Cẩu tấm 10 vào vị trí 4; vị trí 10 trở thành trống,

6. Cẩu tấm 1 từ xe vào vị trí 10.

Sau 6 thao tác chuyển ta thu được:




1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

7







10







13







1







4







Ta tiếp tục:

Pha thứ hai:

7. Cẩu tấm 2 ra xe; vị trí 2 trở thành trống,

8. Cẩu tấm 8 vào vị trí 2; vị trí 8 trở thành trống,

9. Cẩu tấm 14 vào vị trí 8; vị trí 14 trở thành trống,

10. Cẩu tấm 5 vào vị trí 14; vị trí 5 trở thành trống,

11. Cẩu tấm 11 vào vị trí 5; vị trí 11 trở thành trống,

12. Cẩu tấm 2 từ xe vào vị trí 11.

Đến đây ta thu được:




1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

7

8




10

11




13

14




1

2




4

5



Ta lại chuyển tiếp:



Pha thứ ba:

13. Cẩu tấm 3 ra xe; vị trí 3 trở thành trống,

14. Cẩu tấm 9 vào vị trí 3; vị trí 9 trở thành trống,

15. Cẩu tấm 15 vào vị trí 9; vị trí 15 trở thành trống,

16. Cẩu tấm 6 vào vị trí 15; vị trí 6 trở thành trống,

17. Cẩu tấm 12 vào vị trí 6; vị trí 12 trở thành trống,

18. Cẩu tấm 3 từ xe vào vị trí 12.


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

Sau T3 = 18 lần cẩu ta thu được kết quả. Phương án 2 đòi hỏi T2 = 3n = 3.15 = 45 lần cẩu.

Tổng quát, ta hãy tưởng tượng các tấm bê tông được xếp thành vòng tròn như trên mặt số đồng hồ, nếu xuất phát từ vị trí s0 sau ít nhất là k lần chuyển (không tính lần chuyển s0 ra xe) ta sẽ thu được dãy

xe  s0  s1  s2  ...  sk = s0 (xe)

Trong đó tấm bê tông đầu tiên s0 được chuyển ra xe và cuối cùng, tại bước thứ k tấm đó lại được chuyển vào vị trí s0. Ta dễ dàng nhận thấy sj+1 = (sj + i) mod n, j = 0, 1, ..., k1. Từ đây ta suy ra (s0 + ki) mod n = s0, hay ki mod n = 0. Gọi d là ước chung lớn nhất của n và i, d = (n,i). Ta có ngay, n = dn' và i = di'. Đặt k = n' = n/d, ta có kd = n'd = n và ki mod n = n'i mod n = (n/d)i mod n = (ni/d) mod n = ni' mod n = 0. Số pha chuyển là d.

Như vậy tổng cộng sẽ có tất cả T3 = (k+1)d = kd + d = n + d lần chuyển, trong đó d = (n,i). Với n = 15, i = 6 ta tính được d = (15,6) = 3, do đó ta chuyển trong d = 3 pha và tổng số lần chuyển sẽ là T3 = 15 + 3 = 18.



Hàm Move dưới đây nhận vào hai giá trị: tổng số tấm bê tông n và số bê tông đầu tiên cần chuyển về cuối i sau đó giải trình trật tự chuyển các tấm bê tông theo từng pha.

(* SanBay.pas *)

uses crt;

const BL = #32; NL = #13#10;

function Ucln(a, b: integer): integer;

var r: integer;

begin

while (b <> 0) do

begin

r := a mod b; a := b; b := r;

end;

Ucln := a;

end;

function Move(n, i: integer): integer;

var

d: integer;

tamdau, tam, vitri: integer;

t: integer; { tong so lan chuyen }

j, p: integer;

a: array[0..1000] of integer;

begin

d := Ucln(n,i);

writeln(NL,' Se chuyen trong ', d, ' pha', NL);

t := 0; tamdau := 1;

for j := 0 to n do a[j] := j;

for p := 1 to d do

begin

writeln(NL, ' Pha thu ', p, ':', NL);

while(a[tamdau] <> tamdau) do inc(tamdau);

tam := tamdau; inc(t); a[tam] := 0;

write(NL, t, '. Chuyen tam ', tam , ' ra xe');

readln;

while (true) do

begin

vitri := tam; tam := tam + i;

if (tam > n) then tam := tam – n;

inc(t); a[vitri] := tam;

if (tam <> tamdau) then

begin

write(NL,t,'. Chuyen tam ',tam, ' den vi tri ',vitri);

a[tam] := 0;

end

else

begin

write(NL,t,'. Chuyen tam ',tamdau,

' tu xe vao vi tri ', vitri);

write(NL,' Xong pha ',p,NL);

break;

end;

readln;

end { while }

end ; { end for }

write(NL,' Ket qua: ');

for i := 1 to n do write(a[i],BL);

Move := t;

end;

var t: integer;

BEGIN

t := Move(15,6);

writeln(NL, NL, ' Tong cong ', t, ' phep chuyen');

writeln(NL,NL,' Fini');

readln

END.

// DevC++: SanBay.cpp

#include

#include

#include

using namespace std;

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

int Ucln(int a, int b);

int Move(int n, int i);

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

main() {

cout << endl << endl

<< " Tong cong " << Move(15,6) << " phep chuyen";

cout << endl << " Fini "; cin.get();

}

int Ucln(int a, int b) {

int r;

while (b) {

r = a % b; a = b; b = r;

}

return a;

}

int Move(int n, int i) {

int d = Ucln(n,i);

cout << endl << " Se chuyen trong " << d << " pha" << endl;

int tam, vitri;

int t = 0; // tong so lan chuyen

int tamdau = 1; // tam be tong can chuyen dau tien cua moi pha

int a[n+1];

int j, p;

for (j = 0; j <= n; ++j) a[j] = j;

for (p = 1; p <= d; ++p) {

cout << endl << " Pha thu " << p << ":" << endl;

while(a[tamdau] != tamdau) ++tamdau;

tam = tamdau;

++t; a[tam] = 0;

cout << endl << t << ". Chuyen tam " << tam << " ra xe";

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

while (1) {

vitri = tam; tam += i;

if (tam > n) tam -= n;

++t; a[vitri] = tam; // a[tam] = 0;

if (tam != tamdau) {

a[tam] = 0;

cout << endl << t << ". Chuyen tam "

<< tam << " den vi tri " << vitri;

}

else {

cout << endl << t << ". Chuyen tam "

<< tamdau << " tu xe vao vi tri " << vitri;

cout << ". Xong pha " << p << endl;

break;

}

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

} // end while

} // end for

cout << endl << endl << " Ket qua: ";

for (i = 1; i <= n; ++i) cout << a[i] << " ";

return t;

}

Каталог: 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. ĐẠi số TỔ HỢp I. Kiến thức cơ bả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   ...   4   5   6   7   8   9   10   11   ...   21




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương