Through fiction we saw The Birth
Of Futures Yet to come
Yet in Fiction lay the Bones
Ugly in their nakedness
Yet under this Mortal Sun
We cannot hide Ourselves

Để tìm hiểu sai lầm này chúng ta nhắc lại về nguyên lí QHD do Bellman phát minh ra: “Một dãy là tối ưu thì các dãy con của nó cũng là tối ưu”. Nghe có vẻ khó hiểu nhưng đại loại là ta có 1 cái bảng rồi lần lượt điền các số vào bảng đó, các số điền vào đầu tiên thường đơn giản, các số sau
đó dựa vào các số trước mà điền, cho đến khi điền kín bảng. Kết quả bài toán là số mà ta điền cuối cùng. Như vậy nguyên lí “chia để trị” đã được đẩy tới cao độ ở đây.

Khâu quan trọng nhất là làm thế nào điền được số sau dựa trên các số trước, hay nói cách khác là ta đang tìm 1 hệ thức truy hồi.

Gọi f(i) là hàm QHD tại i, ta xây dựng công thức truy hồi tính f(i) dựa vào các f(j) với j = i - 1, i - 2, … Công thức truy hồi này chỉ được phụ thuộc vào các f(j) cùng các đại lượng cố định của các j (cho trong đề bài) tuyệt đối không được phụ thuộc vào tiền sử, cách thức tạo nên f(j). Đây là chính là sai lầm mà tôi muốn nói đến!

Để dễ hiểu chúng ta xét 1 ví dụ rất thú vị sau:

Bài toán: ngày xửa ngày xưa, có 1 chàng Hoàng tử bị 1 mụ Phù thủy hóa phép biến thành 1 con ếch, còn Công chúa thì bị mụ ta nhốt trong 1 tòa lâu đài nằm trên 1 hòn đảo giữa hồ. Bây giờ ếch đang đứng ở bờ hồ, trên đoạn thẳng từ chỗ đó đến tòa lâu đài có các lá sen nổi trên mặt nước ở những vị trí, khoảng cách khác nhau, ếch phải nhảy qua các lá sen để vào tòa lâu đài cứu Công chúa. Bước nhảy kề sau không được dài hơn bước nhảy kề trước A mét cho trước.
Ếch có 1 túi rất nhiều muỗi thần, ăn K con muỗi, ếch có thể nhảy tối đa trong 1 bước là K mét. Mỗi bước nhảy (dù dài hay ngắn) đều tốn 1 giây. Cho trước thời gian giới hạn là T giây, hãy tính số muỗi ít nhất mà ếch cần ăn để có thể nhảy đến tòa lâu đài!

Dữ liệu vào cho trong file ECHOP.INP có cấu trúc:
Dòng đầu là 3 số nguyên N A T
Dòng 2 là N số nguyên dương tăng dần thể hiện tọa độ các lá sen.
Các số trên cùng 1 dòng cách nhau bởi ít nhất 1 dấu cách.
Dữ liệu ra file ECHOP.OUT gồm 1 số duy nhất là số muỗi tối thiểu, nếu không có phương án giải
cứu Công chúa in ra số -1

Rồi, đọc xong là biết phải dùng QHD, đây là cách sai:
Gọi d[t, i] là số muỗi ít nhất cần ăn khi phải nhảy đến lá sen thứ i và thời gian giới hạn là t. Để tính d[t, i] ta chỉ cần xét các d[j, t - 1] với j = i - 1, i - 2, … kiểm tra xem khoảng cách từ lá sen j đến lá sen i là bao nhiêu (là P), xem tiền sử của d[j, t - 1] xem lá sen kề trước j là lá nào (lá thứ z), tính khoảng cách giữa lá sen z và j là Q, kiểm tra Q + A >= P được thỏa mãn rồi đặt x = max(d[t, j], P), trong các x như thế chọn ra cái nhỏ nhất và đó chính là d[t, i]

Cách đúng: gọi d[t, i, j] là số muỗi ít nhất khi trong thời gian t, cần nhảy đến lá sen j nhưng lá kề trước j phải là i. Lúc này hệ thức truy hồi tương tự như trên nhưng không còn phụ thuộc tiền sử nữa.

