markdown:
# Cấu trúc dữ liệu 2005 P12
Chia sẻ: Nhan Hoang | Ngày: | Loại File: PDF | Số trang:34
lượt xem 15
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20091110/nguyen2/80x100/ctdl_2005_chuong_12_3268.jpg)
##
Cấu trúc dữ liệu 2005 P12
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Tham khảo tài liệu 'cấu trúc dữ liệu 2005 p12', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Cấu trúc dữ liệu 2005 P12
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Chöông 12 – BAÛNG VAØ TRUY XUAÁT THOÂNG TIN Chöông naøy tieáp tuïc nghieân cöùu veà caùch tìm kieám truy xuaát thoâng tin ñaõ ñeà caäp ôû chöông 7, nhöng taäp trung vaøo caùc baûng thay vì caùc danh saùch. Chuùng ta baét ñaàu töø caùc baûng hình chöõ nhaät thoâng thöôøng, sau ñoù laø caùc daïng baûng khaùc vaø cuoái cuøng laø baûng baêm. 12.1. Daãn nhaäp: phaù vôõ raøo caûn lgn Trong chöông 7 chuùng ta ñaõ thaáy raèng, baèng caùch so saùnh khoùa, trung bình vieäc tìm kieám trong n phaàn töû khoâng theå coù ít hôn lg n laàn so saùnh. Nhöng keát quaû naøy chæ noùi ñeán vieäc tìm kieám baèng caùch so saùnh caùc khoùa. Baèng moät vaøi phöông phaùp khaùc, chuùng ta coù theå toå chöùc caùc döõ lieäu sao cho vò trí cuûa moät phaàn töû coù theå ñöôïc xaùc ñònh nhanh hôn. Thaät vaäy, chuùng ta thöôøng laøm theá. Neáu chuùng ta coù 500 phaàn töû khaùc nhau coù caùc khoùa töø 0 ñeán 499, thì chuùng ta seõ khoâng bao giôø nghó ñeán vieäc tìm kieám tuaàn töï hoaëc tìm kieám nhò phaân ñeå xaùc ñònh vò trí moät phaàn töû. Ñôn giaûn chuùng ta chæ löu caùc phaàn töû naøy trong moät maûng kích thöôùc laø 500, vaø söû duïng chæ soá n ñeå xaùc ñònh phaàn töû coù khoùa laø n baèng caùch tra cöùu bình thöôøng ñoái vôùi moät baûng. Vieäc tra cöùu trong baûng cuõng nhö vieäc tìm kieám coù chung moät muïc ñích, ñoù laø truy xuaát thoâng tin. Chuùng ta baét ñaàu töø moät khoùa vaø mong muoán tìm moät phaàn töû chöùa khoùa naøy Trong chöông naøy chuùng ta tìm hieåu caùch hieän thöïc vaø truy xuaát caùc baûng trong vuøng nhôù lieân tuïc, baét ñaàu töø caùc baûng hình chöõ nhaät thoâng thöôøng, sau ñoù ñeán caùc baûng coù moät soá vò trí haïn cheá nhö caùc baûng tam giaùc, baûng loài loõm. Sau ñoù chuùng ta chuyeån sang caùc vaán ñeà mang tính toång quaùt hôn, vôùi muïc ñích tìm hieåu caùch söû duïng caùc maûng truy xuaát vaø caùc baûng baêm ñeå truy xuaát thoâng tin. Chuùng ta seõ thaáy raèng, tuyø theo hình daïng cuûa baûng, chuùng ta caàn coù moät soá böôùc ñeå truy xuaát moät phaàn töû, tuy vaäy, thôøi gian caàn thieát vaãn laø 0(1) - coù nghóa laø, thôøi gian coù giôùi haïn laø moät haèng soá vaø ñoäc laäp vôùi kích thöôùc cuûa baûng- vaø do ñoù vieäc tra cöùu baûng coù theå ñaït hieäu quaû hôn nhieàu so vôùi baát kyø phöông phaùp tìm kieám naøo. Caùc phaàn töû cuûa caùc baûng maø chuùng ta xem xeùt ñöôïc ñaùnh chæ soá baèng moät maûng caùc soá nguyeân, töông töï caùch ñaùnh chæ soá cuûa maûng. Chuùng ta seõ hieän thöïc caùc baûng ñöôïc ñònh nghóa tröøu töôïng baèng caùc maûng. Ñeå phaân bieät giöõa khaùi nieäm tröøu töôïng vaø caùc hieän thöïc cuûa noù, chuùng ta coù moät quy öôùc sau: Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 305
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Chæ soá xaùc ñònh moät phaàn töû cuûa moät baûng ñònh nghóa tröøu töôïng ñöôïc bao bôûi caëp daáu ngoaëc ñôn, coøn chæ soá cuûa moät phaàn töû trong maûng ñöôïc bao bôûi caëp daáu ngoaëc vuoâng. Ví duï, T(1,2,3) laø phaàn töû cuûa baûng T ñöôïc ñaùnh chæ soá bôûi daõy soá 1, 2, 3, vaø A[1][2][3] töông öùng phaàn töû vôùi chæ soá trong maûng A cuûa C++. 12.2. Caùc baûng chöõ nhaät Do taàm quan troïng cuûa caùc baûng chöõ nhaät, haàu heát caùc ngoân ngöõ laäp trình caáp cao ñeàu cung caáp maûng hai chieàu ñeå chöùa vaø truy xuaát chuùng, vaø noùi chung ngöôøi laäp trình khoâng caàn phaûi baän taâm ñeán caùch hieän thöïc chi tieát cuûa noù. Tuy nhieân, boä nhôù maùy tính thöôøng coù toå chöùc cô baûn laø moät maûng lieân tuïc (nhö moät maûng tuyeán tính coù phaàn töû naøy naèm keá phaàn töû kia), ñoái vôùi moãi truy xuaát ñeán baûng chöõ nhaät, maùy caàn phaûi coù moät soá tính toaùn ñeå chuyeån ñoåi moät vò trí trong hình chöõ nhaät sang moät vò trí trong maûng tuyeán tính. Chuùng ta haõy xem xeùt ñieàu naøy moät caùch chi tieát hôn. 12.2.1. Thöù töï öu tieân haøng vaø thöù töï öu tieân coät Caùch töï nhieân ñeå ñoïc moät baûng chöõ nhaät laø ñoïc caùc phaàn töû ôû haøng thöù nhaát tröôùc, töø traùi sang phaûi, sau ñoù ñeán caùc phaàn töû haøng thöù hai, vaø cöù theá tieáp tuïc cho ñeán khi haøng cuoái ñaõ ñöôïc ñoïc xong. Ñaây cuõng laø thöù töï maø ña soá caùc trình bieân dòch löu tröõ baûng chöõ nhaät, vaø ñöôïc goïi laø thöù töï öu tieân haøng (row-major ordering). Chaúng haïn, moät baûng tröøu töôïng coù haøng ñöôïc ñaùnh soá laø töø 1 ñeán 2, vaø coät ñöôïc ñaùnh soá töø 5 ñeán 7, thì thöù töï cuûa caùc phaàn töû theo thöù töï öu tieân haøng nhö sau: (1,5) (1,6) (1,7) (2,5) (2,6) (2,7) Ñaây cuõng laø thöù töï ñöôïc duøng trong C++ vaø haàu heát caùc ngoân ngöõ laäp trình caáp cao ñeå löu tröõ caùc phaàn töû cuûa moät maûng hai chieàu. FORTRAN chuaån laïi söû duïng thöù töï öu tieân coät, trong ñoù caùc phaàn töû cuûa coät thöù nhaát ñöôïc löu tröôùc, roài ñeán coät thöù hai,v.v...Ví duï thöù töï öu tieân coät nhö sau: (1,5) (2,5) (1,6) (2,6) (1,7) (2,7) Hình 12.1 minh hoïa caùc thöù töï öu tieân cho moät baûng coù 3 haøng vaø 4 coät. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 306
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Hình 12.1 – Bieåu dieãn noái tieáp cho maûng chöõ nhaät 12.2.2. Ñaùnh chæ soá cho baûng chöõ nhaät Moät caùch toång quaùt, trình bieân dòch coù theå baét ñaàu töø chæ soá (i,j) ñeå tính vò trí trong moät maûng noái tieáp maø moät phaàn töû töông öùng trong baûng ñöôïc löu tröõ. Chuùng ta seõ ñöa ra coâng thöùc tính toaùn sau ñaây. Ñeå ñôn giaûn chuùng ta chæ söû duïng thöù töï öu tieân haøng cuøng vôùi giaû thieát laø haøng ñöôïc ñaùnh soá töø 0 ñeán m-1, vaø coät töø 0 ñeán n-1. Tröôøng hôïp caùc haøng vaø caùc coät ñöôïc ñaùnh soá khoâng phaûi töø 0 ñöôïc xem nhö baøi taäp. Soá phaàn töû cuûa baûng seõ laø mn, vaø ñoù cuõng laø soá phaàn töû trong hieän thöïc lieân tuïc trong maûng. Chuùng ta ñaùnh soá caùc phaàn töû trong maûng töø 0 ñeán mn –1. Ñeå coù coâng thöùc tính vò trí cuûa phaàn töû (i,j) trong maûng, tröôùc heát chuùng ta quan saùt moät vaøi tröôøng hôïp ñaëc bieät. Phaàn töû (0,0) naèm taïi vò trí 0, caùc phaàn töû thuoäc haøng ñaàu tieân trong baûng raát deã tìm thaáy: (0,j) naèm taïi vò trí j. Phaàn töû ñaàu cuûa haøng thöù hai (1,0) naèm ngay sau phaàn töû (0,n-1), ñoù laø vò trí n. Tieáp theo, chuùng ta thaáy phaàn töû (1,j) naèm taïi vò trí n+j. Caùc phaàn töû cuûa haøng keá tieáp cuõng seõ naèm sau soá phaàn töû cuûa hai haøng tröôùc ñoù (2n phaàn töû). Do ñoù phaàn töû (2,j) naèm taïi vò trí 2n+j. Moät caùch toång quaùt, caùc phaàn töû thuoäc haøng i coù n i phaàn töû phía tröôùc, neân coâng thöùc chung laø: Phaàn töû (i,j) trong baûng chöõ nhaät naèm taïi vò trí n i + j trong maûng noái tieáp. Coâng thöùc naøy cho bieát vò trí trong maûng noái tieáp maø moät phaàn töû trong baûng chöõ nhaät ñöôïc löu tröõ, vaø ñöôïc goïi laø haøm chæ soá (index function). Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 307
- Chöông 12 – Baûng vaø truy xuaát thoâng tin 12.2.3. Bieán theå: maûng truy xuaát Vieäc tính toaùn cho caùc haøm chæ soá cuûa caùc baûng chöõ nhaät thaät ra khoâng khoù laém, caùc trình bieân dòch cuûa haàu heát caùc ngoân ngöõ caáp cao seõ dòch haøm naøy sang ngoân ngöõ maùy thaønh moät soá böôùc tính toaùn caàn thieát. Tuy nhieân, treân caùc maùy tính nhoû, pheùp nhaân thöôøng thöïc hieän raát chaäm, moät phöông phaùp khaùc coù theå ñöôïc söû duïng ñeå traùnh pheùp nhaân. Phöông phaùp naøy löu moät maûng phuï trôï chöùa moät phaàn cuûa baûng nhaân vôùi thöøa soá laø n: 0, n, 2n, 3n, ..., (m-1)n. Löu yù raèng maûng naøy nhoû hôn baûng chöõ nhaät raát nhieàu, neân noù coù theå ñöôïc löu thöôøng tröïc trong boä nhôù. Caùc phaàn töû cuûa noù chæ phaûi tính moät laàn (vaø chuùng coù theå ñöôïc tính chæ baèng pheùp coäng). Khi gaëp moät yeâu caàu tham chieáu ñeán baûng chöõ nhaät, trình bieân dòch coù theå tìm vò trí cuûa phaàn töû (i,j) baèng caùch laáy phaàn töû thöù i trong maûng phuï trôï coäng theâm j ñeå ñeán vò trí caàn coù. Maûng phuï trôï naøy cung caáp cho chuùng ta moät ví duï ñaàu tieân veà moät maûng truy xuaát (access maûng) (Hình 12.2). Noùi chung, moät maûng truy xuaát laø moät maûng phuï trôï ñöôïc söû duïng ñeå tìm moät döõ lieäu ñöôïc löu tröõ ñaâu ñoù. Maûng truy xuaát coù khi coøn ñöôïc goïi laø vector truy xuaát (access vector). Hình 12.2 – Maûng truy xuaát cho baûng chöõ nhaät 12.3. Caùc baûng vôùi nhieàu hình daïng khaùc nhau Thoâng tin thöôøng löu trong moät baûng chöõ nhaät coù theå khoâng caàn ñeán moïi vò trí trong hình chöõ nhaät ñoù. Neáu chuùng ta ñònh nghóa ma traän laø moät baûng chöõ nhaät goàm caùc con soá, thì thöôøng laø moät vaøi vò trí trong ma traän ñoù mang trò 0. Moät vaøi ví duï nhö theá ñöôïc minh hoïa trong hình 12.3. Ngay caû khi caùc phaàn töû trong moät baûng khoâng phaûi laø nhöõng con soá, caùc vò trí ñöôïc söû duïng thöïc söï cuõng coù theå khoâng phaûi laø taát caû hình chöõ nhaät, vaø nhö vaäy coù theå coù caùch hieän thöïc khaùc hay hôn thay vì söû duïng moät baûng chöõ nhaät vôùi nhieàu choã troáng. Trong phaàn naøy, chuùng ta tìm hieåu caùc caùch hieän thöïc caùc baûng vôùi nhieàu hình daïng khaùc nhau, Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 308
- Chöông 12 – Baûng vaø truy xuaát thoâng tin nhöõng caùch naøy seõ khoâng ñoøi hoûi vuøng nhôù cho nhöõng phaàn töû vaéng maët nhö trong baûng chöõ nhaät. 12.3.1. Caùc baûng tam giaùc Chuùng ta haõy xem xeùt caùch bieåu dieãn baûng tam giaùc döôùi nhö trong hình veõ 12.3. Moät baûng nhö vaäy chæ caàn caùc chæ soá (i,j) vôùi i≥j. Chuùng ta coù theå hieän thöïc moät baûng tam giaùc trong moät maûng lieân tuïc baèng caùch tröôït moãi haøng ra sau haøng naèm ngay treân noù, nhö caùch bieåu dieãn ôû hình 12.4. Hình 12.3 – Caùc baûng vôùi nhieàu daïng khaùc nhau. Ñeå xaây döïng haøm chæ soá moâ taû caùch aùnh xaï naøy, chuùng ta cuõng giaû söû raèng caùc haøng vaø caùc coät ñeàu ñöôïc ñaùnh soá baét ñaàu töø 0. Ñeå tìm vò trí cuûa phaàn töû (i,j) trong maûng lieân tuïc chuùng ta caàn tìm vò trí baét ñaàu cuûa haøng i, sau ñoù ñeå tìm coät j chuùng ta chæ vieäc coäng theâm j vaøo ñieåm baét ñaàu cuûa haøng i. Neáu caùc phaàn töû cuûa maûng lieân tuïc cuõng ñöôïc ñaùnh soá baét ñaàu töø 0, thì chæ soá cuûa ñieåm baét ñaàu cuûa haøng thöù i cuõng chính laø soá phaàn töû naèm ôû caùc haøng treân haøng i. Roõ raøng laø treân haøng thöù 0 coù 0 phaàn töû, vaø chæ coù moät phaàn töû cuûa haøng 0 laø xuaát hieän tröôùc haøng 1. Ñoái vôùi haøng 2, coù 1 + 2 = 3 phaàn töû ñi tröôùc, vaø trong tröôøng hôïp toång quaùt chuùng ta thaáy soá phaàn töû coù tröôùc haøng i chính xaùc laø: 1 1+2+...+i= i(i + 1). 2 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 309
- Chöông 12 – Baûng vaø truy xuaát thoâng tin 1 Vaäy phaàn töû (i,j) trong baûng tam giaùc töông öùng phaàn töû i(i + 1) + j cuûa 2 maûng lieân tuïc. Hình 12.4 – Hieän thöïc lieân tuïc cuûa baûng tam giaùc. Cuõng nhö chuùng ta ñaõ laøm cho caùc baûng chöõ nhaät, chuùng ta cuõng traùnh moïi pheùp nhaân vaø chia baèng caùch taïo moät maûng truy xuaát chöùa caùc phaàn töû töông öùng vôùi caùc chæ soá cuûa caùc haøng trong baûng tam giaùc. Vò trí i trong maûng truy xuaát 1 mang trò i (i + 1). Maûng truy xuaát ñöôïc tính toaùn chæ moät laàn khi baét ñaàu 2 chöông trình, vaø ñöôïc söû duïng laëp laïi cho moãi truy xuaát ñeán baûng tam giaùc. Chuù yù raèng ngay caû vieäc tính toaùn ban ñaàu cuõng khoâng caàn ñeán pheùp nhaân hoaëc chia maø chí coù pheùp coäng theo thöù töï sau maø thoâi: 0, 1, 1+2, (1 + 2) + 3, . . . 12.3.2. Caùc baûng loài loõm Hình 12.5 – Maûng truy xuaát cho baûng loài loõm. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 310
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Trong caû hai ví duï ñaõ ñeà caäp tröôùc chuùng ta ñaõ xem xeùt moät baûng ñöôïc taïo töø caùc haøng cuûa noù. Trong caùc baûng chöõ nhaät thoâng thöôøng, taát caû caùc haøng ñeàu coù cuøng chieàu daøi; trong baûng tam giaùc, chieàu daøi moãi haøng coù theå ñöôïc tính döïa vaøo moät coâng thöùc ñôn giaûn. Baây giôø chuùng ta haõy xem xeùt ñeán tröôøng hôïp cuûa caùc baûng loài loõm töïa nhö hình 12.5, khoâng coù moät moái quan heä coù theå ñoaùn tröôùc naøo giöõa vò trí cuûa moät haøng vaø chieàu daøi cuûa noù. Moät ñieàu hieån nhieân ñöôïc nhìn thaáy töø sô ñoà raèng, tuy chuùng ta khoâng theå xaây döïng moät haøm thöù töï naøo ñeå aùnh xaï moät baûng loài loõm sang vuøng nhôù lieân tuïc, nhöng vieäc söû duïng moät maûng truy xuaát cuõng deã daøng nhö caùc ví duï tröôùc, vaø caùc phaàn töû cuûa baûng loài loõm coù theå ñöôïc truy xuaát moät caùch nhanh choùng. Ñeå taïo maûng truy xuaát, chuùng ta phaûi xaây döïng baûng loài loõm theo thöù töï voán coù cuûa noù, baét ñaàu töø haøng ñaàu tieân. Phaàn töû 0 cuûa maûng truy xuaát, cuõng nhö tröôùc kia, laø baét ñaàu cuûa maûng lieân tuïc. Sau khi moãi haøng cuûa baûng loài loõm ñöôïc xaây döïng xong, chæ soá cuûa vò trí ñaàu tieân chöa ñöôïc söû duïng tôùi cuûa vuøng nhôù lieân tuïc chính laø trò cuûa phaàn töû keá tieáp trong maûng truy xuaát vaø ñöôïc söû duïng ñeå baét ñaàu xaây döïng haøng keá cuûa baûng loài loõm. 12.3.3. Caùc baûng chuyeån ñoåi Tieáp theo, chuùng ta haõy xem xeùt moät ví duï minh hoïa vieäc söû duïng nhieàu maûng truy xuaát ñeå tham chieáu cuøng luùc ñeán moät baûng caùc phaàn töû qua moät vaøi khoùa khaùc nhau. Chuùng ta xem xeùt nhieäm vuï cuûa moät coâng ty ñieän thoaïi trong vieäc truy xuaát ñeán caùc phaàn töû veà caùc khaùch haøng cuûa hoï. Ñeå in danh muïc ñieän thoaïi, caùc phaàn töû caàn saép thöù töï teân khaùch haøng theo alphabet. Tuy nhieân, ñeå xöû lyù caùc cuoäc goïi ñöôøng daøi, caùc phaàn töû laïi caàn coù thöù töï theo soá ñieän thoaïi. Ngoaøi ra, ñeå tieán haønh baûo trì ñònh kyø, danh saùch caùc khaùch haøng saép thöù töï theo ñòa chæ seõ coù ích cho caùc nhaân vieân baûo trì. Nhö vaäy, coâng ty ñieän thoaïi caàn phaûi löu caû ba, hoaëc nhieàu hôn, danh saùch caùc khaùch haøng theo caùc thöù töï khaùc nhau. Baèng caùch naøy, khoâng nhöõng toán keùm nhieàu vuøng löu tröõ maø coøn coù khaû naêng thoâng tin bò sai leäch do khoâng ñöôïc caäp nhaät ñoàng thôøi. Chuùng ta coù theå traùnh ñöôïc vieäc phaûi löu nhieàu laàn cuøng moät taäp caùc phaàn töû baèng caùch söû duïng caùc maûng truy xuaát, vaø chuùng ta coù theå tìm caùc phaàn töû theo baát kyø moät khoùa naøo moät caùch nhanh choùng chaúng khaùc gì chuùng ñaõ ñöôïc saép thöù töï theo khoùa ñoù. Chuùng ta seõ taïo moät maûng truy xuaát cho teân caùc khaùch haøng. Phaàn töû ñaàu tieân cuûa maûng naøy chöùa vò trí cuûa khaùch haøng ñöùng ñaàu danh saùch theo alphabet. Phaàn töû thöù hai chöùa vò trí khaùch haøng thöù hai, vaø cöù theá. Trong maûng truy xuaát thöù hai, phaàn töû ñaàu tieân chöùa vò trí cuûa khaùch haøng coù soá ñieän thoaïi nhoû nhaát. Töông töï, maûng truy xuaát thöù ba coù caùc phaàn töû chöùa vò trí cuûa caùc khaùch haøng theo thöù töï ñòa chæ cuûa hoï. (Hình 12.6) Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 311
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Hình 12.6 – Maûng truy xuaát cho nhieàu khoùa: baûng chuyeån ñoåi Chuùng ta löu yù raèng trong phöông phaùp naøy caùc thaønh phaàn döõ lieäu ñöôïc xem nhö laø khoùa ñeàu ñöôïc xöû lyù cuøng moät caùch. Khoâng coù lyù do gì buoäc caùc phaàn töû phaûi coù thöù töï vaät lyù öu tieân theo khoùa naøy maø khoâng theo khoùa khaùc. Caùc phaàn töû coù theå ñöôïc löu tröõ theo moät thöù töï tuøy yù, coù theå noùi ñoù laø thöù töï maø chuùng ñöôïc nhaäp vaøo heä thoáng. Cuõng khoâng coù söï khaùc nhau giöõa vieäc caùc phaàn töû ñöôïc löu trong moät danh saùch lieân tuïc laø maûng (maø caùc phaàn töû cuûa caùc maûng truy xuaát chöùa caùc chæ soá cuûa maûng naøy) hay caùc phaàn töû ñang thuoäc moät danh saùch lieân keát (caùc phaàn töû cuûa caùc maûng truy xuaát chöùa caùc ñòa chæ ñeán töøng phaàn töû rieâng). Trong moïi tröôøng hôïp, chính caùc maûng truy xuaát ñöôïc söû duïng ñeå truy xuaát thoâng tin, vaø, cuõng gioáng nhö caùc maûng lieân tuïc thoâng thöôøng, chuùng coù theå ñöôïc söû duïng trong vieäc tra cöùu caùc baûng, hoaëc tìm kieám nhò phaân, hoaëc vôùi baát kyø muïc ñích naøo khaùc thích hôïp vôùi caùch hieän thöïc lieân tuïc. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 312
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Hình 12.7 – Ví duï veà baûng tam giaùc ñoái xöùng qua 0. 12.4. Baûng: Moät kieåu döõ lieäu tröøu töôïng môùi Töø ñaàu chöông naøy chuùng ta ñaõ bieát ñeán moät soá haøm chæ soá ñöôïc duøng ñeå tìm kieám caùc phaàn töû trong caùc baûng, sau ñoù chuùng ta cuõng ñaõ gaëp caùc maûng truy xuaát laø caùc maûng ñöôïc duøng vôùi cuøng moät muïc ñích nhö caùc haøm chæ soá. Coù moät söï gioáng nhau raát lôùn giöõa caùc haøm vôùi vieäc tra cöùu baûng: vôùi moät haøm, chuùng ta baét ñaàu baèng moät thoâng soá ñeå tính moät giaù trò töông öùng; vôùi moät baûng, chuùng ta baét ñaàu baèng moät chæ soá ñeå truy xuaát moät giaù trò döõ lieäu töông öùng ñöôïc löu trong baûng. Chuùng ta haõy söû duïng söï töông töï naøy ñeå xaây döïng moät ñònh nghóa hình thöùc cho thuaät ngöõ baûng. 12.4.1. Caùc haøm Trong toaùn hoïc, moät haøm ñöôïc ñònh nghóa döïa treân hai taäp hôïp vaø söï töông öùng töø caùc phaàn töû cuûa taäp thöù nhaát ñeán caùc phaàn töû cuûa taäp thöù hai. Neáu f laø moät haøm töø taäp A sang taäp B, thì f gaùn cho moãi phaàn töû cuûa A moät phaàn töû duy nhaát cuûa B. Taäp A ñöôïc goïi laø domain cuûa f, coøn taäp B ñöôïc goïi laø codomain cuûa f. Taäp con cuûa B chæ chöùa caùc phaàn töû laø caùc trò cuûa f ñöôïc goïi laø range cuûa f. Ñònh nghóa naøy ñöôïc minh hoïa trong hình 12.8. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 313
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Hình 12.8 – Domain, codomain vaø range cuûa moät haøm Vieäc truy xuaát baûng baét ñaàu baèng moät chæ soá vaø baûng ñöôïc söû duïng ñeå tra cöùu moät trò töông öùng. Ñoái vôùi moät baûng chuùng ta goïi domain laø taäp chæ soá (index set), vaø codomain laø kieåu cô sôû (base type) hoaëc kieåu trò (value type). Laáy ví duï, chuùng ta coù moät khai baùo maûng nhö sau: double array[n]; thì taäp chæ soá laø taäp caùc soá nguyeân töø 0 ñeán n-1, vaø kieåu cô sôû laø taäp taát caû caùc soá thöïc. Laáy ví duï thöù hai, chuùng ta haõy xeùt moät baûng tam giaùc coù m haøng, moãi phaàn töû coù kieåu item. Kieåu cô sôû seõ laø kieåu item vaø taäp chæ soá laø taäp caùc caëp soá nguyeân {(i,j) | 0 ≤ j ≤ i < m} 12.4.2. Moät kieåu döõ lieäu tröøu töôïng Chuùng ta ñang ñi ñeán moät ñònh nghóa cho baûng nhö moät kieåu döõ lieäu tröøu töôïng môùi, ñoàng thôøi trong caùc chöông tröôùc chuùng ta ñaõ bieát raèng ñeå hoaøn taát moät ñònh nghóa cho moät caáu truùc döõ lieäu, chuùng ta caàn phaûi ñaëc taû caùc taùc vuï ñi keøm. Ñònh nghóa: Moät baûng vôùi taäp chæ soá I vaø kieåu cô sôû T laø moät haøm töø I ñeán T keøm caùc taùc vuï sau: 1. Access (truy xuaát baûng): Xaùc ñònh trò cuûa haøm theo baát kyø moät chæ soá trong I. 2. Assignment (ghi baûng): Söûa ñoåi haøm baèng caùch thay ñoåi trò cuûa noù taïi moät chæ soá naøo ñoù trong I thaønh moät trò môùi ñöôïc chæ ra trong pheùp gaùn. Hai taùc vuï naøy laø taát caû nhöõng gì ñöôïc cung caáp bôûi caùc maûng trong C++ hoaëc moät vaøi ngoân ngöõ khaùc, nhöng ñoù khoâng phaûi laø lyù do ñeå coù theå ngaên caûn chuùng ta theâm moät soá taùc vuï khaùc cho moät baûng tröøu töôïng. Neáu so saùnh vôùi ñònh nghóa Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 314
- Chöông 12 – Baûng vaø truy xuaát thoâng tin cuûa moät danh saùch (list), chuùng ta ñaõ coù caùc taùc vuï nhö theâm phaàn töû, xoùa phaàn töû cuõng nhö truy xuaát hoaëc caäp nhaät laïi. Vaäy chuùng ta coù theå laøm töông töï ñoái vôùi baûng. Caùc taùc vuï boå sung cho baûng: 1. Creation (Taïo): Taïo moät haøm töø I vaøo T. 2. Clearing (Doïn deïp): Loaïi boû moïi phaàn töû trong taäp chæ soá I, domain seõ laø moät taäp roãng. 3. Insertion (Theâm): Theâm moät phaàn töû x vaøo taäp chæ soá I vaø xaùc ñònh moät trò töông öùng cuûa haøm taïi x. 4. Deletion (Xoùa): Loaïi boû moät phaàn töû x trong taäp chæ soá I vaø haïn cheá chæ cho haøm xaùc ñònh treân taäp chæ soá coøn laïi. 12.4.3. Hieän thöïc Ñònh nghóa treân chæ môùi laø ñònh nghóa cuûa moät kieåu döõ lieäu tröøu töôïng maø chöa noùi gì ñeán caùch hieän thöïc. Noù cuõng khoâng heà nhaéc ñeán caùc haøm chæ soá hay caùc maûng truy xuaát. Chuùng ta haõy xem hình minh hoïa trong hình 12.9. Phaàn treân cuûa hình naøy cho chuùng ta thaáy moät söï tröøu töôïng trong ñònh nghóa, truy xuaát baûng ñôn giaûn chæ laø moät aùnh xaï töø moät taäp chæ soá sang moät kieåu cô sôû. Phaàn döôùi cuûa hình laø yù töôûng toång quaùt cuûa phaàn hieän thöïc. Moät haøm chæ soá hoaëc moät maûng truy xuaát nhaän thoâng soá töø moät taäp chæ soá theo moät daïng ñaõ ñöôïc ñaëc taû naøo ñoù. Chaúng haïn (i,j) trong baûng 2 chieàu hoaëc (i,j,k) trong baûng 3 chieàu vôùi i, j, k ñaõ coù mieàn xaùc ñònh ñaõ ñònh. Keát quaû cuûa haøm chæ soá hoaëc maûng truy xuaát seõ laø moät trong caùc trò trong mieàn caùc chæ soá, chaúng haïn taäp con cuûa taäp caùc soá nguyeân. Mieàn trò naøy coù theå ñöôïc söû duïng tröïc tieáp nhö chæ soá cho maûng vaø ñöôïc cung caáp bôûi ngoân ngöõ laäp trình. Ñeán ñaây xem nhö chuùng ta ñaõ giôùi thieäu xong moät kieåu caáu truùc döõ lieäu môùi, ñoù laø baûng. Tuøy töøng muïc ñích cuûa caùc öùng duïng, baûng coù theå coù nhieàu phieân baûn khaùc nhau. Phaàn ñònh nghóa chi tieát hôn cho caùc phieân baûn naøy cuõng nhö caùc caùch hieän thöïc cuûa chuùng ñöôïc xem nhö baøi taäp. Phaàn tieáp theo ñaây trình baøy söï gioáng vaø khaùc nhau giöõa danh saùch vaø baûng. Sau ñoù chuùng ta seõ tieáp tuïc laøm quen vôùi moät caáu truùc döõ lieäu khaù ñaëc bieät vaø raát phoå bieán, ñoù laø baûng baêm. Caáu truùc döõ lieäu baûng baêm cuõng xuaát phaùt töø yù töôûng söû duïng baûng nhö phaàn naøy ñaõ giôùi thieäu. 12.4.4. So saùnh giöõa danh saùch vaø baûng Chuùng ta haõy so saùnh hai kieåu döõ lieäu tröøu töôïng danh saùch vaø baûng. Neàn taûng toaùn hoïc cô baûn cuûa danh saùch laø moät chuoãi noái tieáp caùc phaàn töû, coøn ñoái vôùi baûng, ñoù laø taäp hôïp vaø haøm. Chuoãi noái tieáp coù moät traät töï ngaàm trong ñoù, ñoù laø phaàn töû ñaàu tieân, phaàn töû thöù hai, v.v..., coøn taäp hôïp vaø haøm khoâng coù thöù töï. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 315
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Vieäc truy xuaát thoâng tin trong moät danh saùch thöôøng lieân quan ñeán vieäc tìm kieám, nhöng vieäc truy xuaát thoâng tin trong baûng ñoøi hoûi nhöõng phöông phaùp khaùc, ñoù laø caùc phöông phaùp coù theå ñi thaúng ñeán phaàn töû mong muoán. Thôøi gian caàn thieát ñeå tìm kieám trong danh saùch noùi chung phuï thuoäc vaøo n laø soá phaàn töû trong danh saùch vaø ít nhaát laø baèng lg n, nhöng thôøi gian ñeå truy xuaát baûng thöôøng khoâng phuï thuoäc vaøo soá phaàn töû trong baûng, vaø thöôøng laø O(1). Vì lyù do naøy, trong nhieàu öùng duïng, vieäc truy xuaát baûng thöïc söï nhanh hôn vieäc tìm kieám trong moät danh saùch. Hình 12.9 – Hieän thöïc cuûa baûng Maët khaùc, duyeät laø moät taùc vuï töï nhieân ñoái vôùi moät danh saùch, nhöng ñoái vôùi baûng thì khoâng. Vieäc di chuyeån xuyeân suoát moät danh saùch ñeå thöïc hieän moät taùc vuï naøo ñoù leân töøng phaàn töû cuûa noù noùi chung laø deã daøng. Ñieàu naøy ñoái vôùi baûng khoâng deã daøng chuùt naøo, ñaëc bieät trong tröôøng hôïp coù yeâu caàu tröôùc veà moät traät töï naøo ñoù cuûa caùc phaàn töû ñöôïc duyeät. Cuoái cuøng, chuùng ta caàn laøm roõ söï khaùc nhau giöõa baûng vaø maûng. Noùi chung, chuùng ta duøng töø baûng nhö laø chuùng ta ñaõ ñònh nghóa trong phaàn vöøa roài vaø giôùi haïn töø maûng chæ vôùi nghóa nhö laø moät phöông tieän duøng ñeå laäp trình cuûa C++ vaø phaàn lôùn caùc ngoân ngöõ caáp cao, caùc maûng naøy thöôøng ñöôïc söû duïng ñeå hieän thöïc caû hai: baûng vaø danh saùch lieân tuïc. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 316
- Chöông 12 – Baûng vaø truy xuaát thoâng tin 12.5. Baûng baêm Khi giôùi thieäu toång quaùt veà baûng cuõng nhö caùch söû duïng haøm chæ soá vaø maûng truy xuaát, chuùng ta caàn nhaän ra moät ñieàu raèng, thoâng soá cho haøm chæ soá hoaëc maûng truy xuaát phaàn naøo phaûn aùnh vò trí, hay noùi roõ hôn, ñoù laø traät töï cuûa phaàn töû caàn truy xuaát trong baûng. Chaúng haïn traät töï theo chæ soá haøng vaø coät trong baûng (i,j), hay tröôøng hôïp danh saùch caùc khaùch haøng söû duïng ñieän thoaïi: teân cuûa caùc khaùch haøng coù thöù töï theo alphabet. Baûng baêm maø chuùng ta seõ nghieân cöùu tieáp theo mang moät ñaëc ñieåm hoaøn toaøn khaùc. Vieäc truy xuaát baûng baét ñaàu töø giaù trò cuûa khoùa trong phaàn töû döõ lieäu, vaø thoâng thöôøng khoùa naøy khoâng lieân quan ñeán traät töï trong haøng hoaëc coät cuûa baûng ñeå coù theå söû duïng moät haøm chæ soá ñôn giaûn cho ra vò trí cuûa noù trong baûng nhö ôû phaàn treân ñaõ giôùi thieäu. 12.5.1. Caùc baûng thöa 12.5.1.1. Caùc haøm chæ soá Ñieàu chuùng ta coù theå laøm laø xaây döïng söï töông öùng moät – moät giöõa caùc khoùa vaø caùc chæ soá maø chuùng ta söû duïng ñeå truy xuaát baûng. So vôùi caùc phaàn tröôùc, haøm chæ soá maø chuùng ta xaây döïng ôû ñaây seõ phöùc taïp hôn, vì coù khi chuùng ta caàn ñeán söï bieán ñoåi cuûa caùc khoùa, chaúng haïn töø caùc chöõ caùi sang caùc soá nguyeân. Theo nguyeân taéc, ñieàu naøy luoân coù theå laøm ñöôïc. Khoù khaên thöïc söï chæ laø khi soá caùc khoùa coù theå coù vöôït ra ngoaøi khoâng gian cuûa baûng. Laáy ví duï, neáu caùc khoùa laø caùc töø coù 8 kyù töï, thì coù theå coù ñeán 268 ≈ 2 x 1011 khoùa khaùc nhau, vaø ñaây cuõng laø con soá lôùn hôn raát nhieàu dung löôïng cho pheùp cuûa moät boä nhôù toác ñoä cao. Tuy nhieân trong thöïc teá, chæ coù moät soá khoâng lôùn caùc khoùa naøy laø thöïc söï xuaát hieän. Ñieàu ñoù coù nghóa laø baûng chöùa seõ raát thöa thôùt. Chuùng ta coù theå xem baûng ñöôïc ñaùnh chæ soá baèng moät taäp raát lôùn, nhöng chæ coù moät soá töông ñoái ít vò trí laø thöïc söï coù phaàn töû. 12.5.1.2. Khaùi nieäm baêm Nhaèm traùnh moät baûng quaù thöa thôùt coù nhieàu vò trí khoâng bao giôø ñöôïc duøng ñeán, chuùng ta laøm quen vôùi khaùi nieäm baêm. YÙ töôûng cuûa baûng baêm (hình 12.10) laø cho pheùp aùnh xaï moät taäp caùc khoùa khaùc nhau vaøo caùc vò trí trong moät maûng vôùi kích thöôùc cho pheùp. Goïi kích thöôùc maûng naøy laø hash_size, moãi khoùa seõ ñöôïc aùnh xaï vaøo moät chæ soá trong khoaûng [0, hash_size-1]. Aùnh xaï naøy ñöôïc goïi laø haøm baêm (hash function). Moät caùch lyù töôûng, haøm naøy caàn coù caùch tính ñôn giaûn vaø phaân boå caùc khoùa sao cho hai khoùa khaùc nhau luoân vaøo hai vò trí khaùc nhau. Nhöng do kích thöôùc maûng laø giôùi haïn vaø mieàn trò cuûa caùc khoùa laø raát lôùn, ñieàu naøy laø khoâng theå ñöôïc. Chuùng ta chæ coù theå hy voïng raèng moät haøm baêm toát thì seõ phaân boå ñöôïc caùc khoùa vaøo caùc chæ soá moät caùch khaù ñoàng ñeàu vaø traùnh ñöôïc hieän töôïng gom tuï. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 317
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Haøm baêm noùi chung luoân aùnh xaï moät vaøi khoùa khaùc nhau vaøo cuøng moät chæ soá. Neáu phaàn töû caàn tìm ñang naèm taïi chæ soá ñöôïc aùnh xaï ñeán, vaán ñeà cuûa chuùng ta xem nhö ñaõ ñöôïc giaûi quyeát; ngöôïc laïi, chuùng ta caàn söû duïng moät phöông phaùp naøo ñoù ñeå giaûi quyeát ñuïng ñoä. Vieäc ñuïng ñoä (collision) xaûy ra khi hai phaàn töû caàn ñöôïc chöùa trong cuøng moät vò trí cuûa baûng. Treân ñaây laø yù töôûng cô baûn cuûa vieäc söû duïng baûng baêm. Coù ba vaán ñeà chuùng ta caàn xem xeùt khi söû duïng phöông phaùp baêm: • Tìm haøm baêm toát. • Xaùc ñònh phöông phaùp giaûi quyeát ñuïng ñoä. • Xaùc ñònh kích thöôùc baûng baêm. Hình 12.10 – Baûng baêm 12.5.2. Löïa choïn haøm baêm Hai tieâu chí cô baûn ñeå choïn löïa moät haøm baêm laø: • Haøm baêm caàn ñöôïc tính toaùn deã daøng vaø nhanh choùng. • Vieäc phaân phoái caùc khoùa coù theå xuaát hieän raûi ñeàu treân baûng baêm. Neáu chuùng ta bieát tröôùc chính xaùc nhöõng khoùa naøo seõ xuaát hieän, thì chuùng ta coù theå xaây döïng moät haøm baêm thaät hieäu quaû, nhöng noùi chung chuùng ta thöôøng khoâng bieát tröôùc ñieàu naøy. Chuùng ta caàn löu yù raèng moät haøm baêm khoâng heà coù tính ngaãu nhieân. Khi tính nhieàu laàn cho cuøng moät khoùa, moät haøm baêm phaûi cho cuøng moät trò, coù nhö vaäy thì khoùa môùi coù theå ñöôïc truy xuaát sau khi ñöôïc löu tröõ. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 318
- Chöông 12 – Baûng vaø truy xuaát thoâng tin 12.5.2.1. Chia laáy phaàn dö (modular arithmetic) Tröôùc heát chuùng ta haõy xem xeùt moät tröôøng hôïp thaät ñôn giaûn. Neáu caùc khoùa laø caùc soá nguyeân, haøm baêm ñôn giaûn vaø phoå bieán ñöôïc duøng laø pheùp chia cho hash_size ñeå laáy phaàn dö, vì nhö vaäy chuùng ta seõ coù caùc chæ soá thuoäc [0, hash_size -1]. Tuy nhieân cuõng caàn löu yù nhöõng tröôøng hôïp caùc khoùa taäp trung vaøo moät soá giaù trò ñaëc bieät naøo ñoù. Chaúng haïn neáu hash_size = 10, maø phaàn lôùn caùc khoùa laïi coù con soá ôû haøng ñôn vò laø 0. Söï phaân taùn caùc khoùa phuï thuoäc nhieàu vaøo pheùp chia laáy phaàn dö, ñoù chính laø kích thöôùc cuûa baûng baêm. Neáu kích thöôùc ñoù laø moät boäi soá cuûa caùc soá nguyeân nhoû nhö 2 hoaëc 10, thì raát nhieàu khoùa seõ cho cuøng chæ soá nhö nhau, trong khi ñoù coù moät soá chæ soá raát ít ñöôïc söû duïng ñeán. Caùch choïn pheùp chia laáy phaàn dö toát nhaát thöôøng laø chia cho moät soá nguyeân toá (nhöng khoâng phaûi laø luoân luoân), keát quaû seõ raûi ñeàu caùc khoùa trong baûng baêm hôn. Nhö vaäy, thay vì choïn baûng baêm kích thöôùc 1000, chuùng ta neân choïn kích thöôùc 997 hoaëc 1009; caùch choïn 210 = 1024 laø moät caùch choïn raát dôû. Thoâng thöôøng, caùc khoùa laø caùc chuoãi kyù töï. Moät caùch töï nhieân, ngöôøi ta thöôøng laáy moät soá nguyeân baèng vôùi toång cuûa caùc maõ ASCII cuûa caùc kyù töï trong khoùa laøm ñaïi dieän cho noù. Haøm baêm vôùi caùch vieát cuûa C chuaån sau ñaây thaät ñôn giaûn vaø tính cuõng raát nhanh: index Hash(const char *Key, int hash_size) { unsigned int HashVal = 0; while (*Key != ‘\0’) { HashVal += *Key; Key++; } return HashVal % hash_size; } Tuy nhieân, neáu hash_size lôùn, haøm seõ khoâng phaân boå caùc khoùa toát. Laáy ví duï vôùi hash_size =10007 (moät soá nguyeân toá). Giaû söû caùc khoùa coù chieàu daøi 8 kyù töï hoaëc ít hôn. Moãi kyù töï coù maõ ASCII
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Haøm naøy chæ quan taâm 3 kyù töï ñaàu cuûa caùc khoùa, nhöng neáu chuùng laø ngaãu nhieân vaø hash_size laø 10007 nhö treân, thì söï phaân boå khaù ñoàng ñeàu. Ñieàu khoâng may ôû ñaây laø caùc töø trong tieáng Anh khoâng phaûi laø moät söï gheùp caùc kyù töï moät caùch ngaãu nhieân. Maëc duø coù ñeán 263 = 17576 khaû naêng gheùp 3 kyù töï, thöïc teá trong töø ñieån cho thaáy chæ coù 2851 khaû naêng xaûy ra. Ngay caû khi khoâng coù söï ñuïng ñoä xaûy ra giöõa töøng caëp trong caùc khaû naêng naøy, thì cuõng chæ coù 28% vò trí trong baûng laø ñöôïc söû duïng. Theâm moät caûi tieán khaùc nhö sau ñaây: index Hash(const char *Key, int hash_size) { unsigned int HashVal = 0; while (*Key != ‘\0’) { HashVal = (HashVal
- Chöông 12 – Baûng vaø truy xuaát thoâng tin 12.5.2.3. Xaùo troän (folding) YÙ töôûng xaùo troän (folding) döôùi ñaây giuùp cho caùc boä phaän cuûa khoùa ñeàu coù theå tham gia vaøo vieäc xaùc ñònh keát quaû cuoái cuøng cuûa haøm baêm. Töø baêm ôû ñaây coù nghóa laø keát quaû sinh ra coù phaàn gioáng vôùi khoùa ban ñaàu. Ngoaøi ra, söï xaùo troän cho pheùp chuùng ta hy voïng raèng moïi khuoân maãu hoaëc söï laëp laïi coù theå xuaát hieän trong caùc khoùa (haäu quaû cuûa tính thieáu ngaãu nhieân cuûa döõ lieäu trong thöïc teá) seõ bò trieät tieâu. Coù nhö vaäy thì caùc keát quaû môùi ñöôïc phaân phoái theo cuøng moät quy luaät nhö nhau maø khoâng coù söï truøng laëp cuûa töøng nhoùm keát quaû vaø chuùng ta traùnh ñöôïc hieän töôïng gom tuï. ÔÛ ñaây chuùng ta thaáy raèng thuaät ngöõ “baêm” mang tính moâ taû roõ nhaát. Tuy nhieân trong moät soá taøi lieäu khaùc ngöôøi ta duøng caùc caùc töø mang tính kyõ thuaät hôn nhö “boä nhôù phaân taùn” (scatter-storage) hoaëc “pheùp bieán ñoåi khoùa” (key-transformation). Phöông phaùp xaùo troän chia khoùa laøm nhieàu phaàn vaø keát noái caùc phaàn naøy laïi theo moät caùch thích hôïp (thöôøng söû duïng pheùp coäng hoaëc pheùp nhaân). Laáy ví duï, moät soá nguyeân 8 kyù soá coù theå ñöôïc chia laøm 3 nhoùm goàm 3, 3, vaø 2 kyù soá, caùc nhoùm naøy ñöôïc coäng laïi vôùi nhau, sau ñoù coù theå ñöôïc caét xeùn bôùt neáu caàn thieát ñeå cho ra caùc chæ soá phuø hôïp kích thöôùc baûng baêm. Khoùa 21296876 seõ ñöôïc baêm thaønh 212 + 968 + 76 = 1256, caét ngaén coøn 256. Do moïi döõ lieäu trong khoùa ñeàu coù aûnh höôûng ñeán keát quaû haøm baêm neân phöông phaùp naøy laøm cho caùc khoùa raûi ñeàu treân baûng baêm hôn laø phöông phaùp caét xeùn neâu treân. Toùm laïi, chuùng ta ñaõ xem xeùt moät soá phöông phaùp maø chuùng ta coù theå keát hôïp laïi theo nhieàu caùch khaùc nhau ñeå xaây döïng haøm baêm. Laáy phaàn dö thöôøng laø moät caùch toát ñeå keát thuùc vieäc tính toaùn cuûa moät haøm baêm, do noù vöøa coù theå ñaït ñöôïc söï raûi ñeàu caùc khoùa trong baûng baêm vöøa baûo ñaûm keát quaû nhaän ñöôïc luoân naèm trong mieàn caùc chæ soá cho pheùp. 12.5.3. Phaùc thaûo giaûi thuaät cho caùc thao taùc döõ lieäu trong baûng baêm Tröôùc heát, chuùng ta caàn khai baùo moät maûng ñeå chöùa baûng baêm. Sau ñoù, caùc vò trí trong maûng caàn ñöôïc khôûi taïo laø troáng. Giaù trò khôûi taïo phuï thuoäc vaøo öùng duïng, thoâng thöôøng chuùng ta cho caùc vò trí troáng naøy chöùa moät giaù trò ñaëc bieät naøo ñoù. Chaúng haïn, vôùi caùc khoùa laø caùc chöõ caùi, moät trò chöùa toaøn kyù töï troáng coù theå bieåu dieãn moät vò trí troáng. Ñeå theâm moät phaàn töû vaøo baûng baêm, caàn tính haøm baêm cho khoùa cuûa noù. Neáu vò trí tìm thaáy coøn troáng, phaàn töû seõ ñöôïc theâm vaøo; neáu ñaõ coù phaàn töû taïi vò trí naøy vaø khoùa cuûa noù truøng vôùi khoùa cuûa phaàn töû caàn theâm thì vieäc theâm seõ khoâng ñöôïc thöïc hieän; tröôøng hôïp cuoái cuøng, neáu taïi vò trí tìm thaáy ñaõ coù moät phaàn töû nhöng cuûa moät khoùa khaùc, chuùng ta seõ aùp duïng moät phöông phaùp giaûi quyeát ñuïng ñoä naøo ñoù ñeå tìm ñeán moät vò trí khaùc cho vieäc theâm phaàn töû môùi cuûa chuùng ta. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 321
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Vieäc truy xuaát moät phaàn töû vôùi khoùa cho tröôùc ñöôïc laøm töông töï. Tröôùc tieân, haøm baêm ñöôïc tính cho khoùa cho tröôùc. Neáu phaàn töû caàn tìm ñang naèm taïi vò trí ñöôïc chæ bôûi haøm baêm, thì vieäc truy xuaát seõ ñöôïc thöïc hieän thaønh coâng; ngöôïc laïi, trong khi maø vò trí ñang xeùt khoâng troáng vaø moïi vò trí chöa ñöôïc xeùt ñeán, caàn tieán haønh caùc böôùc töông töï nhö caùc böôùc ñaõ ñöôïc söû duïng khi giaûi quyeát ñuïng ñoä trong quaù trình theâm vaøo. Neáu trong khi tìm kieám gaëp moät vò trí troáng, hoaëc khi moïi vò trí ñaõ ñöôïc xeùt ñeán, thì coù theå keát luaän vieäc tìm kieám thaát baïi: khoâng coù phaàn töû vôùi khoùa caàn tìm trong baûng baêm. 12.5.4. Ví duï trong C++ Nhö moät ví duï ñôn giaûn, chuùng ta seõ vieát moät haøm baêm trong C++ ñeå chuyeån ñoåi moät khoùa goàm 8 kyù töï chöõ caùi sang moät soá nguyeân trong mieàn 0 . . hash_size – 1. Chuùng ta coù moät lôùp Key vôùi caùc phöông thöùc nhö sau: class Key: public String{ public: char key_letter(int position) const; void make_blank(); // Caùc constructor vaø caùc phöông thöùc khaùc. }; Ñeå giaûm coâng söùc laäp trình khi hieän thöïc lôùp, chuùng ta choïn caùch thöøa keá caùc phöông thöùc cuûa lôùp String trong chöông 5. Chuùng ta seõ ñôõ phaûi vieát laïi caùc taùc vuï so saùnh. Phöông thöùc key_letter(int position) traû veà kyù töï taïi vò trí position trong khoùa, hoaëc traû veà khoaûng traéng neáu khoùa coù chieàu daøi nhoû hôn n. Phöông thöùc make_blank taïo moät khoùa troáng. int hash(const Key &target) /* post: Haøm baêm treân target traû veà trò trong mieàn 0 .. hash_size-1. uses: Caùc phöông thöùc cuûa lôùp Key. */ { int value = 0; for (int position = 0; position < 8; position++) value = 4 * value + target.key_letter(position); return value % hash_size; } Haøm baêm treân ñôn giaûn chæ coäng doàn caùc maõ cuûa moãi kyù töï trong khoùa sau khi ñaõ nhaân vôùi 4. Chuùng ta khoâng theå lyù giaûi ñöôïc raèng phöông phaùp naøy laø toát hôn (hoaëc xaáu hôn) moät vaøi phöông phaùp khaùc. Chuùng ta cuõng coù theå laáy maõ cuûa kyù töï tröø ñi moät soá naøo ñoù, roài nhaân töøng caëp vôùi nhau, hoaëc boû qua moät vaøi kyù töï naøo Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 322
- Chöông 12 – Baûng vaø truy xuaát thoâng tin ñoù. Ñoâi khi moät öùng duïng seõ cho thaáy moät haøm baêm naøy laø toát hôn moät haøm baêm khaùc, ñoâi khi caàn phaûi coù söï khaûo saùt baèng thöïc nghieäm môùi chæ ra ñöôïc haøm naøo laø toát hôn. 12.5.5. Giaûi quyeát ñuïng ñoä baèng phöông phaùp ñòa chæ môû Coù hai nhoùm phöông phaùp giaûi quyeát ñuïng ñoä: nhoùm phöông phaùp ñòa chæ môû vaø nhoùm phöông phaùp noái keát. Nhoùm phöông phaùp ñòa chæ môû chæ söû duïng caùc maûng caáp phaùt tónh. Nhoùm phöông phaùp noái keát coù söû duïng nhöõng vuøng nhôù caáp phaùt ñoäng ñöôïc quaûn lyù bôûi caùc con troû noái keát. Döôùi ñaây laø caùc phöông phaùp duøng ñòa chæ môû. 12.5.5.1. Thöû tuyeán tính Phöông phaùp ñôn giaûn nhaát ñeå giaûi quyeát ñuïng ñoä laø baét ñaàu töø vò trí traû veà töø haøm baêm coù xaûy ra ñuïng ñoä, vieäc tìm kieám seõ tieáp tuïc moät caùch tuaàn töï ôû caùc vò trí keá trong baûng cho ñeán khi gaëp khoùa mong muoán hoaëc moät vò trí troáng. Phöông phaùp naøy ñöôïc goïi laø phöông phaùp thöû tuyeán tính (linear probing). Baûng ñöôïc xem nhö moät maûng voøng, khi vieäc tìm kieám ñaït ñeán vò trí cuoái cuûa baûng thì seõ quay veà vò trí ñaàu cuûa baûng. Hieän töôïng gom tuï Nhöôïc ñieåm chính cuûa phöông phaùp thöû tuyeán tính laø khi coù khoaûng moät nöûa soá vò trí trong baûng ñaõ chöùa döõ lieäu, khuynh höôùng gom tuï seõ xuaát hieän; nghóa laø, caùc phaàn töû seõ naèm trong caùc chuoãi lieân tuïc caùc vò trí, giöõa caùc chuoãi naøy laø nhöõng loã hoång. Vieäc tìm kieám tuaàn töï moät vò trí troáng trong baûng seõ ngaøy caøng laâu hôn. Chuùng ta haõy xem ví duï ôû hình 12.11. Giaû söû maûng coù n vò trí thì xaùc suaát maø haøm baêm choïn moät vò trí naøo ñoù laø 1/n. Ban ñaàu vieäc phaân phoái ñöôïc thöïc hieän khaù ñeàu trong baûng (phaàn treân cuûa hình). Giaû söû caàn theâm döõ lieäu môùi maø haøm baêm traû veà vò trí b thì döõ lieäu ñöôïc theâm vaøo taïi ñaây, nhöng neáu haøm baêm traû veà vò trí a maø vò trí naøy ñaõ coù döõ lieäu, vieäc theâm vaøo seõ ñöôïc thöïc hieän taïi b. Nhö vaäy xaùc suaát ñeå vò trí b nhaän döõ lieäu laø 2/n. Taïi böôùc tieáp theo, khi döõ lieäu caàn theâm vaøo moät trong caùc vò trí a, b, c, hoaëc d thì choã troáng thöïc söï ñeå theâm vaøo chæ laø d, nhö vaäy xaùc suaát döõ lieäu theâm vaøo d laø 4/n. Sau ñoù, xaùc suaát döõ lieäu theâm vaøo vò trí e laïi laø 5/n. Vaø cöù nhö theá, khi döõ lieäu caøng ñöôïc theâm vaøo nhieàu thì chuoãi lieân tuïc caùc vò trí ñaõ coù döõ lieäu baét ñaàu töø a ngaøy caøng daøi ra. Nhö vaäy caùch thöïc hieän cuûa baûng baêm baét ñaàu suy thoaùi daàn tôùi söï tìm kieám tuaàn töï. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 323
- Chöông 12 – Baûng vaø truy xuaát thoâng tin Hình 12.11 – Hieän töôïng gom tuï trong baûng baêm. Hieän töôïng gom tuï chính laø nguyeân nhaân cuûa tính thieáu oån ñònh. Neáu moät soá ít caùc khoùa ngaãu nhieân naèm keá nhau, thì sau ñoù caùc khoùa khaùc boãng trôû neân keát dính vôùi chuùng, coù nghóa laø vò trí chöùa chuùng phuï thuoäc laãn nhau, vaø söï phaân phoái daàn daàn trôû neân thieáu caân baèng. 12.5.5.2. Haøm gia taêng Ñeå traùnh hieän töôïng gom tuï, chuùng ta phaûi söû duïng phöông phaùp phöùc taïp hôn ñeå choïn ra chuoãi caùc vò trí caàn xem xeùt ñeán ñeå theâm moät döõ lieäu môùi naøo ñoù khi coù xaûy ra ñuïng ñoä. Coù nhieàu caùch ñeå thöïc hieän. YÙ töôûng chung laø söû duïng moät hoaëc moät vaøi haøm gia taêng ñeå xaùc ñònh khoaûng caùch töø vò trí vöøa ñuïng ñoä ñeán moät vò trí môùi. Caàn löu yù raèng keát quaû cuûa haøm gia taêng khoâng ñöôïc pheùp traû veà trò 0. Haøm gia taêng coù theå phuï thuoäc vaøo khoùa, hoaëc vaøo soá laàn ñaõ thöû, sao cho coù theå traùnh ñöôïc hieän töôïng gom tuï. Tröôøng hôïp thöù nhaát, khi haøm gia taêng phuï thuoäc vaøo khoùa, chuùng ta coù khaùi nieäm baêm laïi. Ñoù laø caùch söû duïng moät haøm baêm thöù hai. Keát quaû cuûa haøm baêm naøy laø soá vò trí caàn di chuyeån keå töø vò trí ñaõ bò ñuïng ñoä tröôùc ñoù. Neáu vò trí naøy laïi ñuïng ñoä, chuùng ta laïi duøng moät haøm baêm khaùc nöõa ñeå tìm ñeán vò trí thöù ba, vaø cöù theá. Cuõng coù khi töø keát quaû tính cuûa haøm baêm thöù hai ngöôøi ta duøng luoân soá naøy ñeå di chuyeån giöõa hai laàn thöû keá tieáp. Trong tröôøng hôïp thöù hai, haøm gia taêng phuï thuoäc vaøo soá laàn ñaõ thöû, coù theå keå ra ñaây phöông phaùp thöû baäc hai. Thöû baäc hai Neáu coù söï ñuïng ñoä taïi ñòa chæ baêm ñöôïc h, phöông phaùp thöû baäc hai (quadratic probing) thöû caùc vò trí keá tieáp laø h+1, h+4, h+9, ... trong baûng, coù nghóa laø caùc vò trí h + i2, vôùi i laø laàn thöû. Noùi caùch khaùc, haøm gia taêng laø i2. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 324
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Đề thi cấu trúc dữ liệu và giải thuật có đáp án (2007-2008)
17 p |
3042 |
873
-
Chương 1: Nhập môn cấu trúc dữ liệu
33 p |
427 |
171
-
Các cấu trúc dữ liệu
7 p |
218 |
125
-
Cấu trúc dữ liệu 2005 P18
16 p |
92 |
23
-
Cấu trúc dữ liệu 2005 P15
10 p |
75 |
20
-
Cấu trúc dữ liệu 2005 P17
6 p |
73 |
17
-
Cấu trúc dữ liệu 2005 P16
8 p |
88 |
17
-
Cấu trúc dữ liệu 2005 P14
12 p |
72 |
17
-
Cấu trúc dữ liệu 2005 P10
46 p |
68 |
13
-
Cấu trúc dữ liệu 2005 P11
22 p |
50 |
12
-
Cấu trúc dữ liệu 2005 P9
54 p |
88 |
12
-
Cấu trúc dữ liệu 2005 P13
26 p |
81 |
9
-
Cấu trúc dữ liệu 2005 P5
16 p |
43 |
9
-
Cấu trúc dữ liệu 2005 P4
24 p |
39 |
9
-
Cấu trúc dữ liệu 2005 P6
46 p |
38 |
7
-
Cấu trúc dữ liệu 2005 P3
14 p |
27 |
7
-
Cấu trúc dữ liệu 2005 P7
12 p |
29 |
6

Set-Cookie: TLDEVNamespace=lmbsgtddbtuepi1psa010lhqa6; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Mâu thuẫn trong doanh nghiệp: Làm sao để giải quyết?
Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:7
lượt xem 68
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20100701/maybay_thaboom/80x100/mau_thuan_trong_dn_7736.jpg)
##
Mâu thuẫn trong doanh nghiệp: Làm sao để giải quyết?
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Tuy nhiên, cũng cần biết rằng tất cả các tổ chức, trong đó có doanh nghiệp, đều cần có xung đột và mâu thuẫn. Vấn đề là có quá ít hay quá nhiều xung đột. Vì thế cần học cách để giải quyết xung đột chứ không phải là loại trừ. Nên nhớ rằng doanh nghiệp cần tạo áp lực với số lượng lớn xung đột và mâu thuẫn phù hợp. Nếu có quá nhiều mâu thuẫn và xung đột thì chúng sẽ tàn phá doanh nghiệp và nhân lực. Mâu thuẫn, xung đột có lợi và có hại Cần phân biệt những mâu...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: application/xhtml+xml

Server: Apache/2.2.31 (CentOS)

Connection: close

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Set-Cookie: TLDEVNamespace=6aenfh8nih00o1hb7d948d0hm3; path=/; domain=.tailieu.vn; HttpOnly

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8


markdown:
# Pháp lệnh số 04/2008/PL-UBTVQH12 của Uỷ ban Thường vụ Quốc hội
Chia sẻ: My Ngoc | Ngày: | Loại File: PDF | Số trang:24
523
lượt xem 95
download
lượt xem 95
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20090813/myngoc/80x100/08000282.jpg)
##
Pháp lệnh số 04/2008/PL-UBTVQH12 của Uỷ ban Thường vụ Quốc hội
Mô tả tài liệu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Pháp lệnh sửa đổi bổ sung một số điều của Pháp lệnh xử lý vi phạm hành chính của Uỷ ban Thường vụ Quốc hội số 04/2008/PL-UBTVQH12
Chủ đề:
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

Set-Cookie: TLDEVNamespace=pamd5td5ha3n8hip9i68ppovc3; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Phương pháp đánh giá 360 độ
Chia sẻ: Angle Angel | Ngày: | Loại File: PDF | Số trang:2
239
lượt xem 103
download
lượt xem 103
download
![](http://image1.tailieu.vn/document/thumbnail/2010/20100816/angel_ko_co_canh/80x100/phuong_phap_danh_gia_360_do_571.jpg)
##
Phương pháp đánh giá 360 độ
Mô tả tài liệu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Tham khảo tài liệu 'phương pháp đánh giá 360 độ', kỹ năng mềm, kỹ năng quản lý phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Chủ đề:
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

Set-Cookie: TLDEVNamespace=1lrjrthk91uge21nc66dchodf3; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Physics exercises_solution: Chapter 04
Chia sẻ: Thanh An | Ngày: | Loại File: PDF | Số trang:21
lượt xem 25
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20090722/thanhan/80x100/chapter_04_2404.jpg)
##
Physics exercises_solution: Chapter 04
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Bộ tài liệu bài tập tham khảo môn vật lý bậc đại học bằng tiếng anh Chapter 04
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Physics exercises_solution: Chapter 04
- 4.1: a) For the magnitude of the sum to be the sum of the magnitudes, the forces must be parallel, and the angle between them is zero. b) The forces form the sides of a right isosceles triangle, and the angle between them is 90 . Alternatively, the law of cosines may be used as 2 F 2 F 2 2 F 2 F 2 cos , from which cos 0 , and the forces are perpendicular. c) For the sum to have 0 magnitude, the forces must be antiparallel, and the angle between them is 180 . 4.2: In the new coordinates, the 120-N force acts at an angle of 53 from the x -axis, or 233 from the x -axis, and the 50-N force acts at an angle of 323 from the x - axis. a) The components of the net force are R x (120 N) cos 233 (50 N) cos 323 32 N R y (250 N) (120 N) sin 233 (50 N) sin 323 124 N. b) R Rx Ry 128 N, arctan 124 104 . The results have the same magnitude, 2 2 32 and the angle has been changed by the amount (37) that the coordinates have been rotated. 4.3: The horizontal component of the force is (10 N) cos 45 7.1 N to the right and the vertical component is (10 N) sin 45 7.1 N down. 4.4: a) Fx F cos , where is the angle that the rope makes with the ramp ( θ 30 in F this problem), so F F cosx cos.030 69.3 N. 60 N b) Fy F sin θ Fx tan θ 34.6 N.
- 4.5: Of the many ways to do this problem, two are presented here. Geometric: From the law of cosines, the magnitude of the resultant is R (270 N) 2 (300 N) 2 2(270 N)(300 N) cos 60 494 N. The angle between the resultant and dog A’s rope (the angle opposite the side corresponding to the 250-N force in a vector diagram) is then sin 120(300 N) arcsin 31.7. 494 N Components: Taking the x -direction to be along dog A’s rope, the components of the resultant are Rx (270 N) (300 N) cos 60 420 N R y (300 N) sin 60 259.8 N, so R (420 N) 2 (259.8 N) 2 494 N, θ arctan 259.8 31.7. 420 4.6: a) F1x F2 x (9.00 N) cos 120 (6.00 N) cos (126.9) 8.10 N F1 y F2 y (9.00 N) sin 120 (6.00 N) sin (126.9) 3.00 N. b) R Rx2 Ry (8.10 N) 2 (3.00 N) 2 8.64 N. 2 4.7: a F / m (132 N) / (60 kg) 2.2 m / s 2 (to two places). 4.8: F ma (135 kg)(1.40 m/s 2 ) 189 N. 4.9: m F / a (48.0 N)/(3.00 m/s 2 ) 16.00 kg. 4.10: a) The acceleration is a 2x t2 2 (11.0 m ) (5.00 s) 2 0.88 m / s 2 . The mass is then m F a 80.0 N 0.88 m/s 2 90.9 kg. b) The speed at the end of the first 5.00 seconds is at 4.4 m/s , and the block on the frictionless surface will continue to move at this speed, so it will move another vt 22.0 m in the next 5.00 s.
- 4.11: a) During the first 2.00 s, the acceleration of the puck is F / m 1.563 m/s2 (keeping an extra figure). At t 2.00 s , the speed is at 3.13 m/s and the position is at 2 / 2 vt / 2 3.13 m . b) The acceleration during this period is also 1.563 m/s2 , and the speed at 7.00 s is 3.13 m/s (1.563 m/s 2 )(2.00 s) 6.26 m/s . The position at t 5.00 s is x 3.13 m (3.13 m/s)(5.00 s 2.00 s) 125 m , and at t 7.00 s is 12.5 m (3.13 m/s)(2.00 s) (1/2)(1.563 m/s 2 )(2.00 s) 2 21.89 m, or 21.9 m to three places. 4.12: a) a x F / m 140 N / 32.5 kg 4.31 m/s 2 . b) With v0 x 0, x 1 at 2 215 m . 2 c) With v0 x 0, vx axt 2 x / t 43.0 m/s . 4.13: a) F 0 b), c), d) 4.14: a) With v0 x 0 , vx (3.00 106 m/s) 2 2 ax 2.50 1014 m/s 2 . 2 x 2(1.80 10 2 m) 3.0010 6 m / s 1.20 108 s . Note that this time is also the distance divided by vx b) t ax 2.501014 m / s 2 the average speed. c) F ma (9.11 1031 kg)(2.50 1014 m/s 2 ) 2.28 1016 N. 4.15: F ma w(a / g ) (2400 N)(12 m/s 2 )(9.80 m/s 2 ) 2.94 103 N. F F F 160 4.16: a g (9.80 m/s ) 22.0 m/s . 2 2 m w/ g w 71.2 4.17: a) m w / g (44.0 N) /(9.80 m/s 2 ) 4.49 kg b) The mass is the same, 4.49 kg, and the weight is (4.49 kg)(1.81 m/s 2 ) 8.13 N.
- 4.18: a) From Eq. (4.9), m w / g (3.20 N) /(9.80 m / s 2 ) 0.327 kg. b) w mg (14.0 kg)(9.80 m / s 2 ) 137 N. 4.19: F ma (55 kg)(15 m / s 2 ) 825 N. The net forward force on the sprinter is exerted by the blocks. (The sprinter exerts a backward force on the blocks.) 4.20: a) the earth (gravity) b) 4 N, the book c) no d) 4 N, the earth, the book, up e) 4 N, the hand, the book, down f) second g) third h) no i) no j) yes k) yes l) one (gravity) m) no 4.21: a) When air resistance is not neglected, the net force on the bottle is the weight of the bottle plus the force of air resistance. b) The bottle exerts an upward force on the earth, and a downward force on the air. 4.22: The reaction to the upward normal force on the passenger is the downward normal force, also of magnitude 620 N, that the passenger exerts on the floor. The reaction to the passenger’s weight is the gravitational force that the passenger exerts on the earth, upward and also of magnitude 650 N. 620 N650 N 0.452 m/s 2 . The passenger’s F m 650 N /9.80 m/s 2 acceleration is 0.452 m / s 2 , downward. F mg (45 kg)(9.80 m / s 2 ) 4.23: aE 7.4 10 23 m / s 2 . mE mE (6.0 10 kg) 24
- 4.24: (a) Each crate can be considered a single particle: FAB (the force on mA due to mB ) and FBA (the force on mB due to mA ) form an action-reaction pair. (b) Since there is no horizontal force opposing F, any value of F, no matter how small, will cause the crates to accelerate to the right. The weight of the two crates acts at a right angle to the horizontal, and is in any case balanced by the upward force of the surface on them. 4.25: The ball must accelerate eastward with the same acceleration as the train. There must be an eastward component of the tension to provide this acceleration, so the ball hangs at an angle relative to the vertical. The net force on the ball is not zero.
- 4.26: The box can be considered a single particle. For the truck: The box’s friction force on the truck bed and the truck bed’s friction force on the box form an action-reaction pair. There would also be some small air-resistance force action to the left, presumably negligible at this speed.
- 4.27: a) b) For the chair, a y 0 so Fy ma y gives n mg F sin 37 0 n 142 N 4.28: a) b) T mg sin (65.0 kg)(9.80 m / s 2 ) sin 26.0 279 N
- 4.29: tricycle and Frank T is the force exerted by the rope and f g is the force the ground exerts on the tricycle. spot and the wagon T is the force exerted by the rope. T and T form a third-law action-reaction pair, T T . 4.30: a) The stopping time is x vave x ( v0 / 2 ) 2 ( 0.130 m ) 350 m / s 7.43 10 4 s. b) F ma (1.80 10 3 kg ) (7.4310-/4s )s) 848 N. (Using a v0 / 2 x gives the same ( 350 m 2 result.) 4.31: Take the x -direction to be along F1 and the y -direction to be along R . Then F2 x 1300 N and F2 y 1300 N , so F2 1838 N , at an angle of 135 from F1 . 4.32: Get g on X: 1 2 y gt 2 1 10.0 m g (2.2 s) 2 2 g 4.13 m / s 2 wX mg X (0.100 kg)(4.03 m / s 2 ) 0.41 N
- 4.33: a) The resultant must have no y-component, and so the child must push with a force with y-component (140 N) sin 30 (100 N) sin 60 16.6 N. For the child to exert the smallest possible force, that force will have no x-component, so the smallest possible force has magnitude 16.6 N and is at an angle of 270 , or 90 clockwise from the x -direction. b) m 100 N cos260m1402 N cos 30 85.6 kg. w mg (85.6 kg)(9.80 m / s 2 ) 840 N. . F a .0 / s 4.34: The ship would go a distance v02 v02 mv 2 (3.6 107 kg)(1.5 m / s) 2 0 506.25 m, 2a 2( F / m) 2 F 2(8.0 104 N) so the ship would hit the reef. The speed when the tanker hits the reef is also found from 2(8.0 104 N)(500 m) v v0 (2 Fx / m) (1.5 m/s)2 2 0.17 m/s, (3.6 107 kg) so the oil should be safe. 4.35: a) Motion after he leaves the floor: v y v0 y 2a y ( y y0 ). 2 2 v y 0 at the maximum height, y y 0 1.2 m, a y 9.80 m/s 2 , so v0 y 4.85 m/s. b) a av v / t (4.85 m / s) /(0.300 s) 16.2 m/s 2 . c) Fav w maav Fav w ma av 890 N (890 N / 9.80 m / s 2 )(16.2 m / s 2 ) Fav 2.36 10 3 N 4.36: 2 v0 (12.5 m / s) 2 F ma m (850 kg) 2 3.7 10 6 N. 2x 2(1.8 10 m)
- 4.37: a) Fnet F mg (upward) b) When the upward force has its maximum magnitude Fmax (the breaking strength), the net upward force will be Fmax mg and the upward acceleration will be F mg Fmax 75.0 N a max g 9.80 m / s 2 5.83 m / s 2 . m m 4.80 kg 4.38: a) w mg 539 N b) Downward velocity is decreasing so a is upward and the net force should be upward. Fair mg , so the net force is upward. c) Taking the upward direction as positive, the acceleration is F F mg Fair 620 N a air 9.80 m / s 2 9.80 m / s 2 1.47 m / s 2 . m m m 55.0 kg
- 4.39: a) Both crates moves together, so a 2.50 m / s 2 b) T m1 a (4.00 kg )(2.50 m / s 2 ) 10.0 N c) r F T and the net force is to the right, in the direction of a . d) F T m2 a F T m2 a 10.0 N (6.00 kg)(2.50 m / s 2 ) 25.0 N 4.40: a) The force the astronaut exerts on the rope and the force that the rope exerts on the astronaut are an action-reaction pair, so the rope exerts a force of 80.0 N on the astronaut. b) The cable is under tension. c) a m 105.0 N 0.762 m / s 2 . d) There is no F 80.0 kg net force on the massless rope, so the force that the shuttle exerts on the rope must be 80.0 N (this is not an action-reaction pair). Thus, the force that the rope exerts on the shuttle must be 80.0 N. e) a m 9.05.10Nkg 8.84 10 4 m / s 2 . F 80 0 4 4.41: a) x (0.025 s) (9.0 10 3 m / s 2 )(0.025 s) 2 (8.0 10 4 m / s 3 )(0.025 s) 3 4.4 m. b) Differentiating, the velocity as a function of time is v(t ) (1.80 10 4 m / s 2 )t (2.40 10 5 m / s 3 )t 2 , so v(0.025 s) (1.80 10 4 m / s 2 )(0.025 s) (2.40 10 5 m / s 3 )(0.025 s) 2 3.0 10 2 m / s. c) The acceleration as a function of time is a (t ) 1.80 104 m / s 2 (4.80 105 m / s 3 ) t , so (i) at t 0, a 1.8 10 4 m / s 2 , and (ii) a (0.025 s) 6.0 103 m / s 2 , and the forces are (i) ma 2.7 104 N and (ii) ma 9.0 103 N.
- 4.42: a) The velocity of the spacecraft is downward. When it is slowing down, the acceleration is upward. When it is speeding up, the acceleration is downward. b) speeding up: w F and the net force is downward slowing down: w F and the net force is upward c) Denote the y-component of the acceleration when the thrust is F1 by a1 and the y- component of the acceleration when the thrust is F2 by a2 . The forces and accelerations are then related by F1 w ma1 , F2 w ma2 . Dividing the first of these by the second to eliminate the mass gives F1 w a1 , F2 w a2 and solving for the weight w gives a F a2 F1 w 1 2 . a1 a2 In this form, it does not matter which thrust and acceleration are denoted by 1 and which by 2, and the acceleration due to gravity at the surface of Mercury need not be found. Substituting the given numbers, with y upward, gives (1.20 m / s 2 )(10.0 10 3 N) (0.80 m / s 2 )(25.0 10 3 N) w 16.0 10 3 N. 1.20 m / s (0.80 m / s ) 2 2 In the above, note that the upward direction is taken to be positive, so that a2 is negative. Also note that although a2 is known to two places, the sums in both numerator and denominator are known to three places.
- 4.43: a) The engine is pulling four cars, and so the force that the engine exerts on the first car is 4m a . b), c), d): Similarly, the forces the cars exert on the car behind are 3m a , 2m a and m a . e) The direction of the acceleration, and hence the direction of the forces, would change but the magnitudes would not; the answers are the same. 4.44: a) If the gymnast climbs at a constant rate, there is no net force on the gymnast, so the tension must equal the weight; T mg . b) No motion is no acceleration, so the tension is again the gymnast’s weight. c) T w T mg ma m a (the acceleration is upward, the same direction as the tension), so T m( g a ) . d) T w T mg ma m a (the acceleration is downward, the same opposite as the tension), so T m( g a ) . 4.45: a) The maximum acceleration would occur when the tension in the cables is a maximum, Fnet T mg T 28,000 N a g 9.80 m / s 2 2.93 m / s 2 . m m m 2200 kg 28,000 N b) 1.62 m / s 2 11.1 m / s 2 . 2200 kg
- 4.46: a) His speed as he touches the ground is v 2 gh 2(9.80 m / s 2 )(3.10 m) 7.80 m / s. b) The acceleration while the knees are bending is v 2 (7.80 m / s) 2 a 50.6 m / s 2 . 2y 2(0.60 m) c) The net force that the feet exert on the ground is the force that the ground exerts on the feet (an action-reaction pair). This force is related to the weight and acceleration by F w F mg ma, so F m(a g ) (75.0 kg)(50.6 m / s 2 9.80 m / s 2 ) 4532 N . As a fraction of his weight, this force is mg a 1 6.16 (keeping an extra figure in the F g intermediate calculation of a). Note that this result is the same algebraically as 3.10 m 0.60 m 1 . 4.47: a) b) The acceleration of the hammer head will be the same as the nail, a v0 / 2 x (3.2 m / s) 2 / 2(0.45 cm) 1.138 103 m / s 2 . The mass of the hammer head is 2 its weight divided by g , 4.9 N / 9.80 m / s 2 0.50 kg , and so the net force on the hammer head is (0.50 kg)(1.138 10 3 m / s 2 ) 570 N. This is the sum of the forces on the hammer head; the upward force that the nail exerts, the downward weight and the downward 15-N force. The force that the nail exerts is then 590 N, and this must be the magnitude of the force that the hammer head exerts on the nail. c) The distance the nail moves is .12 m, so the acceleration will be 4267 m / s 2 , and the net force on the hammer head will be 2133 N. The magnitude of the force that the nail exerts on the hammer head, and hence the magnitude of the force that the hammer head exerts on the nail, is 2153 N, or about 2200 N.
- 4.48: a) The net force on a point of the cable at the top is zero; the tension in the cable must be equal to the weight w. b) The net force on the cable must be zero; the difference between the tensions at the top and bottom must be equal to the weight w, and with the result of part (a), there is no tension at the bottom. c) The net force on the bottom half of the cable must be zero, and so the tension in the cable at the middle must be half the weight, w / 2 . Equivalently, the net force on the upper half of the cable must be zero. From part (a) the tension at the top is w, the weight of the top half is w / 2 and so the tension in the cable at the middle must be w w/ 2 w/ 2 . d) A graph of T vs. distance will be a negatively sloped line. 4.49: a) b) The net force on the system is 200 N (15.00 kg)(9.80 m / s 2 ) 53.0 N (keeping three figures), and so the acceleration is (53.0 N) /(15.0 kg) 3.53 m / s 2 , up. c) The net force on the 6-kg block is (6.00 kg)(3.53 m / s 2 ) 21.2 N , so the tension is found from F T mg 21.2 N , or T (200 N) (6.00 kg)(9.80 m / s 2 ) 21.2 N 120 N . Equivalently, the tension at the top of the rope causes the upward acceleration of the rope and the bottom block, so T (9.00 kg ) g (9.00 kg ) a , which also gives T 120 N . d) The same analysis of part (c) is applicable, but using 6.00 kg 2.00 kg instead of the mass of the top block, or 7.00 kg instead of the mass of the bottom block. Either way gives T 93.3 N .
- 4.50: a) b) The athlete’s weight is mg (90.0 kg)(9.80 m / s 2 ) 882 N . The acceleration of the barbell is found from vav 0.60 m / 1.6 s 0.375 m / s . Its final velocity is thus (2)(0375 ms) 0750 ms , and its acceleration is v v0 0.750 m / s a 0.469 m / s 2 t 1.65 The force needed to lift the barbell is given by: Fnet Flift wbarbell ma The barbell’s mass is (490 N) (980 ms 2 ) 500 kg , so Flift wbarbell ma 490 N (50.0 kg)(0.469 m / s 2 ) 490 N 23 N 513 N The athlete is not accelerating, so: Fnet Ffloor Flift wathlete 0 Ffloor Flift wathlete 513 N 882 N 1395 N
- 4.51: a) L is the lift force b) Fy ma y Mg L M ( g / 3) L 2Mg / 3 c) L mg m(g / 2) , where m is the mass remaining. L 2Mg / 3 , so m 4M / 9 . Mass 5M / 9 must be dropped overboard.
- 4.52: a) m mass of one link The downward forces of magnitude 2ma and ma for the top and middle links are the reaction forces to the upward force needed to accelerate the links below. b) (i) The weight of each link is mg (0.300 kg)(9.80 m / s 2 ) 2.94 N . Using the free- body diagram for the whole chain: F 12 N 3(2.94 N) 3.18 N a net 3.53 m / s 2 or 3.5 m / s 2 3m 0.900 kg 0.900 kg (ii) The second link also accelerates at 3.53 m / s 2 , so: Fnet Ftop ma 2mg ma Ftop 2ma 2mg 2(0.300 kg )(3.53 m / s 2 ) 2(2.94 N ) 2.12 N 5.88 N 8.0 N 4.53: Differentiating twice, the acceleration of the helicopter as a function of time is ˆ ˆ a (0.120 m / s 3 )ti (0.12 m / s 2 )k , and at t 50s , the acceleration is ˆ ˆ a (0.60 m / s 2 )i (0.12 m / s 2 )k . The force is then w (2.75 10 5 N) F ma a g 2 (9.80 m / s ) ˆ ˆ (0.60 m / s 2 )i (0.12 m / s 2 )k ˆ ˆ (1.7 10 N)i (3.4 10 3 N)k. 4
- 4.54: The velocity as a function of time is v(t ) A 3Bt 2 and the acceleration as a function of time is a(t ) 6 Bt , and so the Force as a function of time is F (t ) ma(t ) 6mBt . 4.55: 1 t 1 ˆ k 2 4 ˆ v (t ) a dt k1ti t j. m 0 m 4
- 4.56: a) The equation of motion, Cv 2 m dv cannot be integrated with respect to time, dt as the unknown function v(t ) is part of the integrand. The equation must be separated before integration; that is, C dv dt 2 m v Ct 1 1 , m v v0 where v0 is the constant of integration that gives v v0 at t 0 . Note that this form shows that if v0 0 , there is no motion. This expression may be rewritten as 1 dx 1 Ct v , dt v0 m which may be integrated to obtain m Ctv0 x x0 ln 1 . C m To obtain x as a function of v, the time t must be eliminated in favor of v; from the expression obtained after the first integration, Ctv0 vv0 1 , so m m v0 x x0 ln . C v b) By the chain rule, dv dv dv dv v, dt dx dt dx and using the given expression for the net force, dv Cv 2 v m dx C dv dx m v C v ( x x0 ) ln v m 0 m v0 x x0 ln . C v
CÓ THỂ BẠN MUỐN DOWNLOAD
-
ĐỀ ÔN TỐT NGHIỆP THPT MÔN ANH VĂN - 04
5 p |
234 |
180
-
Đề thi thử CĐ ĐH năm 2010 môn Anh văn mã đề 04
9 p |
246 |
98
-
ỨNG DỤNG PHẦN MỀM CROCODILE PHYSICS VÀO THIẾT KẾ BÀI GIẢNG BÀI “THẤU KÍNH MỎNG”CHƯƠNG TRÌNH VẬT LÝ LỚP 11 NÂNG CAO
6 p |
238 |
79
-
Giải phương trình lượng giác 27.04 (Bài tập và hướng dẫn giải)
10 p |
198 |
60
-
Đề và đáp án thi thử đại học môn Toán 2010_số 04
5 p |
97 |
50
-
Physics exercises_solution: Chapter 03
41 p |
120 |
34
-
Thông tư số 15/2009/TT-BTTTT ngày 04/05/2009 Quy định về việc tổ chức Liên hoan phát thanh, truyền hình
4 p |
169 |
29
-
Đề bài tập trong sách 200 Puzzling Problems in Physics
2 p |
172 |
23
-
Physics exercises_solution: Chapter 05
49 p |
89 |
17
-
Tuyển sinh vào lớp 9 Chuyên Nguyễn Trãi Hải Dương 04-05
3 p |
58 |
10
-
Chapter VIII Dielectrics
15 p |
59 |
8
-
Đề thi thử đại học tham khảo môn Toán, khối A tỉnh Lâm Đồng (Đề 04)
6 p |
82 |
7
-
Đề 04 - Luyện thi tú tài và ĐH-CĐ năm 2008
4 p |
66 |
5
-
Đề thi thử sức trước kì thi tuyển sinh vào lớp 10 môn Toán - Đề số 04
4 p |
21 |
2
-
Tuyển sinh vào Chuyên Hải Phòng - 04-05
2 p |
31 |
1
-
Đề thi thử đại học năm 2012 môn: Toán - Đề số 04
1 p |
9 |
1
-
Đề thi môn Toán - Đề số 04
1 p |
9 |
1

Set-Cookie: TLDEVNamespace=44nt6385pltpsm7lbk1c1gj830; path=/; domain=.tailieu.vn; HttpOnly