Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: 6301
Последний выпуск: 19.06.2015

EuroDiffusion

351
13 апреля 2005 года
PitxBull
633 / / 22.12.2004
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.

P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))
Страницы:
351
13 апреля 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by PitxBull
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.

P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))



Упс, забыл постановку задачи...

Problem D
Eurodiffusion
Input File: euro.in
On January 1, 2002, twelve European countries abandoned their national currency for a new currency, the euro. No more francs, marks, lires, guldens, kroner,... only euros, all over the eurozone. The same banknotes are used in all countries. And the same coins? Well, not quite. Each country has limited freedom to create its own euro coins:
“Every euro coin carries a common European face. On the obverse, member states decorate the coins with their own motif. No matter which motif is on the coin, it can be used anywhere in the 12 Member States. For example, a French citizen is able to buy a hot dog in Berlin using a euro coin with the imprint of the King of Spain.” (source: http://europa.eu.int/euro/html/entry.html)
On January 1, 2002, the only euro coins available in Paris were French coins. Soon the first non-French coins appeared in Paris. Eventually, one may expect all types of coins to be evenly distributed over the twelve participating countries. (Actually this will not be true. All countries continue minting and distributing coins with their own motifs. So even in a stable situation, there should be an excess of German coins in Berlin.) So, how long will it be before the first Finnish or Irish coins are in circulation in the south of Italy? How long will it be before coins of each motif are available everywhere?
You must write a program to simulate the dissemination of euro coins throughout Europe, using a highly simplified model. Restrict your attention to a single euro denomination. Represent European cities as points in a rectangular grid. Each city may have up to 4 neighbors (one to the north, east, south and west). Each city belongs to a country, and a country is a rectangular part of the plane. The figure below shows a map with 3 countries and 28 cities. The graph of countries is connected, but countries may border holes that represent seas, or non-euro countries such as Switzerland or Denmark. Initially, each city has one million (1000000) coins in its country’s motif. Every day a representative portion of coins, based on the city’s beginning day balance, is transported to each neighbor of the city. A representative portion is defined as one coin for every full 1000 coins of a motif.
A city is complete when at least one coin of each motif is present in that city. A country is complete when all of its cities are complete. Your program must determine the time required for each country to become complete.
The 2003 ACM Programming Contest World Finals sponsored by IBM Input
The input consists of several test cases. The first line of each test case is the number of countries (1 ≤ c ≤ 20). The next c lines describe each country. The country description has the format: name xl yl xh yh, where name is a single word with at most 25 characters; xl, yl are the lower left city coordinates of that country (most southwestward city ) and xh, yh are the upper right city coordinates of that country (most northeastward city). 1 ≤ xl ≤ xh ≤ 10 and 1 ≤ yl ≤ yh ≤ 10.
The last case in the input is followed by a single zero.
Output
For each test case, print a line indicating the case number, followed by a line for each country with the country name and number of days for that country to become complete. Order the countries by days to completion. If two countries have identical days to completion, order them alphabetically by name.
Use the output format shown in the example.
Sample Input Output for the Sample Input 3


France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
1
Luxembourg 1 1 1 1
2
Netherlands 1 3 2 4
Belgium 1 1 2 2
0


Case Number 1
Spain 382
Portugal 416
France 1325
Case Number 2
Luxembourg 0
Case Number 3
Belgium 2
Netherlands 2

424
13 апреля 2005 года
sq_deep
498 / / 18.02.2005
Цитата:
Originally posted by PitxBull
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.

P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))


Мне программа понравилась.

Вот если бы в код добавить комментариев, то даже Янукович не смог бы помешать IBM взять вас на работу ;)

424
13 апреля 2005 года
sq_deep
498 / / 18.02.2005
Прошу прощения, файл почему-то не прикрепился. Попробую ещё раз.
285
13 апреля 2005 года
Shiizoo
958 / / 14.03.2004
О БЛИН. Форум откатили???? =) Половина ответов в теме канула в лету.. Юпиииии!!! :D
4
14 апреля 2005 года
mike
3.7K / / 01.10.2002
Цитата:
Originally posted by Shiizoo
О БЛИН. Форум откатили???? =) Половина ответов в теме канула в лету.. Юпиииии!!! :D



Тема разделена на две

1. Эта, про EuroDiffusion
2. Про комментирование исходников

351
14 апреля 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by mike
Тема разделена на две

1. Эта, про EuroDiffusion
2. Про комментирование исходников



А зачем удалять мое последнее сообщение, уже после того как тема была разделена на две ? Может там был матюк ? тогда почему не был удален предыдущий ответ ( не мой )? Ээээ ребята.... по моему вы чего то испугались...