Bạn cũng dễ mắc sai lầm này khi đi tìm cách giải hoàn hảo cho các bài toán “bất trị”, cho đến nay loài người vẫn chưa giải được như bài toán Người du lịch, bài toán Tìm đường đi dài nhất không lặp lại đỉnh trên đồ thị trọng số dương, bài toán Tập thống trị nhỏ nhất…

Về đến nhà mệt bã người, xong xuôi đâu đấy, theo thói quen trước khi đi ngủ, tôi bật máy lên nghe nhạc. Đã hết thời hạn làm crazy fan “tạm thời” của MCR, “I don’t love you”, uh, đúng đấy, “I don’t hate you”, cũng đúng luôn, tôi không thích mà cũng chẳng ghét MCR. Tôi định đêm nay tìm hiểu 1 band mới. Trong list các album download về để đó, ít hoặc chưa nghe, tôi ngẫu nhiên chọn Dolmen (Demo) của Öröm (country: Hungary, genres: Doom/Dark/Folk). OK, để xem thế nào.

Mở đầu album là tiếng mưa rơi tầm tã, 1 kiểu khá quen thuộc. Nhưng kiểu Doom của Öröm thì chả quen thuộc, không có gào thét thảm thiết, không có những đoạn riff xé lòng hay thê lương, không có cao trào hay điệp khúc gì cả. Tất cả cứ chầm chậm, đều đều, từ từ, vocal thì thầm, thở dài ngao ngán, khô khan. Bài nào cũng như bài nào, nhưng bài nào cũng hay.

Nhạc của Öröm gợi lên trước mắt người nghe những cảnh tượng của rừng già xám xịt, ảm đạm, bi ai, khói sương mù mịt, của nỗi nhớ, kỷ niệm buồn xa xăm.

Öröm cũng mới chỉ có 1 full length duy nhất ra năm 2006, tên là “8″, chỉ phát hành đúng 8 bản, nhưng album lại có 9 bài.

Chưa thể nói có thể làm fan của Öröm hay không, đợi nghe xong “8″ đã. Tuy nhiên, sống giữa cái thành phố ồn ào, bụi bặm và tắc đường này, đêm nay nghe Öröm, vâng, cho nói phét tí, như được sống giữa rừng thiêng nước độc, thiên nhiên hoang vắng, nỗi buồn và sự cô đơn mới đẹp làm sao!

Phát biểu bài toán nghe khá hấp dẫn: có N chàng trai và N cô gái, mỗi chàng trai phát biểu cảm nghĩ về N cô gái kia (rằng là cô này anh ta thích nhất, cô này thích nhì, ba, … cho đến cô thích thứ N) tương tự các cô gái cũng phát biểu như vậy về các chàng trai. Hãy ghép đôi họ với nhau sao cho các cuộc hôn nhân này là bền vững nghĩa là không được tồn tại 2 cặp mà người chồng bên cặp này lại thích người vợ bên cặp kia hơn vợ mình, đồng thời người vợ bên cặp kia lại cũng thích người chồng bên cặp này hơn chồng mình, khi đó 2 người này sẽ tìm đến với nhau và thế là ngoại tình.

Bây giờ chúng ta sẽ nghiên cứu 1 thuật toán xây dựng các cặp bền vững dựa trên ý tưởng giống như đời thực của bài toán. Mỗi chàng trai X sẽ chọn cho mình 1 cô dâu, hiển nhiên là anh ta sẽ chọn cô gái đầu tiên trong danh sách của mình. Nếu cô này đã hứa hôn (đã được chọn trước đó) với chàng trai khác mà cô ta thích hơn thì anh chàng X phải chọn người phụ nữ kế tiếp trong danh sách của anh ta, quá trình này tiếp tục cho đến khi X tìm được một cô Y chưa được hứa hôn hoặc thích anh ta hơn anh chàng đã hứa hôn trước đó. Nếu Y chưa được hứa hôn thì cô ta sẽ được gả cho X và chúng ta tiếp tục cho người đàn ông kế tiếp. Còn nếu Y đã hứa hôn thì sẽ hủy bỏ cuộc đính hôn và gả cô ta cho X (vì cô ta thích X hơn), và chúng ta lại tiếp tục với anh chàng vừa bị từ hôn.

