22 апреля 2009
Немного тестов BFS
Добавилось наконец-таки несколько тестов для BFS. На прежнем месте: http://barashev.net/src/graph.zip
Drum höher und höher und höher!
Всех с наступившей неделей матмеха, гимн которого пели ещё в 1930 году немецкие бравые парни :)
А заодно и с успешным выступлением команды СПбГУ (читай матмех) в финале чемпионата мира по программированию. Литмошники правда опять впереди планеты всей -- сколько уж можно :)
А заодно и с успешным выступлением команды СПбГУ (читай матмех) в финале чемпионата мира по программированию. Литмошники правда опять впереди планеты всей -- сколько уж можно :)
16 апреля 2009
Занятие 16 апреля: разминка
Вопрос 1
В каком порядке будут напечатаны строки после выполнения этого кода?
1. В некотором порядке, одинаковом для любого экземпляра hs
2. В порядке, зависящем от конкретного экземпляра hs
3. В порядке добавления
4. В лексикографическом порядке
В каком порядке будут напечатаны строки после выполнения этого кода?
// HashSet -- это множество, реализованное хеш-таблицей
void test(HashSet hs) {hs.clear();for (int i=0; i<=100; i++) {
// Строковое представление числа
hs.add(String.valueOf(i));
}
// Проходим по множествуfor (Iterator i = hs.iterator(); i.hasNext();) {System.out.println(i.next());}}
1. В некотором порядке, одинаковом для любого экземпляра hs
2. В порядке, зависящем от конкретного экземпляра hs
3. В порядке добавления
4. В лексикографическом порядке
07 апреля 2009
Дни Санкт-Техника
Не знаю, все ли в курсе про Sun Tech Days и найдёт ли кто-нибудь там что-нибудь полезное для себя, но таки объявлю: они начинаются завтра.
Графы: алгоритмы
Итак, обещанные алгоритмы на графе. Минимальный джентльменский набор -- обход в ширину, обход в глубину, топологическая сортировка. Но они завёрнуты в более-менее взрослые интерфейсы: итераторы и (псевдо-)визиторы.
Итератор (Iterator), если кто не знает, это такой интерфейс, который позволяет в каком-то порядке перебрать некоторое множество элементов. Обычно у него есть методы, позволяющие получить текущий элемент и узнать, есть ли ещё непройденные элементы. Что это за множество и что это за порядок -- зависит от реализации итератора. В нашем случае множеством будет множество всех вершин графа, а порядок будет разным. В одном случае это будет порядок обходав ширину, а в другом -- порядок топологической сортировки.
Визитор (Visitor) в классическом виде -- это сложныйи практически неприменимый шаблон проектирования. У нас будет профанация визитора, представляющая собой в общем-то тот же итератор, но с вывернутой наизнанку последовательностью управления. Если при переборе итератором команды "стой! шаг вперёд! руки за голову" отдаются клиентом, а итератор их послушно исполняет, то в случае визитора всё наоборот: клиент инициирует итерирование и передаёт алгоритму объект-визитор. Итерирование идет само, без участия клиента, а при переходе к очередному элементу алгоритм вызывает методы визитора: "эй, ты, у меня тут следующий клиент -- хочешь с ним что-нибудь сделать?". Такой "визитор" называют иногда callback'ом, что на русский переводится корявой фразой "функция обратного вызова".
Архив с интерфейсами графа и алгоритмов на прежнем месте: http://barashev.net/src/graph.zip
Итератор (Iterator), если кто не знает, это такой интерфейс, который позволяет в каком-то порядке перебрать некоторое множество элементов. Обычно у него есть методы, позволяющие получить текущий элемент и узнать, есть ли ещё непройденные элементы. Что это за множество и что это за порядок -- зависит от реализации итератора. В нашем случае множеством будет множество всех вершин графа, а порядок будет разным. В одном случае это будет порядок обходав ширину, а в другом -- порядок топологической сортировки.
Визитор (Visitor) в классическом виде -- это сложный
Архив с интерфейсами графа и алгоритмов на прежнем месте: http://barashev.net/src/graph.zip
02 апреля 2009
Занятие 2 апреля: разминка
Вопрос 1.
Что делает метод hasCycle(), при условии что длина списка равна N?
Какая структура данных больше подходит для реализации обхода в ширину?
Что делает метод hasCycle(), при условии что длина списка равна N?
01: class Node {
02: Node next;
03: Object value;
04: }
05:
06: class List {
07: Node first;
08:
09: boolean hasCycle() {
10: if (first == null) return false;
11:
12: int stepCount = 1;
13: Node t1 = first;
14: Node t2 = first;
15:
16: while (true) {
17: t1 = t2;
18: stepCount *= 2;
19: for (int i = 0; i < stepCount; i++) {
20: t2 = t2.next;
21: if (t2 == null) return false;
22: if (t2 == t1) return true;
23: }
24: }
25: }
26: }
- Проверяет наличие цикла за время O(log(N))
- Проверяет наличие цикла за время O(N)
- Проверяет наличие цикла за время O(N*log(N))
- Проверяет наличие цикла за время O(N^2)
- Иногда тупо зависает в бесконечном цикле
Какая структура данных больше подходит для реализации обхода в ширину?
- FIFO
- LIFO
- GIGO
01 апреля 2009
Написание программ на родном языке является реальностью.
Вы когда-нибудь мечтали написания программ на вашем родном языке, без обучения Java, C + + и все другие вещи? Теперь вы можете. Просто введите программы на русском, китайском или любом другом человеческом языке, а также опубликовать его в Интернете. Вам даже не придется беспокоиться о правильности написания. Поиск кода Google будет автоматически переводить ваш код Английский для тех, кто не говорят Ваш родной язык.
Проверьте перевод на примерах http://google.com/codesearch и FUNNAH!
Проверьте перевод на примерах http://google.com/codesearch и FUNNAH!
Подписаться на:
Сообщения (Atom)