PHƯƠNG PHÁP KHỬ ĐỆ QUY ĐẶC BIỆT

Một số bài toán giải bằng phương pháp đệ quy cho ta lời giải rất gọn và có thể ra được lời giải. Những bài toán giải bằng đệ quy truyền thống như: THÁP HÀ-NỘI, bà toán 8-HẬU, bài toán MÃ ĐI TUẦN, ... Tuy nhiên phương pháp đệ quy khi áp dụng chỉ giải được những bài toán với cấu trúc dữ liệu nhỏ thường là với N<30 (hay NxN < 30x30). Vì vậy bài toán đặt ra là có thể giải quyết những bài toán như trên với dữ liệu lớn được hay không? Ví dụ như: bài toán MÃ ĐI TUẦN và THÁP HÀ-NỘI với bàn cờ cỡ 80x80 hay không? Xin trình bày một số phương pháp khử đệ quy để giải quyết những bài toán đệ quy truyền thống. 1. Bài toán MÃ ĐI TUẦN: Trên bàn cờ NxN (với 5<=N<=100) đặt một quân mã tại một vị trí bất kỳ. Hãy tìm cách cho mã nhảy theo luật nhảy của quân mã và nhảy hết tất cả các ô trên bàn cờ đó, mỗi ô chỉ nhảy vào đúng một lần. 2. Phân tích và xây dựng chương trình: Khi quân mã nhảy hết tất cả các ô trên bàn cờ, và tại ô cuối cùng quân mã có thể nhảy về vị trí của ô xuất phát chính là một chu trình Euler (Nhảy qua tất cả các ô, mỗi ô đúng một lần và nhảy về vị trí xuất phát). Còn nếu vị trí cuối cùng không thể nhảy về vị trí xuất phát được chính là một đường đi Euler. Ta thử tìm cách bài toán tìm đường đi Euler qua tất cả các ô của bàn cờ theo luật nhảy của quân mã, mỗi ô chỉ nhảy vào một lần. a. Phương pháp đệ quy truyền thống: Với phương pháp đệ quy cho bài mã đi tuần này đã có nhiều bài báo đề cập và có nhiều cải tiến như số 6-2003, số 7-2003. Tuy nhiên chỉ giải quyết được với N<30. Xin nhắc lại sơ phương pháp truyền thống như sau: Từ vị trí xuất phát trên bàn cờ NxN ta gán giá trị là 1, theo luật nhảy của quân mã có tối đa là 8 vị trí kế tiếp để quân mã nhảy tới theo luật nhảy. Ta lần lượt kiểm tra 8 vị trí này xem vị trí đó có nằm trong bàn cờ hay không, quân mã đã nhảy đến ô này hay chưa nếu chưa nhảy đến và ô này nằm trong bàn cờ thì nhảy vào ô này. Sau đó dùng đệ quy để tiếp tục quá trình trên cho đến khi quân mã nhảy hết tất cả các ô. b. Phương pháp mới :“xử lý những đoạn gen”  i. Mô tả:  Ta để ý rằng đáp án của bài toán là mội chuỗi những bước nhảy liên tiếp qua hết tất cả các ô trên bàn cờ giống như một “đoạn gen” duy nhất gồm nhiền “nhiễm sắc thể” nối tiếp nhau. Các nhiễm sắc thể tức là các ô của bàn cờ. Hai nhiễm sắc thể liên tiếp được nối với nhau nếu thỏa mãn luật nhảy của quân mã . Như vậy ta có thể đưa bài toán về một bài toán khác là từ những “nhiễm sắc thể” đơn lẻ hãy tìm cách ghép nối chúng lại với nhau sao cho tạo thành một “đoạn gen” duy nhất. Ví dụ: Ta xem đáp án của bàn cờ 5x5 và “đoạn gen” hoàn chỉnh: ii. Định nghĩa các thuật ngữ:  1. Nhiễm sắc thể: là một ô trên bàn cờ NxN 2. Đoạn gen: là một chuỗi gồm một hoặc nhiều nhiễm sắc thể liên tiếp nhau.Hai nhiễm sắc thể liên tiếp nhau trong một đoạn gen thỏa mãn luật nhảy của quân mã. Mỗi đoạn gen sẽ có đầu và đuôi, đoạn gen gồm duy nhất một nhiễm sắc thể thì đầu và đuôi là một. (hình trên gồm 7 đọan gen có đầu là các ô tô đậm) 3. Nối gen: Ta nối đầu (hay đuôi) của đoạn gen A vào đầu (hay đuôi) của đoạn gen B tạo thành đoạn C thỏa mãn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ đoạn gen A và đoạn gen B. 4. Trộn gen: Ta trộn gen A vào trong gen B như sau: Từ đầu và đuôi của đoạn gen A ta nối vàotại một bước nhảy nào đó của đoạn gen B tạo thành đoạn C thỏa mãn đoạn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ A và B. 5. Cắt gen: Cắt hai đoạn gen A và đoạn B tạo thành hai đoạn gen C và đoạn gen D như sau: ta tìm trên đoạn gen B vị trí để có thể nối đầu (hay đuôi) của đoạn gen A vào và tạo thành đoạn gen C. Phần còn lại của đoạn gen B sẽ bị cắt ra ngoài tạo thành đoạn gen D. iii. Chứng minh quy tắc:  Với ba công cụ biến đổi những đoạn gen như trên: nối gen, trộn gen và cắt gen ta chứng minh rằng sẽ luôn tìm ra lời giải cho bài toán đặt ra: nối các nhiễm sắc thể riêng lẻ lại và tạo thành một đoạn gen duy nhất Ta thấy rằng với phương pháp nối gen, từ hai đoạn gen A và đoạn gen B ban đầu sau khi nối tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Như vậy số đoạn gen sau khi thực hiện một phép nối sẽ giảm đi một đoạn. Trộn đoạn gen A vào đoạn gen B tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Nên sau khi thực hiêm một phép trộn gen số đoạn gen sẽ giảm đi một đoạn. Với phép cắt gen, đoạn gen A cắt vào đoạn gen B, tạo thành đoạn gen C và đoạn gen D trong đó đoạn gen C và đoạn gen D chứa các nhiễm sắc thể của đoạn gen A và đoạn gen B. Như vậy số đoạn gen sau khi thực hiện phép cắt gen sẽ không đổi (nhưng nó sẽ tạo ra những trường hợp mới để có thể thực hiện hai phép nối gen và trộn gen. Vì quân mã tại một vị trí bất kỳ trên bàn cờ có tối thiểu là 2 cách chọn cho bước nhảy kế tiếp nên ta luôn luôn tồn tại hai cặp gen nào đó mà chúng có thể cắt nhau được. Từ đó ta có thể kết luận rằng số đoạn gen ban đầu N*N đoạn sau nhiều lần biến đổi gen (dùng lần lượt ba phép biến đổi trên) sẽ tạo thành một đoạn gen duy nhất chính là lời giải ta cần tìm. iv. Tiến hành xây dựng chương trình  Bước 1: Chuyển N*N ô bàn cờ vào các đoạn ghen ta sẽ được N*N đoạn ghen. Mỗi đoạn ghen có chiều dài là 1. Bước 2: Thược hiện các phép “nối ghen”, “trộn gen” và “cắt gen” cho đến khi chỉ còn một đoạn gen duy nhất. Đoạn gen này có chiều dài là N*N chính là đáp án của bài toán. Tuy nhiên để tiết kiệm bộ nhớ ta có thể thực hiện theo các sau : Ngay từ khi khởi tạo ta dùng phương pháp đệ quy truyền thống nhưng chỉ cho chương trình đệ quy tới giá trị N*(N-1), sau đó mới áp dụng phương pháp xử lý các đoạn gen như sau. Bước 1. Ban đầu ta dùng cách đệ quy truyền thống cho mã nhảy đến một giá trị là N*(N-1) thì dừng lại. (Còn lại N ô chưa điền) Bước 2. Lần lượt điền những ô chưa điền với những giá tri tăng dần N*(N-1)+1, N*(N-1)+2,... đến N*N thì dừng lại (nhu vậy tất cả các ô đều được điền nhưng không đúng luật nhảy của quân mã). Bước 3. Biến đổi mảng mảng 2 chiều đã điền thành các đoạn gen Bước 4. Sau đó ta phân tích bàn cờ hai chiều (đã đánh số từ 1=>NxN) thành các đoạn gen. Bước 5. Tiến hành xử lý các đoạn gen dùng lần lượt 3 công cụ “nối gen”, “trộn gen” và “cắt gen” để nối các đọan gen thành một đoạn gen duy nhất. Bước 6. Xuất kết quả ra file. Chương trình minh họa được viết bằng ngôn ngữ Pascal (Free Pascal Compiler Version 1.0.4) load trên trang web: http://www.freepascal.org/ Khi viết trong Free Pascal bộ nhớ có thể mở rộng phù hợp cho việc khai báo của bài toán trên. Chương trình viết bằng ngôn ngữ Visual C (cho phép N<=87) vớn ngôn ngữ Free Pascal (N<=80 có thể khai báo maxN=90 nhưng khi khởi động có thể hơi lâu). v. Những lưu ý khi khi xây dựng chương trình  Khi “nối gen” và “trộn gen” không thể thực hiện được nữa chương trình thường chạy “cắt gen”. Sau khi đoạn gen A cắt đoạn gen B và sinh ra đoạn gen C và gen D thì ta phải đảo ngược đoạn gen C này để tránh trường hợp đoạn gen C lại cắt đoạn gen D sẽ sinh ra đoạn gen A và B thì chương trình sẽ bị lặp. Tuy nhiên ta không thể dự đoán trước được có những trường hợp bị lặp đặc biệt nào đó nên cách giải quyết tốt nhất là khi đoạn gen A cắt đoạn gen B ta tìm hết các vị trí cắt trên B mà A có thể cắt (tối đa là 8 vị trí), nếu có vị trí cắt ta lấy ngẫu nhiên một vị trí trên B trong các vị trí có thể đó để làm điểm cắt. Như thế chương trình sẽ tránh được những trường hợp lặp đặc biệt nào đó. vi. Đánh giá và mở rộng bài toán:  - Với chương trinh đệ quy truyền thống cũng như đệ quy có tri thức (thuật tóan Warnsdorff) thì chỉ giải quyết đuợc vói những bàn cờ kích thước nhỏ và thời giai đưa ra kết quả khá lâu. Không những thế một số vị trí xuất phát và hướng nhảy của quân mã trên bàn cờ có thể sẽ đưa ra lời giải trong thời gian khá lâu cho dù N bé vì đệ quy chính là “vét cạn” các trường hợp nếu đáp án nằm ở vị trí cuối của các lần lặp đệ quy ban đầu. - Với cách giải quyết qua các “đoạn gen” khắc phục được những điểm yếu của đệ quy truyền thống. Kích thước của bàn cờ có khả năng đạt đến là 87x87 khi sử dụng mảng lưu trữ tĩnh. Kích thức của bàn cờ có thể lớn hơn nữa nếu tổ chức dữ liệu bằng danh sách liên kết. 3. Bài tập: 1. Lập trình giải bài toán tìm đường đi Euler dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng tĩnh. 2. Lập trình giải bài toán tìm đường đi Euler (hay bài MÃ ĐI TUẦN) dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng động. 4. Tài liệu tham khảo: Giáo trình trí tuệ nhân tạo – Cấu trúc dữ liệu + thuật giải di truyền = Lập trình tiến hóa Ts. Nguyễn Đình Thúc (NXB LĐ-XH)

---

URL của bài viết này::http://www.schoolnet.vn/modules.php?name=News&file=article&sid=4389

---

© Cong ty Cong Nghe Tin hoc Nha truong

contact: schoolnet@vnschool.net

Học thuật toán qua các bài toán

Học tập thuật toán là một trong những yêu cầu cơ bản để trở thành các lập trình viên. Đối với các sinh viên ngành tin học và những ai yêu thích lập trình, việc học thuật toán còn là một thú vui, giúp nâng cao tư duy logic và làm phong phú thêm kiến thức về việc xây dựng các giải thuật cho các bài toán mới. Trong bài báo nhỏ này tôi xin đưa ra một số bài toán nhỏ, để qua đó trình bày một số thuật toán khá tinh tế để giải quyết chúng, mong rằng bài báo sẽ mang lại cho các bạn độc giả những điều thú vị. Bài toán 1: Cho một dãy số nguyên a có N phần tử và một số nguyên k. Hãy xác định xem trong dãy a có tồn tại hai số nguyên a[i] và a[j] sao cho k là trung bình cộng của a[i] và a[j] (i≠j). Bài toán này còn có thể chuyển thành bài toán tìm xem có tồn tại hai phần tử a[i], a[j] mà k là hiệu của chúng không. Thuật toán dành cho bài toán 1 cũng không có gì quá phức tạp, chỉ cần hai vòng lặp lồng nhau, một dành cho chỉ số i và một dành cho chỉ số j (chạy từ 0 tới N-1) sau đó trong thân của hai vòng lặp này ta kiểm tra điều kiện a[i] + a[j] = 2*k hay không. Đoạn chương trình cài đặt cụ thể như sau: Các bạn có thể dễ dàng nhận thấy thuật toán trên có độ phức tạp . Tuy nhiên xem xét kỹ hơn một chút chúng ta thấy rằng có thể cải tiến để nhận được thuật toán tốt hơn cho bài toán 1. Để ý vòng lặp thứ 2 với chỉ số j chính là áp dụng của thuật toán tìm kiếm tuyến tính đối với dãy a (điều kiện tìm kiếm là tìm xem có tồn tại a[i], a[j] thỏa mãn điều kiện của bài toán 1 hay không), nên chúng ta có thể thay bằng thuật toán tìm kiếm nhị phân với độ phức tạp . Thay vì tìm điều kiện tồn tại a[i]+a[j] == 2*k, chúng ta sẽ tìm xem có tồn tại chỉ số j mà a[j] = 2*k – a[i] hay không, cụ thể nếu 2*k – a[i] > a[i] thì chúng ta sẽ tìm trên mảng a[i+1..N-1] còn nếu 2*k – a[i] < a[i] thì ta sẽ tìm trên mảng a[0..i-1]. Để có thể thực hiện thuật toán tìm kiếm nhị phân chúng ta sẽ sắp xếp dãy a trước khi tiến hành tìm kiếm, thuật toán sắp xếp được chọn ở đây sẽ là thuật toán quick sort, có độ phức tạp là  . Vòng lặp đối với chỉ số i có độ phức tạp là  nên đoạn thuật toán tìm kiếm sẽ có độ phức tạp là  và do đó thuật toán cuối cùng sẽ có độ phức tạp là . Cài đặt cụ thể của thuật toán như sau: Về hàm qsort() của C/C++ các bạn có thể tra thêm với Turbo C 3.0 để biết thêm chi tiết, ở đây chúng ta chỉ cần chú ý là khi gọi tới hàm này cần có một hàm trợ giúp làm nhiệm vụ so sánh các phần tử trong dãy cần sắp, và khi gọi hàm cần chỉ rõ kích thước của một phần tử quan toán tử sizeof của C/C++. Bài toán 2: Hãy viết chương trình in ra tất cả các số nguyên tố có hai chữ số. Có thể nói đây là một bài toán khá đơn giản, chỉ cần có một hàm kiểm tra tính nguyên tố (các bạn có thể tham khảo bài viết Số nguyên tố của tôi để biết thêm về thuật toán kiểu này), sau đó chạy một vòng lặp với các số có hai chữ số là xong.Tuy nhiên sẽ là thế nào nếu như đề bài có thêm yêu cầu xây dựng thuật toán tốt nhất cho bài toán trên. Chúng ta sẽ đi tìm một thuật toán tốt hơn ý tưởng sử dụng hàm kiểm tra tính nguyên tố của mỗi số nguyên. Có thể nhận thấy rằng các số nguyên tố có hai chữ số (hay bất cứ số nguyên tố nào lớn hơn 10) đều chữ số cuối thuộc tập {1, 3, 7, 9}. Lại do các số nguyên tố cần tìm đều là các số nhỏ hơn 100 (có hai chữ số) nên chúng chỉ có thể có các ước số nguyên tố nhỏ hơn 10, hay chính xác là chỉ có thể là 3 hoặc 7 (không có 2, 5). Vậy ta chỉ cần tạo ra các số có hai chữ số mà đảm bảo chúng có chữ số kết thúc thuộc tập {1, 3, 7, 9} và kiểm tra xem chúng có chia hết cho 3 và 7 không là đủ. Đoạn chương trình cài đặt cụ thể của thuật toán là: Bài toán 3 (bài toán tìm điểm yên ngựa của ma trận): Cho một ma trận kích thước NxM (N hàng, M cột). Hãy tìm xem trên ma trận có tồn tại phần tử a[i][j] nào vừa là phần tử nhỏ nhất của hàng i, lại vừa là phần tử lớn nhất của cột j hay không. Đây có lẽ là một bài toán khá quen thuộc với đa số các bạn độc giả đã học về cấu trúc dữ liệu và giải thuật. Thuật toán để giải quyết bài toán cũng khá đơn giản: ta sử dụng hai vòng lặp cho các chỉ số hàng (i) và cột (j), với mỗi phần tử a[i][j] đó ta sẽ tìm phần tử nhỏ nhất của hàng i, gọi là x, tìm phần tử lớn nhất của cột j, gọi là y, cuối cùng so sánh xem x, y và a[i][j] có bằng nhau hay không để đi đến kết luận a[i][j] có là phần tử yên ngựa hay không (kết quả là có nếu a[i][j] bằng x, và bằng y). Việc tìm x sẽ tiến hành với M phần tử của hàng i, việc tìm y sẽ tiến hành với N phần tử của cột j nên thuật toán sẽ có độ phức tạp là  . N*M tương ứng với hai vòng lặp của biến i và biến j. Thuật toán này có thể cải tiến nếu chúng ta nhận thấy rằng: việc tìm các giá trị x (có N giá trị x như vậy, do có N hàng), giá trị y (có M giá trị y như vậy) trong thân vòng lặp tương ứng của các biến i, j là chưa tối ưu. Chúng ta có thể tìm N giá trị nhỏ nhất của các hàng và lưu vào mảng minh[0..N-1], thuật toán tương ứng sẽ có độ phức tạp là  , do ta tìm N lần, mỗi lần tìm trong một hàng có M phần tử. Tương tự chúng ta sẽ tìm các phần tử lớn nhất của các cột và lưu vào mảng maxc[0..M-1], thuật toán này cũng có độ phức tạp là  . Cuối cùng trong vòng lặp với các biến i, j chúng ta chỉ cần so sánh a[i][j] với minh[i] và maxc[j], nếu ba số này bằng nhau thì a[i][j] chính là một phần tử yên ngựa. Thuật toán cải tiến cho bài toán 3 này có độ phức tạp  , tất nhiên là tốt hơn so với thuật toán ban đầu có độ phức tạp  . Việc cài đặt cụ thể thuật toán này xin dành lại như là một bài tập cho các bạn độc giả. Bài toán 4 (bài toán số trung bình): Cho một dãy các số nguyên a1, a2, … , aN. Một phần tử akđược gọi là phần tử trung bình của dãy đã cho nếu tồn tại hai phần tử ai, aj (i≠j) sao cho ak = (ai + aj)/2. Chẳng hạn với dãy số 3, 7, 10, 22, 17, 15 ta có (a1 + a5)/2 = 10 = a3 nên a3 là một phần tử trung bình. Nhưng dãy 3, 8, 11, 17, 30 lại không có phần tử trung bình nào. Hãy viết chương trình đếm số phần tử trung bình của một dãy cho trước có N phần tử (N ≤ 10000). Về thực chất đây là một bài toán khá giống với bài toán 1, nhưng các bạn cần để ý tới điều kiện của N (N ≤ 10000) để tránh dẫn tới sử dụng một thuật toán sai (không chạy hết được các test của bài toán). Lời giải đơn giản cho bài toán có độ phức tạp là  , lời giải này hoàn toàn trực tiếp đối với lời phát biểu của bài toán: Vòng lặp kiểm tra tồn tại j và k cần N*N bước thực hiện (cần kiểm tra tất cả các cặp để xem a[i] có là trung bình cộng của cặp đó không). Do đó độ phức tạp của thuật toán sẽ là  . Lời giải này có thể qua được khoảng 30% số test của bài toán, đo điều kiện về biến N. Tuy nhiên chúng ta có thể đạt được hiệu quả lớn hơn nhiều so với lời giải trên. Chúng ta có thể xác định được một phần tử nào đó có là trung bình cộng của hai phần tử khác không bằng một thuật toán có độ phức tạp  thay vì thuật toán có độ phức tạp  . Quan sát đầu tiên cho chúng ta nhận xét: nếu a[i] là trung bình cộng của a[j] và a[k] thì trong 2 số a[j], a[k] sẽ có một số nhỏ hơn hoặc bằng a[i], số còn lại sẽ lớn hơn hoặc bằng a[i]. Giả sử dãy số của chúng ta đã được sắp theo thứ tự không giảm từ trước: a[0]  a[1]  … a[N-1]. Hơn nữa chúng ta giả sử các số là phân biệt (tôi sẽ để trường hợp các số lặp cho các bạn như là một bài tập nhỏ), do đó a[0] < a[1] < … < a[N-1]. Để kiểm tra a[i] có thể là một phần tử trung bình không, chúng ta trước hết xem xét a[i-1] và a[i+1]. Nếu như trung bình cộng của a[i-1] và a[i+1] là a[i] thì chúng ta kết luận ngay a[i] là một phần tử trung bình. Nhưng nếu không phải thì sẽ có hai trường hợp xảy ra: Trường hợp 1: trung bình cộng của a[i-1], a[i+1] lớn hơn a[i]. Khi đó a[i] không thể là trung bình cộng của a[i-1] với bất cứ phần tử a[j] nào mà j < i, và trung bình cộng của a[i-1] với bất cứ phần tử a[j] nào mà j > i+1 cũng sẽ lớn hơn a[i]. Do đó ta sẽ không cần thiết phải xem xét phần tử a[i-1] nữa. Trường hợp 2: trung bình cộng của a[i-1, a[i+1] nhỏ hơn a[i]. Khi đó a[i] sẽ không thể là trung bình cộng của a[i+1] với bất cứ phần tử a[j] nào mà j > i, và a[i] cũng không thể là trung bình cộng của a[i+1] với bất cứ phần tử a[j] nào mà j < i. Có nghĩa là phần tử a[i+1] sẽ không cần phải xét tới nữa. Thật tuyệt vì chúng ta dường như loại bỏ được rất nhiều các cặp cần xem xét chỉ sau một thao tác so sánh. Có thể áp dụng các nhận xét trên để đưa ra một thuật toán có độ phức tạp N thay vì N*N hay không? Câu trả lời là có, cùng với lập luận tương tự như trên chúng ta có nhận xét sau: Giả sử left < i và right > i. Giả sử avg(a[left], a[right]) > a[i] (avg là ký hiệu trung bình cộng). • a[i] không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j  right. • Tương tự nếu avg(a[left], a[right]) < a[i] thì a[i] cũng sẽ không thể là trung bình cộng của a[right] với bất cứ a[j] nào mà j  left. Nhận xét này dẫn chúng ta tới một thuật toán hiệu quả hơn. Chiến lược của thuật toán là chúng ta xét hai chỉ số left và right thỏa mãn: 1) left < i và right > i 2) a[i] không phải là trung bình cộng của bất cứ cặp đôi nào liên quan tới một phần tử a[j] nào mà left < j < right. Để bắt đầu ta khởi tạo left = i-1 và right = i+1 (do ta giả sử dãy là phân biệt và sắp xếp tăng dần nên điều kiện 2 luôn được thỏa mãn). Nếu avg(a[left], a[right]) = a[i] thì ta tăng biến đếm lên 1 đơn vị. Nếu avg(a[left], a[right]) > a[i] thì ta giảm left đi 1 đơn vị. Tất nhiên điều kiện 1 vẫn thỏa mãn, về điều kiện 2 thì ta biết rằng bất cứ a[j] nào mà left < j < right, a[j] đều không thể xuất hiện trong cặp có trung bình cộng bằng a[i]. Hơn nữa do (1) nên ta biết rằng a[i] cũng không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j  i. Và rõ ràng là a[i] cũng không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j < left. Do đó a[i] không thể là trung bình cộng của a[left] với bất cứ a[j] nào, nên giảm left đi 1 đơn vị không mâu thuẫn với (2). Ngược lại nếu avg(a[left], a[right]) < a[i], chúng ta sẽ tăng right lên 1 đơn vị. Hoàn toàn tương tự ta có thể chứng minh các điều kiện 1 và 2 không bị vi phạm. Chúng ta sẽ dừng lại và kết luận a[i] không phải là một phần tử trung bình trong trường hợp left < 0 hoặc right = N. Và cài đặt của thuật toán là: Trong mỗi lần lặp của vòng lặp while, biến chỉ số left sẽ được giảm đi 1 hoặc biến chỉ số right sẽ bị giảm đi 1. Do đó vòng lặp while này chỉ có thể chạy tối đa N lần trước khi kết thúc. Do đó độ phức tạp của thuật toán là N*N. Vì chúng ta giả sử a[0] < a[1] < … < a[N-1] và các phần tử là khác nhau nên chúng ta cần phải sắp xếp trước khi thực hiện thuật toán trên. Và tất nhiên chúng ta có thể chọn một thuật toán sắp xếp có độ phức tạp  hoặc  . Tóm lại là thuật toán sẽ có độ phức tạp là . Nếu như các phần tử không phải là phân biệt, thì sau khi sắp xếp xong chúng ta có thể sửa đổi đôi chút để thuật toán trên vẫn có thể làm việc được trong cả trường hợp này (phần này sẽ dành cho các bạn như là một bài tập nhỏ). Chú ý là trong thuật toán trên chúng ta đã sử dụng một thuộc tính của trung bình cộng: nếu x y và w  z thì agv(x, w)  agv(y, z). Tính chất này được gọi là tính đơn điệu. Nếu như chúng ta cần phải tính số lượng phần tử là tổng của hai phần tử, hay bất cứ giá trị nào thỏa mãn tính đơn điệu thì đều có thể giải quyết bằng một thuật toán có độ phức tạp là O(N2) thay vì một thuật toán có độ phức tạp  . Các bạn có thể thấy rằng thuật toán trên cũng khá phức tạp và không quá dễ hiểu cho bài toán, lời giải thứ hai của bài toán khá gọn và dễ hiểu: do các số đều là số nguyên, ta lại cần đếm các số là trung bình cộng của hai số trong dãy, nên ta sẽ đánh dấu tất cả các tổng của hai số khác nhau (về vị trí chứ không phải về giá trị) trong dãy, sau đó duyệt lại dãy tổng này để đếm và đưa ra kết quả, cài đặt cụ thể của thuật toán này như sau: Độ phức tạp của thuật toán này cũng là  , nhưng đơn giản và dễ hiểu hơn nhiều so với thuật toán trước. Mặc dù đã hết sức thận trọng và xem xét kỹ các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

