Trong cu\u1ed9c s\u1ed1ng ng\u01b0\u1eddi ta hay g\u1eb7p t\u00ecnh hu\u1ed1ng sau \u0111\u00e2y: Trong v\u00f4 v\u00e0n c\u00e1c lo\u1ea1i h\u00e0ng ho\u00e1 b\u00e0y b\u00e1n, l\u00e0m th\u1ebf n\u00e0o ch\u1ecdn \u0111\u01b0\u1ee3c m\u00f3n h\u00e0ng v\u1eeba \u00fd nh\u1ea5t? \u0110\u01b0\u01a1ng nhi\u00ean l\u00e0 nh\u1eefng ng\u01b0\u1eddi b\u00e1n h\u00e0ng s\u1ebd \u0111em c\u00e1c lo\u1ea1i h\u00e0ng ho\u00e1 \u0111\u1ec3 c\u00e1c b\u1ea1n c\u00f3 th\u1ec3 ch\u1ecdn. Ch\u00fang ta kh\u00f4ng c\u00f3 nhi\u1ec1u c\u01a1 h\u1ed9i \u0111\u1ec3 ch\u1ecdn v\u00ec h\u00e0ng ho\u00e1 \u0111em b\u00e0y kh\u00e1 nhi\u1ec1u lo\u1ea1i, b\u1ea1n s\u1ebd kh\u00f4ng \u0111\u1ee7 th\u1eddi gi\u1edd \u0111\u1ec3 l\u00e0m vi\u1ec7c ch\u1ecdn l\u1ef1a. L\u1ea1i nh\u01b0 c\u00f3 tr\u01b0\u1eddng h\u1ee3p c\u00e1c nh\u00e0 s\u1ea3n xu\u1ea5t ch\u1ecdn c\u00e1c s\u1ea3n ph\u1ea9m t\u1ed1t nh\u1ea5t c\u1ee7a m\u00ecnh \u0111em b\u00e0y ra, l\u00e0m th\u1ebf n\u00e0o ch\u1ecdn \u0111\u01b0\u1ee3c c\u00e1i t\u1ed1t nh\u1ea5t trong nh\u1eefng m\u1eb7t h\u00e0ng \u0111\u00e3 tr\u00ecnh b\u00e0y?<\/p>\n\n\n\n
C\u00f3 kh\u00e1 nhi\u1ec1u ti\u00eau chu\u1ea9n \u0111\u1ec3 \u0111\u00e1nh gi\u00e1 m\u1ed9t m\u1eb7t h\u00e0ng t\u1ed1t. \u0110\u1ee9ng v\u1ec1 ph\u00eda kh\u00e1ch h\u00e0ng, c\u00f3 ba ti\u00eau chu\u1ea9n \u0111\u1ec3 \u0111\u00e1nh gi\u00e1 m\u1ed9t m\u1eb7t h\u00e0ng t\u1ed1t: 1. ch\u1ea5t l\u01b0\u1ee3ng h\u00e0ng ho\u00e1, 2. h\u00ecnh th\u1ee9c b\u00ean ngo\u00e0i s\u1ea3n ph\u1ea9m, 3. gi\u00e1 c\u1ea3. V\u1edbi ba ti\u00eau chu\u1ea9n n\u00e0y kh\u00f4ng d\u1ec5 nh\u00e2n nh\u01b0\u1ee3ng l\u1eabn nhau. T\u00e2m l\u00ed c\u1ee7a kh\u00e1ch h\u00e0ng c\u0169ng c\u00f3 nhi\u1ec1u xu h\u01b0\u1edbng: c\u00f3 ng\u01b0\u1eddi c\u00f3 y\u00eau c\u1ea7u cao v\u1ec1 ch\u1ea5t l\u01b0\u1ee3ng, c\u00f3 ng\u01b0\u1eddi l\u1ea1i \u0111\u00e1nh gi\u00e1 cao v\u1ec1 h\u00ecnh th\u1ee9c, c\u00f3 ng\u01b0\u1eddi l\u1ea1i ch\u00fa \u00fd nhi\u1ec1u v\u1ec1 gi\u00e1 c\u1ea3.<\/p>\n\n\n\n
Ch\u00fang ta gi\u1ea3 thi\u1ebft kh\u00e1ch h\u00e0ng \u0111\u00e3 c\u00f3 m\u1ed9t \u0111\u1ecbnh h\u01b0\u1edbng v\u1ec1 ti\u00eau chu\u1ea9n ch\u1ecdn h\u00e0ng, c\u00f3 th\u1ec3 ch\u1ecdn h\u00e0ng ho\u00e1 t\u1ed1t x\u1ea5u t\u1eeb hai v\u1eadt ph\u1ea9m \u0111em so s\u00e1nh v\u1edbi nhau.<\/p>\n\n\n\n
B\u00e2y gi\u1edd gi\u1ea3 thi\u1ebft c\u00f3 n v\u1eadt ph\u1ea9m \u0111\u1ec3 b\u1ea1n ch\u1ecdn l\u1ef1a. Ph\u01b0\u01a1ng ph\u00e1p chung l\u00e0 nh\u1eb7t l\u1ea5y hai s\u1ea3n ph\u1ea9m r\u1ed3i so s\u00e1nh v\u1edbi nhau. Sau \u0111\u00f3 l\u1ea1i \u0111\u1ed5i hai s\u1ea3n ph\u1ea9m kh\u00e1c v\u00e0 l\u1ea1i ti\u1ebfn h\u00e0nh so s\u00e1nh. Vi\u1ec7c l\u1ef1a ch\u1ecdn c\u1ee9 th\u1ebf ti\u1ebfp t\u1ee5c cho \u0111\u1ebfn khi ch\u1ecdn \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m v\u1eeba \u00fd nh\u1ea5t. Th\u1ebf th\u00ec t\u1eeb n s\u1ea3n ph\u1ea9m ta c\u1ea7n ti\u1ebfn h\u00e0nh bao nhi\u00eau l\u1ea7n ch\u1ecdn l\u1ef1a \u0111\u1ec3 \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m t\u1ed1t. \u0110\u1ec3 ti\u1ec7n theo d\u00f5i ta g\u1ecdi s\u1ed1 l\u1ea7n ti\u1ebfn h\u00e0nh ch\u1ecdn l\u00e0 f(n).<\/p>\n\n\n\n
Gi\u1ea3 s\u1eed khi n = 2 t\u1ee9c ch\u1ecdn s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb hai s\u1ea3n ph\u1ea9m, r\u00f5 r\u00e0ng ch\u1ec9 c\u1ea7n 1 l\u1ea7n ch\u1ecdn l\u00e0 ch\u1ecdn \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m t\u1ed1t, v\u00ec v\u1eady ta c\u00f3 f(2) =1<\/p>\n\n\n\n
Khi n = 3, tr\u01b0\u1edbc h\u1ebft ta ch\u1ecdn hai trong ba s\u1ea3n ph\u1ea9m \u0111em so s\u00e1nh, sau khi ch\u1ecdn \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb hai s\u1ea3n ph\u1ea9m, ta l\u1ea1i \u0111em s\u1ea3n ph\u1ea9m v\u1eeba \u0111\u01b0\u1ee3c ch\u1ecdn so v\u1edbi s\u1ea3n ph\u1ea9m c\u00f2n l\u1ea1i, nh\u1edd v\u1eady ta ch\u1ecdn \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb ba s\u1ea3n ph\u1ea9m v\u00e0 ch\u1ec9 qua hai l\u1ea7n ch\u1ecdn, n\u00ean ta c\u00f3 f(3) = 2.<\/p>\n\n\n\n
Ta l\u1ea1i xem x\u00e9t ti\u1ebfp tr\u01b0\u1eddng h\u1ee3p n l\u00e0 s\u1ed1 b\u1ea5t k\u00ec: Tr\u01b0\u1edbc h\u1ebft ta ch\u1ecdn hai s\u1ea3n ph\u1ea9m \u0111em so s\u00e1nh r\u1ed3i ch\u1ecdn 1, sau \u0111\u00f3 l\u1ea1i \u0111em s\u1ea3n ph\u1ea9m \u0111\u01b0\u1ee3c ch\u1ecdn so s\u00e1nh v\u1edbi 1 trong c\u00e1c s\u1ea3n ph\u1ea9m c\u00f2n l\u1ea1i cho \u0111\u1ebfn khi ch\u1ec9 c\u00f2n 1 s\u1ea3n ph\u1ea9m ch\u1ecdn \u0111\u01b0\u1ee3c cu\u1ed1i c\u00f9ng. R\u00f5 r\u00e0ng \u0111\u1ec3 \u0111\u1ea1t \u0111\u1ebfn k\u1ebft qu\u1ea3 ta ph\u1ea3i ti\u1ebfn h\u00e0nh n – 1 l\u1ea7n ch\u1ecdn. Ph\u01b0\u01a1ng \u00e1n l\u1ef1a ch\u1ecdn n\u00e0y r\u00f5 r\u00e0ng kh\u00f4ng nh\u1ecf h\u01a1n s\u1ed1 f(n) n\u00ean f(n) \u2264 n -1.<\/p>\n\n\n\n
Khi \u0111\u00e3 c\u00f3 ph\u01b0\u01a1ng \u00e1n ta ch\u1ec9 c\u1ea7n ti\u1ebfn h\u00e0nh f(n) l\u1ea7n ch\u1ecdn. \u0110\u1ec3 th\u1ef1c hi\u1ec7n ta b\u1eaft \u0111\u1ea7u th\u1ef1c hi\u1ec7n l\u1ea7n so s\u00e1nh \u0111\u1ea7u ti\u00ean; ch\u1ecdn hai trong n s\u1ea3n ph\u1ea9m \u0111\u1ec3 so s\u00e1nh. Sau khi \u0111\u00e3 lo\u1ea1i b\u1ecf m\u1ed9t s\u1ea3n ph\u1ea9m t\u1ed1t nh\u1ea5t t\u1eeb n – 2 s\u1ea3n ph\u1ea9m c\u00f2n l\u1ea1i s\u1ebd \u0111\u01b0\u1ee3c t\u00ecm th\u1ea5y khi th\u1ef1c hi\u1ec7n s\u1ed1 l\u1ea7n th\u1eed f(n – 1) t\u1ee9c l\u00e0 th\u1ef1c hi\u1ec7n vi\u1ec7c tuy\u1ec3n ch\u1ecdn s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb n-1 s\u1ea3n ph\u1ea9m c\u00f2n l\u1ea1i. Do f(n) – 1 \u2265 f(n – 1) n\u00ean f(n) \u2265 f(n – 1) + 1 \u2265 f(n -2) +1 + 1 \u2265 f(n – 3) + 3 \u2265 f(n – (n – 2)) + n – 2 = f(2) + n – 2 = 1 + n – 2 = n – 1<\/p>\n\n\n\n
T\u1eeb k\u1ebft qu\u1ea3 tr\u01b0\u1edbc \u0111\u00e2y ta c\u00f3 b\u1ea5t \u0111\u1eb3ng th\u1ee9c f(n) \u2264 n – 1 so v\u1edbi k\u1ebft qu\u1ea3 suy lu\u1eadn v\u1eeba r\u1ed3i ta l\u1ea1i c\u00f3 (f(n) \u2265 n-1, do \u0111\u00f3 f(n) = n – 1. T\u1eeb \u0111\u00f3 c\u00f3 th\u1ec3 th\u1ea5y \u0111\u1ec3 ch\u1ecdn \u0111\u01b0\u1ee3c s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb n s\u1ea3n ph\u1ea9m ta ph\u1ea3i ti\u1ebfn h\u00e0nh n – 1 l\u1ea7n so s\u00e1nh. Tr\u00ean \u0111\u00e2y ch\u00fang ta \u0111\u00e3 \u0111\u01b0a ra ph\u01b0\u01a1ng \u00e1n ch\u1ecdn s\u1ea3n ph\u1ea9m t\u1ed1t t\u1eeb n s\u1ea3n ph\u1ea9m v\u00e0 th\u1ea5y r\u1eb1ng ph\u1ea3i ti\u1ebfn h\u00e0nh n – 1 l\u1ea7n so s\u00e1nh. \u0110\u01b0\u01a1ng nhi\u00ean c\u00f3 th\u1ec3 c\u00f2n c\u00f3 c\u00e1c ph\u01b0\u01a1ng \u00e1n kh\u00e1c. V\u00ed d\u1ee5 tr\u01b0\u1edbc h\u1ebft ta chia c\u00e1c s\u1ea3n ph\u1ea9m th\u00e0nh t\u1eebng nh\u00f3m sau \u0111\u00f3 l\u1ea1i \u0111em c\u00e1c s\u1ea3n ph\u1ea9m t\u1ed1t \u0111\u01b0\u1ee3c tuy\u1ec3n ch\u1ecdn t\u1eeb c\u00e1c nh\u00f3m \u0111em so s\u00e1nh v\u1edbi nhau v.v..<\/p>\n\n\n\n
<\/p>\n\n\n\n\n\n\n","protected":false},"excerpt":{"rendered":"
Trong cu\u1ed9c s\u1ed1ng ng\u01b0\u1eddi ta hay g\u1eb7p t\u00ecnh hu\u1ed1ng sau \u0111\u00e2y: Trong v\u00f4 v\u00e0n c\u00e1c lo\u1ea1i h\u00e0ng ho\u00e1 b\u00e0y b\u00e1n, l\u00e0m th\u1ebf n\u00e0o ch\u1ecdn \u0111\u01b0\u1ee3c m\u00f3n h\u00e0ng v\u1eeba \u00fd nh\u1ea5t? \u0110\u01b0\u01a1ng nhi\u00ean l\u00e0 nh\u1eefng ng\u01b0\u1eddi b\u00e1n h\u00e0ng s\u1ebd \u0111em c\u00e1c lo\u1ea1i h\u00e0ng ho\u00e1 \u0111\u1ec3 c\u00e1c b\u1ea1n c\u00f3 th\u1ec3 ch\u1ecdn. Ch\u00fang ta kh\u00f4ng c\u00f3 nhi\u1ec1u c\u01a1 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_disable_autopaging":false},"categories":[15,9],"tags":[],"class_list":["post-7630","post","type-post","status-publish","format-standard","hentry","category-hoi-dap-khoa-hoc","category-toan-hoc"],"_links":{"self":[{"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/posts\/7630","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/comments?post=7630"}],"version-history":[{"count":0,"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/posts\/7630\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/media?parent=7630"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/categories?post=7630"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vietlearn.org\/kien-thuc\/wp-json\/wp\/v2\/tags?post=7630"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}