12K
25 июня 2005 года
sam-N
7 / / 25.06.2005
Можно описание алгоритма программы eurodiffusion , в любом виде.
Очень нужно!!!!!!!!!!!!!!!!!! __________________
12K
26 июня 2005 года
SEn2005
1 / / 26.06.2005
Цитата:
Originally posted by PitxBull
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.

P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))




А алгоритм для решения этой задачи у Вас есть?

351
27 июня 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by SEn2005
А алгоритм для решения этой задачи у Вас есть?



Алгоритмы устарели :)), пользуйтесь OOP :))).

12K
27 июня 2005 года
sam-N
7 / / 25.06.2005
X)- Да ладно, я программау уже написала!!!!!!!

А насчет ООР, мне нужно на чистом С++, без ООР.
т.е. ручками нужно написать, без Visual!!!!!
285
28 июня 2005 года
Shiizoo
958 / / 14.03.2004
ооп есть главное отличие c++ от c. и причем тут visual.. :o не понять мне, не понять.. :{
3
28 июня 2005 года
Green
4.8K / / 20.01.2000
Цитата:
Originally posted by Shiizoo
ооп есть главное отличие c++ от c. и причем тут visual.. :o не понять мне, не понять.. :{



А мне не понять и фразы: "Алгоритмы устарели ), пользуйтесь OOP ))."

12K
28 июня 2005 года
sam-N
7 / / 25.06.2005
Как могут устареть алгоритмы.
Интересно а насколько устарело?
285
28 июня 2005 года
Shiizoo
958 / / 14.03.2004
Да, неясная тема. Много неоднозначных высказываний. Не буду сюда больше заглядывать, а-то ведь еще и меня устарелым признают.. :{
351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by Shiizoo
Да, неясная тема. Много неоднозначных высказываний. Не буду сюда больше заглядывать, а-то ведь еще и меня устарелым признают.. :{



?????????:))))))))))??????????:)))))))))) а что здесь происходит ?

351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by Green
А мне не понять и фразы: "Алгоритмы устарели ), пользуйтесь OOP ))."



ну ладно поясню.....по всей видимости девушке нужен был алгоритм как средство документирования проекта....смысл фразы состоял и в том что документироание проги в виде одного большого, толстого и детального алгоритма устарело, и это надо делать в терминах OOP. Это примерно как фраза : мне нужен алгоритм работы Windows. Эта прога конечно не Windows, но вследтвии фрактального построения мира, это правило применимо и к ней. Вот блин, файл скачан 45 раз!!, кому это он интересно понадобился??? еббб....задача ж решена по секретной технологии прораммирования ....главное что б никто не догадался :))))))))))))

12K
28 июня 2005 года
sam-N
7 / / 25.06.2005

Я тоже скачала и выкинула.
285
28 июня 2005 года
Shiizoo
958 / / 14.03.2004
Я тоже скачал, но забыл куда :{ второй раз качать лень было, а искать, и мне, и ВЫНЬу уж тем более :D да и ваще я ничего в этих цифрах буквах непонимаю, зачем оно надо, мое дело подъезды мести :}
351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
:)))))))) ???????? и все таки .... а что здесь происходит ? :)))))))))) кому понадобилось поднимать тему двухмесячной давности ????? ааа...понимаю.....и 2000 лет война.....
351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
ух... ты .....файл скачан уже 48 раз.....популярность наша растет а доходы падают :)))))))))
285
28 июня 2005 года
Shiizoo
958 / / 14.03.2004
Да эт я седня качал:D Решил ишо раз глянуть=) Так объяснитя мне, в чем сила кода? Как с ним можно эффективнее жевачки с пола соскребать?:D
351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by Shiizoo
Да эт я седня качал:D Решил ишо раз глянуть=) Так объяснитя мне, в чем сила кода? Как с ним можно эффективнее жевачки с пола соскребать?:D



эээ...я смотрю у тя как в том анекдоте : сила есть, код есть, силы кода нет :D

351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
Вот блин какое дело народ.....я злостно прогулял два дня работы(неделю назад устроился) и теперь передо мной стоит диллема :
1. Придти завтра на работу и что нибудь соврать про свое отсутсвие.
2. Придти завтра на работу и сказать что я увольняюсь.

