Problems

Val Petruchek

подписывайтесь, а то хуже будет!  

ПОДПИСЫВАЙТЕСЬ НА RSS

На чём учат?

09.02.09 @ 17:30 — Problems, Programming

У меня возник вопрос: а на каких языках программирования сейчас учат в школе решать задачи по информатике? Ну, и соответственно, на чём их разрешают решать на олимпиадах по информатике?

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

Пару лет назад слышал, что паскаль как бы вычеркнули. Интересно, это правда? Если правда, то очень грустная.

Нет, я не против C++, pascal как язык программирования у C++ сосёт.

Но вот учиться составлять алгоритмы и воплощать их на компьютере, не умея программировать, лучше на паскале. Потому что он проще. В C++ слишком много лишнего — не лишнего для программиста, но лишнего для умения составлять алгоритмы. Память, строки, указатели — это очень важно, но отвлекает от главного — составления алгоритмов.

В паскале всё проще: достаточно строго, чтобы не привыкнуть к basic-расхлябанности, но довольно просто, чтобы не утонуть в отладке и среде, как в C++.

Другое дело, что паскаль в реальной жизни малоприменим — сколько тех Delphi вакансий по сравнению c С++? Но переучиться с паскаля, умея составлять алгоритмы, не составит никакого труда.

Задачка на Apache Basic Authentication

Дано: урл вида http://www.zliy.pes/members/

На папке установлена Basic Authentication (.htaccess):

AuthType Basic
require valid-user

Надо: сделать урл вида http://www.zliy.pes/members/freeaccess/ доступным без авторизации.

Попытка #1 (неудачная): положить в /members/freeaccess/ .htaccess следующего содержания:

Allow from all

Попытка #2 (удачная): положить в /members/freeaccess/ .htaccess следующего содержания:

Allow from all
Satisfy any

Групповуха с двумя презервативами

14.03.07 @ 00:40 — Problems, Logics

Вспомнил такую логическую задачу:

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

Вопрос: как партнёрам обезопасить все четыре сексуальных акта? Сексом без презерватива партнёры заниматься не могут, т.к. болезни у всех разные и заразные.

Решение
: (more…)

Функция, возвращающая N случайных элементов из потока неизвестной длины

12.03.07 @ 07:00 — Problems, Programming

Усложняем задачу о выборе случайного элемента из потока неизвестной длины:

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

Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.

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

Функция должна использовать n+O(1) памяти (n — количество элементов, возвращаемых функцией).

У этих задач существует практическое применение: потоком неизвестной длины может служить файл, элементами потока — его части (строки в случае текстового файла). Данная задача заключается в выборе N случайных строк из файла за одно прохождение без хранения в памяти всех строк.

Решение: (more…)

Функция, возвращающая случайный элемент из потока неизвестной длины

24.02.07 @ 02:37 — Problems, Programming

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

Известно, что поток когда-нибудь кончается, но заранее про количество элементов ничего не известно.

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

Функция должна использовать фиксированное количество памяти (иными словами, O(1) памяти).

(via avva)

Решение: (more…)

  
Реклама::

 
Реклама::