데이터구조 - Project 3 - Alliances, disjoint sets, and graphs - 연세대학교 최정윤 교수님
*보*
다운로드
장바구니
소개글
데이터구조 연세대 최정윤교수님 project 3 입니다Alliances, disjoint sets, and graphs
보고서첨부되어있습니다
컴파일 실행환경
Microsoft Visual C++ 6본문내용
EEE2020-01 Data Structures 2011 Fall term Jeung-Yoon ChoiProject 3
Alliances, disjoint sets, and graphs
(assigned 11/24/11, due 12/11/11)
There are eight countries in the world of Dataria. The countries are called Unoland, Binarepublic, Troy, Quaro, Penta, Sixar, Septima, and Octavania, denoted with numbers 1 through 8. Of these, the two major powers are Unoland and Octavania. Each country has different amounts of a vital resource, called invaluablium, which all the countries need to survive. (In our world, invaluablium is also called … water.) The amount of invaluablium in each country is calculated as
invaluablium in country n = [ ( n * 42 ) mod 19 ] * 1,000,000 tons
where n = 1 , 2, .. 8.
Since the resources are not distributed uniformly, the countries of Dataria forge alliances, headed by Unoland and Octavania, to try to “pool” their resources. (Sorry for the pun…) However, it is necessary to build pipelines that transport invaluablium between countries, so it is better if allied countries are not too far apart. The countries are located in the center of sectors given by
( x, y ) location of country n = [ 2 * ( ( n * 7 ) mod 3 ), ( n * 9 ) mod 5 ]
and the distances between countries are found using the Euclidean distance
distance between (x1, y1) and (x2, y2) = [ (x1-x2)2 + (y1-y2)2 ] 1/2
where each sector is 100 kilometers square.
The countries form alliances in this manner:
1. Initially, all countries are independent. (No alliances.)
2. Each year, Unoland and Octavania each finds two closest unallied countries and chooses the one with the greater supply of invaluablium to be an ally. In case both major powers choose the same country to be an ally, the alliance with the most resources wins.
3. Repeat Step 2 until all countries are in either the Unoland or Octavania alliance.
Your Final Project as Foreign Minister for Octavania, is to prepare a simulation for the Queen which shows how the alliances grow as the years progress, and to chart out the most efficient network of pipelines to connect the allied countries. Also, you will calculate how many kilometers of pipelines the alliance will have to build.
You may use algorithms and/or code related to disjoint sets and path searches in the textbook, such as Dijkstra’s algorithm. You may also implement your own algorithm for conducting a path search.
The report should be written in English, and should not exceed 3 pages (excluding code).
The report should include
(1) Brief explanation of the problem
(2) Your view as to how it ties in with what we covered in class
(3) Short explanation of your code
(4) Your code (hard copy)
(5) Your code (soft copy)
Grades will not be based on English fluency or writing style.
Grades will be based on correctness of implementation and sincerity of effort.
Good luck!
압축파일 내 파일목록
.DS_Store
1.5.bmp
1.bmp
2.bmp
3.5.bmp
3.bmp
4.bmp
5.bmp
Debug/Project3.exe
Debug/Project3.ilk
Debug/Project3.obj
Debug/Project3.pch
Debug/Project3.pdb
Debug/vc60.idb
Debug/vc60.pdb
DS_Project3_0640167_서보국.hwp
Project 3.doc
Project3.cpp
Project3.dsp
Project3.dsw
Project3.ncb
Project3.opt
Project3.plg
제목 없음.bmp
1.5.bmp
1.bmp
2.bmp
3.5.bmp
3.bmp
4.bmp
5.bmp
Debug/Project3.exe
Debug/Project3.ilk
Debug/Project3.obj
Debug/Project3.pch
Debug/Project3.pdb
Debug/vc60.idb
Debug/vc60.pdb
DS_Project3_0640167_서보국.hwp
Project 3.doc
Project3.cpp
Project3.dsp
Project3.dsw
Project3.ncb
Project3.opt
Project3.plg
제목 없음.bmp