Trang 3/3 Đầu 123
kết quả từ 25 tới 34 trên 34

Nhờ các bạn xem bài này giùm nên làm thế nào

  1. #25
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.723

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Chủ yếu giải thuật phải chứng minh được, khi không có cơ sở chứng minh mà chỉ là nhận định, thì ý tưởng đó vẫn có thể dẫn đến kết quả sai. Giống mình đã chứng minh ở trên của giải thuật của tengiday có kẽ hở qua việc test thử tập input. Đôi khi một sai lệch nhỏ cũng ảnh hưởng đến vận mệnh cả thế giới, vì vậy mình rất quan tâm đến việc chạy đúng trước khi nghĩ cách giải nhanh. Vì có những cái không thể giải nhanh được.

    Còn tài liệu giải thuật bạn đưa chờ mình phải dịch và đọc hiểu cách người ta chứng minh xem có đúng hay không đã mới nói được sau. Vì trong toán học không có gì là bất biến cả, các tiên đề toán học được người đời công nhận hàng thế kỷ nhưng về sau lại có người chứng minh được nó sai. Hãy nhớ đến câu truyện "trái đất phẳng".

    P/S: mình không bảo người khác không làm được và đầy người thông minh, tài năng hơn mình, nhưng họ có thể nhìn nhận đúng bản chất vấn đề hay không lại phụ thuộc vào thế giới quan và cách nhìn nhận của mỗi người
    www.thuthuatdoday.tk - Chia sẻ thủ thuật, tiện ích máy tính


  2. #26
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 403392
    Bài gửi
    7

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Khẩu khí lớn quá!!! Nếu như bạn tengiday là người mình quen thật, thì 10 năm về trước chính bạn đó đã đưa tài liệu cho mình về bài này đó nha. From Wikipedia,
    In the case where there are an arbitrary number of people with arbitrary crossing times, and the capacity of the bridge remains equal to two people, the problem has been completely analyzed by graph-theoretic methods.
    HTML Code:
    https://en.wikipedia.org/wiki/Bridge_and_torch_problem
    Bạn nói câu "chạy cho đúng trước" là hiểu trình độ rồi, còn non lắm nha. Mình chờ kết quả bạn xem cái đó đúng hay sai đó!!!

  3. Đã cảm ơn tuan.huynh.87:


  4. #27
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.723

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Trích Nguyên văn bởi tuan.huynh.87 Xem bài viết
    Khẩu khí lớn quá!!! Nếu như bạn tengiday là người mình quen thật, thì 10 năm về trước chính bạn đó đã đưa tài liệu cho mình về bài này đó nha. From Wikipedia,

    HTML Code:
    https://en.wikipedia.org/wiki/Bridge_and_torch_problem
    Bạn nói câu "chạy cho đúng trước" là hiểu trình độ rồi, còn non lắm nha. Mình chờ kết quả bạn xem cái đó đúng hay sai đó!!!
    Đây là một câu đố kinh điển đã làm bao nhiêu nhà toán học trên thế giới phải trăng trở và nhiều nhà toán học đã cố gắng phát thảo các bổ đề, mệnh đề để tìm MIN mà không phải liệt kê

    Còn người ta lấy ví dụ khảo sát với N=4, tìm ra các quy luật để xây dựng, nhưng đây không phải toán cộng 1 + 1 = 2, vì vậy các mệnh đề ban đầu có phát sinh trường hợp sai nên mới có các bổ đề để bổ sung để xử lý riêng các trường hợp đó

    Khi N=5, N=6 -> vô cùng, với N càng cao thì càng nhiều biến cố phát sinh, vì vậy mới phải cần một chương trình chạy đúng để đem so sánh với kết quả với mệnh đề, bổ đề đã xây dựng. Vì vậy, các nhà toán học bây giờ mới cần các siêu máy tính để trợ giúp việc tính toán đó bạn.

    Còn tài liệu bạn đưa mình đọc không hiểu, bạn có thể giúp mình thông, khai sáng các tiền đề mà tác giả xây dựng, tập trung vào phần 3: The Optimal Solution, còn Theorem 1: chẳng biết từ đâu nhảy ra công thức xác định MIN, các tài liệu tham khảo kèm theo thì không kiếm được

  5. #28
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    35

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    gunshot9x: Em xem rất nhiều bài viết của bạn thì bạn rất giỏi (rất giỏi), giỏi hơn cả mấy bạn ktv em quen. Nhưng về mảng lập trình, thuật toán thì bạn chỉ chạm vào bề mặt của nó. Bạn chưa xem tài liệu mà đã tuyên bố trong bài viết #25 "xem có đúng hay không" rồi bây giờ quay sang bảo không hiểu thì thật sự .... Cái thái độ của bạn chính là lý do mấy người không ưa. Bạn ham nói đại ngôn, nói chi tiết là hớ, làm thì tự bạn hiểu lấy...

    Bài nghiên cứu đó dùng lý thuyết đồ thị (graph-theoretic methods). Thầy em bảo sau này em sẽ được học. Bạn tự nói chưa qua trường lớp, tự học. Bây giờ bảo chỉ bạn thì phải xây dựng cả 1 lý thuyết cho bạn đó. Cấu trúc của bài nghiên cứu là state cái results ngay phần introduction. Sau đó tới những bài nghiên cứu có liên quan chứ không phải "Theorem 1 chẵng biết từ đâu". Sau đó là chứng minh (The Optimal solution). Nhận xét của bạn thể hiện rõ "trình độ" giống như bạn tuan.huynh.87 nói đó.

    tuan.huynh.87: Em đọc chưa hiểu được. Chắc sau này sẽ hiểu. Nó được đăng trên tạp chí khoa học luôn. Quá ghê!!! Mà nè, nếu vét cạn thì bài này em vét như thế nào vậy? Bạn chỉ em đi.

  6. Đã cảm ơn LanSG9x:


  7. #29
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.723

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Phần nghiêm cứu cấu trúc thì hiểu rồi nha bạn, nó xét N = 4 và có 3 hướng sắp xếp, nhưng tự nhiên nó độp ra cái Theorem 1: ra công thứ MIN(C0, C1, ..., C[N/2-1]) với mọi N>= 2. Nó mới khảo sát N = 4 với 1 dẫy 1, 2, 5, 10 mà lại đưa ra nhận định cho toàn bộ.

    - Xây dựng các công thức cũng phải xét U(n) và U(n + 1) để tìm ra mối liên hệ mới xây dựng được công thức tổng quát.
    - Nó mới xét bộ số với tính chất sau: a1 < a2 < a3 < a4 và a2 - a1 < a3 - a2 < a4 - a3 vậy các bộ số khác thì sao a2 - a1 < a4 - a3 < a3 - a2, a4 - a3 < a2 - a1 < a3 - a2 ...

    Dù mình không học chuyên sâu toán cao cấp nhưng mấy điều cơ bản đó mình đều biết. Mình không phải theo bên Toán tin ứng dụng, Công nghệ thông tin mà học một ngành khác và lĩnh vực hoàn toàn khác, nhưng khối kỹ thuật mấy môn Giải tích, Đại số cao cấp, Vật lý đại cương, Tin học đại cương là bắt buộc, các định lý lúc học đêu được thầy cô xây dựng lại và chứng minh, nó giúp hình thành cách tư duy và đặt vấn đề

    Mình đang cần bạn ấy cung cấp thêm các tài liệu tham khảo ở phần cuối tài liệu gốc có nhắc đến đó bạn, không học qua trường lớp thì không phải không biết tư duy và tự học nha bạn, không hiểu mới phải có tài liệu để đọc thêm vì mấy cuốn đó khó kiếm, khó tìm, thuật toán mình dùng tự nghĩ ra và suy luận chứ không đi sâu vào tìm hiểu học, khái quát thành mô hình tổng quát, đơn giản đó không phải ngành của mình, vì bạn nên biết rằng khi muốn khái quát một vấn đề trong toán học người ta tốn thời gian rất lâu để xây dựng, đưa ra thảo luận, nhiều người nghĩ trên nhiều quan điểm phương diện mới có cái nhìn khách quan, lúc đó là thời gian kiểm trứng, chứ bạn không thể một sớm một chiều mà chứng minh nó có chính xác hay không, được đăng báo khoa học cũng chỉ là một hình thức khác đưa công trình nghiên cứu của mình tới nhiều độc giả hơn, từ đó mới tiếp nhận lại các phản hồi, các luận điểm các nhà toán học khác với công trình mình công bố

    Bài này có thể dùng thuật toán quay lui để xử lý vét cạn

    Ý tưởng: A = a[1], a[2], a[3], ..., a[n]

    A = prefix(n-i) | subfix(i)

    sẽ có một phân cách ảo mỗi lần đi và về

    chưa di chuyển A = n|0 khi bài toán kết thúc khi A = 0|n

    liêt kê tập con 2 phần tử trong n phần tử: for (i: 1 => n-1) for (j: i+1 => n) => a[i], a[j]

    di chuyển đi 2 từ prefix sang subfix => địch 2 phần tử được chọn xuống cuối mảng đó, vị trí phân cách là 2, A= n-2|2
    di chuyển về 1 từ subfix sang prefix => lấy 1 phần tử subfix(i) dịch vào cuối prefix(n-i), vị trí phân cách là 1, A= n-1|1

    rồi lại truy hồi về hàm đó lại thực hiện liệt kê lựa chọn và tính bước di chuyển

    1 2 5 10 |

    Lúc đi, chọn 2 phần tử prefix
    1 2 => 5 10 | 1 2
    1 5 => 2 10 | 1 5
    1 10 => ...
    2 5 => ...
    2 10 => ...
    5 10 => ...

    Trong nhánh 1 2 => 5 10 | 1 2 vể sẽ chọn 1 phần tử subfix chuyển lại
    1 => 5 10 1 | 2
    2 => 5 10 2 | 1

    Cứ như vậy tiếp tục đi sâu vào nhánh đi 5 10 1 | 2
    5 10 => 1 | 2 5 10
    5 1 => 10 | 2 5 1
    10 1 => 5 | 2 10 1

    Xét nhánh về nhánh 1|2 5 10
    2 => 1 2 | 5 10
    5 => 1 5 | 2 10
    10 => 1 10 | 2 5

    prefix đến nhánh này chỉ còn 2 phần tử nên chỉ có đi và kết thúc nhánh đó và quay trở lại nhánh cha phía trên
    1 2 | 5 10 => |5 10 1 2
    1 5 | 2 10 => |2 10 1 5
    1 10 | 2 5 => |2 5 1 10

    nhánh ngọn đã hết trở lại nhánh cha phía quay trở lại nhánh về 10 | 2 5 1
    2 => 10 2 | 5 1
    5 => 10 5 | 2 1
    1 => 10 1 | 2 5

    ...

    cứ như vậy đến đi hết các nhánh, mỗi nhánh đường đi nhớ lại vết, khi nhánh chính (nhánh bên trái, ngoài cũng) đã thực hiện xong, lấy thời gian nhánh đó làm gốc

    - nếu thời gian các nhánh sau ở vị trí xét mà đã lớn hơn nhánh chính đã hoàn thành thì có thể bỏ qua toàn bộ nhánh dưới cấp nó, để tiết kiệm thời gian tính toán

    - nếu nhánh khác đã đến đích mà có thời gian ngắn hơn thì đặt nó làm mốc

    Hình ảnh chỉ mang tính chất minh họa cho bạn dễ hình dung


  8. #30
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.723

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Trích Nguyên văn bởi tuan.huynh.87 Xem bài viết
    @gunshot9x: Mình chả hiểu bạn nói gì luôn đó. Bạn bỏ tính nói đại ngôn và nói một cách rõ ràng đi. Tài liệu nào? Google không có sao? Mấy cái này không học đàng hoàng, tay ngang vào mà phán bừa "xem có đúng không". Sau đó quay sang nói đọc không hiểu. Đó không phải ngành của bạn mà bạn mạnh miệng dữ ha. NẾU BẠN LÀ MÌNH THÌ BẠN NGHĨ GÌ, CẢM GIÁC GÌ KHI NGHE NGƯỜI NGOÀI NGÀNH NÓI KIỂU ĐÓ????
    Bạn có tư duy không vậy => lúc bạn đưa mình đã tiếp cận tài liệu đó đâu, còn bạn LanG9x sửa đổi bổ sung lại mệnh đề tengiday giải sau khi mình đưa ra trường hợp không đúng => đưa ra giải pháp phải lý giải giải pháp đó là đúng, để tránh bỏ sót trường hợp như ban đầu

    Còn tài liệu bạn đưa, có chỗ đọc không hiểu, nên mới cần các tài liệu liên quan để xem cách nó chứng minh, từ đó nắm rõ bản chất và trong đó có nhắc tới cuốn Puzzle book của Levmore and Cook năm 1981 tài liệu cổ nhất tác giả có nhắc đến mà mình không tìm được

    Mình nói không phải ngành của mình vì nó không phải ngành mình theo học, còn khi người ngoài nói vậy thì mình chẳng có cảm giác gì cả nha bạn, đó là cảm giác thật của mình, không phải vì không yêu nghề, không có tự trọng, tự tôn ngành của mình, bạn không thể đòi hỏi một con người toàn năng, toàn diện. Nó chẳng phải không học hành đàng hoàng, mỗi người có một thế mạnh khác nhau và bạn nên biết thiên tài toán học cũng không nhiều như cây trong rừng, các thứ bạn đang học đang thừa hưởng lại từ những người đi trước chứ không phải do bạn sáng tạo ra, không có người đi lật lại vấn đề, phát hiện ra những điểm hạn chế, nhưng sai sót thì nhiều định lý toán học đã không được bổ sung và sửa đổi, lịch sử những người phát hiện ra để sửa đổi, đều là những người dành cả đời cho toán học (giải dạy, nghiên cứu xây dựng và phân tích các mô hình toán học, ...)

    Muốn gì thì gì cũng phải đọc hiểu cái đã, đã không hiểu bạn bảo mình sao phân tích xem nó có đúng không

  9. #31
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 403392
    Bài gửi
    7

    Angry Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    @gunshot9x: Mình chả hiểu bạn nói gì luôn đó. Bạn bỏ tính nói đại ngôn và nói một cách rõ ràng đi. Tài liệu nào? Google không có sao? Mấy cái này không học đàng hoàng, tay ngang vào mà phán bừa "xem có đúng không". Sau đó quay sang nói đọc không hiểu. Đó không phải ngành của bạn mà bạn mạnh miệng dữ ha. NẾU BẠN LÀ MÌNH THÌ BẠN NGHĨ GÌ, CẢM GIÁC GÌ KHI NGHE NGƯỜI NGOÀI NGÀNH NÓI KIỂU ĐÓ????

  10. Đã cảm ơn tuan.huynh.87:


  11. #32
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 403392
    Bài gửi
    7

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Trích Nguyên văn bởi LanSG9x Xem bài viết
    tuan.huynh.87: Em đọc chưa hiểu được. Chắc sau này sẽ hiểu. Nó được đăng trên tạp chí khoa học luôn. Quá ghê!!! Mà nè, nếu vét cạn thì bài này em vét như thế nào vậy? Bạn chỉ em đi.
    @lansg9x: Bạn gunshot9x cho ví dụ có thể tham khảo. Nhưng mà chi tiết như lưu trạng thái ra sao (cái quan trọng nhất) thì bạn đó bỏ rồi (điển hình mấy bài của bạn đó đều thế). Lưu nguyên mảng cũng được, nhưng mà mỗi lần phải chạy so sánh mảng. Bạn biết xử lý bit thì encode nguyên cái trạng thái thành 2^(n+1) trường hợp thì so sánh dễ hơn. Ví dụ như 4 người đều ở bờ A, thuyến ở bờ A thì ban đầu là 11111 (5 con số 1 với 4 số đầu tượng trưng cho 4 người đang ở bờ 1, số 1 ở cuối tượng trưng cho thuyền đang ở bờ 1). Tức có nghĩa rằng trạng thái (2^5 - 1) được đánh dấu lại xem như trạng thái ban đầu. Ai ở bờ bên kia thì bit đó là số 0. Duyệt như thế nào thì bạn dùng đệ quy quay lui như bạn gunshot9x nói đó.

  12. Đã cảm ơn tuan.huynh.87:


  13. #33
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 403392
    Bài gửi
    7

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Đây là comment cuối cùng của mình cho bạn gunshot9x (sổ đen thôi): Thiếu hiểu biết thì đừng tỏ ra nguy hiểm làm gì nha! Bạn muốn tự học thì tự mà tìm tòi, bỏ ra giá, vào thư viện mà học hỏi (bạn tốt nghiệp THPT chưa mà không biết điều này). Mình không có nghĩa vụ phải cung cấp tài liệu free cho bạn đâu để bạn tự hiểu. Tìm cái sai thì tự tìm bằng chứng (pháp luật hiện hành đấy). Topic này thể hiện ra kiến thức của bạn về lĩnh vực thuật toán rất con nít mà cứ thích tuyên bố cuồng ngôn.
    Mình xin lỗi diễn đàn, nhưng mà có những hạng người mình không chửi không được!!!!

  14. Đã cảm ơn tuan.huynh.87:


  15. #34
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    35

    Reply: Nhờ các bạn xem bài này giùm nên làm thế nào

    Trích Nguyên văn bởi tuan.huynh.87 Xem bài viết
    @lansg9x: Bạn gunshot9x cho ví dụ có thể tham khảo. Nhưng mà chi tiết như lưu trạng thái ra sao (cái quan trọng nhất) thì bạn đó bỏ rồi (điển hình mấy bài của bạn đó đều thế). Lưu nguyên mảng cũng được, nhưng mà mỗi lần phải chạy so sánh mảng. Bạn biết xử lý bit thì encode nguyên cái trạng thái thành 2^(n+1) trường hợp thì so sánh dễ hơn. Ví dụ như 4 người đều ở bờ A, thuyến ở bờ A thì ban đầu là 11111 (5 con số 1 với 4 số đầu tượng trưng cho 4 người đang ở bờ 1, số 1 ở cuối tượng trưng cho thuyền đang ở bờ 1). Tức có nghĩa rằng trạng thái (2^5 - 1) được đánh dấu lại xem như trạng thái ban đầu. Ai ở bờ bên kia thì bit đó là số 0. Duyệt như thế nào thì bạn dùng đệ quy quay lui như bạn gunshot9x nói đó.
    Xin lỗi, dạo này em bận quá. Tranh thủ đêm khuya và em mới tìm hiểu xong, em viết như sau:
    Mã:
    int *a, n, *f;
    long long int min_time = LLONG_MAX;
    
    void helper(int status, long long int cur_time) {
        if (!status) // all people on B side
            min_time = min(min_time, cur_time);
        else if (cur_time < min_time) {
            if (status & 1) {
                // Boat at A. 2 people cross the river.
                for (int i = 1; i <= n; i++)
                    if ((status >> i) & 1) {
                        for (int j = i+1; j <= n; j++)
                            if ((status >> j) & 1) {
                                int change2 = (status ^ (1 << i)) ^ (1 << j);
                                if (f[change2]) {
                                    f[change2] = 0;
                                    helper(change2 ^ 1, cur_time + max(a[i-1], a[j-1]));
                                    f[change2] = 1;
                                }
                            }
                    }
            }
            else {
                // Boat at B. Only 1 person can cross.
                for (int i = 1; i <= n; i++)
                    if (!((status >> i) & 1)) {
                        int change1 = status ^ (1 << i);
                        if (f[change1]) {
                            f[change1] = 0;
                            helper(change1 ^ 1, cur_time + a[i-1]);
                            f[change1] = 1;
                        }
                    }
            }
        }
    }
    
    void river_crossing_brute_force2() {
        f = (int *)malloc(sizeof(int) * (1 << (n+1)));
        for (int i = 0; i < (1 << (n+1)); f[i++] = 1);
        f[(1 << (n+1)) - 1] = 0;
    
        helper((1 << (n+1)) - 1, 0);
    
        free(f);
    }
    
    int main() {
        n = 7;
        a = (int *)malloc(sizeof(int) * n);
        a[0] = 2;
        a[1] = 10;
        a[2] = 12;
        a[3] = 14;
        a[4] = 16;
        a[5] = 18;
        a[6] = 20;
    
        river_corssing_brute_force2();
        printf("%lld\n", min_time);
    }

Trang 3/3 Đầu 123