kết quả từ 1 tới 8 trên 8

Bài tập C Chu trình và đường đi EULER

  1. #1
    Ðến Từ
    Vĩnh Long
    Thành Viên Thứ: 275165
    Giới tính: Nam
    Bài gửi
    120

    Post Bài tập C Chu trình và đường đi EULER

    mình cần 1 chương trình viết bằng C++ bạn nào giỏi giỏi giúp mình với.

    mong được giúp đỡ nhiều ạ.
    mình cảm ơn trước
    14 giọng đọc tiếng anh chuẩn thất truyền nè Khách


    PHP Code:
    http://vforum.vn/diendan/showthread.php?96700-14-giong-doc-Tieng-Anh-chuan-tong-hop-phan-mem-ho-tro-da-that-truyen-D 
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C Chu trình và đường đi EULER

    Mình làm câu 4 cho bạn nhé (Euler cycle: chu trình qua các cạnh, mỗi cạnh 1 lần). Đề quá ngắn gọn, mình không có nhiều thời gian, nên mình sẽ assume rằng:
    - Input lúc nào cũng có chu trình Euler cả (đỉnh bậc chẵn).
    Code đơn giản nhất đây:
    Mã:
    #include <vector>
    #include <stack>
    
    #define MAX_DIGITS 64
    
    std::vector<int> EulerCycle(std::vector<std::vector<int>> &a) {
        std::vector<int> result;
        if (a.empty()) return result;
        std::stack<int> s;
        s.push(0);
        while (!s.empty()) {
            int x = s.top();
            for (int i = 0; i < (int)a.size(); ++i)
                if (a[x][i] > 0) {
                    --a[x][i];
                    --a[i][x];
                    s.push(i);
                    break;
                }
            if (x == s.top()) {
                s.pop();
                result.push_back(x);
            }
        }
        return result;
    }
    
    void EulerProblem(char * inputF, char * outputF) {
        FILE * f = fopen(inputF, "r");
        if (f == 0) {
            printf("%s not found.\n", inputF);
            return;
        }
        char s[MAX_DIGITS];
        fgets(s, MAX_DIGITS, f);
        int n(0), m(0), x(-1), y(-1);
        sscanf(s, "%d %d", &n, &m);
        std::vector<std::vector<int>> a(n, std::vector<int>(n, 0));
        while (fgets(s, MAX_DIGITS, f) != 0) {
            sscanf(s, "%d %d", &x, &y);
            a[y][x] = ++a[x][y];
        }
        fclose(f);
        
        std::vector<int> result = EulerCycle(a);
    
        f = fopen(outputF, "w");
        if (result.empty()) {
            fprintf(f, "-1\n");
            fclose(f);
            return;
        }
        for (int i = (int)result.size() - 1; i > 0; --i)
            fprintf(f, "%d -> ", result[i]);
        fprintf(f, "%d\n", result[0]);
        fclose(f);
    }
    Độ phức tạp của thuật toán O(|E|), linear theo số cạnh, nếu optimize được quá trình tìm cạnh chưa đi (vòng 'for' bên trong có thể đơn giản).

    Bạn đang học phần này àh? Mấy câu trên có vẻ lý thuyết quá; hoàn toàn có trong sách mà.
    Đường đi tối thiểu bao phủ đồ thị là gì mình không rõ. Tối thiểu là đg` đi ngắn nhất? Bao phủ là bao phủ đỉnh hay cạnh?
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Vĩnh Long
    Thành Viên Thứ: 275165
    Giới tính: Nam
    Bài gửi
    120

    Reply: Bài tập C Chu trình và đường đi EULER

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình làm câu 4 cho bạn nhé (Euler cycle: chu trình qua các cạnh, mỗi cạnh 1 lần). Đề quá ngắn gọn, mình không có nhiều thời gian, nên mình sẽ assume rằng:
    - Input lúc nào cũng có chu trình Euler cả (đỉnh bậc chẵn).
    Code đơn giản nhất đây:
    Mã:
    #include <vector>
    #include <stack>
    
    #define MAX_DIGITS 64
    
    std::vector<int> EulerCycle(std::vector<std::vector<int>> &a) {
        std::vector<int> result;
        if (a.empty()) return result;
        std::stack<int> s;
        s.push(0);
        while (!s.empty()) {
            int x = s.top();
            for (int i = 0; i < (int)a.size(); ++i)
                if (a[x][i] > 0) {
                    --a[x][i];
                    --a[i][x];
                    s.push(i);
                    break;
                }
            if (x == s.top()) {
                s.pop();
                result.push_back(x);
            }
        }
        return result;
    }
    
    void EulerProblem(char * inputF, char * outputF) {
        FILE * f = fopen(inputF, "r");
        if (f == 0) {
            printf("%s not found.\n", inputF);
            return;
        }
        char s[MAX_DIGITS];
        fgets(s, MAX_DIGITS, f);
        int n(0), m(0), x(-1), y(-1);
        sscanf(s, "%d %d", &n, &m);
        std::vector<std::vector<int>> a(n, std::vector<int>(n, 0));
        while (fgets(s, MAX_DIGITS, f) != 0) {
            sscanf(s, "%d %d", &x, &y);
            a[y][x] = ++a[x][y];
        }
        fclose(f);
        
        std::vector<int> result = EulerCycle(a);
    
        f = fopen(outputF, "w");
        if (result.empty()) {
            fprintf(f, "-1\n");
            fclose(f);
            return;
        }
        for (int i = (int)result.size() - 1; i > 0; --i)
            fprintf(f, "%d -> ", result[i]);
        fprintf(f, "%d\n", result[0]);
        fclose(f);
    }
    Độ phức tạp của thuật toán O(|E|), linear theo số cạnh, nếu optimize được quá trình tìm cạnh chưa đi (vòng 'for' bên trong có thể đơn giản).

    Bạn đang học phần này àh? Mấy câu trên có vẻ lý thuyết quá; hoàn toàn có trong sách mà.
    Đường đi tối thiểu bao phủ đồ thị là gì mình không rõ. Tối thiểu là đg` đi ngắn nhất? Bao phủ là bao phủ đỉnh hay cạnh?
    này là 1 bài kiểm tra chỉ có câu 4-5 là viết chương trình đó bạn?

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C Chu trình và đường đi EULER

    Mình đã làm câu 4 rồi; riêng câu 5 mình cần biết rõ về giả thuyết. Ý nghĩa "bao phủ tối thiểu", đồ thị vô hướng hay có hướng. Kiến thức của mình toàn bằng tiếng Anh cả nên mình ko rõ thuật ngữ chuyên môn tiếng Việt. Nếu bạn nói đến path cover với đồ thị vô hướng thì ko có thuật toán đa thức nhé. Nếu là đồ thị có hướng thì đưa bài toán này về bài stable matching, cặp ghép, thì sẽ có giải thuật tốt.

  6. Đã cảm ơn tengiday:


  7. #5
    Ðến Từ
    Vĩnh Long
    Thành Viên Thứ: 275165
    Giới tính: Nam
    Bài gửi
    120

    Reply: Bài tập C Chu trình và đường đi EULER

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình đã làm câu 4 rồi; riêng câu 5 mình cần biết rõ về giả thuyết. Ý nghĩa "bao phủ tối thiểu", đồ thị vô hướng hay có hướng. Kiến thức của mình toàn bằng tiếng Anh cả nên mình ko rõ thuật ngữ chuyên môn tiếng Việt. Nếu bạn nói đến path cover với đồ thị vô hướng thì ko có thuật toán đa thức nhé. Nếu là đồ thị có hướng thì đưa bài toán này về bài stable matching, cặp ghép, thì sẽ có giải thuật tốt.
    vậy cho xin 2 dạng
    có hướng và vô hướng đi bạn

    cảm ơn bạn đã trợ giúp!

  8. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Bài tập C Chu trình và đường đi EULER

    Trích Nguyên văn bởi hienn366 Xem bài viết
    vậy cho xin 2 dạng
    có hướng và vô hướng đi bạn

    cảm ơn bạn đã trợ giúp!
    Bạn giải thích (định nghĩa) rõ "bao phủ tối thiểu" và "đg` đi" ở trong bài là thế nào trc đã. Ví dụ đơn giản như hình chữ Y, thì ko cách gì đi qua mỗi đỉnh mà đi liên tục và mỗi đỉnh đi đúng 1 lần đc (chỉ có thể đi lại, hoặc xuất phát từ đỉnh khác để tạo thành 2 đg` đi). Như vậy cái đg` đi ở đây đc định nghĩa như thế nào? Ngoài ra, đồ thị có trọng sô hay không có, trọng số không âm hay như thế nào? Bạn quyết định luôn vô hướng hay có hướng nhé vì mình ko có thời gian code 2 bài.
    Nhiều bài graph cho tới nay cũng ko có thuật toán tốt.

  9. #7
    Ðến Từ
    Vĩnh Long
    Thành Viên Thứ: 275165
    Giới tính: Nam
    Bài gửi
    120

    Reply: Bài tập C Chu trình và đường đi EULER

    Trích Nguyên văn bởi tengiday Xem bài viết
    Bạn giải thích (định nghĩa) rõ "bao phủ tối thiểu" và "đg` đi" ở trong bài là thế nào trc đã. Ví dụ đơn giản như hình chữ Y, thì ko cách gì đi qua mỗi đỉnh mà đi liên tục và mỗi đỉnh đi đúng 1 lần đc (chỉ có thể đi lại, hoặc xuất phát từ đỉnh khác để tạo thành 2 đg` đi). Như vậy cái đg` đi ở đây đc định nghĩa như thế nào? Ngoài ra, đồ thị có trọng sô hay không có, trọng số không âm hay như thế nào? Bạn quyết định luôn vô hướng hay có hướng nhé vì mình ko có thời gian code 2 bài.
    Nhiều bài graph cho tới nay cũng ko có thuật toán tốt.
    nó là đường đi Euler
    bài tập viết chương trình tìm đường đi

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

    Reply: Bài tập C Chu trình và đường đi EULER

    Tham khảo
    Mã:
    https://vi.wikipedia.org/wiki/%C4%90%C6%B0%E1%BB%9Dng_%C4%91i_Euler#C.C3.A1c_.C4.90.E1.BB.8Bnh_ngh.C4.A9a_v.E1.BB.81_chu_tr.C3.ACnh_v.C3.A0_.C4.91.C6.B0.E1.BB.9Dng_.C4.91i_Euler
    www.thuthuatdoday.tk - Chia sẻ thủ thuật, tiện ích máy tính