Lớp: Tin18a1HN - Đại học kinh tế kỹ thuật công nghiệp Hà Nội
Bạn nên đăng nhập vào diễn đàn để được hưởng tất cả những quyền lợi của 1 Member. Chúc các bạn có những phút giây vui vẻ trong Forum.
Nếu bạn chưa có ID trong forum hãy đăng kí tại đây ngay hôm nay!!

Lớp: Tin18a1HN - Đại học kinh tế kỹ thuật công nghiệp Hà Nội

Minh Nguyễn
 
IndexIndex  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng Nhập  
Latest topics
Top posters
LeeStar (407)
 
hjkazu (362)
 
Ring_ThieuGia (141)
 
khongthethieuem (134)
 
tramy_idol (78)
 
akjrahuy (77)
 
vinaphone1989 (62)
 
Thaimeoyb91 (55)
 
MyungJinHo (46)
 
khoameo (41)
 
Liên kết Website

Phim Hàn, Phim Cấp 3, Phim Hot...
Hỗ trợ online


THINHLONG.NET
LeeStar


THINHLONG.NET
Ring_ThieuGia
Thống Kê
Hiện có 1 người đang truy cập Diễn Đàn, gồm: 0 Thành viên, 0 Thành viên ẩn danh và 1 Khách viếng thăm

Không

Số người truy cập cùng lúc nhiều nhất là 27 người, vào ngày Thu Sep 22, 2011 10:05 am
Statistics
Diễn Đàn hiện có 378 thành viên
Chúng ta cùng chào mừng thành viên mới đăng ký: thuytmbn

Tổng số bài viết đã gửi vào diễn đàn là 1717 in 468 subjects

Share | 
 

 Bài toán người du lịch ( C++)

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
LeeStar
Super Moderator
Super Moderator


Nam Tổng số bài gửi : 407
Điểm Post : 12401
Thanked : 6
Ngày sinh : 18/06/1991
Ngày tham gia : 16/04/2010
Tuổi : 25
Đến từ : 당신을 사랑합니다

Bài gửiTiêu đề: Bài toán người du lịch ( C++)   Mon May 17, 2010 8:58 pm

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

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.

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.*/

#include

#include

#include

#include


using namespace std;


const
int size = 100;

int maxE = 100;

int maxC = size * maxE;


int C[size][size];

int X[size+1];

int T[size];


int BestWay[size+1];


bool FREE[size];


int minSpending;

int M,N;



void Enter ()

{

int i,j,k;

cout << " CITY: " ; cin >> N;

cout << " TRAFFIC ROAD: "; cin >> M;



for (
i = 0; i < N; i++ )

{

for (
j = 0; j < N; j++ )

{

if (
i == j ) C[i][j] = 0;

else
C[i][j] = maxC;



}

}

for (
int k = 0; k < M; k++ )

{

cout << "Enter i: "; cin >> i;

cout << "Enter j: "; cin >> j;

cout << "Cost : "; cin >> C[i][j];

C[j][i] = C[i][j];

}

}

void InI()

{

for (
int i = 0; i <= N; i++ )

{

FREE[i] = true;

}


FREE[1] = false;

X[0] = 1;

T[0] = 0;



minSpending = maxC;

}


void PRINT()

{

if (
minSpending == maxC )

{

cout << "NO SOLUTION ";

}

else

{

for (
int i = 0; i < N; i++ )

{

cout << BestWay[i] << "->";

}

cout << " Minimum Spending is : " << minSpending;

}

}


void BACKTRACK ( int i )

{

for (
int j = 2; j <= N; j++ )

{

if (
FREE[j] == true )

{

X[i] = j;

T[i] = T[i-1] + C[X[i-1]][j];

if (
T[i] < minSpending )

{

if (
i < N )

{

FREE[j] = false;

BACKTRACK ( i + 1 );

FREE[j] = true;

}

}

else

{

if ( (
T[N] + C[X[N]][0] ) < minSpending )

{

for (
int var = 0; var <= N; var++ )

{

BestWay[var] = X[var];

}

minSpending = T[N] + C[X[N]][0];

}

}

}

}

}


int main()

{

Enter();

InI();

BACKTRACK (1);

PRINT();

getch();

}

_______________________________________________

Chữ ký (Signature):
[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this link.]
Nếu thấy bài viết hay hãy cho thêm 1 điểm + nha
[You must be registered and logged in to see this image.]
Về Đầu Trang Go down
Xem lý lịch thành viên http://tin18a1.forumakers.com
LeeStar
Super Moderator
Super Moderator


Nam Tổng số bài gửi : 407
Điểm Post : 12401
Thanked : 6
Ngày sinh : 18/06/1991
Ngày tham gia : 16/04/2010
Tuổi : 25
Đến từ : 당신을 사랑합니다

Bài gửiTiêu đề: Re: Bài toán người du lịch ( C++)   Mon May 17, 2010 9:03 pm

Bài này cũng gần giống như là bài toán mà thầy làm. Chỉ khác chút ít thôi về cơ bản thuật toán cũng giống nhau. bài này chính là bài 1 của BTVN.
Chú ý: Chỉ có 1 bài tập về viết chương trình thôi nên các bạn cố gắng học bản chất của bài toán. Học cái đấy dễ hơn là học thuộc lòng thuật toán. Tất cả những tài liệu đều có trên mạng các bạn cố gắn tìm và hiểu đc bản chất của nó.

Đề thi sẽ ko khó lắm đâu Cả nhà mình cùng cố gắng nha!!! Chai yo 举办

_______________________________________________

Chữ ký (Signature):
[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this link.]
Nếu thấy bài viết hay hãy cho thêm 1 điểm + nha
[You must be registered and logged in to see this image.]
Về Đầu Trang Go down
Xem lý lịch thành viên http://tin18a1.forumakers.com
khongthethieuem
THÀNH VIÊN TÍCH CỰC
THÀNH VIÊN TÍCH CỰC


Nam Tổng số bài gửi : 134
Điểm Post : 882
Thanked : 7
Ngày sinh : 25/03/1990
Ngày tham gia : 12/05/2010
Tuổi : 26
Đến từ : Ha Noi

Bài gửiTiêu đề: Re: Bài toán người du lịch ( C++)   Mon May 17, 2010 9:07 pm

thanks bạn nhiều. mình sẽ chép bài này vào giấy rồi mang vào phong thi có gì bỏ ra chép :D
Về Đầu Trang Go down
Xem lý lịch thành viên
Sponsored content




Bài gửiTiêu đề: Re: Bài toán người du lịch ( C++)   Today at 4:48 am

Về Đầu Trang Go down
 
Bài toán người du lịch ( C++)
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
Lớp: Tin18a1HN - Đại học kinh tế kỹ thuật công nghiệp Hà Nội :: Học tập :: Các môn chuyên ngành-
Chuyển đến