Windows Việt

Cộng Đồng Công Nghệ Thông Tin Việt

Trang ChínhTrang Chính  Trợ giúpTrợ giúp  Thành viênThành viên  NhómNhóm  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share | 
 
 Bài giải bài tập thực hành UCS
Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

Trước tiên, bài này mỗi người giải 1 cách. Nên tui hướng dẫn theo cách tui nghĩ. Tình hình là nếu ai test thấy sai thì góp ý chứ đừng chửi hay nói lời thô tục nhé, vì cái này mình viết trực tiếp trong khi post chứ không viết trên Visual Studio nên chắc sai lỗi cú pháp nhìu....silent


Để giải bài này, mình sẽ đi từng bước:
Trước hết, khái báo các thư viện cần dùng:
Code:

#include <stdio.h>
#include <conio.h>
#include <math.h>
và khai báo các biến toàn cục trong hàm main():
Code:

void main()
{
      graph g;
      char start,end;
      TaoMangDuyet(g);
      getch();
}

1/ Cài đặt các struct:
a. struct dinh:
Code:

struct dinh
{
    char ten; // ten của 1 đỉnh trong đồ thị
    int x; // tọa độ x của đỉnh đó
    int y; // tọa độ y của đỉnh đó
    double.cost; // chi phí đường đi để đến đỉnh đó
};

b. struct ctql : // viết tắt của con trỏ quay lui
Code:

struct ctql
{
      char dinh1; // tên của 1 đỉnh trong đồ thị
      char dinh0; // tên của đỉnh kề và có chi phí đường đi nhỏ nhất đến dinh1 
}

c. struct graph
Code:

struct graph
{
      int n; // số đỉnh trong đồ thị
      char a[[max][max]; // ma trận chứa tên các đỉnh cùng các đỉnh kề của nó  trong đồ thị
      dinh b[max]; // mảng chứa các đỉnh trong đồ thị
      dinh duyet[max]; // mảng chứa các đỉnh đã duyệt qua trong thuật toán ucs
      ctql quaylui[max]; // mảng chứa các đỉnh cùng các đỉnh kề gần nhất của mỗi đỉnh
};
max đc định nghĩa bởi người viết (100 ở dưới chỉ là ví dụ)
Code:

  #define max 100;
đặt ở sau cac dòng khai báo thư viện
d. struct queue
Code:

struct queue
{
         dinh *QArray; // mảng chứa các đỉnh nằm trong hàng đợi
   int QMax; // số phần tử lớn nhất của hàng đợi
   int QNumItems; // số phần tử hiện có trong hàng đợi
   int QFirst; // vi trí phần tử đấu tiên trong mảng QArray
   int QLast; // vị trí phần tử sau cùng trong mảng QArray
};

2. Cài đặt các hàm thao tác
a. Các ham thao tác với mảng duyet trong struct graph
Code:

// khoi tao mang
void TaoMangDuyet(graph &g)
{
   for(int i=0; i<max; i++)
      g.duyet[i].ten = '0';  // gán mặc định cho tên các dỉnh trong mảng là ký tự ' 0 '
}

// kiem tra co trung phần tử trong mảng hay khong
bool  KiemTraTrung(graph g, char kt)
{
   for(int i=0; i <max; i++)
   {
      if(a == g.duyet[i].ten)
         return true;
      if((int)g.duyet[i].ten == 0)
         break;
   }
   return false;
}
// them phan tu vao mang
bool ThemDuyet(graph &g, dinh newitem)
{
   for(int i=0; i < 100; i++)
      if(g.duyet[i].ten == '0') // nếu phần tử là phần tử ban đầu chưa đc gán tên đỉnh thì thêm tên dỉnh vào
      {
         g.duyet[i].ten = newitem.ten;
         g.duyet[i].cost = newitem.cost;
         return true;
      }
   return false;
}

b. Các ham thao tác với hàng đợi
Code:

// khoi tao
int InitQueue(queue &q, int MaxItems)
{
   q.QArray = new dinh[MaxItems];
   if(q.QArray == NULL)
      return 0;
   q.QMax = MaxItems;
   q.QNumItems = 0;
   q.QFirst = q.QLast = -1;
   return 1;
}
// kiem tra rong
int IsQueueEmpty(const queue &q)
{
   if(q.QNumItems == 0)
      return 1;
   return 0;
}
// kiem tra day
int IsQueueFull(const queue &q)
{
   if(q.QNumItems == q.QMax)
      return 1;
   return 0;
}
// them phan tu
int EnQueue(queue &q, dinh newitem)
{
   if(IsQueueFull(q))
      return 0;
   q.QLast++;
   if(q.QLast == q.QMax)
      q.QLast = 0;
   q.QArray[q.QLast].ten = newitem.ten;
   q.QArray[q.QLast].cost = newitem.cost;
   if(IsQueueEmpty(q))
      q.QFirst = 0;
   q.QNumItems++;
   return 1;
}
// lay phan tu ra
int DeQueue(queue &q, dinh &outitem)
{
   if(IsQueueEmpty(q))
      return 0;
        // tim phần tử có chi phí đường đi ngắn nhất trong hàng đợi
   int min = q.QFirst;
   int reach = 0;
   for(int i=q.QFirst+1; i<q.QNumItems; i++)
   {
      if(q.QArray[i].cost < q.QArray[min].cost)
         min = i;
      if(i == q.QLast)
      {
         reach = 1;
         break;
      }
   }
   if(reach == 0)
   {
      for(int i=0; i<q.QLast; i++)
      {
         if(q.QArray[i].cost < q.QArray[min].cost)
            min = i;
      }
   }
   outitem.ten = q.QArray[min].ten;
   outitem.chiphi = q.QArray[min].cost;
   // chinh  lại so phan tu cua mang QArray
   q.QArray[min] = q.QArray[q.QLast];
   q.QNumItems--;
   if(IsQueueEmpty(q))
      q.QFirst = q.QLast = -1;
   else
   {
      q.QLast--;
      if(q.QLast < 0)
         q.QLast = q.QMax -1;
   }
   return 1;
}

3./ Cài đặt các hàm chức năng
a. Hàm tính chi phí đường đi từ 1 đỉnh đến 1 đỉnh trong đồ thị
Code:

// các tham số truyền vào gồm g và tên 2 đỉnh cần tính chi phí
double ChiPhi(graph g, char dinh1, char dinh2)
{
   int a,b;
   for(int i=0; i < g.n; i++)
   {
      if(g.b[i].ten == dinh1)
          a = i;
      if(g.b[i].ten == dinh2)
                    b = i;
   }
   return sqrt(pow((double)g.b[a].x-g.b[b].x,2) + pow((double)g.b[a].y-g.b[b].y,2));
}

b. Hàm đọc dữ liệu từ file input.txt


Code:

void Doc(char* file, graph &g, char &start, char &end)
{
   FILE *f = fopen(file, "r");
   if (f == NULL)
              printf("Loi doc file.");
   else
   {
                char temp[max]; //  tạo 1 biến chuỗi tạm
      fscanf(f, "%d", &g.n); // đọc số đỉnh  từ file input vào đồ thị
      fgets(temp,max,f); // doc dòng 1 vào biến temp mục đích để con trỏ chạy xuống dòng 2
      fgets(temp,max,f); // đọc dòng 2 vào biến temp và dĩ nhiên sau dòng này nếu đọc tiếp thì con  trỏ sẽ bắt đầu từ dòng 3
      start = temp[0]; // gán biến start = đỉnh đầu. Lúc này temp[0] = 'M'
      end = temp[2]; // gán biến start = đỉnh cuối. Lúc này temp[2] = 'T'
                for(int i = 0; i < g.n; i++)
                {
                      // đọc tên dỉnh và các tọa độ vào mảng b
                      fscanf(f,"%c",&g.b[i].ten);
                      fscanf(f,"%d",&g.b[i].x);
                      fscanf(f,"%d",&g.b[i].y);
                      fgets(temp,max,f); // đọc dòng tiếp theo vào biến temp, với i = 0 thì biến  temp có giá trị:
                      // temp[0] = A, temp[1] = ' ', temp[2] = '9', temp[3] = ' ', temp[4] = '1'; temp[5] = '9'; temp[6] = ' ', temp[7] = 'B', ...... tương tự với các ký tự con lại trong dòng đó
                      int e = 0; // biến đếm cột của ma trận g.a
                      g.quaylui[i].dinh1 = temp[0]; // thêm các đỉnh  vào mảng quay lui.
                      for(int j = 0; j < max; j++)
                      {
                                int k = (int)temp[j] ; // lấy mã số ascii của ký tự. VD: A = 65
                                if(k >64 && k < 91) // nếu temp[j] là ký tự số trong khoảng (A - Z)
                                {
                                        g.a[i][e] = temp[j];
                                        e++;
                                }
                                if(k == 0) // nếu gặp phải kí tự NULL thì thoát khỏi vòng lặp
                                          break;
                          }
                }
        }
 
   fclose(f);
}


c. Hàm ghi file output.txt
Code:

void Ghi(char* file, graph g, char start char end)
{
   FILE *f = fopen(file, "w"); // mo file
      char a[max]; // tạo 1 mảng tạm chứa tên các đỉnh
      char k = end;
      int dem = 0; // doạn này chạy tay là hỉu dc
      do
      {
          for(int i = 0; i <g.n; i++)
          {
                if(g.quaylui[i].dinh1 == k)
                {
                    a[i] = g.quaylui[i].dinh0;
                    k = g.quaylui[i].dinh0;
                    dem++;
                    break;
                }
            }
        }
        while( k !=  start)
        fprintf(f,"%c ", start);
   for(int j = dem; j>=0; j--)
   {
      fprintf(f,"%c ", a[j]);
   }
        fprintf(f,"%c ", end;
   fclose(f);
}

4. Cài đặt hàm tìm kiếm UCS[size]
-- Những struct mình đã tạo đều giống như những dữ liệu cần có file ly thuyết UCS nên các bạn cứ đọc file lý thuyết rùi dùng các hàm thao tác là có thể viết đc hàm này. Vì bây giờ là 3h30 phút sáng và mắt mở hết lên, tay gõ phím hết nổi rồi nên mình dừng ở đây.....................
Neutral

[size=18]
P/S: Nói câu cuối, hi vọng các bạn hỉu dc cách làm của mình rồi có thể nghĩ dc cách làm hay hơn, đừng code giống nhau vì code giống nhau zero hết đó.......
No


Ôi 1 Thời Để Nhớ....
<br>


Được sửa bởi kitsudo ngày Tue 26 Oct 2010, 11:54; sửa lần 1.

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

Member
Giới tính : Nam
Tuổi : 21
Posts Posts : 18
Coins Coins : 31
Thanked Thanked : 1

thanks nè, đẳng cấp cao rùi, viết trực tiếp lên 4rum lun, bái phục bái phục

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 39
Coins Coins : 63
Thanked Thanked : 5

Thank Phong chủ yếu là hiểu thuật toán, không cần nộp bài cũng được.

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nữ
Tuổi : 27
Posts Posts : 1
Coins Coins : 1
Thanked Thanked : 0

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 315
Coins Coins : 638
Thanked Thanked : 61

hĩ đẳng cấp gà của em, đọc kg hiểu luôn ... !!! Sad => die



Tôi là fan của taekwondo, tôi cuồng nhiệt với karate, hào hứng với vovinam, lăn xả với judo, điên cuồng với ..sumô.. Tôi là a ji nô mô tô ...!
[You must be registered and logged in to see this link.]
You Are Not Alone, Remember That, I Will Be There, With You !!!

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

Tiếp tục... câu 4.
Trước tiên, sau khi thực hiện bước 3, chúng ta sẽ có:
- g.n = 10
- start = M
- end = T
- g.a

- g.b

- g.duyet

- g.quaylui

- q



4. Cài đặt hàm tìm kiếm UCS
Mình sẽ làm từng bước :
- Các tham số truyền vào bao gồm g, start và end
Code:

int TimKiem(graph &g, char start, char end)
{
        .....
        .....
}
- Nếu đỉnh bắt đầu trùng với đỉnh kết thúc thì dừng lại
Code:

   if(start == end)
   {
      return 1;
   }
- Cài đặt hàng đợi q
Code:

   queue q; // khai báo hàng đợi
   InitQueue(q,max); // khởi  tạo q.QMax = max và q.QArray có max phần tử
   dinh temp; // tạo 1 biến tạm
   temp.ten = start; // gán biến tạm = đỉnh bắt đầu
   temp.cost = 0; // chi phí đường đi đến đỉnh bắt đầu là 0
        EnQueue(q,temp); // thêm đỉnh bắt đầu vào hàng đợi
Sau khi thực hiện bước này, hàng đợi sẽ như thế này:


- Trong khi hàng đợi ko rỗng thì thực hiện các lệnh:
Code:

   while(IsQueueEmpty(q) == 0)
   {
      // lấy đỉnh có chi phí thấp nhất trong hàng đợi
      dinh temp2; // tạo biến tạm khác. Biến tạm này sẽ chứa đỉnh sẽ duyệt trong lần lặp của vòng while
      DeQueue(q,temp2); // temp2.ten = M , temp.cost = 0
              // nếu đỉnh duyệt trùng với đỉnh kết thúc
      if(temp2.ten == end)
      {
         return 1; // thoát khỏi hàm
      }
                // kiểm tra xem đỉnh duyệt có trùng với các đỉnh đã duyệt chưa ?
      if(KiemTraTrung(g,temp2.ten))
         continue; // nếu có bỏ qua đỉnh đang duyệt,  tiếp tục vòng while mới để duyệt đỉnh khác
      // Nếu đỉnh đang duyệt không nằm trong các đỉnh đã duyệt, thì thêm đỉnh vào các đỉnh đã duyệt
      ThemDuyet(g,temp2);
      // duyet các dinh kề của đỉnh đang duyệt
                // vd: nếu đang duyệt A thì sẽ duyệt các đỉnh kề của A là: B C G H
                // tìm vi trí dòng của đỉnh đang duyệt
      int index;
      for(int i = 0; i < g.n; i++)
      {
         if(g.a[i][0] == temp2.ten)
         {
            index = i;
            break;
         }
      }
                // duyệt các đỉnh kề
            for(int j = 1; j < max; j++)
            {
                int x = (int)g.a[index][j]; // lấy mã số ascii của phần tử g.a[index][j]
                if(x == 0)
                    break;
      if((x>64 && x<91) // nếu phần tử g.a[index][j] là ký tự thuộc A-Z
      {
                        // kiểm tra xem đỉnh g.a[index][j] có nằm trong các đỉnh đã duyệt chưa
         if(!KiemTraTrung(g,g.a[index][j]))
         {
            // thêm đỉnh này vào hàng đợi
            dinh temp3;
            temp3.ten = g.a[index][j];
                                // chi phí đường đi đến đỉnh temp3 sẽ = chi phí đến đỉnh temp2 + khoảng cách của 2 đỉnh temp2 và temp3
            temp3.cost = temp2.cost + ChiPhi(g,temp2ten,temp3.ten);
            EnQueue(q,temp3);

            // đặt preview của temp3 là temp2 trong mảng quaylui
                                for(int i = 0; i <g.n; i++)
                                {
                                      if(g.quaylui[i].dinh1 == temp3)
                                      {
                                              // nếu temp3 chưa co preview thì đặt preview của temp3 = temp2
                                              if((int)g.quaylui[i].dinh0 == 0)
                                                      g.quaylui[i].dinh0 = temp2.ten;
                                              // nếu temp3 đã co preview thì so sánh chiphi(preview, temp3) và chiphi(temp2, temp3)
                                              else
                                              {
                                                // lấy chichi(preview,temp3) nhỏ nhất trong hàng đợi q
                       double t_cost = 9000000000; // lười nên ko tìm giá trị mã trước nên lấy đại con số to to
                       for(int i=0; i < q.QNumItems ;i++)
                       {   
                          if(temp3.ten == q.QArray[i].ten)
                          {
                             if(q.QArray[i].cost < tcost && q.QArray[i].cost != temp3.cost)
                                t_cost = q.QArray[i].cost;
                          }
                       }
                                                // nếu chiphi(temp2,temp3) nhỏ hơn chi phí dương đi nhỏ nhất hiện có của temp3 thì đặt preview của temp3 = temp2
                       if(temp3.cost < t_cost)
                              g.quaylui[i].dinh0 = temp2.ten;
                                              }
                                        }
                                }
         }
      }
            }
   }
Debug:
Lần lặp thứ 0 của vòng while:

Lần lặp thứ 1 của vòng while:

Lần lặp thứ 2 của vòng while:

Tương tự ở các lần sau..... vì nó lặp đến > 20 lần nên..........ko ghi nổi

5. Chạy chương trình
Việc cuối cùng là gọi các hàm ở hàm main:
Code:

void main()
{
   graph g;
   char start;
   char end;
        TaoMangDuyet(g);
   Doc("c://input.txt",g,start,end);
   InitVisit(g);
   TimKiem(g,start,end);
   Ghi("c://output.txt",g.start,g,end);
   getch();
}

JOB DONE.

P/S: Nói câu cuối, hi vọng các bạn hỉu dc cách làm của mình rồi có thể nghĩ dc cách làm hay hơn, đừng code giống nhau vì code giống nhau zero hết đó....... No


Ôi 1 Thời Để Nhớ....
<br>


Được sửa bởi kitsudo ngày Tue 02 Nov 2010, 21:42; sửa lần 1.

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 18
Posts Posts : 377
Coins Coins : 564
Thanked Thanked : 33

GIẢI THÍCH GIÙM MÌNH DÒNG NÀY ĐI:
Code:
      if(q.QLast < 0)
        q.QLast = q.QMax -1;
Thank nhìu nhé! Chủ topic cứ từ từ trả lời câu hỏi do Anh Em đặt ra nhé, trước mắt thì mình có nhìu câu để hỏi chủ topic này lắm ^^.


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

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

Toend2008 đã viết:
GIẢI THÍCH GIÙM MÌNH DÒNG NÀY ĐI:
Code:
      if(q.QLast < 0)
        q.QLast = q.QMax -1;
Thank nhìu nhé! Chủ topic cứ từ từ trả lời câu hỏi do Anh Em đặt ra nhé, trước mắt thì mình có nhìu câu để hỏi chủ topic này lắm ^^.

Cái này năm trong file hướng dẫn thực hành trên moodle, tui chỉ copy và pastte thôi. Nhưng mà nếu bảo tui giải thích thì tui cũng nói cách nghĩ của mình:
- Đầu tiên cần xem lại hàm thêm 1 phần tử của hàng đợi:
Code:

// them phan tu
int EnQueue(queue &q, dinh newitem)
{
  if(IsQueueFull(q))
      return 0;
  q.QLast++;
  if(q.QLast == q.QMax)
      q.QLast = 0;
  q.QArray[q.QLast].ten = newitem.ten;
  q.QArray[q.QLast].cost = newitem.cost;
  if(IsQueueEmpty(q))
      q.QFirst = 0;
  q.QNumItems++;
  return 1;
}

Sau đó mới xét đến đoạn điều chỉnh số lượng phần tử trong hàm lấy phần tử ra của hàng đợi
Code:

  if(IsQueueEmpty(q))
      q.QFirst = q.QLast = -1;
  else
  {
      q.QLast--;
      if(q.QLast < 0)
        q.QLast = q.QMax -1;
  }
Code:

  if(IsQueueEmpty(q))
      q.QFirst = q.QLast = -1;
Nếu hàng đợi rỗng thì vị trí của phần tử cuối (q.QLast) trong hàng đợi = -1
Code:

  else
  {
      q.QLast--;
Nếu ngược lại, hàng đợi không rỗng, thì vị trị của phần tử cuối (q.QLast) giảm đi 1
Code:


      if(q.QLast < 0)
        q.QLast = q.QMax -1;
  }
- Nếu vị trí phần tử cuối (q.QLast) < 0. Tức ban đầu hàng đợi còn đúng 1 phần tử, lúc đó q.QLast = 0 nên sau khi giảm 1 còn -1 < 0. Tức là sau khi lấy phần tử ra thì hàng đợi rỗng. Lúc này q.QLast = q.QMax -1

Nhìn lên đoạn code khi thêm 1 phần tử:
Code:

q.QLast++;
  if(q.QLast == q.QMax)
          q.QLast = 0;

Đây Là điều kiện kiểm tra hàng đợi rỗng của hàm thêm phần tử. Neutral


Ôi 1 Thời Để Nhớ....
<br>

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 43
Coins Coins : 85
Thanked Thanked : 8


Sống Trên Đời Phải Có Chữ "Tâm"



Muốn Sinh Tồn Phải Thêm Chữ "Nhẫn"

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 588
Coins Coins : 1307
Thanked Thanked : 128


[You must be registered and logged in to see this link.]
___________________________________________________

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên http://codoc.tk
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 26
Posts Posts : 68
Coins Coins : 110
Thanked Thanked : 7

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 28
Posts Posts : 416
Coins Coins : 400
Thanked Thanked : 43

Hix tinh thần chia sẻ lớn lao, chắc lớp mình ko ai bằng Idea


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

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 1
Coins Coins : 1
Thanked Thanked : 0

Lỗi tùm lum hết.

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
The author of this message was banned from the forum - See the message
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 18
Posts Posts : 377
Coins Coins : 564
Thanked Thanked : 33

Code:
bool ThemDuyet(graph &g, dinh newitem)
{
  for(int i=0; i < 100; i++)
      if(g.duyet[i].ten == '0') // nếu phần tử là phần tử ban đầu chưa đc gán tên đỉnh thì thêm tên dỉnh vào (**)
      {
        g.duyet[i].ten = newitem.ten;
        g.duyet[i].cost = newitem.cost;
        return true;
      }
  return false;
}
Bạn kitsudo có thể nói rõ qua ví dụ chỗ comment (**) ở đoạn code trên giúp mình được không? Xin cám ơn!


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

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

Toend2008 đã viết:
Code:
bool ThemDuyet(graph &g, dinh newitem)
{
  for(int i=0; i < 100; i++)
      if(g.duyet[i].ten == '0') // nếu phần tử là phần tử ban đầu chưa đc gán tên đỉnh thì thêm tên dỉnh vào (**)
      {
        g.duyet[i].ten = newitem.ten;
        g.duyet[i].cost = newitem.cost;
        return true;
      }
  return false;
}
Bạn kitsudo có thể nói rõ qua ví dụ chỗ comment (**) ở đoạn code trên giúp mình được không? Xin cám ơn!

Đây chỉ là 1 trong nhìu cách kiểm tra xem vị trí trong mảng đã có giá trị chưa. Nếu chưa thì thêm 1 giá trị vào.
Ban đầu, mảng g.duyet dc khởi tạo và tất cả vị trí trong mảng đều chưa có giá tri. Để làm đặc điểm cho việc chưa có giá trị., nên khi tạo mảng g.duyet mình đã gán cho tất cả phần tử trong mảng = ' 0 '.
Code:

// khoi tao mang
void TaoMangDuyet(graph &g)
{
  for(int i=0; i<max; i++)
      g.duyet[i].ten = '0';  // gán mặc định cho tên các dỉnh trong mảng là ký tự ' 0 '
}
Nên khi duyệt mảng, nếu duyệt 1 vi trí của mảng mà giá trị của nó là ' 0 ' tức tại vị trị đó chưa có giá trị nên dc quyền thêm giá trị vào.
VD: ban dầu mảng g.duyet sẽ:
i 0 1 2 3 4 5 6 7
g.duyet[i].ten 0 0 0 0 0 0 0 0

khi duyệt dỉnh M sẽ duyệt mảng g.duyet[i] bắt đầu từ i = 0. Lúc này g.duyet[i].ten = ' 0 '. nên dc quyền thêm giá trị M vào g.duyet[i]
i 0 1 2 3 4 5 6 7
g.duyet[i].ten M 0 0 0 0 0 0 0

tiếp tục khi duyệt dỉnh khác cũng sẽ kiểm tra nếu g.duyet[i]='0' thì mới them 1 dỉnh vào


Ôi 1 Thời Để Nhớ....
<br>

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 18
Posts Posts : 377
Coins Coins : 564
Thanked Thanked : 33

Thank kitsudo nhiều, lỗi là của mình khi chưa xem code của bạn kỹ!


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

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 26
Posts Posts : 362
Coins Coins : 1573
Thanked Thanked : 41

kitsudo đã viết:
temp3.cost = g.a[index][j].cost + ChiPhi(g,temp2ten,temp3.ten);
Bác xem lại code này nhá, a là mảng char của struct Graph thì làm sao mà .cost được ?

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

theghost đã viết:
kitsudo đã viết:
temp3.cost = g.a[index][j].cost + ChiPhi(g,temp2ten,temp3.ten);
Bác xem lại code này nhá, a là mảng char của struct Graph thì làm sao mà .cost được ?

hix ! cái đó chắc là temp2.cost + ChiPhi(g,temp2ten,temp3.ten)

tui nói gòi mà, code trực tiếp lun khi post nên co lỗi cũng hok co biết dc Sad


Ôi 1 Thời Để Nhớ....
<br>

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 28
Posts Posts : 416
Coins Coins : 400
Thanked Thanked : 43

lỗi mà cũng post


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

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 235
Coins Coins : 581
Thanked Thanked : 59

acb093 đã viết:
lỗi mà cũng post

Tui post bài hướng dẫn cách làm còn code chỉ là minh họa. Chứ có phải code hoàn chỉnh bài đó đâu.


Ôi 1 Thời Để Nhớ....
<br>

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 28
Posts Posts : 3
Coins Coins : 5
Thanked Thanked : 1

thank
chi xem cho hieu thuat toan thoi Smile

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Member

avatar
Member
Giới tính : Nam
Tuổi : 27
Posts Posts : 1
Coins Coins : 2
Thanked Thanked : 1

Thanks. đang cần cái này. không biết sao nữa. hi

※ Bài viết cùng chuyên mục


Xem lý lịch thành viên
Tác giảThông điệp
Sponsored content



※ Bài viết cùng chuyên mục


 
Bài giải bài tập thực hành UCS
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
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
Windows Việt :: Lưu Trữ :: Lưu Trữ - Các môn học cũ :: Trí Tuệ Nhân Tạo-
[Windows Việt] Deverloped by Nguyễn Gia Phú - http://windows.forumvi.com
Powered by © Forumotion.com - phpBB™ version ©phpBB2
Go to top Go to bottom