---

URL của bài viết này::http://www.schoolnet.vn/modules.php?name=News&file=article&sid=2145

---

© Cong ty Cong Nghe Tin hoc Nha truong

contact: schoolnet@vnschool.net

[BDHSG] - [HA HUY KHOAI] - SO HOC THUAT TOAN

Download : Tại đây

[GS. TSKH Hoàng Kiếm] THUẬT TOÁN & GIẢI THUẬT

Đứng trên quan điểm cá nhân, tôi cho rằng đây là một trong những tài liệu đáng giá dành cho các bạn trẻ yêu thích tin học, đặc biệt là các bạn HSG đang chuẩn bị tham gia các kỳ thi tin học quốc gia và quốc tế. Tài liệu này được biên soạn công phu nhằm giới thiệu những kiến thức mở đầu về Trí tuệ nhân tạo.
Tài liệu này được sưu tầm từ Internet, để thuận tiện hơn cho công tác lưu trữ và nghiên cứu của cá nhân, đồng thời dễ dàng cung cấp cho bạn đọc tra cứu và tham khảo, tôi đã đưa lên www.mediafire.com.
Tác giả : 

• GS. TSKH Hoàng Kiếm
• Ths. Đinh Anh Dũng

Download : Tại đây

Giải toán Thống kê bằng máy tính casio fx 570ES

