Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    1 Bài toán tìm đường đi ngắn nhất? on Tue Jun 14, 2011 8:10 pm

    sangminh


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Em sang minh đây.
    Em cám ơn các anh chị nhé
    Em có một vấn đề muốn trao đổi. Khi em làm bài toán du lịch thì gặp một vấn đề anh ah. Đó là tìm min tương ứng với hàng và cột giao nhau bằng 0, sau đó cộng chúng lại với nhau. Tìm tổng có giá trị lớn nhất. Tương ứng với cùng (hàng, cột). Nhưng nếu có nhiều giá trị như nhau = max thì làm thế nào anh?

    Đây là bài toán trong toán rời rạc... em làm nhiều ví dụ thấy toàn gặp trường hợp có nhiều giá trị max giống nhau nên ko biết lựa chọn cái nào để loại bỏ?
    Nhờ anh chị xem giúp em
    em cảm ơn nhé!

    Ban QT Diễn đàn nhắc: Bạn sangminh chú ý một chút nhé!
    Bạn sangminh cần sử dụng một bộ gõ tiếng Việt, để gõ tiếng Việt có dấu vào diễn đàn.
    Nếu nêu vấn đề mới, bạn nên viết một chủ đề riêng, để các chủ đề theo dõi được tập trung.
    Không spam vào các bài viết, để chủ đề khỏi bị loãng.
    Nên viết chương trình ở dạng giả mã, để có thể tránh những sai sót của phần mềm mình mắc phải. Nếu dùng C hoặc Pascal, hoặc Basic sẽ có rất nhiều lỗi của phần mềm → dễ mất điểm

    sangminh


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    anh chị ơi..ở ngoài đó ôn cấu trúc dữ liệu như thế nào? có thể chỉ cho em hướng đi với được không?
    em cứ tự mò mẫm.. rồi tập cài đặt các thuật toán anh chị xem giúp em nhé
    ah... có tài liệu ôn thi nào. ,, các đề năm ngoái về cấu trúc dữ liệu anh chị cho em với.
    Đây là bài của em.. Lần đầu tham gia. có gì anh chị góp ý nhé.
    ≡≡≡≡≡- cai dat thuat toan tim duong di ngan nhat-≡
    #include
    #include

    #define TOIDA 50
    #define VOCUNG 30000
    #define TRUE 1
    #define FALSE 0

    /* Khai bao ma tran trong so cua do thi
    weight[i][j] = VOCUNG: neu tren do thi khong co cung
    weight[i][j] != 0 : tren do thi co cung */
    int weight[TOIDA][TOIDA];

    int SoNut; // so nut thuc su co tren do thi

    // Khoi dong ma tran trong so cua do thi
    void initialize()
    {
    int i, j;
    for(i = 0; i < TOIDA; i++)
    for(j = 0; j < TOIDA; j++)
    weight[i][j] = VOCUNG;
    }

    // Tac vu joinwt: them mot cung moi tu node1 den node2 co trong so wt
    void joinwt(int node1, int node2, int wt)
    {
    weight[node1][node2] = wt;
    }

    // Tac vu remvwt: xoa mot cung tu node1 den node2
    void remvwt(int node1, int node2)
    {
    weight[node1][node2] = VOCUNG;
    }

    /* Tac vu dijkstra: tim duong di ngan nhat tren do thi co trong so theo
    giai thuat Dijkstra.
    Du lieu nhap:
    s: nut di, t: nut den
    Du lieu xuat:
    ngan1: chieu dai duong di ngan nhat tu s den t
    duongdi[]: mang ghi nhan lo trinh ngan nhat tu s den t, luu y
    duongdi[i] la nut truoc nut i tren lo trinh ngan nhat */
    void dijkstra(int s, int t, int *ngan1, int duongdi[])
    {
    int i, k, kc, nuthientai, min, kcachmoi;
    int tapcacnut[TOIDA]; // tap cac nut da xet
    int kcach[TOIDA]; /* mang luu chieu dai duong di ngan nhat tu nut
    s den cac nut khac */

    // Buoc 0: khoi dong mang tapcacnut[] va kcach[]
    for(i = 0; i < SoNut; i++)
    {
    tapcacnut[i] = FALSE;
    kcach[i] = VOCUNG;
    }

    // dua nut s vao tap nut da xet
    tapcacnut[s] = TRUE;
    kcach[s] = 0;
    nuthientai = s;

    /* vong lap thuc hien cac buoc 1, 2, ... cho den khi dua duoc nut t vao
    tap nut da xet */
    while(nuthientai != t)
    {
    min = VOCUNG;
    kc = kcach[nuthientai]; /* kc chieu dai duong di ngan nhat tu nut s
    den nuthientai */
    for(i = 0; i < SoNut; i++)
    if(tapcacnut[i] == FALSE)
    {
    kcachmoi = kc + weight[nuthientai][i];
    if(kcachmoi < kcach[i])
    {
    kcach[i] = kcachmoi;
    duongdi[i] = nuthientai; /* gan nuthientai la nut truoc
    nut i tren lo trinh */
    }
    if(kcach[i] < min)
    {
    min = kcach[i];
    k = i;
    }
    }
    // Dua nut k vao tap nut da xet
    nuthientai = k;
    tapcacnut[nuthientai] = TRUE;
    }
    *ngan1 = kcach[t];
    }

    // Chuong trinh chinh
    void main()
    {
    int chon, x, y, i, j;
    char c;
    int wt, ngan1;
    int duongdi[TOIDA];
    int s, t;
    clrscr();

    initialize();
    SoNut = 0;

    do
    {
    printf("\n\n\tCHUONG TRINH TIM DUONG DI NGAN NHAT - GIAI THUAT DIJKSTRA");
    printf("\n\nCac chuc nang cua chuong trinh:\n");
    printf("\n1: Tao do thi moi");
    printf("\n2: Them mot nut");
    printf("\n3: Them mot cung");
    printf("\n4: Xoa mot cung");
    printf("\n5: Xoa toan bo do thi");
    printf("\n6: Xac dinh so nut co tren do thi");
    printf("\n7: Duyet cac cung");
    printf("\n8: Tim cung");
    printf("\n9: Tim duong di ngan nhat");
    printf("\n0: Thoat");
    printf("\nChon chuc nang: ");
    scanf("%d", &chon);
    switch(chon)
    {
    case 1:
    {
    initialize();
    printf("\nDo thi moi co bao nhieu nut: ");
    scanf("%d", &SoNut);
    printf("\Hay nhap cac cung cua do thi (nhap %d %d de ket thuc):\n",
    SoNut, SoNut);
    x = 0;
    y = 0;
    while(x < SoNut && y < SoNut)
    {
    printf(" Nhap cung: ");
    scanf("%d %d", &x, &y);
    if(x < SoNut && y < SoNut)
    {
    printf(" Trong so cua cung %d %d: ", x, y);
    scanf("%d", &wt);
    weight[x][y] = wt;
    }
    };
    break;
    }
    case 2:
    {
    if(SoNut < TOIDA)
    {
    SoNut++;
    printf("So nut hien co la %d", SoNut);
    }
    else
    printf("Khong the them nut moi");
    break;
    }
    case 3:
    {
    printf("\nNhap cung can them: ");
    scanf("%d %d", &x, &y);
    if(x >= SoNut || y >= SoNut)
    printf("Khong hop le");
    else
    {
    printf("Trong so cua cung %d -> %d : ", x, y);
    scanf("%d", &wt);
    joinwt(x, y, wt);
    }
    break;
    }
    case 4:
    {
    printf("\nNhap cung can xoa: ");
    scanf("%d %d", &x, &y);
    remvwt(x, y);
    break;
    }
    case 5:
    {
    printf("\nBan co chac khong (c/k): ");
    c = getche();
    if(c == 'c' || c == 'C')
    {
    initialize();
    SoNut = 0;
    }
    break;
    }
    case 6:
    {
    printf("\nSo nut co tren do thi la %d", SoNut);
    break;
    }
    case 7:
    {
    printf("\nCac cung co tren do thi:\n");
    for(i = 0; i < SoNut; i++)
    for(j = 0; j < SoNut; j++)
    if(weight[i][j] < VOCUNG)
    printf(" %d%s%d : %d\n", i, " -> ", j, weight[i][j]);
    break;
    }
    case 8:
    {
    printf("\nNhap cung can tim: ");
    scanf("%d %d", &x, &y);
    if(x >= SoNut || y >= SoNut)
    printf("Khong hop le");
    else
    if(weight[x][y] < VOCUNG)
    printf("Co cung voi trong so %d", weight[x][y]);
    else
    printf("Khong co cung nay");
    break;
    }
    case 9:
    {
    printf("\nNhap nut di: ");
    scanf("%d", &s);
    printf("\nNhap nut den: ");
    scanf("%d", &t);
    dijkstra(s, t, &ngan1, duongdi);
    printf("\nDuong di ngan nhat tu %d->%d la: %d ", s, t, ngan1);
    printf("\nLo trinh: ");
    i = t;
    while(i != s)
    {
    printf("%d <- ", i);
    i = duongdi[i];
    }
    printf("%d", s);
    break;
    }
    }
    } while(chon !=
    0);
    }

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    @sangminh:

    - Cảm ơn đã chia sẻ.

    - Hi vọng là bạn đã có tài liệu, chẳng hạn như sách [You must be registered and logged in to see this link.].

    - Bạn nên giải quyết bài toán dưới dạng thuật toán + giả mã. Viết rõ ràng từng bước một, đặc biệt là giải thuật Dijkstra.

    - Viết bài như bạn thì lúc thi kể cả có tài liệu để chép thì cũng chưa chắc là đã kịp. [You must be registered and logged in to see this image.]


    ================
    [You must be registered and logged in to see this image.]

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - Nếu chỉ số max bằng nhau thì chọn cung nào cũng được. Nhưng phải chỉ ra tất cả các cung → có thể có nhiều hành trình tối ưu.


    ================
    [You must be registered and logged in to see this image.]

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Một số ý kiến với bạn sangminh:
    Bài làm của bạn như trên chỉ cho vui thôi vì không đáp ứng được yêu cầu của đề bài thi ra. Có nghĩa là nếu bạn làm như vậy vào bài đi thi sẽ được 0 điểm.
    1. Ở đây yêu cầu của đề là trình bày thuật toán và vận dụng thuật toán phù hợp để giải quyết vấn đề nêu ra, nên người ta không yêu cầu phải viết thành chương trình.
    2. Nếu bạn cố tình viết chương trình, bạn phải viết có cấu trúc. Chỉ riêng vấn đề thụt thò không đúng là các thầy cũng đưa điểm của bạn về 0 rồi.
    3. Khi chia sẻ, bạn nên viết thành câu có dấu để người đọc không hiểu lầm ý của bạn. Vì mình đang giả mã mà.
    4. Bạn nên đọc các hướng dẫn và xem các bài trình bày của các chuyên gia để rút ra được cách trình bày được điểm. Nên nhớ một điều rằng, bạn chỉ viết sai cấu trúc một chữ thôi, đã bị đánh giá là không hiểu, thì bạn sẽ không có điểm nào đâu.
    5. Bạn nên đọc tài liệu Cấu trúc dữ liệu và giải thuật mà anh MrP đưa đường link, nếu bạn không muốn mua tài liệu đó, để biết cách viết bằng giả mã.
    6. Bạn nên tập làm, gửi bài lên, các anh chị chuyên viên sẽ sửa cho. Từ đó rút kinh nghiệm đi thi để tránh 0 điểm.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    sangminh


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    em cảm ơn các anh chị nhé.
    em sẽ rút kinh nghiệm.
    Anh chị ơi. thế môn cấu trúc dữ liệu không cần viết thành chương trình ah?
    em chỉ cần viết thuật toán mô phổng giả lập có được điểm không?
    anh chị có đề thi môn này các năm trước không chia sẽ cho em với.
    Em cảm ơn anh chị nhé.
    chúc mọi người vui vẻ nhé!@

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Free blog