никак не могу определиться, предлагаю всем желающим проголосовать ( нужна помощь зала :))) ), за правильный по их мнению вариант.
351
28 июня 2005 года
PitxBull
633 / / 22.12.2004
и еще... СРОЧНО нужен алгоритм работы Windows!!!!....а то чем я хуже других....напишу свой а этот(Windows) выкину :))))
285
29 июня 2005 года
Shiizoo
958 / / 14.03.2004
Эээ, флудер:) Предлагаю придти (..мм, седня?) на работу, и сказать что ты всех увольняешь=) По крайней мере врать не придется;)
351
02 июля 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by sam-N
Как могут устареть алгоритмы.
Интересно а насколько устарело?



Долго думал что на это ответить и наконец меня осенило : алгоритмы устарели процентов на 98%. :)))) ( да простят меня за тупость ответа ). Как было написано в одной книге тело метода должно состоять не более чем из трех строчек. О каких алгоритмах тут может идти речь ???? Остаете товарищи отстаете. :D

351
02 июля 2005 года
PitxBull
633 / / 22.12.2004
и по всей видимости две из этих трех строчек должны быть фигурными скобками {}. Во время работы над одним проектом ввиду некоторых особенностей его проектирования меня не покидала мысль что вся жизнь эта последовательность врапперов. Одного на другим. И так далее до вершины пирамиды.....
3
02 июля 2005 года
Green
4.8K / / 20.01.2000
Цитата:
Originally posted by PitxBull
Долго думал что на это ответить и наконец меня осенило :
<skip>
<skip>
<skip>



"И тут Остапа понесло..." (c)И.Ильф,Е.Петров

351
02 июля 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by Green
"И тут Остапа понесло..." (c)И.Ильф,Е.Петров



Насчет skipa это ты зря :). Без паники. Я дам вам парабеллум.

P.S. Интересуемя ценами на нефть?. А на то фотке ск картой ты по всей видимости по середине ?:))))))))))))

3
02 июля 2005 года
Green
4.8K / / 20.01.2000
Цитата:
Originally posted by PitxBull
P.S. Интересуемя ценами на нефть?.


Ну да... Подхалтуриваю на международных торгах...

Цитата:
Originally posted by PitxBull
А на то фотке ск картой ты по всей видимости по середине ?:))))))))))))


Нет. Я это фото делаю, поэтому меня там быть не может или может и не быть...
Но вот в маске - это я.

P.S. Долой оффтоп!

351
02 июля 2005 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by Green
Ну да... Подхалтуриваю на международных торгах...

Нет. Я это фото делаю, поэтому меня там быть не может или может и не быть...
Но вот в маске - это я.

P.S. Долой оффтоп!




ок.....:)))).

351
18 сентября 2005 года
PitxBull
633 / / 22.12.2004
ух ты... файл скачан 96 раз...
351
19 марта 2006 года
PitxBull
633 / / 22.12.2004
год спустя.... файл скачан 110 раз... помоему абсолютный рекорд по download-ам на этом сайте. Принимаю поздравления и денежные переводы. Могу опубликовать всеь список вступительных заданий от IBM и решений к ним за отдельную плату.
351
03 мая 2006 года
PitxBull
633 / / 22.12.2004
Цитата:
Originally posted by PitxBull
год спустя.... файл скачан 110 раз... помоему абсолютный рекорд по download-ам на этом сайте. Принимаю поздравления и денежные переводы. Могу опубликовать всеь список вступительных заданий от IBM и решений к ним за отдельную плату.


эйййййййййййййййййййййй.... уки_дуки и прочие математически настроеные личности которые утверждали что разработка в програмировании есть выведение математических формул :))))))))))))))))))))))))))))))) вы мне на 25 апреля какого года математическое решение этой задачи обещали ? а то уже 3 мая я начинаю за вас беспокоится как бы вы там не перевешались пытаясь решить мою задачу.

20K
25 июля 2006 года
arsenaltula
1 / / 25.07.2006
Привет,
Вы не подскажите как скачать исходники данной замечательной программы?
я новичок на форумах и никак не могу найту линк где можно скачать исходники
Спасибо
351
02 ноября 2006 года
PitxBull
633 / / 22.12.2004
[QUOTE=arsenaltula]Привет,
Вы не подскажите как скачать исходники данной замечательной программы?
я новичок на форумах и никак не могу найту линк где можно скачать исходники
Спасибо[/QUOTE]
вот исходники... а то сменой дизайна форума предыдущие исчезли.
3
02 ноября 2006 года
Green
4.8K / / 20.01.2000
Это единственная программа, которой ты можешь гордиться?
Ты с ней носишься уже второй год, рекламируя на каждом шагу,не гнушаясь создавать липовый ажиотаж липовыми участниками форума.
Бедный arsenaltula был создан и забыт с одной лишь целью - поднять тему наверх... :D
Неужели, больше нечем похвастаться?
Чтож взгляну, что там внтри... Жди коментариев. :D
351
02 ноября 2006 года
PitxBull
633 / / 22.12.2004
[QUOTE=Green]Это единственная программа, которой ты можешь гордиться?
Ты с ней носишься уже второй год, рекламируя на каждом шагу,не гнушаясь создавать липовый ажиотаж липовыми участниками форума.
Бедный arsenaltula был создан и забыт с одной лишь целью - поднять тему наверх... :D
Неужели, больше нечем похвастаться?
Чтож взгляну, что там внтри... Жди коментариев. :D[/QUOTE]
расскажи об этом своему психиатру.
351
02 ноября 2006 года
PitxBull
633 / / 22.12.2004
ааааа... я понял вашу стратегию.... вы хотите что бы я умер от смеха ? :)))))))))))))))
3
04 ноября 2006 года
Green
4.8K / / 20.01.2000
Посмотрел сиё творение...
Код не понравился. Код сырой, нагромажденный, запутанный, одним словом некрасивый. Автор не потрудился взглянуть на задачу с математической или алгоритмической точки зрения, считая, что это как-то противоречит ООП, а решил делать "в лоб", что в купе с низкой культурой и практикой использования C++, привело к печальным результатам. Код работает, но вот как он это делает, с какими ресурсозатратами, а так же его читабельность оставляет желать лучшего.

О структуре проекта могу сказать следущее:
1) зачем тащить лишние файлы в архиве (.ncb, .asp и т.п.) ?
2) зачем тащить лишние файлы в проекте (Resource.rc, Resource.h и т.п.) ?
3) зачем подключать столько лишних файлов (см. stdafx.h) ?

Теперь объективно обо всех нюансах.
Я довольно скурпулезно разобрался в работе этого кода, и вот мои замечания:

1. Использование контейнеров STL и MFC. Само по себе использование MFC (по сути своей, оконной библиотеки) в консольном приложении - плохая практика. Причем, из STL используется только vector. Видимо, автор кода не знает о существовании в STL других контейнеров, таких как map или list, поэтому он использует CList и CMap из MFC.

2. Использование глобальных переменных, инициализация и пр. операции с которыми разбросаны по всему коду.

3. Многочисленное дублирование информации. Так, например, введено лишнее поле Space::nCountries, информация в котором идентична Space::ListOfCountries.GetSize(). Это далеко не единичный случай. Еще примеры: поле Space::nCountriesCompleted, Space::AllCountriesCompleted и т.д.

4. Огромное количество контейнеров:
CList: 1 + 3*N, где N - количество городов (!!!)
CMap: N, где N - количество городов (!!!)
std::vector: 3
C-array: 1
Это как увеличивает количество потребляемой памяти, так и приводит к избыточным пересылкам данных, что снижает производительность. Кстати, а зачем понадобился ассоциативный контейнер? Там вполне хватило бы и обычного динамического выделенного массива.

5. Используется C-string, хотя, не причин не использовать std::string. Это снижает читабельность алгоритма, приводит к потенциальным багам, т.к. проверки размерности C-string нет.

6. Множество перекрестных зависимостей. Например, класс Space агрегирует набор экземпляров класса Country, класс Country в свою очередь имеет ссылку на класс Space, а так же информацию об общем количестве своих экзеспляров. Ну это ещё что... Вот класс City тоже содержит информацию о количестве экземпляров класса Country, и ссылку на сам класс Country. Причем класс Country не агрегирует набор классов City, для этого служит глобальный (!!!) массив. Конечно, горожане должны знать в какой стране живут, да и количество стран тоже надо знать, это же школьный курс географии. Странно, что в класса City нет информации о президенте страны или хотя бы мэре города. :)

7. Удивляют так же "callback-и". Например, по заполнению каждого (!) города об этом сигнализируется отдельным вызовом классу Country.

8. Судя по коду, наибольшую трудность у автора вызвала операция передачи монет в соседние города. Для этого он завел целых три (!!!) списка, хотя хватило бы одного контейнера. Ну и весьма разветвленная схема вызовов (см. прикрепленную диаграмы вызовов).

9. Поражает и медленная скорость работы: 3000 итераций из 3х стран обрабатывались около 400 сек. (!!!), т.е. за секунду обрабатывалось менее 10 итераций (!!!). Я уверен, что скорость при должном алгоритме и архитектуре можно поднять как минимум в 10 раз.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог