Задачки по программированию

Поиск в массиве пузырьковым методом же

Доказательство равенства или неравенства P и NP.

взботай BFS и DFS + алгоритм крускала. Попробуй что либо из них реализовать.

Ну и хватить. Больше ботать смысла не имеет.

Что-нибудь примитивное вроде реверса строки без использования дополнительной памяти.

Поиск

пузырьковым методом

наркоман штоле?

Бред какой-то.

А че не так? Проходишь по массиву столько раз, пока не найдешь нужное значение.

Если с первого раза не нашел - то ищешь пока не найдешь.

Когда меня первый раз попросили придумать алгоритм сортировки я и то что-то побыстрее придумал. Так что нафиг этот пузИрёк.

петросян тогда, штоле?)

Почему же норкоман? Делаем сериализацию данных, у полученных данных берём некий хеш в 128 бит где-то, у образца берём хеш; затем сортируем данные по хешу пузырьковой сортировкой и ищем хеш образца бинарным поиском. Всё быстро и надёжно.

Так что нафиг этот пузИрёк

Он ещё не так и плох. Вот самый аутсайдер: http://en.wikipedia.org/wiki/Bogosort

твой вброс некорректен. алгоритм поиска у тебя все-таки бинарный :)

Обычно, при нужном уровне мат.подготовки (а реалии таковы, что достаточно удовлетворительных знаний вузовского курса) никаких доп.знаний не нужно.

ну это смотря в каком направлении будет будущая работа. вполне возможно тебе скажут написать небольшой прототип клиент-серверного приложения. или какую-то фигню вроде построителя сложных запросов к БД.

Классику.

Обращение односвязного списка.

Поиск колец в списке.

Без выделения памяти обратить порядок слов в строке.

Написать реализацию strrchr(), atoi(), или ещё чего-то подобного.

Считать 2 числа, вывести их сумму. Если это решишь, то можешь даже не париться.

Зависит от фантазии твоих собеседников.

Определить, принадлежит ли точка (необязательно выпуклому) многоугольнику.

Посмотри mail.ru code cup. Так есть в архивах пара интересных задачек.

Да всё что угодно может быть. Если что-то алгоритмическое, то читай Шень «Программирование теоремы и задачи»

Сомневаюсь - там будет 3 задачки и врядли на все дадут больше пары часов.

напиши функцию, которая может принимать на вход два числа: 2 или 3. (корректность ввода проверять не нужно).

Если на вход пришла 2-ка, то вернуть тройку. Если пришла 3-ка, то вернуть 2-ку.

Написал? Теперь напиши вариант без if-ов. Написал? Еще два варианта.

еще такое может быть:

* in-place удалить дублирующиеся подряд символы в строке.

* поменять значения двух int-овых переменных местами.

* напечатать значение переменной в hex-виде (без библиотечных вызовов).

* определить какой элемент последовательности не имеет пары. (остальные все имеют).

* определить место цикла в односвязном списке, если мало памяти

* восстановить дерево, если дан его inorder и postorder обход.

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

да, хороший вопрос.

http://informatics.mccme.ru/

Но это не то. Вот один товарищ решал задачки на собеседовании:

1. Разница между "строка" и u"строка".
2. Результат работы 0.3 - 0.2 - 0.1 < 0 (фэйл).
3. Какой тип нужно использовать при работе с деньгами.
4. Сложность алгоритма for i in range(n): if i in lst: pass (фэйл, пойду Кнута все-же доосилю).
5. Есть файл с логами посещаемости. 1 запись в логе - 1 просмотр. 15 млн уникальных посетителей в день. Лог за 3 года. Получить количество уникальных пользователей за заданный промежуток времени.

Это пистон что ли? Нафиг такое собеседование! Еще оценивают сложность алгоритма для пистона!

Задачи для олимпиад по программированию. Например такая:

Охотник кружит возле поляны напичканой зайцами. Не учитывая сопротивление воздуха и зайцев пуле найти максимальное количество зайцев, которое можно убить одним выстрелом.

