thiết kế và đánh giá thuật toán - trần tuấn minh -4

Tính đơn giản của thuật toán. Thường ta mong muốn có được một thuật toán đơn giản, dễ hiểu, dễ lập trình. Đặc biệt là những thuật toán chỉ dùng một vài lần ta cần coi trọng tính chất này, vì công sức và thời gian bỏ ra để xây dựng thuật toán thường lớn hơn rất nhiều so với thời gian thực hiện nó.
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -4 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 49 - { int t, i1 = 1,i2 = 1,r1,r2; int h = 0; while(i1 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 50 - while(i2 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 51 - Kq = nhan(a,c)*10n + nhan(a,d)*10n/2 + nhan (b,c)*10n/2 + nhan(b,d); Baøi 2 : Thuaät toaùn nhaân 2 soá nguyeân n bit. Giaû söû x vaø y laø 2 soá nguyeân n bit. Kyõ thuaät “ chia ñeå trò “ cho pheùp nhaân xy laø taùch x, y ra 2 soá nguyeân n/2 bit : x a b n/2 bit traùi n/2 bit phaûi y c d vaø tính theo coâng thöùc : x*y = a*c*2n + ( (a-b)*(d-c) + a*c + b*d)*2n/2 + b*d Ghi chuù : - Taùch bit : Copy caùc bit. - Nhaân 2n cho a : Dòch chuyeån traùi a n bit. Baøi 3 : Cho x, s, n ∈ Z+. Giaû söû x ≤ s , tính x. n n Baøi 4 : Saép taêng daàn moät daõy x caùc soá, baèng thuaät toaùn troän töï nhieân : Trong khi (soá ñöôøng chaïy cuûa x > 1) - Taùch luaân phieân töøng ñöôøng chaïy cuûa x vaøo caùc daõy trung gian x1, x2; - Troän töøng caëp ñöôøng chaïy cuûa x1, x2 , löu tröû vaøo x; Ghi chuù : Ñöôøng chaïy trong x laø caùc daõy con coù thöù töï ( taêng daàn) coù chieàu daøi lôùn nhaát. Baøi 5 : Laäp lòch thi ñaáu voøng troøn 1 löôït cho n ñoäi boùng ñaù, n laø luyõ thöøa 2. Trong 1 ñôït thi ñaáu , moãi ñoäi ñaáu 1 traän. Ñaáu trong n-1 ñôït. Kyõ thuaät chia ñeå trò xaây döïng lòch cho moät nöûa soá ñoäi . Lòch naøy ñöôïc laäp neân do aùp duïng ñeä qui cuûa thuaät toaùn baèng caùch tìm lòch cho moät nöûa soá ñoäi ... khi chæ coøn 2 ñoäi thì ta coù moät caëp ñaáu ñôn giaûn. Caùc ñoäi ñöôïc ñaùnh soá töø 1 ñeán n. Giaû söû coù 8 ñoäi . Lòch thi ñaáu cho 4 ñoäi töø 1 ñeán 4 laáp ñaày goùc traùi treân ( 4 haøng 3 coät) coi nhö ñaõ laäp xong. Goùc traùi döôùi ( 4 haøng 3 coät ) phaûi cho vaøo caùc ñoäi coù soá thöù töï cao (töø 5 ñeán 8) ngöôïc vôùi caùc soá khaùc.Lòch con naøy taïo ra baèng caùch coäng 4 cho moãi soá nguyeân cuûa goùc traùi treân . Baây giôø ta ñaõ laøm ñôn giaûn baøi toaùn. Taát caû phaàn coøn laïi laø caùc ñoäi coù soá thaáp ñaáu vôùi caùc ñoäi coù soá cao. Ñieàu ñoù deã hieåu laø caùc ñoäi töø 1-4 ñaáu vôùi caùc ñoäi 5-8 töông öùng töø ñôït thöù 4 vaø hoaùn vò theo chu kyø 5 ñeán 8 trong caùc ñôït tieáp theo. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 52 - ñôït 1 ñôït 1 2 3 ñôït 1 2 3 4 5 6 7 →1 ñoäi 1 2 2 3 4 ñoäi 1 2 3 4 5 6 7 8 →2 2 1 2 1 4 3 1 4 3 6 7 8 5 3 4 1 2 3 4 1 2 7 8 5 6 4 3 2 1 4 3 2 1 8 5 6 7 5 6 7 8 1 4 3 2 6 5 8 7 2 1 4 3 7 8 5 6 3 2 1 4 8 7 6 5 4 3 2 1 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 53 - CHÖÔNG 3 : PHÖÔNG PHAÙP QUAY LUI (Back Tracking) I. Môû ñaàu 1. YÙ töôûng Neùt ñaëc tröng cuûa phöông phaùp quay lui laø caùc böôùc höôùng tôùi lôøi giaûi cuoái cuøng cuûa baøi toaùn hoaøn toaøn ñöôïc laøm thöû. Taïi moãi böôùc, neáu coù moät löïa choïn ñöôïc chaáp nhaän thì ghi nhaän laïi löïa choïn ...