Phương pháp này có lẽ được mô phỏng từ 1 câu chuyện trong các tiểu thuyết của thế kỉ 19. Rất đơn giản phải không? Nhưng còn cài đặt thì sao? Trong các tài liệu thường thấy ở VN thì họ dùng foward bởi phải xây dựng 2 hàm mà trong thân hàm này gọi tới hàm kia, rất rối rắm phức tạp, khó sửa lỗi và code cũng dài dòng. Còn trong cuốn Cẩm Nang Thuật Toán (sách dịch nước ngoài) tập 2, tác giả đã có 1 cách cài đặt vô cùng đỉnh cao, gọn nhẹ và xúc tích, (điều thường thấy trong bộ sách này) chẳng phải pho goắc pho ghiếc gì hết.

Bởi vì tất cả các danh sách sở thích đều co chung độ dài, cài đặt đơn giản nhất là dùng mảng 2 chiều. Ví dụ prefer[m, w] là cô gái thứ w trong danh sách sở thích của chàng trai thứ m. Hơn nữa chúng ta cần theo dõi xem mỗi chàng trai đã xử lí đến đâu trong danh sách anh ta. Điều nay có thể được thực hiện bằng 1 mảng 1 chiều next, mảng này khởi tạo đến 0 và next[m] + 1 là chỉ số của cô gái kế tiếp trong danh sách của chàng trai thứ m, chỉ danh của cô tra sẽ là prefer[m, next[m] + 1]. Với mỗi cô gái ta cần theo dõi vị hôn phu hiện thời là ai (fiancee[w] sẽ là chàng trai đã hứa hôn với cô gái w) và chúng ta cần trả lời câu hỏi ” người đàn ông thứ s có được thích hơn so với người đàn ông fiancee[w] hay không?”. Câu trả lời này có thể được giải đáp bằng cách tìm kiếm tuần tự cho tới khi s hoặc fiancee[w] được tìm thấy, nhưng cách này không hiệu quả nếu 2 người nằm ở cuối danh sách. Thay vì vậy, chúng ta dùng 1 danh sách ngược: rank[w, s] là chỉ số của chàng trai thứ s trong danh sách sở thích của cô w. Sự phù hợp của vị hôn phu s có thể xác định rất nhanh chóng bằng cách kiểm tra xem rank[w, s] có nhỏ hơn rank[w, fiancee[w]] hay không. Các mảng này được xây dựng dễ dàng và trực tiếp từ danh sách các sở thích. Để khởi đầu, chúng ta dùng 1 lính canh là chàng trai 0 để khởi tạo cho vị hôn phu và đặt anh ta ở cuối tất cả các danh sách sở thích của các cô gái.

Với cấu trúc dữ liệu được khởi tạo bằng phương pháp này, việc cài đặt có thể thực hiện dễ dàng như sau:

Language: Pascal
Author: Katatunix

for m := 1 to N do
begin
    s := m;
    repeat
        next[s] := next[s] + 1;
        w := prefer[s, next[s]];
        if rank[w, s] < rank[w, fiancee[w]] then
        begin
            t := fiancee[w]; fiancee[w] := s; s := t;
        end;
    until s = 0;
end;

package calexp;

public class CalculateExpression {

    private static final String MSG = "Invalid Expression";

    private static final String[] FUNCTION_LIST = {
        "abs", "sqrt", "sin", "cos", "tan", "cotan", "log", "exp", "pow"
    };

    private static final int[] PARAMETER_NUMBER = {
            1,      1,     1,     1,     1,       1,     1,     1,     2
    };

    public static double calculate(String exp) throws Exception {
        int sepa = findSeparator(exp);

        if (sepa == -1)
            return calcuSingleExp(exp);

        if (sepa == 0)
            switch (exp.charAt(0)) {
                case '+':
                    return calculate(exp.substring(1));
                case '-':
                    return -calculate(exp.substring(1));
                default:
                    throw new Exception(MSG);
            }

        double part1 = calculate(exp.substring(0, sepa));
        double part2 = calculate(exp.substring(sepa + 1));

        switch (exp.charAt(sepa)) {
            case '+':
                return part1 + part2;
            case '-':
                return part1 - part2;
            case '*':
                return part1 * part2;
            default:
                return part1 / part2;
        }
    }

