Bài t p 9
ậ
Nhi u d ng m u đ duy t m ng mà ta đã g p cũng có th đ
c vi t theo cách đ quy. Đó
ề
ạ
ẫ
ể
ệ
ả
ặ
ể ượ
ế
ệ
không ph i là cách th
ng dùng, nh ng là m t bài t p h u ích.
ả
ườ
ư
ộ
ậ
ữ
1.
Hãy vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
maxInRange, nh n vào m t m ng s nguyên mà m t kho ng ch s
ậ
ộ
ả
ố
ộ
ả
ỉ ố
(lowIndex và highIndex), r i tìm giá tr l n nh t trong m ng, nh ng ch xét nh ng ph n t
ồ
ị ớ
ấ
ả
ư
ỉ
ữ
ầ ử
gi a
ữ lowIndex và highIndex, k c hai đ u này. Ph ng th c ph i đ c vi t theo cách đ quy. N u chi u
ể ả
ầ
ươ
ứ
ả ượ
ế
ệ
ế
ề
dài c a kho ng b ng 1, nghĩa là n u
ủ
ả
ằ
ế lowIndex == highIndex, thì ta bi t ngay r ng ph n t duy nh t
ế
ằ
ầ ử
ấ
trong kho ng ph i là giá tr l n nh t. Do đó đây là tr
ng h p c s . N u có nhi u ph n t trong
ả
ả
ị ớ
ấ
ườ
ợ ơ ở ế
ề
ầ ử
kho ng, thì ta có th chia m ng làm đôi, tìm c c đ i trên m i ph n, r i sau đó l y giá tr l n h n trong
ả
ể
ả
ự ạ
ỗ
ầ
ồ
ấ
ị ớ
ơ
s hai c c đ i tìm đ
c.
ố
ự ạ
ượ
2.
Các ph
ng th c nh
ươ
ứ
ư maxInRange có th gây lúng túng khi dùng. Đ tìm ph n t l n nh t trong m ng,
ể
ể
ầ ử ớ
ấ
ả
ta ph i cung c p m t kho ng bao g m toàn b m ng đó.
ả
ấ
ộ
ả
ồ
ộ ả
double
max = maxInRange(array, 0, a.length-1);
Hãy vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
max nh n tham s là m t m ng r i dùng
ậ
ố
ộ
ả
ồ
maxInRange đ tìm và tr
ể
ả
l i giá tr l n nh t. Các ph
ng th c nh
ạ
ị ớ
ấ
ươ
ứ
ư max đôi khi còn đ c g i là
ượ ọ
ph
ng th c gói b c
ươ
ứ
ọ vì chúng
cung c p m t l p khái ni m xung quanh m t ph
ng th c l ng c ng và giúp nó d dùng. Ph
ng th c
ấ
ộ ớ
ệ
ộ
ươ
ứ ủ
ủ
ễ
ươ
ứ
mà th c s th c hi n tính toán đ
c g i là
ự ự ự
ệ
ượ ọ
ph
ng th c tr giúp
ươ
ứ
ợ
.
3.
Hãy vi t m t phiên b n
ế
ộ
ả find theo cách đ quy và dùng đ n d ng m u gói b c-tr giúp.
ệ
ế
ạ
ẫ
ọ
ợ
find c n ph i
ầ
ả
nh n m t m ng các s nguyên và m t s nguyên m c tiêu. Nó c n ph i tr l i ch s c a v trí đ u tiên
ậ
ộ
ả
ố
ộ ố
ụ
ầ
ả ả ạ
ỉ ố ủ ị
ầ
t i đó xu t hi n s nguyên m c tiêu, ho c tr l i -1 n u không xu t hi n.
ạ
ấ
ệ ố
ụ
ặ
ả ạ
ế
ấ
ệ
Bài t p 10
ậ
M t cách không hi u qu l m đ s p x p các ph n t trong m ng là tìm ph n t l n nh t
ộ
ệ
ả ắ
ể ắ
ế
ầ ử
ả
ầ ử ớ
ấ
r i đ i ch nó cho ph n t th nh t, sau đó tìm ph n t l n th hai r i đ i ch v i ph n t th hai, và
ồ ổ
ỗ
ầ ử ứ
ấ
ầ ử ớ
ứ
ồ ổ
ỗ ớ
ầ ử ứ
c nh v y. Cách này g i là
ứ
ư ậ
ọ
s p x p ch n
ắ
ế
ọ (xem http://vi.wikipedia.org/wiki/S p_x p_ch n
ọ ).
1.
Hãy vi t m t ph
ng th c mang tên
ế
ộ
ươ
ứ
indexOfMaxInRange nh n vào m t m ng s nguyên, tìm ph n t
ậ
ộ
ả
ố
ầ ử
l n nh t trong kho ng cho tr
c, r i tr l i ch s c a nó. B n có th s a l i phiên b n
ớ
ấ
ả
ướ
ồ
ả ạ
ỉ ố ủ
ạ
ể ử ạ
ả maxInRange hay
b n có th vi t t đ u m t phiên b n t
ng tác v i máy.
ạ
ể ế ừ ầ
ộ
ả ươ
ớ
2.
Vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
swapElement nh n m t m ng s nguyên cùng hai ch s , r i đ i ch hai
ậ
ộ
ả
ố
ỉ ố ồ ổ
ỗ
ph n t t i các ch s đó.
ầ ử ạ
ỉ ố
3.
Vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
selectionSort nh n vào m t m ng các s nguyên và trong đó
ậ
ộ
ả
ố
dùngindexOfMaxInRange cùng swapElement đ x p m ng t nh đ n l n.
ể ế
ả
ừ
ỏ ế ớ
Bài t p 11
ậ
Vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
letterHist nh n m t chu i làm tham s r i tr l i histogram
ậ
ộ
ỗ
ố ồ ả ạ
c a các ch cái trong chu i. Ph n t th không c a histogram c n ph i ch a s ch a trong chu i (c
ủ
ữ
ỗ
ầ ử ứ
ủ
ầ
ả
ứ ố ữ
ỗ
ả
ch in và th
ng); ph n t th 25 c n ph i ch a s ch z. L i gi i c a b n ch đ
c duy t chu i này
ữ
ườ
ầ ử ứ
ầ
ả
ứ ố ữ
ờ
ả ủ
ạ
ỉ ượ
ệ
ỗ
đúng m t l n.
ộ ầ
Bài t p 12
ậ
M t t đ
c g i là “doubloon” n u trong t đó, m i ch cái xu t hi n đúng hai l n. Ch ng
ộ ừ ượ ọ
ế
ừ
ỗ
ữ
ấ
ệ
ầ
ẳ
h n, các t sau đây là doubloon mà tôi đã tìm th y trong cu n t đi n.
ạ
ừ
ấ
ố ừ ể
Abba, Anna, appall, appearer, appeases, arraigning, beriberi, bilabial, boob, Caucasus, coco,
Dada, deed, Emmett, Hannah, horseshoer, intestines, Isis, mama, Mimi, murmur, noon,
Otto, papa, peep, reappear, redder, sees, Shanghaiings, Toto
Hãy vi t m t ph
ng th c có tên
ế
ộ
ươ
ứ
isDoubloon đ tr l i
ể ả ạ true n u t đã cho là m t doubloon và
ế ừ
ộ
false n u
ế
không ph i.
ả
Bài t p 13
ậ
Hai t là t đ o (anagram) n u nh chúng có ch a cùng nh ng ch cái (đ ng th i cùng s
ừ
ừ ả
ế
ư
ứ
ữ
ữ
ồ
ờ
ố