А что не так в питоне?

Скорость не его конек?

Да не очень он и тормозит.

Ты должен мне новый парсер. Что в задаче найти надо?

количество зайцев, которое можно убить одним выстрелом

Тока на олимпиаде задание было на англицком :)

А их количество и прочие параметры брать из libastral? Или ответ - все в кого попадёт? :)

Естественно входные данные - количество и набор координатов зайцев. (пробелы и новые строки - разделители). Ты бы сначала задачу решил, а потом уж интересовался.

Сначала сделай что-нибудь, а потом это что-нибудь подгони под ТЗ? Или считается, что задачу чисто математически решить сложно?

Ты решил?

Стандартная ситуация (не только для олимпиад): входной файл содержит количество элементов и атрибуты (набор, разделённых пробелами литералов), разделённые новыми строками. Что ещё надо-то?

Подскажу: я задачу про зайцев решал ч/з уравнения прямой.

Скорость не его конек?

Это всего лишь константа в оценке при n*m.

А что там решать? Есть круг, есть хорда, есть области в круге, найди какие области пересекаются с хордой. Задачка для _в_каком_там_классе_геометрия_начинается_ класса.

Т.е. существует ФОРМУЛА?

Или таки задачу нужно решать?

Есть круг, есть хорда, есть области в круге, найди какие области пересекаются с хордой.

Астрономы будут тебя на руках носить.

Т.е. для тебя элементарными задачами считаются только те, которые на одну формулу?

Есть круг x2+y2=r2, есть прямая y=kx+b, которая пересекается с кругом (хотя можно и это проверить), есть набор точек, которые по условию находятся внутри круга. Подставляем координаты в уравнение прямой и смотрим какие подходят, для них проверяем принадлежность кругу (хотя это итак должно выполняться). Это если решать в лоб и без оптимизации.

Ещё раз спрашиваю - что тут решать?

Хм. Из 30 команд тока наша (читай я) её решила. Ты не забыл, что нужно искать максимум?

Всё дело в том что ты нифига не умеешь формулировать условия.

Это не я. Олимпидное задание ~2005г. ТРТУ. Тока там на английском было.

Ну так и замечательно, возможных хорд становится сразу меньше, получаем вполне себе дискретный поиск, сожрёт конечно время, но ответ найдётся. Либо, если точек не слишком много (а здесь судя по всему именно так), то для всех пар ищем прямые, а потом проверяем на какой из них точек больше всего.

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

Как же не ты, когда ты.

В любых вменяемых олимпиадах чётко поставлено условие (или дополнительно оговаривается то, что частью задачи будет формализация), задан формат входных и выходных данных.

Ты же несёшь полный бред, который к олимпиадной задачке не может относиться ни при каких обстоятельствах.

Подскажу: я задачу про зайцев решал ч/з уравнения прямой.

Вот это и вовсе победа.

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

Жжош. Что тебе непонятно в условии из двух предложений?

Охотник кружит возле поляны напичканой зайцами. Не учитывая сопротивление воздуха и зайцев пуле найти максимальное количество зайцев, которое можно убить одним выстрелом.

Ничего. Это тебе понятно, потому что ты нормальное условие читал.

Что есть заяц? Материальная точка, или он имеет размеры? Что есть выстрел? Видимо прямая и видимо стреляет охотник из-за пределов круга, но это надо уточнить. Пуля ведь тоже материальная точка? Что есть поляна, какой она формы и как задана? Не понятно какие вообще параметры задаются (это из тебя уже потом вытащили). По сути каждое существительное требует уточнения.

Вот скажи честно, в каком классе учишься? В условии понятно, что не хватает данных. Ведь принцип решения будет совершенно разным, если у нас зайцев >100 или over9000, если зайца можно только ранить, но не убить, если заяц есть точка с координатами (x,y) или область (ещё вопрос как она задаётся).

s/>/</