    private static double calcuSingleExp(String exp) throws Exception {
        exp = exp.trim();
        if (exp.isEmpty()) throw new Exception(MSG);

        int len = exp.length();
        if (exp.charAt(len - 1) == ')') {
            if (len < 3 || findOpen(exp, len - 1) != 0)
                throw new Exception(MSG);
            return calculate(exp.substring(1, len - 1));
        }

        try {
            return Double.valueOf(exp);
        } catch (NumberFormatException e) {
            if (exp.charAt(len - 1) != ']') throw new Exception(MSG);
            int open = findOpen(exp, len - 1);
            String func = exp.substring(0, open).trim();

            exp = exp.substring(open + 1, len - 1);
            String[] sub = splitFay(exp);

            int funcIndex = findFuncIndexOf(func);
            if (funcIndex == -1) throw new Exception(MSG);
            if (sub.length > PARAMETER_NUMBER[funcIndex]) throw new Exception(MSG);

            double res = calculate(sub[0]);

            switch (funcIndex) {
                case 0: return Math.abs(res);
                case 1: return Math.sqrt(res);
                case 2: return Math.sin(res);
                case 3: return Math.cos(res);
                case 4: return Math.tan(res);
                case 5: return 1.0 / Math.tan(res);
                case 6: return Math.log(res);
                case 7: return Math.exp(res);
                default: return Math.pow(res, calculate(sub[1]));
            }
        }
    }

    private static int findFuncIndexOf(String func) {
        for (int i = 0; i < FUNCTION_LIST.length; i++)
            if (FUNCTION_LIST[i].equalsIgnoreCase(func))
                return i;
        return -1;
    }

    private static String[] splitFay(String listExp) throws Exception {
        java.util.ArrayList<String> listSub = new java.util.ArrayList<String>();
        char ch;
        int j = 0;
        for (int i = listExp.length() - 1; i >= 0; i--) {
            ch = listExp.charAt(i);
            if (ch == ')' || ch == ']')
                i = findOpen(listExp, i);
            else if (ch == ',') {
                listSub.add(listExp.substring(j, i));
                j = i + 1;
            }
        }
        listSub.add(listExp.substring(j, listExp.length()));
        String[] s = new String[listSub.size()];
        for (j = 0; j < s.length; j++)
            s[j] = listSub.get(j);
        return s;
    }

    private static int findSeparator(String exp) throws Exception {
        int len = exp.length();
        if (isOperator(exp.charAt(len - 1)))
            throw new Exception(MSG);

        int i, j = -1;
        char ch;
        for (i = len - 1; i >= 0; i--) {
            ch = exp.charAt(i);
            if (ch == ')' || ch == ']') {
                i = findOpen(exp, i);
                if (i == -1)
                    throw new Exception(MSG);
            } else if (ch == '+' || ch == '-') {
                return i;
            } else if (ch == '*' || ch == '/') {
                j = i;
            }
        }
        return j;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    private static int findOpen(String exp, int off) throws Exception {
        int count = 0;
        char close = exp.charAt(off);
        char open = close == ')' ? '(' : '[';
        while (off >= 0) {
            if (exp.charAt(off) == close) {
                count++;
            } else if (exp.charAt(off) == open) {
                count--;
                if (count == 0) return off;
            }
            off--;
        }
        throw new Exception(MSG);
    }

    public static void main(String[] args) {
        try {
            String s = "12*(16-(6-40/20)-7)  +  5*(23-3*(7-2))";
            System.out.println(calculate(s));

            s = "sqrt[pow[12*(16-(6-40/20)-7)  +  5*(23-3*(7-2)),3]]";
            System.out.println(calculate(s));

            s = "abs[cotan[sin[(5*(13-7)- (5*6-9)*2)+pow[2,3]*(sqrt[9*pow[9.13,2.2]]-8+12*cos[23])]-log[4]]]";
            System.out.println(calculate(s));

            s = "(1 * (4 + 50)) / 69";
            System.out.println(calculate(s));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

Sử dụng phương thức tĩnh setLights(num, level) của lớp DeviceControl trong gói com.nokia.mid.ui để điều khiển đèn điện thoại. Trong đó num = 0, level là mức độ sáng (0-100).

Để làm được màn hình trắng trơn, ta cần viết 1 Canvas có màu nền là White, đặt nó ở chế độ toàn màn hình bằng lệnh setFullScreenMode(true).

Code khá đơn giản:

// TestLight.java

import javax.microedition.lcdui.*;
import javax.microedition.midlet.*;
import com.nokia.mid.ui.*;

public class TestLight extends MIDlet
    implements CommandListener, Runnable {

    private Display display;
    private Form form;
    private Command exitCommand;
    private Command setCommand;
    private MyCanvas cv;

    public TestLight() {
        this.display = Display.getDisplay(this);
        this.form = new Form("Katatonia");
        this.exitCommand = new Command("Exit", Command.EXIT, 1);
        this.setCommand = new Command("Fuck it!", Command.OK, 1);
        this.form.addCommand(this.exitCommand);
        this.form.addCommand(this.setCommand);
        this.form.setCommandListener(this);
        this.form.append("Last fair deal gone down");

        this.cv = new MyCanvas();
    }

    protected void destroyApp(boolean unc) {
    }

    protected void pauseApp() {
    }

    protected void startApp() throws MIDletStateChangeException {
        this.display.setCurrent(this.form);
    }

    public void commandAction(Command c, Displayable d) {
        if (c == this.exitCommand) {
            this.destroyApp(false);
            this.notifyDestroyed();
        } else if (c == this.setCommand) {
            new Thread(this).start();
        }
    }

    public void run() {
        this.display.setCurrent(this.cv);
        for (int i = 0; i < 20; i++) {
            if (i % 2 == 0) DeviceControl.setLights(0, 0);
            else DeviceControl.setLights(0, 100);
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        this.display.setCurrent(this.form);
    }

}

// MyCanvas.java

import javax.microedition.lcdui.*;

public class MyCanvas extends Canvas {

    public MyCanvas() {
        this.setFullScreenMode(true);
    }

    protected void paint(Graphics g) {
        g.setColor(255, 255, 255);
        g.fillRect(0, 0, this.getWidth(), this.getHeight());
    }

}

Và chúng ta phải dùng JavaScript (xin đừng nhầm với Java, chúng hoàn toàn khác nhau). Một trong những thế mạnh to bự của JavaScript là nó có thể chọc ngoáy vào mã HTML vốn là tĩnh. Trang web ban đầu chỉ là mã HTML tĩnh để hiện "Loading…", khi tải xong, dùng Node.removeChild() để xóa chữ "Loading…", kế tiếp dùng Node.appendChild() để đưa vào nội dung chính.

Một sai lầm phổ biến tôi thường thấy là code đơn giản như sau:

var oImg = new Image;
oImg.src = "abc.jpg";

Câu lệnh thứ 2 sẽ mở ra một Thread mới, Thread này âm thầm tải ảnh "abc.jpg" vào bộ đệm, đồng thời, ko cần biết đã tải xong hay chưa, ngay tắp lự chạy dòng lệnh tiếp theo. Thế là hỏng việc!

Vậy thì vấn đề là ta phải túm được thời điểm tất cả các ảnh đã tải xong hết!

Bây giờ ta sẽ tạo 1 lớp tên là ImagePreloader, trong contructor của lớp này nhận vào 2 tham số là mảng URL của các tấm hình và tên gọi của hàm sẽ được thực thi sau khi tải xong hết các tấm hình ấy:

function ImagePreloader(images, call-back) {
    // store the call-back
    this.call-back = call-back;
    // initialize internal state
    this.nLoaded = 0;
    this.nProcessed = 0;
    this.aImages = new Array;
    // record the number of images
    this.nImages = images.length;
    // for each image, call preload()
    for (var i = 0; i < images.length; i++)
        this.preload(images[i]);
}

Hàm call-back được lưu lại để sử dụng sau này, các URL được truyền vào hàm preload:

ImagePreloader.prototype.preload = function(image) {
    // create new Image object and add to array
    var oImage = new Image;
    this.aImages.push(oImage);
    // set up event handlers for the Image object
    oImage.onload = ImagePreloader.prototype.onload;
    oImage.onerror = ImagePreloader.prototype.onerror;
    oImage.onabort = ImagePreloader.prototype.onabort;
    // assign pointer back to this
    oImage.oImagePreloader = this;
    oImage.bLoaded = false;
    // assign the .src property of the Image object
    oImage.src = image;
}

Hàm preload tạo ra 1 đối tượng Image mới, cho nó đăng kí 3 sự kiện: onload, onerror, onabort. onload được gọi khi tải thành công, onerror khi có lỗi và onabort khi user ngưng tải bằng cách nhấn nút Stop trên Toolbar của trình duyệt. Các câu lệnh tiếp theo đều dễ hiểu.

Cuối cùng, ta cài đặt sự kiện:

ImagePreloader.prototype.onComplete = function() {
    this.nProcessed++;
    if ( this.nProcessed == this.nImages ) {
        this.call-back(this.aImages, this.nLoaded);
    }
}

ImagePreloader.prototype.onload = function() {
    this.bLoaded = true;
    this.oImagePreloader.nLoaded++;
    this.oImagePreloader.onComplete();
}

ImagePreloader.prototype.onerror = function() {
    this.bError = true;
    this.oImagePreloader.onComplete();
}

ImagePreloader.prototype.onabort = function() {
    this.bAbort = true;
    this.oImagePreloader.onComplete();
}

Chú ý từ khóa this, theo lẽ thường, this sẽ trỏ vào lớp ImagePreloader, tuy nhiên ở trong ngữ cảnh này, this lại trỏ vào đối tượng Image xin đăng kí sự kiện.

Đương nhiên thứ mà lần nào cũng có là ruốc do chính tay mama làm (trong này gọi là chà bông, hừm, hồi đầu nghe tường xà bông, quái, người ta ăn được xà bông sao). Thứ này để được lâu, xếp vào loại lương khô. Tôi không ăn nổi ruốc miền Nam, ngọt quá! Mua mấy cái bánh mì không, cho ruốc vào, ngồi nhâm nhi đọc Teppi, nghe mấy bản nhạc ưa thích, chà chà…

Và… kẹo lạc! Cái thứ kẹo quê mùa. Các bạn trẻ xì tin ngày nay mấy ai thích ăn kẹo lạc? Hehe, tôi thì thích, nếu có trà xanh để nhắm nữa thì cứ gọi là hết cả gói to.

Nhắc đến kẹo lạc, có ai còn nhớ bài đồng dao ngày xưa này ko:

Anh lớp trưởng lấy chị quản ca
Tối hôm qua đi ra Bờ Hồ
Ăn kẹo lạc, hút thuốc lá
Một hai ba chúng ta… tụt quần

• a[i, j] = 0 nếu ô (i, j) trống
• a[i, j] = k > 0 nếu ô (i, j) chứa quân thứ k

Giả sử có 2 ô có quân Pokemon giống nhau cho trước (i1, j1) và (i2, j2) làm thế nào để kiểm tra đường đi thỏa mãn giữa chúng? Vì số lần rẽ chỉ giới hạn là 2 nên bạn có thể liệt kê, xét hết tất cả các trường hợp cùng với 1 đống if else lồng nhau loạn xạ, cách này không hay cho lắm. Ta hãy xét 1 cách khác hay hơn, chuyển bài toán về dạng đồ thị như sau:

• 2 ô (i1, j1) và (i2, j2) cho trở thành ô trống
• tập đỉnh của đồ thị là tập các ô trống
• 2 đỉnh có cạnh nối với nhau nếu 2 ô tương ứng với chúng là (u1, v1) và (u2, v2) cùng nằm trên 1 cột hay 1 hàng và nằm giữa 2 ô này toàn là ô trống
• trọng số tất cả các cạnh đều = 1

Bài toán chuyển về tìm đường đi ngắn nhất từ đỉnh ứng với ô (i1, j1) đến đỉnh ứng với ô (i2, j2). Nên dùng Tìm kiếm theo chiều rộng vì trọng số các cạnh chỉ là 1. Nếu đường đi này có độ dài không vượt quá 3 thì kết luận có đường đi thỏa mãn, ngược lại thì không có.

Các bạn thấy sao? Có ai có thuật toán nào nhanh hơn thì vào bàn bạc nhé!