Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: [ Solved ]Giải thuật Prim !

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    1

    Red face [ Solved ]Giải thuật Prim !

    các anh ơi,cho em hỏi để viết chương trình bài toán tìm đường đi ngắn nhất bằng giải thuật prim viết trên ngôn ngữ lập trình c thì phải làm sao.xin cho em 1 vd cu thể giúp e với

    Vui lòng post Tiếng Việt có dấu cho tiêu đề nhé cậu ! Thân !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 23-04-2008 lúc 09:23 AM.

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi phubaby Xem bài viết
    các anh ơi,cho em hỏi để viết chương trình bài toán tìm đường đi ngắn nhất bằng giải thuật prim viết trên ngôn ngữ lập trình c thì phải làm sao.
    Bạn cần phải

    - Trình bày giải thuật bằng ngôn ngữ tự nhiên (tiếng Việt) hay giả mã (ngôn ngữ pha trộn giữa ngôn ngữ lập trình và ngôn ngữ tự nhiên).

    - Nêu rõ những điểm nào trong giải thuật đã làm bạn thắc mắc và cần giúp đỡ để diễn đạt bằng ngôn ngữ C.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    There
    C Code:
    1. #include <cstdio>
    2.  
    3. /*The input file :
    4.         4
    5.         0 0 0 21
    6.         0 0 8 17
    7.         0 8 0 16
    8.         21 17 16 0
    9.  
    10.     The first line contains n, the number of nodes.
    11.     Next is an nxn matrix containg the distances between the nodes
    12.     NOTE: The distance between a node and itself should be 0
    13. */
    14.  
    15. int n; /* The number of nodes in the graph */
    16.  
    17. int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
    18.             if there is no path between i and j, weight[i][j] should
    19.             be 0 */
    20.  
    21. char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
    22.             spanning tree; 0 otherwise*/
    23.  
    24. int d[100]; /* d[i] is the distance between node i and the minimum spanning
    25.         tree; this is initially infinity (100000); if i is already in
    26.         the tree, then d[i] is undefined;
    27.         this is just a temporary variable. It's not necessary but speeds
    28.         up execution considerably (by a factor of n) */
    29.  
    30. int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
    31.             linked to in order to get a distance of d[i] */
    32.  
    33. /* updateDistances(int target)
    34.     should be called immediately after target is added to the tree;
    35.     updates d so that the values are correct (goes through target's
    36.     neighbours making sure that the distances between them and the tree
    37.     are indeed minimum)
    38. */
    39. void updateDistances(int target){
    40.     int i;
    41.     for (i = 0; i < n; ++i)
    42.         if ((weight[target][i] != 0) && (d[i] > weight[target][i])){
    43.             d[i] = weight[target][i];
    44.             whoTo[i] = target;
    45.         }
    46. }
    47.  
    48. int main(int argc, char *argv[]){
    49.     FILE *f = fopen("dist.txt", "r");
    50.     fscanf(f, "%d", &n);
    51.     int i, j;
    52.     for(i = 0; i < n; ++i)
    53.         for (j = 0; j < n; ++j)
    54.             fscanf(f, "%d", &weight[i][j]);
    55.     fclose(f);
    56.  
    57.     /* Initialise d with infinity */
    58.     for(i = 0; i < n; ++i)
    59.         d[i] = 100000;
    60.  
    61.     /* Mark all nodes as NOT beeing in the minimum spanning tree */
    62.     for (i = 0; i < n; ++i)
    63.         inTree[i] = 0;
    64.  
    65.     /* Add the first node to the tree */
    66.     printf("Adding node %c\n", 0 + 'A');
    67.     inTree[0] = 1;
    68.     updateDistances(0);
    69.  
    70.     int total = 0;
    71.     int treeSize;
    72.     for (treeSize = 1; treeSize < n; ++treeSize) {
    73.         /* Find the node with the smallest distance to the tree */
    74.         int min = -1;
    75.         for (i = 0; i < n; ++i)
    76.             if (!inTree[i])
    77.                 if ((min == -1) || (d[min] > d[i]))
    78.                     min = i;
    79.  
    80.         /* And add it */
    81.         printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
    82.         inTree[min] = 1;
    83.         total += d[min];
    84.  
    85.         updateDistances(min);
    86.     }
    87.   printf("Total distance: %d\n", total);
    88.  
    89.     return 0;
    90. }

  4. #4
    Ngày gia nhập
    12 2007
    Bài viết
    224

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #include<dos.h>
    4. #define max 50
    5. typedef struct Canh{
    6.   int d,c,ts;
    7. };
    8. void nhap(Canh A[max],int *m,int *n){
    9.   int mx=0;
    10.   printf("\n Nhap so canh: ");
    11.   scanf("%d",m);
    12.   for(int i=1;i<=*m;i++){
    13.     printf("\n Nhap canh(%d)(dau,cuoi,t_so):",i);
    14.     scanf("%d%d%d",&A[i].d,&A[i].c,&A[i].ts);
    15.     if(A[i].d>mx) mx=A[i].d;
    16.     if(A[i].c>mx) mx=A[i].c;
    17.   }
    18.   *n=mx;
    19. }
    20. void sx(Canh A[max],int m){
    21. Canh tg;
    22.   for(int i=1;i<m;i++)
    23.     for(int j=i+1;j<=m;j++)
    24.       if(A[j].ts<A[i].ts){
    25.     tg=A[i];
    26.     A[i]=A[j];
    27.     A[j]=tg;
    28.       }
    29. }
    30. void hienc(Canh A[max],int m){
    31.   for(int i=1;i<=m;i++)
    32.     printf("\n(%d)(%d,%d,%d)",i,A[i].d,A[i].c,A[i].ts);
    33. }
    34. int KT(Canh A,int D[max],int n){
    35.   int a=0,b=0;
    36.   for(int i=1;i<=n;i++){
    37.     if(D[A.d]==1){a=1;}
    38.     if(D[A.c]==1){b=1;}
    39.   }
    40.   return (a+b);
    41. }
    42. void Prim(Canh A[max],int m,int n){
    43.   int D[max],cx[max],d=1,TS,kt;
    44.   for(int i=1;i<=n;i++){
    45.     if(i==A[1].d||i==A[1].c)
    46.       D[i]=1;
    47.     else
    48.       D[i]=0;
    49.   }
    50.   for(i=2;i<=m;i++)
    51.     cx[i]=0;
    52.     cx[1]=1;
    53.     printf("\n Chon duoc.");
    54.     printf("(%d)(%d%d%d)",d,A[1].d,A[1].c,A[1].ts);
    55.     TS=A[1].ts;
    56.     nh:
    57.   do{
    58.     for(i=2;i<=m;i++){
    59.       kt=KT(A[i],D,n);
    60.       if(cx[i]==0&&kt==1){
    61.     d++;
    62.     printf("\n Chon duoc.");
    63.     printf("(%d)(%d%d%d)",i,A[i].d,A[i].c,A[i].ts);
    64.     TS+=A[i].ts;
    65.     cx[i]=1;
    66.     for(int j=1;j<=n;j++){
    67.         D[A[i].d]=1;
    68.         D[A[i].c]=1;
    69.       }
    70.     delay(500);
    71.     goto nh;
    72.       }
    73.     }
    74.   }while(d!=n-1);
    75.   printf("\n Tong trong so : %d",TS);
    76. }
    77. void main(){
    78.   Canh A[max];
    79.   int m,n;
    80.   char lc;
    81.   clrscr();
    82.   nhap(A,&m,&n);
    83.   printf("\n so canh: %d , so dinh : %d",m,n);
    84.   sx(A,m);
    85.   hienc(A,m);
    86.   do{
    87.     printf("\n Tim cay khung nho nhat:");
    88.     printf("\n 1.Prim...");
    89.     printf("\n 2. Thoat..");
    90.     lc=getch();
    91.     switch(lc){
    92.       case '1':
    93.     printf("\n Tim theo Prim.\n ");
    94.     Prim(A,m,n);
    95.     getch();
    96.     break;
    97.       }
    98.   }while(lc!='2');
    99. }

    Code Prim = C đó , bạn hiểu thì chia sẻ cho mình với nhá ^^

Các đề tài tương tự

  1. Lập trình C Tìm cây khung nhỏ nhất bằng giải thuật Prim trên C
    Gửi bởi ba_duong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 02-12-2012, 09:05 PM
  2. Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
    Gửi bởi lephithang trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 25-03-2011, 06:57 AM
  3. Lập trình C Tìm đường đi ngắn nhất trong giải thuật Prim viết bằng C
    Gửi bởi ba_duong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 26-02-2011, 11:16 AM
  4. Lập trình C++ Tìm đường đi ngắn nhất viết bằng giải thuật prim trong lập trình C++?
    Gửi bởi minhtoan991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 25-02-2011, 05:49 PM
  5. Bài tập C Tìm cây khung nhỏ nhất trên C bằng giải thuật Prim
    Gửi bởi lephithang trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 18-02-2011, 08:25 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn