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

cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù 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
    153

    cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chu trình và đường đi Euler

    đây là code bài tập

    PHP Code:
    [code]
    #include<iostream>
    #include<stdio.h>
    #include<conio.h>
    char stack[20]; //them phan tu vao Stack
    int dinh=-1n//  luu dinh (top) da di qua
    char b[20],duongdi_ketthuc[20]; //i
    char ma_tranke[20][20]; //A(ij)
    int fp=0,count//dinh xuat phat la dinh bac le neu do thi co dinh bac le


    //day hoat dong vao trong stack(phan tu tren cung cua stack)
    void them_vao(char gia_tri)
    {
    dinh=dinh+1;
    stack[dinh]=gia_tri;
    }


    //lay hoat dong ra tu stack(phan tu tren dinh cua Stack)
    char lay_ra()
    {
    return 
    stack[dinh--];
    }


    //kiem tra tat ca cac dinh lien ke ben ngoai/cac nut da di qua
    //hoac khong co
    int daqua_tatca(int i)// bieu dien bang ma tran dinh-dinh co hoac khong
    {
        
    int j;
        for(
    j=0;j<n;j++)
        {
           if(
    ma_tranke[i][j]=='c')
           return 
    0;
        }
        return 
    1;
    }


    //cho biet den cac chi so cua nut hien hanh trong mang b tai cac nut
    int chobiet_khong(char k)
    {
        
    int l=0;
        while(
    k!=b[l])
        
    l++;
        return 
    l;


    }


    //hien thi duong di/chu trinh euler
    void duong_ht()
    {
         
    int i;
         for(
    i=0;i<fp;i++)
         {
           
    printf("%c ->",duongdi_ketthuc[i]);
         }
    }


    //tim kiem chu trinh/duong di euler va su luu lai no trong mang[] duong di ket thuc
    void tim_euler(int goc)
    {
         
    int l,j;
         
    //day goc vao trong stack
        
    them_vao(b[goc]);
        
    //tien trinh len den kho chua tro nen rong v.e(G) dinh=-1
        
    while(dinh!=-1)
        {
          
          
    //cho biet chi so mang cua dinh nam o stack
          
    l=chobiet_khong(stack[dinh]);
          
    // neu tat ca cac nut lien ke da di qua
          // lay phan tu tu stack ra va su luu lai no trong mang[] duong di ket thuc
          
    if(daqua_tatca(l))
          {
            
    duongdi_ketthuc[fp++]=lay_ra();
            
          }
          
    // neu bat ki nut nao chua di qua co the su dung nut do them vo trong stakc
          //dau vet canh(Edge(ij)-noi 2 dinh) do nhu da di qua boi danh dau 'k' trong ma tran ke[][]
          // pha vo cac vong lap(thuc hien lap)
          
    else
          {
            for(
    j=0;j<n;j++)
            {
            if(
    ma_tranke[l][j]=='c')
            {
                
                 
    ma_tranke[l][j]='k';
                 
    ma_tranke[j][l]='k';
                 
    them_vao(b[j]);
                
                 break;
               
            }
            }
           }
         }
    }


    //cho biet den bac dinh cua nut v.e(G) khong co cac canh hien thoi da ket noi den nut
    int chobiet_bacdinh(int i)
    {
        
    int j,deg_bac=0;
        for(
    j=0;j<n;j++)
        {
          if(
    ma_tranke[i][j]=='c'deg_bac++;
        }
        return 
    deg_bac;
    }


    //gan gia tri goc cua do thi
    //dieu kien 1: Neu tat ca cac nut co bang bac dinh chan, nen tai do se la mot mach/chu trinh euler
    //chung ta co the bat dau duong di tu nut bat ki
    //dieu kien 2: Neu chinh xa la 2  dinh bac le, nen tai do se la mot duong di euler
    //chung ta co the bat dau tu nut nao co dinh bac le
    //dieu kien 3: neu cac nut hon 2 hoac chinh xac la 1 nut dinh bac le, khong la duong di/chu trinh euler


    //tim_goc se quay lai 0 neu khong la duong di/chu trinh euler
    //mat khac no se quay lai chi so mang cua nut bat ki nhu goc
    int tim_goc()
    {
         
         
    int i,cur=1;// gia dinh goc la 1
         
    for(i=0;i<n;i++)
         {
            if(
    chobiet_bacdinh(i)%2!=0)
            {
               
    count++;
               
    cur=i;// su luu lai nut co lua chon dinh bac le den bien cur
            
    }
         }
         
    // neu dem khong chinh xac la 2 khi khong la duong di/chu trinh euler vi the quay lai 0
         
    if(count!=&& count!=2)
         {
            return 
    0;
         }
         else return 
    cur;// neu cac nut chinh xac la 2 dinh bac le, no se quay lai nhu 1 nut goc mat khac quay lai 1 nhu da gia dinh o goc
    }


    int main()
    {
        
    char v;
        
    int i,j,l;
        
    printf("nhap so dinh do thi:\n");
        
    scanf("%d",&n);
        
    printf("nhap ten dinh cua do thi:\n");
        for( 
    i=0i<ni++)
        {
         
    scanf("%s",&b[i]);// suu luu lai cac nut trong mang b[]
        
    }
        
        
    //cho biet chi tiet do thi boi dung ma tran lien ke  
        
    printf("gia tri ma tran lien ke tuong ung la 'Co' hoac 'Khong'\n");
        
    printf("\nnhap gia tri trong ma tran la 'C' hoac 'K'\n");
        for( 
    i=0i<ni++)
        
    printf(" %c ",b[i]);
        for( 
    i=0;i<ni++)
        {
         
    printf("\n%c ",b[i]);
         for( 
    j=0j<nj++)
         {
          
    printf("%c ",v=getch());
          
    ma_tranke[i][j]=v;
         }
          
    printf("\n\n");
        }
        
    // tim_goc se quay lai 0 neu khong la duong di/chu trinh euler
    // mat khac no se quay lai chi so mang cua nut bat ki nhu goc
        
    int goc1;
        if(
    goc1=tim_goc())
        {
          if(
    countprintf("la duong di euler\n");
          else 
    printf("la chu trinh euler\n");
          
    tim_euler(goc1);
          
    duong_ht();
        }
        else 
    printf("khong la duong di hoac chu trinh euler\n");
        
    getch();
    }
    [/
    code

    đối với chu trình thì in ra mình thấy ok rồi chỉ còn đường đi thôi ạ
    nên mình cần mấy bạn pro giúp mình ở chổ này
    mình đang cần in ra kết quả như hình này ạ

    phần code bài tập anh bạn học chung chỉ mà chỉ có làm được 1 đường đi
    không thể in ra nhiều đường đi như hình
    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
    881

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Mình viết rất đơn giản. Giả sử chỉ có mỗi 1 cung duy nhất nối giữa mọi cặp đỉnh (như trong code của bạn).
    Mã:
    void dfs(std::vector<std::vector<char>> &a, int start, int &m, std::vector<int> &path) {
        if (m < 1) {
            printf("%d", path[0]);
            for (int i = 1; i < (int)path.size(); ++i)
                printf("->%d", path[i]);
            printf("\n");
        }
        else
            for (int i = 0; i < (int)a.size(); ++i)
                if (a[start][i] == '1') {
                    a[start][i] = '0';
                    a[i][start] = '0';
                    path.push_back(i);
                    --m;
                    dfs(a, i, m, path);
                    a[start][i] = '1';
                    a[i][start] = '1';
                    path.pop_back();
                    ++m;
                }
    }
    
    void find_all_Euler_Paths(std::vector<std::vector<char>> &a, int m) {
        std::vector<int> path;
        for (int i = 0; i < (int)a.size(); ++i) {
            path.clear();
            path.push_back(i);
            dfs(a, i, m, path);
        }
    }
    
    void allEulerPaths() {
        int n = 0;
        printf("N = "); scanf("%d", &n);
        if (n > 0) {
            printf("Enter '-1 -1' to finish.\n");
            std::vector<std::vector<char>> a(n, std::vector<char>(n, '0'));
            int i = -1, j = -1, m = 0;
            do {
                i = j = -1;
                printf("0 <= u,v < n   (u,v) = ");
                scanf("%d %d", &i, &j);
                if (i > -1 && j > -1) {
                    a[i][j] = a[j][i] = '1';
                    ++m;
                }
            } while (i > -1 && j > -1);
            find_all_Euler_Paths(a, m);
        }
    }

    Bài này chỉ có thể vét cạn, không có thuật toán tốt. Đây là bài #P, tương ứng với bài tìm số lượng chu trình Euler trong đồ thị.
    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. #3
    Ðến Từ
    Vĩnh Long
    Thành Viên Thứ: 275165
    Giới tính: Nam
    Bài gửi
    153

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình viết rất đơn giản. Giả sử chỉ có mỗi 1 cung duy nhất nối giữa mọi cặp đỉnh (như trong code của bạn).
    Mã:
    void dfs(std::vector<std::vector<char>> &a, int start, int &m, std::vector<int> &path) {
        if (m < 1) {
            printf("%d", path[0]);
            for (int i = 1; i < (int)path.size(); ++i)
                printf("->%d", path[i]);
            printf("\n");
        }
        else
            for (int i = 0; i < (int)a.size(); ++i)
                if (a[start][i] == '1') {
                    a[start][i] = '0';
                    a[i][start] = '0';
                    path.push_back(i);
                    --m;
                    dfs(a, i, m, path);
                    a[start][i] = '1';
                    a[i][start] = '1';
                    path.pop_back();
                    ++m;
                }
    }
    
    void find_all_Euler_Paths(std::vector<std::vector<char>> &a, int m) {
        std::vector<int> path;
        for (int i = 0; i < (int)a.size(); ++i) {
            path.clear();
            path.push_back(i);
            dfs(a, i, m, path);
        }
    }
    
    void allEulerPaths() {
        int n = 0;
        printf("N = "); scanf("%d", &n);
        if (n > 0) {
            printf("Enter '-1 -1' to finish.\n");
            std::vector<std::vector<char>> a(n, std::vector<char>(n, '0'));
            int i = -1, j = -1, m = 0;
            do {
                i = j = -1;
                printf("0 <= u,v < n   (u,v) = ");
                scanf("%d %d", &i, &j);
                if (i > -1 && j > -1) {
                    a[i][j] = a[j][i] = '1';
                    ++m;
                }
            } while (i > -1 && j > -1);
            find_all_Euler_Paths(a, m);
        }
    }

    Bài này chỉ có thể vét cạn, không có thuật toán tốt. Đây là bài #P, tương ứng với bài tìm số lượng chu trình Euler trong đồ thị.
    cái code của mình làm thì chỉ in ra được 1 đường đi Euler
    1 -> 2 -> 5 -> 4 -> 3 -> 2 -> 4
    nếu như trong code của mình thì mình nên sửa chổ nào để nó in ra danh sách đường đi Euler như vậy
    1 -> 2 -> 3 -> 4 -> 2 -> 5 -> 4
    1 -> 2 -> 3 -> 4 -> 5 -> 2 -> 4
    1 -> 2 -> 4 -> 3 -> 2 -> 5 -> 4
    1 -> 2 -> 4 -> 5 -> 2 -> 3 -> 4
    1 -> 2 -> 5 -> 4 -> 2 -> 3 -> 4
    C++ này mình chưa hiểu nhiều ở nó lấm
    Mong bạn trợ giúp cho mình hiểu để mình sửa ở những dòng code của mình để nó in ra danh sách đường đi
    cảm ơn bạn nhiều



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

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Mình dựa theo code của bạn viết 2 functions này.
    Mã:
    void dfs(int start, int m) {
        if (m < 1) {
            printf("%c", duongdi_ketthuc[0]);
            for (int i = 1; i < fp; ++i)
                printf(" -> %c", duongdi_ketthuc[i]);
            printf("\n");
        }
        else
            for (int i = 0; i < n; ++i)
                if (ma_tranke[start][i] == 'c') {
                    ma_tranke[start][i] = ma_tranke[i][start] = 'k';
                    duongdi_ketthuc[fp++] = b[i];
                    dfs(i, m - 1);
                    ma_tranke[start][i] = ma_tranke[i][start] = 'c';
                    --fp;
                }
    }
    
    void all_Eulerian_paths(int goc) {
        int m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (ma_tranke[i][j] == 'c')
                    ++m;
        duongdi_ketthuc[0] = b[goc];
        fp = 1;
        dfs(goc, m);
    }

    Trong 'main', bạn đổi 2 functions 'tim_euler' và 'duong_ht' bằng function 'all_Eulerian_paths(goc1)' thì nó sẽ in ra tất cả đường đi Euler có điểm xuất phát là goc1. Nếu bạn muốn in ra tất cả Eulerian paths thì bạn phải thay đổi function 'tim_goc' để trả ra danh sách tất cả các đỉnh có thể xuất phát từ đó đc.

    Thuật toán bạn dùng để in ra 1 đg` đi / chu trình Euler không thích hợp thay đổi để nó in ra nhiều đg` đi. Mình đã nói, bài này chỉ có thể vét cạn tất cả các cách đi, nó tương ứng với bài tìm số lượng đg` đi / chu trình Euler, thuộc về #P, ko có thuật toán tốt.

    - Bạn nên hạn chế dùng global variables, mà nên viết trong functions nhiều hơn.

    PS: Bạn đã học tới Euler rồi mà giáo viên không cho dùng STL stack và vector của C++ nữa hả bạn?

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

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình dựa theo code của bạn viết 2 functions này.
    Mã:
    void dfs(int start, int m) {
        if (m < 1) {
            printf("%c", duongdi_ketthuc[0]);
            for (int i = 1; i < fp; ++i)
                printf(" -> %c", duongdi_ketthuc[i]);
            printf("\n");
        }
        else
            for (int i = 0; i < n; ++i)
                if (ma_tranke[start][i] == 'c') {
                    ma_tranke[start][i] = ma_tranke[i][start] = 'k';
                    duongdi_ketthuc[fp++] = b[i];
                    dfs(i, m - 1);
                    ma_tranke[start][i] = ma_tranke[i][start] = 'c';
                    --fp;
                }
    }
    
    void all_Eulerian_paths(int goc) {
        int m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (ma_tranke[i][j] == 'c')
                    ++m;
        duongdi_ketthuc[0] = b[goc];
        fp = 1;
        dfs(goc, m);
    }

    Trong 'main', bạn đổi 2 functions 'tim_euler' và 'duong_ht' bằng function 'all_Eulerian_paths(goc1)' thì nó sẽ in ra tất cả đường đi Euler có điểm xuất phát là goc1. Nếu bạn muốn in ra tất cả Eulerian paths thì bạn phải thay đổi function 'tim_goc' để trả ra danh sách tất cả các đỉnh có thể xuất phát từ đó đc.

    Thuật toán bạn dùng để in ra 1 đg` đi / chu trình Euler không thích hợp thay đổi để nó in ra nhiều đg` đi. Mình đã nói, bài này chỉ có thể vét cạn tất cả các cách đi, nó tương ứng với bài tìm số lượng đg` đi / chu trình Euler, thuộc về #P, ko có thuật toán tốt.

    - Bạn nên hạn chế dùng global variables, mà nên viết trong functions nhiều hơn.

    PS: Bạn đã học tới Euler rồi mà giáo viên không cho dùng STL stack và vector của C++ nữa hả bạn?
    thuật toán này là tím kiếm chiều sâu hả bạn?


    trong lớp mình giáo viên chỉ hướng lí thuyết 1 chút ,bài tập làm nhóm thì tự tìm hiểu sau đó khi gần hết môn mới chỉ ra...?
    mấy bạn trong nhóm mình giờ mới có lịch học tiếp theo nên hơn 1 tuần con ai mắt muốn thâm quầng hết rồi

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

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Trích Nguyên văn bởi hienn366 Xem bài viết
    thuật toán này là tím kiếm chiều sâu hả bạn?


    trong lớp mình giáo viên chỉ hướng lí thuyết 1 chút ,bài tập làm nhóm thì tự tìm hiểu sau đó khi gần hết môn mới chỉ ra...?
    mấy bạn trong nhóm mình giờ mới có lịch học tiếp theo nên hơn 1 tuần con ai mắt muốn thâm quầng hết rồi
    Đúng rồi, là DFS, nhưng đi theo cạnh.

    Hồi đó mình mới học lập trình thì học Pascal, bậc THCS và THPT. Lúc đó Google mới đc vài năm chưa phát triển đc như bây giờ, lúc đấy tài liệu toàn thuộc trường chuyên, không truyền ra ngoài. Thầy của mình cũng ko rõ nhiều chỗ, bởi vậy ko dạy gì đc cả. Bạn của mình lén lén lấy dùm bài tập (ko phải lý thuyết) từ trường chuyên ra đưa cho mình làm. Nhớ lại cảm giác vô cùng thích khi gặp đc 1 bài tập, mặc dù mình làm chả ra sao cả. Lúc sau mới biết mấy cái này đc dạy trên đại học.

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

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    Trích Nguyên văn bởi tengiday Xem bài viết
    Đúng rồi, là DFS, nhưng đi theo cạnh.

    Hồi đó mình mới học lập trình thì học Pascal, bậc THCS và THPT. Lúc đó Google mới đc vài năm chưa phát triển đc như bây giờ, lúc đấy tài liệu toàn thuộc trường chuyên, không truyền ra ngoài. Thầy của mình cũng ko rõ nhiều chỗ, bởi vậy ko dạy gì đc cả. Bạn của mình lén lén lấy dùm bài tập (ko phải lý thuyết) từ trường chuyên ra đưa cho mình làm. Nhớ lại cảm giác vô cùng thích khi gặp đc 1 bài tập, mặc dù mình làm chả ra sao cả. Lúc sau mới biết mấy cái này đc dạy trên đại học.
    mình học có giao viên nhiệt tình lấm... ko hiểu là cứ mời thầy xuống coi hướng dẫn tận tình
    có giáo viên nói nói... chỉ qua loa kêu mình tự tìm hiểu mà ko hướng dẫn tìm
    như thủ thuật trên google hay là các loại toài liệu, cứ như là mò kim dưới biển
    nản lắm...môn này thuộc cái loại " giải thuật và lập trình" bọn bạn mình muốn xỉu thiệt chứ...

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

    Reply: cần mấy bạn pro hổ trợ bổ sung giúp mình bài tập C++ tìm chù trình và đường đi Euler

    bạn ơi nếu như code bài của mình có thể thêm chức năng đọc và ghi dữ liêu file text không bạn?