Bài viết này sẽ hướng dẫn sử dụng máy tính Casio fx 570ES, loại máy được đa số học sinh THPT sử dụng hiện nay, để giải toán Thống kê ở cấp THPT.
Bước 1. Bật cột tần số khi nhập dữ liệu
Bấm lần lượt các phím: SHIFT SETUP REPLAY(xuống) 4 1
Bước 2. Vào chương trình thống kê và nhập dữ liệu
Bấm lần lượt các phím: MODE 3 1
Sau đó nhập dữ liệu: giá trị nhập ở cột X, tần số nhập ở cột FREQ
Bước 3. Tính các số đặc trưng của mẫu số liệu
Để tính số trung bình, bấm: SHIFT 1 5 2
Để tính độ lệch chuẩn, bấm: SHIFT 1 5 3
Còn phương sai chính là bình phương của độ lệch chuẩn vừa tìm được.

Tìm ước chung lớn nhất và bội chung nhỏ nhất của 2 số

Hãy nhập 2 số tự nhiên mà bạn muốn tìm ước chung lớn nhất và bội chung nhỏ nhất vào 2 ô đầu tiên. Sau đó bấm nút "calculate", lập tức bạn sẽ có kết quả.
Thực hành ở đây:
Lưu ý: Script này ko chạy được trên IE, bạn phải dùng 1 trong các trình duyệt sau: Chrome, FireFox.
Xem thêm: Thuật toán phân tích một số nguyên ra các thừa số nguyên tố.

Thuật toán phân tích một số nguyên ra các thừa số nguyên tố

Hãy nhập số tự nhiên ở ô đầu tiên. Sau đó, nhấn nút "factorize". Bạn sẽ có ngay các thừa số nguyên tố.

Thực hành ở đây:

Lưu ý: Script này ko chạy được trên IE, bạn phải dùng 1 trong các trình duyệt sau: Chrome, FireFox.

Xem thêm: Thuật toán tìm ƯCLN, BCNN của 2 số