Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Bài toán người du lịch sử dụng kỹ thuật nhánh cận trong lập trình C++

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

    Mặc định Bài toán người du lịch sử dụng kỹ thuật nhánh cận trong lập trình C++

    Mình đang đọc cuốn DSAP Textbook của tác giả Lê Minh Hoàng ! Trong chương I bài 4 "Kĩ thuật nhánh cận" có 1 bài "Bài toán người đi du lịch", vì mình bắt đầu từ C++ nên hoàn toàn mù tịt về pascal ! Mình đã cố chuyển về C++ nhưng nó ra kết quả không như ý muốn. Mong các bạn giúp đỡ! Code pascal thì đã có trong sách nên mình chỉ post code do mình chuyển về C++.

    C++ Code:
    1. /* Xet so do gòm n nút giao thông danh sô tù 1 -> n và m doan duong nói chúng, môi doan duong nói 2 nút
    2.    giao thông s và d. Hãy nhap du lieu vè mang luoi giao thông dó, nhap só hieu 2 nút giao thông s và d.
    3.    Hay in ra tat ca các cách di tù s tói d và môi cách di không dc qua nút giao thông nào quá 1 làn.*/
    4. #include <iostream>
    5. #include <conio.h>
    6. #include <iomanip>
    7. #include <stdio.h>
    8.  
    9. using namespace std;
    10.  
    11. const int size = 100;
    12. int maxE = 100;
    13. int maxC = size * maxE;
    14.  
    15. int C[size][size];
    16. int X[size+1];
    17. int T[size];
    18.  
    19. int BestWay[size+1];
    20.  
    21. bool FREE[size];
    22.  
    23. int minSpending;
    24. int M,N;
    25.  
    26.  
    27. void Enter ()
    28. {  
    29.         int i,j,k;
    30.         cout << " CITY: " ;         cin >> N;
    31.         cout << " TRAFFIC ROAD: ";  cin >> M;
    32.        
    33.         for ( i = 0; i < N; i++ )
    34.         {
    35.                 for ( j = 0; j < N; j++ )
    36.                 {
    37.                         if ( i == j ) C[i][j] = 0;
    38.                         else          C[i][j] = maxC;
    39.        
    40.                 }
    41.         }
    42.         for ( int k = 0; k < M; k++ )
    43.         {
    44.                 cout << "Enter i: "; cin >> i;
    45.                 cout << "Enter j: "; cin >> j;
    46.                 cout << "Cost : ";   cin >> C[i][j];
    47.                 C[j][i] = C[i][j];    
    48.         }
    49. }
    50. void InI()
    51. {
    52.         for ( int i = 0; i <= N; i++ )
    53.         {
    54.                 FREE[i] = true;
    55.         }
    56.  
    57.         FREE[1] = false;
    58.         X[0] = 1;
    59.         T[0] = 0;
    60.        
    61.         minSpending = maxC;
    62. }
    63.  
    64. void PRINT()
    65. {
    66.            if ( minSpending == maxC )
    67.            {
    68.                     cout << "NO SOLUTION ";
    69.            }
    70.            else
    71.            {
    72.                     for ( int i = 0; i < N; i++ )
    73.                     {
    74.                            cout << BestWay[i] << "->";
    75.                     }
    76.                     cout << " Minimum Spending is : " << minSpending;
    77.            }
    78. }
    79.  
    80. void BACKTRACK ( int i )
    81. {
    82.         for ( int j = 2; j <= N; j++ )
    83.         {
    84.                 if ( FREE[j] == true )
    85.                 {
    86.                         X[i] = j;
    87.                         T[i] = T[i-1] + C[X[i-1]][j];
    88.                         if ( T[i] < minSpending )
    89.                         {
    90.                                   if ( i < N )
    91.                                   {
    92.                                            FREE[j] = false;
    93.                                            BACKTRACK ( i + 1 );
    94.                                            FREE[j] = true;
    95.                                   }
    96.                         }
    97.                         else
    98.                         {
    99.                                   if ( ( T[N] + C[X[N]][0] ) < minSpending )
    100.                                   {
    101.                                            for ( int var = 0; var <= N; var++ )
    102.                                            {
    103.                                                     BestWay[var] = X[var];
    104.                                            }
    105.                                            minSpending = T[N] + C[X[N]][0];
    106.                                   }
    107.                         }
    108.                }
    109.        }
    110. }
    111.  
    112. int main()
    113. {
    114.           Enter();
    115.           InI();
    116.           BACKTRACK (1);
    117.           PRINT();
    118.           getch();
    119. }
    Đoạn khó hiểu nhất trong bài viết bằng pascal là chỗ:
    Khai báo :
    var:
    X, BestWay: array[1..max+1] of Integer;
    nhưng trong thân hàm lại có câu lệnh thế này :
    BestWay := X;
    sao lại gán mãng cho mãng nhỉ ?
    Đã được chỉnh sửa lần cuối bởi rox_rook : 18-06-2007 lúc 07:46 AM.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Đây có phải đoạn mã để cập nhật lựa chọn tốt nhất khi dùng backtracking phải không.
    Trong Pascal nó hỗ trợ như vậy, không những mảng mà bất kì hai biến có chung kiểu dữ liệu đều có thể gán cho nhau. Sau khi gán thì biến này sẽ mang nội dung y hệt của biến kia.
    Như vậy khi chuyển sang C++ bạn có thể thay dòng lệnh trên bằng lệnh sau
    for (i=1; i<=n; bestway[i]= x[i], i++); {n là số phần tử của mảng, cái này sẽ biết khi nhập dữ liệu ban đầu}

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

    Uhm mình hiểu rồi ! Để mình thử lại ! Cám ơn Hailoc nhiều ! Thực sự thì mình cũng đoán là như vậy nhưng không dám chắc lắm ! Mà pascal thấy nó cũng rát hay sao lại bị out of date nhỉ ?

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Theo mình biết, thì bước phát triển tiếp theo của Pascal là Delphi dùng để lập trình cho Win, cái này cũng mạnh lắm nhưng sau do công ty làm nó bị phá sản hay mua lại gì đó nên nó không được phát triển tiếp. Với lại trong một số trường hợp cụ thể mã lệnh C ngắn hơn và chạy nhanh hơn Pascal, tuy nhiên đổi lại mã lệnh Pascal ít sai hơn.

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

    Mà cho mình hỏi là Hailoc có học pascal mà phải không! nếu hailoc có thời gian thì có thể test dùm mình đoạn code trong cuốn sách đó được không? Cám ơn hailoc rất nhiều. Vì mình đã chuyển sang C++ ( ko biết mình có làm sai không ) debug mãi mà nó cứ ra kết quả sai !
    Theo mình biết, thì bước phát triển tiếp theo của Pascal là Delphi dùng để lập trình cho Win, cái này cũng mạnh lắm nhưng sau do công ty làm nó bị phá sản hay mua lại gì đó nên nó không được phát triển tiếp. Với lại trong một số trường hợp cụ thể mã lệnh C ngắn hơn và chạy nhanh hơn Pascal, tuy nhiên đổi lại mã lệnh Pascal ít sai hơn.
    .À mình hiểu rồi, vì mình cũng đọc code pascal thấy nó rất thuần túy, chẳng khác C++ là mấy + thêm lịch sử lâu đời nên cũng chẳng biết vì sao nó lại không còn phổ biến ngày nay ! Again, cám ơn hailoc !

  6. #6
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Bài toán người du lịch sử dụng kỹ thuật nhánh cận trong lập trình C++

    Code trong cuốn sách đó thì không cần kiểm tra đâu, nó chuẩn lắm. Minh đã kiểm tra lại đoạn code trên của bạn thì thấy có một số chỗ nhầm lẫn trong việc truy nhập mảng. Vì mảng trong C bắt đầu từ 0, nên phần tử thứ N của nó là mang[N-1] nhưng bạn dùng mang[N]. Tốt nhất là cứ khai báo dư ra một phần tử rồi dùng như nó bắt đầu từ 1.
    Trong lúc kiểm tra trong backtracking bạn dùng hai if *****g nhau. Như vậy để dùng else cho if thứ nhất thì bắt buộc phải có thêm else cho if thứ hai vì else thuộc về if gần nhất.
    Ngoài ra thủ tục backtracking còn có thể thiết kế theo dạng sau ( mình thường dùng dạng này hơn, tuy rằng cả hai dạng đều như nhau )
    C++ Code:
    1.  try( int i) //coi như mảng bắt đầu từ 1
    2. {
    3.   //if (giatri> Min) return 0; Đây là dạng nhánh cận, nếu trường hợp hiện tại    //không tốt hơn trường hợp tốt nhất đã có thì thoát
    4.   if (i>N)  kt(); //đây là hàm kiểm tra và cập nhật kết quả nhận được
    5.   else
    6.     {
    7.        for (int j=..; j<...; j++)
    8.          if (check(j))  // ham để kiểm tra có chọn được không, nếu điều kiện phức tạp tốt nhất làm hàm riêng, còn đơn giản thì có thể thay luôn vào if
    9.           {
    10.              {cap nhat trang thai}
    11.              try(i+1);
    12.              {Khoi phuc trang thai}
    13.           }
    14.     }
    15. }

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

    Pascal Code:
    1. procedure Attempt ( i : Interger )
    2. var
    3.         j : Integer;
    4. begin
    5.         for j := 2 to n do
    6.                 if Free[j] then
    7.                 begin
    8.                         X[i] := j;
    9.                         T[i] := T[i-1] + C[x[i-1],j];
    10.                         if T[i] < MinSpending then /*Dòng này that là la quá.
    11.                                 if i < n then
    12.                                     begin
    13.                                             Free[j] := False;
    14.                                             Attempt ( i + 1 );
    15.                                             Free[j] := True;
    16.                                     end
    17.                                 else
    18.                                     if T[n] + C[x[n],1] < MinSpending then
    19.                                           Begin
    20.                                                   BestWay := X;
    21.                                                   MinSpending := T[n] + C[x[n],1];
    22.                                           end
    23.                 end                  
    24. end
    Về phần mãng và BestWay := X thì mình nghĩ đã ok rồi nhưng.
    có lẽ mình vẫn chưa hiểu hết ý của Hailoc !
    Trong lúc kiểm tra trong backtracking bạn dùng hai if *****g nhau. Như vậy để dùng else cho if thứ nhất thì bắt buộc phải có thêm else cho if thứ hai vì else thuộc về if gần nhất.
    .
    Chỗ cái dòng if T[i] < MinSpending then ( mình thấy nó đứng riệng lẻ ) Mà theo mình nghĩ thì trong C++ { } tương đương với Begin-End của Pascal ! theo mình nghĩ thì nó là 3 cái if *****g vào nhau không biết có đúng không ! Mình dùng 2 cái if ngang nhau chỗ nào nhỉ ! Hailoc có thể nói rõ hơn 1 tí được không ! cám ơn hailoc trước !

  8. #8
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mình đã sửa lại code hoàn chỉnh cho bạn, tốt nhất bạn so sánh sẽ tìm thấy chỗ bị nhầm

    C++ Code:
    1. /* Xet so do gòm n nút giao thông danh sô tù 1 -> n và m doan duong nói chúng, môi doan duong nói 2 nút
    2.    giao thông s và d. Hãy nhap du lieu vè mang luoi giao thông dó, nhap só hieu 2 nút giao thông s và d.
    3.    Hay in ra tat ca các cách di tù s tói d và môi cách di không dc qua nút giao thông nào quá 1 làn.*/
    4. #include <iostream.h>
    5. #include <conio.h>
    6. //#include <iomanip>
    7. #include <stdio.h>
    8.  
    9. //using namespace std;
    10.  
    11. const int size = 100;
    12. int maxE = 100;
    13. int maxC = size * maxE;
    14.  
    15. int C[size][size];
    16. int X[size+1];
    17. int T[size];
    18.  
    19. int BestWay[size+1];
    20.  
    21. int FREE[size];
    22.  
    23. int minSpending;
    24. int M,N;
    25.  
    26.  
    27. void Enter ()
    28. {  
    29.         int i,j,k;
    30.         cout << " CITY: " ;         cin >> N;
    31.         cout << " TRAFFIC ROAD: ";  cin >> M;
    32.        
    33.     for ( i = 1; i <= N; i++ )
    34.     {
    35.         for ( j = 1; j <= N; j++ )
    36.         {
    37.             if ( i == j ) C[i][j] = 0;
    38.             else          C[i][j] = maxC;
    39.  
    40.         }
    41.     }
    42.     for ( k = 1; k <= M; k++ )
    43.     {
    44.         cout << "Enter i: "; cin >> i;
    45.         cout << "Enter j: "; cin >> j;
    46.         cout << "Cost : ";   cin >> C[i][j];
    47.         C[j][i] = C[i][j];
    48.     }
    49. }
    50. void InI()
    51. {
    52.     for ( int i = 1; i <= N; i++ )
    53.     {
    54.         FREE[i] = 1;
    55.     }
    56.  
    57.     FREE[1] = 0;
    58.     X[1] = 1;
    59.     T[1] = 0;
    60.  
    61.     minSpending = maxC;
    62. }
    63.  
    64. void PRINT()
    65. {
    66.        if ( minSpending == maxC )
    67.        {
    68.             cout << "NO SOLUTION ";
    69.        }
    70.        else
    71.        {
    72.             for ( int i = 1; i <= N; i++ )
    73.             {
    74.                cout << BestWay[i] << "->";
    75.             }
    76.             cout << " Minimum Spending is : " << minSpending;
    77.        }
    78. }
    79.  
    80. void BACKTRACK ( int i )
    81. {
    82.     for ( int j = 2; j <= N; j++ )
    83.     {
    84.         if ( FREE[j] )
    85.         {
    86.             X[i] = j;
    87.             T[i] = T[i-1] + C[X[i-1]][j];
    88.             if (( T[i] + C[i][1]) < minSpending )
    89.             {
    90.                   if ( i < N )
    91.                   {
    92.                        FREE[j] = 0;
    93.                        BACKTRACK ( i + 1 );
    94.                        FREE[j] = 1;
    95.                   }
    96.                   else
    97.                  {
    98.                       for ( int var = 1; var <= N; var++ )
    99.                       {
    100.                            BestWay[var] = X[var];
    101.                       }
    102.                       minSpending = T[N] + C[X[N]][1];               }
    103.             }
    104.             else goto finish;
    105.            }
    106.        }
    107.   finish:
    108. }
    109.  
    110. int main()
    111. {
    112.           Enter();
    113.           InI();
    114.       BACKTRACK (2);
    115.           PRINT();
    116.       getch();
    117.       return 0;
    118. }

  9. #9
    Ngày gia nhập
    12 2008
    Nơi ở
    Hà Nội
    Bài viết
    374

    Hì hì, hơn 5 năm rồi, em bây giờ cũng đang ngâm cứu quyển Cấu trúc dữ liệu và giải thuật của thầy Lê Minh Hoàng, và cũng đang ở bài Kỹ thuật nhánh cận. Em xin đóng góp chút công sức của mình :

    KyThuatNhanhCan.h

    C++ Code:
    1. #pragma once
    2.  
    3. #include <fstream>
    4.  
    5. class CKyThuatNhanhCan
    6. {
    7. private:
    8.     CKyThuatNhanhCan(void);
    9.     ~CKyThuatNhanhCan(void);
    10.    
    11.  
    12. public:
    13.     static void KhoiTaoChoBaiToanNguoiDuLich(std::ifstream &ifs, bool*& ThanhPho, int**& ChiPhi, int*& DuongDi, int*& DuongDiTotNhat, int& SoThanhPho, int& SoDuongDi);
    14.     static void BaiToanNguoiDuLich(std::ofstream &ofs, bool* ThanhPho, int** ChiPhi, int* DuongDi, int* DuongDiTotNhat, int SoThanhPho, int ChiPhiHienTai, int &ChiPhiTotNhat, int index);
    15. };

    KyThuatNhanhCan.cpp

    C++ Code:
    1. #include "KyThuatNhanhCan.h"
    2. #include <iostream>
    3.  
    4. CKyThuatNhanhCan::CKyThuatNhanhCan(void)
    5. {
    6. }
    7.  
    8.  
    9. CKyThuatNhanhCan::~CKyThuatNhanhCan(void)
    10. {
    11. }
    12.  
    13. /*
    14.  * Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều
    15.  * giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây
    16.  * C[i, j] = C[j, i] = Chi phí đi đoạn đường trực tiếp từ thành phố i đến
    17.  * thành phố j. Giả thiết rằng C[i, i] = 0 với ∀i, C[i, j] = +∞ nếu không
    18.  * có đường trực tiếp từ thành phố i đến thành phố j.Một người du lịch xuất
    19.  * phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành
    20.  * phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra cho người
    21.  * đó hành trình với chi phí ít nhất. Bài toán đó gọi là bài toán người du
    22.  * lịch hay bài toán hành trình của một thương gia (Traveling Salesman).
    23.  *
    24.  
    25.  Khởi tạo mảng miêu tả chi phí đoạn đường;
    26.  Khởi tạo Chi phí tốt nhất ban đầu;
    27.  
    28.  BaiToanNguoiDuLich(Chi phí tốt nhất , Chi phí hiện tại , Chỉ số thành phố hiện tại )
    29.  {
    30.     for ( i = 0 -> Số thành phố - 1 )
    31.         if ( Chưa đi qua thành phố này && Có đường đi tới )
    32.         {
    33.             if ( i == Chỉ số thành phố khởi hành && Chỉ số thành phố hiện tại < Số thành phố )
    34.                 continue;
    35.  
    36.             Đi qua;
    37.             Tính chi phí hiện tại;
    38.  
    39.             if ( Chi phí hiện tại < Chi phí tốt nhất )
    40.             {
    41.                 if ( Chỉ số thành phố hiện tại == Số thành phố )
    42.                     Thay đổi chi phí tốt nhất;
    43.                 else
    44.                 {
    45.                     Đánh dấu đã đi qua thành phố này;
    46.                     BaiToanNguoiDuLich(Chi phí tốt nhất , Chi phí hiện tại , Chỉ số thành phố tiếp theo);
    47.                     Bỏ đánh dấy đã đi qua thành phố này;
    48.                 }
    49.             }
    50.         }
    51.  }
    52.  
    53.  Ví dụ input:
    54.  4 6
    55.  0 1 3
    56.  0 2 2
    57.  0 3 1
    58.  1 2 1
    59.  1 3 2
    60.  2 3 4
    61.  
    62.  4 là số lượng thành phố.
    63.  6 là số tuyến đường.
    64.  chi phí từ tp 1 tới 2 mất 3
    65.  chi phí từ tp 1 tới 3 mất 2
    66.  ...
    67.  
    68.  Mảng miêu tả chi phí đoạn đường :
    69.  
    70.  0 3 2 1
    71.  3 0 1 2
    72.  2 1 0 4
    73.  1 2 4 0
    74.  
    75.  Sử dụng :
    76.  
    77.  int SoThanhPho = 0;
    78.  int SoDuongDi = 0;
    79.  bool* ThanhPho = 0;
    80.  int** ChiPhi = 0;
    81.  int* DuongDi = 0;
    82.  int ChiPhiTotNhat = 1000;
    83.  int* DuongDiTotNhat = 0;
    84.  
    85.  CKyThuatNhanhCan::KhoiTaoChoBaiToanNguoiDiDuong(ifs, ThanhPho, ChiPhi, DuongDi, DuongDiTotNhat, SoThanhPho, SoDuongDi);
    86.  CKyThuatNhanhCan::BaiToanNguoiDuLich(ofs, ThanhPho, ChiPhi, DuongDi, DuongDiTotNhat, SoThanhPho, 0, ChiPhiTotNhat, 1);
    87.  
    88.  cout<<endl<<"Duong di voi muc chi phi thap nhat : "<<endl;
    89.  for (int i = 0 ; i <= SoThanhPho ; i++)
    90.     cout<<DuongDiTotNhat[i]<<" ";
    91.  cout<<endl<<ChiPhiTotNhat;
    92.  
    93.  
    94.  delete[] ThanhPho;
    95.  for (int i = 0 ; i < SoThanhPho ; i++)
    96.     delete[] ChiPhi[i];
    97.  delete[] ChiPhi;
    98.  delete[] DuongDi;
    99.  delete[] DuongDiTotNhat;
    100.  
    101.  
    102. */
    103. void CKyThuatNhanhCan::BaiToanNguoiDuLich(std::ofstream &ofs, bool* ThanhPho, int** ChiPhi, int* DuongDi, int* DuongDiTotNhat, int SoThanhPho, int ChiPhiHienTai, int &ChiPhiTotNhat, int index)
    104. {
    105.     using namespace std;
    106.     for (int i = 0 ; i < SoThanhPho ; i++ /*i = 0 -> Số thành phố - 1*/ )
    107.         if ( ThanhPho[i] && ChiPhi[DuongDi[index-1]][i] > 0 /*Chưa đi qua thành phố này && Có đường đi tới*/ )
    108.         {
    109.             if ( i == DuongDi[0] && index < SoThanhPho /*i == Chỉ số thành phố khởi hành && Chỉ số thành phố hiện tại < Số thành phố*/ )
    110.                 continue;
    111.  
    112.             cout<<endl<<"index : "<<index;
    113.             cout<<endl<<"Chi phi hien tai truoc : "<<ChiPhiHienTai;
    114.  
    115.             DuongDi[index] = i; /*Đi qua;*/
    116.             // ChiPhiHienTai + ChiPhi[DuongDi[index-1]][i] /*Tính chi phí hiện tại;*/
    117.  
    118.             cout<<endl;
    119.             for (int j = 0 ; j <= index ; j++)
    120.                 cout<<DuongDi[j]<<" ";
    121.             cout<<endl<<"Tu "<<DuongDi[index-1]<<" den "<<i<<" mat "<<ChiPhi[DuongDi[index-1]][i];
    122.             cout<<endl<<"Chi phi hien tai sau :  "<<ChiPhiHienTai + ChiPhi[DuongDi[index-1]][i];
    123.             cout<<endl;
    124.  
    125.             if ( ChiPhiHienTai + ChiPhi[DuongDi[index-1]][i] < ChiPhiTotNhat /*Chi phí hiện tại < Chi phí tốt nhất*/ )
    126.             {
    127.                 if ( index == SoThanhPho /*Chỉ số thành phố hiện tại == Số thành phố*/ )
    128.                 {
    129.                     ChiPhiTotNhat = ChiPhiHienTai + ChiPhi[DuongDi[index-1]][i];/*Thay đổi chi phí tốt nhất;*/
    130.                     for (int j = 0 ; j <= SoThanhPho ; j++)
    131.                         DuongDiTotNhat[j] = DuongDi[j];
    132.                     cout<<endl<<"----------Thay doi chi phi tot nhat---------------";
    133.                 }
    134.                 else
    135.                 {
    136.                     ThanhPho[i] = false; /*Đánh dấu đã đi qua thành phố này;*/
    137.                     /*BaiToanNguoiDuLich(Chi phí tốt nhất , Chi phí hiện tại , Chỉ số thành phố tiếp theo);*/
    138.                     BaiToanNguoiDuLich(ofs, ThanhPho, ChiPhi, DuongDi, DuongDiTotNhat, SoThanhPho, ChiPhiHienTai + ChiPhi[DuongDi[index-1]][i], ChiPhiTotNhat, index + 1);
    139.                     ThanhPho[i] = true; /*Bỏ đánh dấy đã đi qua thành phố này;*/
    140.  
    141.                 }
    142.             }
    143.         }
    144. }
    145.  
    146. void CKyThuatNhanhCan::KhoiTaoChoBaiToanNguoiDuLich(std::ifstream &ifs, bool*& ThanhPho, int**& ChiPhi, int*& DuongDi, int*& DuongDiTotNhat, int& SoThanhPho, int& SoDuongDi)
    147. {
    148.     ifs>>SoThanhPho>>SoDuongDi;
    149.     std::cout<<SoThanhPho<<"\t"<<SoDuongDi<<std::endl;
    150.  
    151.     ThanhPho = new bool[SoThanhPho];
    152.  
    153.     for(int i = 0 ; i < SoThanhPho ; i++)
    154.         ThanhPho[i] = true;
    155.  
    156.     DuongDi = new int[SoThanhPho + 1];
    157.     DuongDiTotNhat = new int[SoThanhPho + 1];
    158.     DuongDi[0] = 0; /* Chỉ số thành phố muốn khởi hành */
    159.  
    160.     ChiPhi = new int*[SoThanhPho];
    161.  
    162.     for(int i = 0 ; i < SoThanhPho ; i++)
    163.     {
    164.         ChiPhi[i] = new int[SoThanhPho];
    165.         ChiPhi[i][i] = 0;
    166.     }
    167.  
    168.     for (int i = 0 ; i < SoDuongDi ; i++)
    169.     {
    170.         ifs.ignore();
    171.         int TuTP;
    172.         int DenTP;
    173.         int MucChiPhi;
    174.         ifs>>TuTP>>DenTP>>MucChiPhi;
    175.         std::cout<<TuTP<<"\t"<<DenTP<<"\t"<<MucChiPhi<<std::endl;
    176.         ChiPhi[TuTP][DenTP] = MucChiPhi;
    177.         ChiPhi[DenTP][TuTP] = MucChiPhi;
    178.     }
    179.  
    180.     std::cout<<std::endl;
    181.  
    182.     for (int i = 0 ; i < SoThanhPho ; i++)
    183.     {
    184.         for (int j = 0 ; j < SoThanhPho ; j ++)
    185.         {
    186.             std::cout<<ChiPhi[i][j]<<" ";
    187.         }
    188.         std::cout<<std::endl;
    189.     }
    190. }

    main.cpp

    C++ Code:
    1. #include <iostream>
    2. #include <fstream>
    3. #include "PhuongPhapQuayLui.h"
    4. #include "PhuongPhapSinh.h"
    5. #include "KyThuatNhanhCan.h"
    6.  
    7. int main()
    8. {
    9.     using namespace std;
    10.  
    11.     ifstream ifs("in.txt");
    12.     if(!ifs.is_open())
    13.         return -1;
    14.  
    15.     ofstream ofs("out.txt",ios::out | ios::trunc);
    16.     if (!ofs.is_open())
    17.         return -1;
    18.  
    19.  
    20.     int SoThanhPho = 0;
    21.     int SoDuongDi = 0;
    22.     bool* ThanhPho = 0;
    23.     int** ChiPhi = 0;
    24.     int* DuongDi = 0;
    25.     int ChiPhiTotNhat = 1000;
    26.     int* DuongDiTotNhat = 0;
    27.    
    28.     CKyThuatNhanhCan::KhoiTaoChoBaiToanNguoiDuLich(ifs, ThanhPho, ChiPhi, DuongDi, DuongDiTotNhat, SoThanhPho, SoDuongDi);
    29.     CKyThuatNhanhCan::BaiToanNguoiDuLich(ofs, ThanhPho, ChiPhi, DuongDi, DuongDiTotNhat, SoThanhPho, 0, ChiPhiTotNhat, 1);
    30.  
    31.     cout<<endl<<"Duong di voi muc chi phi thap nhat : "<<endl;
    32.     for (int i = 0 ; i <= SoThanhPho ; i++)
    33.         cout<<DuongDiTotNhat[i]<<" ";
    34.     cout<<endl<<ChiPhiTotNhat;
    35.  
    36.  
    37.     delete[] ThanhPho;
    38.     for (int i = 0 ; i < SoThanhPho ; i++)
    39.         delete[] ChiPhi[i];
    40.     delete[] ChiPhi;
    41.     delete[] DuongDi;
    42.     delete[] DuongDiTotNhat;
    43.    
    44.  
    45.     ifs.close();
    46.     ofs.close();
    47.  
    48.     cin.get();
    49.     return 0;
    50. }

    Console

    4 6
    0 1 3
    0 2 2
    0 3 1
    1 2 1
    1 3 2
    2 3 4

    0 3 2 1
    3 0 1 2
    2 1 0 4
    1 2 4 0

    index : 1
    Chi phi hien tai truoc : 0
    0 1
    Tu 0 den 1 mat 3
    Chi phi hien tai sau : 3

    index : 2
    Chi phi hien tai truoc : 3
    0 1 2
    Tu 1 den 2 mat 1
    Chi phi hien tai sau : 4

    index : 3
    Chi phi hien tai truoc : 4
    0 1 2 3
    Tu 2 den 3 mat 4
    Chi phi hien tai sau : 8

    index : 4
    Chi phi hien tai truoc : 8
    0 1 2 3 0
    Tu 3 den 0 mat 1
    Chi phi hien tai sau : 9

    ----------Thay doi chi phi tot nhat---------------
    index : 2
    Chi phi hien tai truoc : 3
    0 1 3
    Tu 1 den 3 mat 2
    Chi phi hien tai sau : 5

    index : 3
    Chi phi hien tai truoc : 5
    0 1 3 2
    Tu 3 den 2 mat 4
    Chi phi hien tai sau : 9

    index : 1
    Chi phi hien tai truoc : 0
    0 2
    Tu 0 den 2 mat 2
    Chi phi hien tai sau : 2

    index : 2
    Chi phi hien tai truoc : 2
    0 2 1
    Tu 2 den 1 mat 1
    Chi phi hien tai sau : 3

    index : 3
    Chi phi hien tai truoc : 3
    0 2 1 3
    Tu 1 den 3 mat 2
    Chi phi hien tai sau : 5

    index : 4
    Chi phi hien tai truoc : 5
    0 2 1 3 0
    Tu 3 den 0 mat 1
    Chi phi hien tai sau : 6

    ----------Thay doi chi phi tot nhat---------------
    index : 2
    Chi phi hien tai truoc : 2
    0 2 3
    Tu 2 den 3 mat 4
    Chi phi hien tai sau : 6

    index : 1
    Chi phi hien tai truoc : 0
    0 3
    Tu 0 den 3 mat 1
    Chi phi hien tai sau : 1

    index : 2
    Chi phi hien tai truoc : 1
    0 3 1
    Tu 3 den 1 mat 2
    Chi phi hien tai sau : 3

    index : 3
    Chi phi hien tai truoc : 3
    0 3 1 2
    Tu 1 den 2 mat 1
    Chi phi hien tai sau : 4

    index : 4
    Chi phi hien tai truoc : 4
    0 3 1 2 0
    Tu 2 den 0 mat 2
    Chi phi hien tai sau : 6

    index : 2
    Chi phi hien tai truoc : 1
    0 3 2
    Tu 3 den 2 mat 4
    Chi phi hien tai sau : 5

    index : 3
    Chi phi hien tai truoc : 5
    0 3 2 1
    Tu 2 den 1 mat 1
    Chi phi hien tai sau : 6

    Duong di voi muc chi phi thap nhat :
    0 2 1 3 0
    6
    Đã được chỉnh sửa lần cuối bởi luc13aka47 : 22-09-2012 lúc 05:06 PM.

  10. #10
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    ^
    Đâu cần dùng class làm gì ạ? Nếu muốn gom nhóm các hàm lại, ta dùng namespace cũng được mà. Còn nếu viết thành class, thì nên viết hàm khởi tạo xử lý raw-data, sau đó mới gọi hàm để process.
    P/s: Anh chỉ mới học giải thuật, chứ chưa học cấu trúc dữ liệu rồi.

    C++ Code:
    1. namespace KyThuatNhanhCan
    2. {
    3.     void KhoiTaoChoBaiToanNguoiDuLich(std::ifstream &ifs, bool*& ThanhPho, int**& ChiPhi, int*& DuongDi, int*& DuongDiTotNhat, int& SoThanhPho, int& SoDuongDi);
    4.     void BaiToanNguoiDuLich(std::ofstream &ofs, bool* ThanhPho, int** ChiPhi, int* DuongDi, int* DuongDiTotNhat, int SoThanhPho, int ChiPhiHienTai, int &ChiPhiTotNhat, int index);
    5. };
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

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

  1. Các thuật toán sắp xếp trong lập trình C | Cấu trúc dữ liệu và giải thuật
    Gửi bởi iamvtn trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 11-02-2017, 04:44 PM
  2. Lập trình C++ Thắc mắc về thuật toán trong giao thức thoả thuận khoá Station to station?
    Gửi bởi luongthienaz trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 05-12-2012, 09:56 AM
  3. Kỹ thuật in - Vai trò của kỹ thuật in trong thiết kế, in ấn
    Gửi bởi thongthanhhungland trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 18-11-2011, 01:04 PM
  4. Thuật toán trong C | Cẩm nang thuật toán | "Algorithims In C" của Robert Sedgewick
    Gửi bởi clementboy03 trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 3
    Bài viết cuối: 20-05-2009, 07:50 PM
  5. Trả lời: 6
    Bài viết cuối: 04-05-2008, 08:04 AM

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