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

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
[ah]
PHP:
[code]
#include<iostream>
#include<stdio.h>
#include<conio.h>
char stack[20]; //them phan tu vao Stack
int dinh=-1, n; //  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!=0 && 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=0; i<n; i++)
    {
     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=0; i<n; i++)
    printf(" %c ",b[i]);
    for( i=0;i<n; i++)
    {
     printf("\n%c ",b[i]);
     for( j=0; j<n; j++)
     {
      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(count) printf("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]
[/ah]
đố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 ạ
HbwJ9b1.jpg

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 :(
 

tengiday

Happy life
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).
[ah]
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);
    }
}
[/ah]
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ị.
 
Sửa lần cuối:

hienn366

[you] còn zin kooo?
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).
[ah]
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);
    }
}
[/ah]
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


 

tengiday

Happy life
Mình dựa theo code của bạn viết 2 functions này.
[ah]
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);
}
[/ah]
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?
 
Sửa lần cuối:

hienn366

[you] còn zin kooo?
Mình dựa theo code của bạn viết 2 functions này.
[ah]
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);
}
[/ah]
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
 

tengiday

Happy life
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.
 
Sửa lần cuối:

hienn366

[you] còn zin kooo?
Đú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ứ...
 

hienn366

[you] còn zin kooo?
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?
 

Thống kê

Chủ đề
100,667
Bài viết
467,441
Thành viên
339,833
Thành viên mới nhất
duythinh2222
Top