데이터구조 - 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 Choi

Project 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!

참고자료

· 없음