Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 2, средняя оценка - 5.00
Spill
40 / 40 / 1
Регистрация: 22.02.2008
Сообщений: 65
#1

Олимпиадная подготовка - Алгоритмы

26.02.2008, 13:53. Просмотров 46838. Ответов 38
Метки нет (Все метки)

Многие из участников форума принимают участие в различных олимпиадах, конкурсах по программированию.Я предлагаю выкладывать в этой теме алгоритмы для подготовки к олимпиадам, возможно, какие-нибудь планы занятий и пр.Все алгоритмы должны быть написаны на псевдокоде, отвлеченно от языка реализации. Задачи тоже не нужно выкладывать. Обсуждение и вопросы тоже не сюда. И пожалуйста, не флудить, пишем только по делу
http://www.cyberforum.ru/algorithms/thread628305.html
16
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2008, 13:53
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Олимпиадная подготовка (Алгоритмы):

Олимпиадная задача
Доброго времени суток! Есть задача, которую я приложил в текстовом документе....

олимпиадная задачка
На доске наклеено несколько листов объявлений. Все они прямоугольной формы....

Подсуммы (олимпиадная задачка), нужны идеи
64 megabytes / 1 seconds / stdin / stdout Не все числа одинаково полезны....

Олимпиадная задачка. Если есть идеи то помогите. Вместе решим
B. Время исполнения Time Limit: 1000 ms Memory Limit: 1024 kb При...

Подготовка к экзамену
Ребят помогите ответить на билет, больше всего интересует 3 вопрос.

38
Spill
40 / 40 / 1
Регистрация: 22.02.2008
Сообщений: 65
27.02.2008, 14:33  [ТС] #2
Графы. Определение. Способы представления графов в памяти компьютера
Определение
Математическое определение графа довольно сложно для понимания. Поэтому ограничимся более простым и понятным. Итак, граф – это набор точек (вершины графа), притом некоторые пары вершин соединены дугами (ребра графа).* Можно представить граф, как, например, несколько городов. Некоторые соединены дорогами.
Вот пример простейшего графа.
Название: 5c773ef85351.jpg
Просмотров: 5438

Размер: 7.4 Кб
Граф может быть ориентированный, или неориентированный. В ориентированном графе по ребру можно двигаться только в одном направлении. (пример – граф 1.2, рисунок:

*Более точное определение можно найти в книге «Алгоритмы, построение и анализ» (Кормен, Лейзер). Кстати, хорошая книга, рекомендую иметь каждому. Если не хочется читать (ок. 1000 стр.), то хотя бы знать по содержанию, что там есть, чтобы в случаи чего посмотреть.
Способы представления графов в памяти компьютера
Существует несколько способов представления графов. Но чаще всего используются 2. О них и пойдет речь ниже.
1. Матрица смежности.
Для хранения графа необходима матрица (например, A) N*N, где N – количество вершин. A[V, U]=1, если есть путь из V в U, или 0 в противном случаи. В неориентированном графе A[V,U] = A[U,V] = 1, поскольку есть путь как из V в U, так и из U в V.1.
Достоинства :
1. Возможность хранить вес дуги (об этом позже)
2. Быстрое и простое добавление/удаление ребра
3. Возможность оптимизации памяти (для тех, кто знает, что такое разреженные матрицы)
2. Недостатки:1. Большой расход памяти
2. Существует ограничение на размер графа. (Может не влезть в массив)
2. Список инцидентности ребер
Граф хранится следующим образом: Для каждой вершины существует список (массив, или чего-нибудь поэффективнее). Первый элемент хранит число N - количество эл-тов в списке (не обязательно, если есть признак конца списка). Далее идет N чисел – вершины, в которые есть путь из текущей. Приведу пример списка для графа 1.2:
Список для вершины 1: 2, 2, 5
Список для вершины 2: 1, 3
Список для вершины 3: 0
Список для вершины 4: 3, 5, 2, 3
Список для вершины 5: 0
Чаще всего в этом случаи используют матрицу
Достоинства :
1. Более-менее оптимальный расход памяти
2. Недостатки:
1. Невозможно хранить вес дуги
Выбор способа хранения нужно делать в соответствии с условиями конкретной задачей, в зависимости от того, что вы собираетесь делать с элементами графа, как именно собираетесь с ним работать и еще много от чего.
Кликните здесь для просмотра всего текста
Название: 1bf53632a022.jpg
Просмотров: 9474

Размер: 10.1 Кб
22
exe-dealer
302 / 155 / 11
Регистрация: 07.06.2009
Сообщений: 538
09.06.2009, 01:38 #3
"Комбинаторика для программистов(В. Липский)" - очень хорошая книга по графам и комбинторике, примеры на псевдокоде, понятные объяснения. Нужная вещь для подготовки к олимпиаде.
11
Doc.X
11 / 11 / 0
Регистрация: 23.06.2009
Сообщений: 8
23.06.2009, 21:01 #4
Алгоритмы: построение и анализ
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
Очень хорошая книга.. псевдокод.

http://www.williamspublishing.com/Books/5-8459-0857-4.html
10
Veyron
106 / 106 / 9
Регистрация: 02.06.2009
Сообщений: 578
11.10.2009, 20:31 #5
Федор Меньшиков: Олимпиадные задачи по программированию, 2006. 90 задач, разборы, чекер в комплекте. По мне так книга самый сок.
6
Phantom
Эксперт С++
3168 / 850 / 39
Регистрация: 29.12.2008
Сообщений: 952
30.10.2009, 10:57 #6
http://g6prog.narod.ru/first.html
Интересный сайт, посвященный разбору олимпиадных задач.
6
Unrealler
653 / 351 / 113
Регистрация: 11.12.2009
Сообщений: 508
09.05.2010, 10:22 #7
http://olympiads.ru/
Разборы, проверка олимпиадных и не только задач
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
09.05.2010, 15:16 #8
Еще сайты с олимиадными задачами

http://acm.timus.ru/
3
shash
6 / 2 / 0
Регистрация: 03.05.2009
Сообщений: 7
13.05.2010, 10:33 #9
informatics.mccme.ru
супер сайт с архивом почти всех олимпиад (от РОИ до IOI)

e-maxx.ru
хороший набор алоритмов и их описание + код на языке с++
2
FireSpace
0 / 0 / 0
Регистрация: 24.03.2010
Сообщений: 4
14.05.2010, 21:47 #10
http://codeforces.com/ - пока находится на стадии бета-тестирования, но очень большой задел на будущее. Олимпиады проводят сами участники. После каждой олимпиады есть возможность посмотреть код решения других людей.
http://neerc.ifmo.ru/school/io/index.html - Питерский сайт, тоже постоянно проводятся олимпиады.

А из учебников сам сейчас читаю "Фундаментальные алгоритмы на С++" (Седжвик Р.)
0
HERETIC
91 / 91 / 13
Регистрация: 10.10.2008
Сообщений: 606
Завершенные тесты: 1
15.05.2010, 01:31 #11
Может кому пригодятся исходники с описанием алгоритмов. Краткое содержание:

1)Алгоритмы компьютерной графики
- Инвертирование цветов;
-Фильтр RGB - градации серого;
-Фильтр Контур;
-Фильтр Размытие;
-Фильтр Резкость;
2)Графы
-Определение числа компонент связности;
-Поиск кратчайшего пути методом фронта волны;
-Путь минимального веса в нагруженном графе;
-Существование пути между 2 вершинами;
3)Деревья
-Модуль с работы с деревьями
4)Массивы
-Поиск;
-Сортировка;
5)Матрицы
-Модуль для работы с матрицами
6)Строки
-Алгоритм Бойера Мура;
-Алгоритм замены одной подстроки другой;
-Алгоритм Кнута Морриса и Пратта;
-Алгоритм последовательного поиска;
-Взятие подстроки
7)Структуры данных
-Дек;
-Список;
-Стек
8)Численные методы
-LU-разложение матрицы СЛАУ;
-Метод вращений Якоби;
-Метод Зейделя решения СЛАУ;
-Метод прогонки;
-метод Якоби решения СЛАУ;
-Поиск детерминанта матрицы методом Гаусса;
-Поиск обратной матрицы методом Гаусса;
-Решение СЛАУ методом Гаусса

Пользуйтесь на здоровье !!!!!!!!!!
26
Вложения
Тип файла: 7z Алгоритмыкомпьютернойграфики.7z (3.2 Кб, 190 просмотров)
Тип файла: 7z Графы.7z (86.9 Кб, 228 просмотров)
Тип файла: 7z Деревья.7z (6.4 Кб, 173 просмотров)
Тип файла: 7z Массивы.7z (122.3 Кб, 208 просмотров)
Тип файла: 7z Матрицы.7z (5.3 Кб, 186 просмотров)
Тип файла: 7z Строки.7z (97.7 Кб, 183 просмотров)
Тип файла: 7z Структурыданных.7z (8.8 Кб, 171 просмотров)
Тип файла: 7z Численныеметоды.7z (327.8 Кб, 399 просмотров)
Unrealler
653 / 351 / 113
Регистрация: 11.12.2009
Сообщений: 508
18.05.2010, 19:58 #12
С.Окулов "Программирование в алгороритмах". Великолепная книга: длинная арифметика, комбинаторика, алгоритмы на графах, методы динамического программирования, геометрия. Запросто можно найти в электронном виде
6
woohoo
7 / 7 / 1
Регистрация: 30.06.2010
Сообщений: 27
07.07.2010, 20:20 #13
есть еще нерусский сайт spoj.pl - чем хорош, там языков много поддерживается, разных версий причем
0
g-man
9 / 9 / 1
Регистрация: 02.04.2010
Сообщений: 25
27.09.2010, 00:03 #14
spoj.pl - огромная база замечательных задач по программированию различной направленности и сложности с системой тестирования
topcoder.com - сайт на котором проводятся различные соревнования по программированию(алгоритмы, дизайн и т.д.)
0
Евгений М.
1047 / 986 / 98
Регистрация: 28.02.2010
Сообщений: 2,858
Завершенные тесты: 2
31.10.2010, 20:15 #15
Здесь я постараюсь чаще выкладывать разборы олимпиадных задач.
http://em92.uni.cc/index_ru.html
1
кот Бегемот
Платежеспособный зверь
8447 / 3886 / 1511
Регистрация: 28.10.2009
Сообщений: 10,062
01.11.2010, 19:44 #16
да, Евгений М., много у Вас там задач разобрано, целых одна.
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
26.03.2011, 23:39 #17
Товарищи, а есть кто-нибудь, кто этим профессионально занимается (занимался) ? Было бы чудесно получить консультацию по парочке вопросов
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
26.03.2011, 23:50 #18
Ну я немношко.
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
27.03.2011, 09:23 #19
Хохол, подскажите, а по чем готовились? Кормен, Ахо, что ещё?
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
27.03.2011, 09:58 #20
Кормен, гугл, умные люди в аське.
0
27.03.2011, 09:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2011, 09:58
Привет! Вот еще темы с решениями:

Подготовка к IT-соревнованиям
Привет всем. Заранее извиняюсь за то, что тема выбрана неккоректно, но создать...

Подготовка по c#
подскажите пожалуйста сайты, книги, где можно найти разобранные примеры и...

Подготовка к олимпиаде !!!!
Здравствуйте уважаемые программисты! У меня после завтра олимпиада сегодня...

Подготовка к ГОСам)
Добрый день. Готовлюсь к ГОСам и возник такой вопрос по сетевым устройствам и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru