Что такое достойная графическая головоломка для начинающих?[закрыто]

Question

Я пытаюсь поближе познакомиться с задачами, требующими решения с помощью графиков (которые лучше всего решаются с помощью графиков).

Если у кого-то есть старая задача конкурса ACM по программированию, в которой использовались графики, или другая задача, которую он нашел особенно полезной во время ее решения, я был бы признателен.Я хочу ознакомиться с графами, легко выявлять проблемы типа графов и уметь использовать основные алгоритмы обхода графов.

У кого-нибудь есть сладкая проблема, которую они могут отправить мне?

Answer 1

Я нашел эту книгу очень сильно полезно (ссылка на Amazon):Проблемы программирования

Он не только дает довольно подробное объяснение графов, деревьев и базовых структур данных, но и дает несколько задач по программированию, связанных с каждым типом!Этот документ для меня полезнее моего учебника!

Вот некоторые из проблем с графами в нем:

Проблемы, связанные Обход графа:

• Биколорирование:стр. 203
• Игра с колесами:стр. 204
• Туристический гид:стр. 206
• Слэш-лабиринт:стр. 208
• Редактировать стремянки:стр. 210
• Башня кубиков:стр. 211
• От заката до рассвета:стр. 213
• Проблемы с Ханойской башней (снова!):стр. 215

Проблемы, связанные Графовые алгоритмы (Дейкстра, Min Spanning Tree и т. д.):

• Веснушки:стр. 231
• Ожерелье :стр. 231
• Пожарная станция :стр. 234
• Железные дороги:стр. 235
• Война :стр. 237
• Большой ужин:стр. 241

Answer 2

Чтобы лучше понять операции на графике, вы можете просто реализовать некоторые известные Графовые алгоритмы.

Попробуйте реализовать Нурикабе решатель или генератор.Для этого потребуется немало классических операций с графами.

Answer 3

Вы должны быть знакомы с Проблема Кенигсбергского моста.Вам также следует хорошо ознакомиться с типами структуры данных которые часто возникают в задачах теории графов.

Answer 4

Графики можно буквально использовать для моделирования почти любая проблема. Топкодер.com Марафонские матчи часто позволяют использовать графические решения.

• А Планирование процессора Проблема может быть решена с помощью графиков.
• А Графстроитель проблема.
• А Расстояние проблема.
• А Картограф проблема (задача взвешенной k-раскраски, которая является классической задачей информатики).

Вы можете проверить некоторые из этих проблем — и их гораздо больше.

Answer 5

Вы не говорите, какой язык вы используете (думаете об использовании).Если можно, я бы предложил Lisp или Python.Они оба хороши для простого манипулирования графиками.Если вы хотите проявить фантазию, вы можете создать красивый результат с помощью PyGame.

Что касается проблемы, взгляните на простую программу и преобразуйте ее в график.Совет: каждый токен является узлом.Предполагая, что у вас есть несколько циклов и уравнений, вы можете пройти по графику и определить, что можно вынести за пределы цикла.Уравнения можно было бы переставить, чтобы они были более «эффективными».

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

Кстати, если вы попробуете вышеперечисленное, взгляните на Плекс, это сэкономит вам много времени при работе с парсерами.

Answer 6

http://codekata.pragprog.com/2007/01/kata_nineteen_w.html

Намекать:DAWG — довольно хороший метод.