Форум 'Этюды для программистов' на RSDN.RU

Каким требованиям удовлетворяет эта программа?

Mon, 15 Mar 2010 23:32:20 GMT

sleep(86400 * 3);
print "black $_, " x 2 foreach (qw!shirts pants boots socks!);
print 'black jacket, ' . '$' x 300;

Сабж

хорда

Thu, 11 Mar 2010 17:03:37 GMT

Разминка по геометрии и теорверу:

Рассмотрим круг, в который вписан правильный N-угольник.
Проведём хорду, соединяющую две точки окружности.
С какой вероятностью длина этой хорды будет больше стороны многоугольника?

Машина Минского

Tue, 02 Mar 2010 13:42:40 GMT

Привет.

Машина Минского aka регистровая машина aka машина со счётчиками -- модель абстрактной машины, позволяющая реализовать любой алгоритм. Типа машины Тьюринга, но другая. Автор -- Марвин Минский -- попытался сделать её немного ближе к реальным компьютерам Сильно ближе, конечно не получилось.

Регистровая машина имеет конечное количество регистров R1, .., Rn каждый из которых может содержать произвольно большое натуральное число. Машина выполняет программу, состоящую из конечного числа инструкций снабжённых метками S1, .., Sm.

Инструкции бывают трёх типов:

* Sk: Rl++; Si -- увеличить значение в регистре Rl на 1, перейти к команде с меткой Si

* Sk: Rl--; Si; Sj -- если в регистре Rl не 0, уменьшить его значение на 1 и перейти к команде с меткой Si, иначе перейти к команде с меткой Sj

* Sk: STOP -- конец работы

(с) более-менее по первому слайду лекции

В книжке "Вычисления и автоматы" Минский вводит эти машины немного иначе. Но приведённый мною вариант более лаконичен и удобен, а вычислительная равносильность очевидна.

Что с ними можно делать:

* Сделать 0 в выбранном регистре.

Si-1: ...
Si: Rl--; Si; Si+1
Si+1: ...

* Прибавить к одному регистру другой

Si-1: ...
Si: Rl--; Si+1; Si+2
Si+1: Rk++; Si
Si+2: ...

* Но при этом мы потеряли значение в Rl. Чтобы его сохранить, нужно уже три регистра.

Si-1: ...

// сначала очистим Rt
Si: Rt--; Si; Si+1

// Теперь прибавим Rl к Rk и к Rt
Si+1: Rl--; Si+2; Si+4
Si+2: Rk++; Si+3
Si+3: Rt++; Si+1
// Здесь Rl == 0

// Теперь прибавим к Rl Rt
Si+4: Rt--; Si+5; Si+6
Si+5: Rl++; Si+4

Si+6: ...

Ну и так далее.

Задачка: смоделировать на машине Минского машину Тьюринга. Т.е. описать алгоритм, позволяющий по заданной машине Тьюринга построить машину Минского, выполняющую ту же задачу.

Задачка №2: то же самое, но использовать не более трёх регистров.

Задачка №3: _говорят_, что Минский сумел упихать МТ в два регистра, "с некоторыми ограничениями". Что за ограничения мне не сказали, т.к. "слишком большая подсказка". Но намекнули, что дело в хитром кодировании. У меня на двух регистрах получается очень уж неполноценная МТ, и никакого хитрого кодирования в голову не пришло. Буду рад, если кто-то придумает.

Написать хак

Tue, 02 Mar 2010 10:46:13 GMT

тут

СЛУ запросом SQL

Fri, 26 Feb 2010 10:38:33 GMT

Возможно ли решить систему линейных уравнений запросом?
Дано:
— таблица А с тремя полями: номер строки, номер столбца, коэффициент
— таблица Б с двумя полями: номер строки, свободный член
— все значения заполнены
— система имеет единственное решение
Требуется:
вывести набор данных из двух столбцов: номер переменной, значение.
Текст запроса не должен зависеть от количества переменных. Без использования процедурных расширений SQL. Один запрос SELECT ...

Задать диофантовым уравнением множество не квадратов

Fri, 19 Feb 2010 11:25:12 GMT

Привет

Немного упрощая теорию для задачи.

Диофантовы уравнения это уравнения вида , где M это многочлен с целыми коэффициентами. Решения уравнения ищутся в натуральных числах (в логике натуральные числа по традиции начинаются с 0).

Например, уравнение решений не имеет. -1 подходит, но он не натуральный. тоже не имеет решений, т.к. корень из 2 не натуральный.

Будем рассматривать диофантовы уравнения с одним параметром , где a это параметр -- целое число.

Например, . При некоторых значениях a это уравнение имеет решения, при некоторых нет. Т.е. можно сказать, что уравнение задаёт множество таких а, при которых оно имеет решение. Множества, которые можно задать таким образом называются диофантовыми.

Например,
задаёт множество всех квадратов.
задаёт множество всех составных чисел.
задаёт множество всех НЕ степеней двойки.

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

Собственно задачка: как таким образом задать множество натуральных чисел, не являющихся квадратами? Это не очень сложно.

Задачка была дана Юрием Владимировичем Матиясевичем на первой лекции курса http://logic.pdmi.ras.ru/~infclub/?q=courses/hilbertstenthproblem

[ANN] Сайт-задачник Ruby Quiz

Fri, 19 Feb 2010 09:03:51 GMT

Я недавно искал какой-нибудь ранее неизвестный мне задачник для изучения F# и набрёл на Ruby Quiz. Этот сайт показался мне интересным тем, что задачки из него не математические, а скорее инженерные, ближе к практике. Ну и, несмотря на название, решать их, конечно, можно на любом языке

PS: Конечно, это не очень настоящий [ANN], потому что сайту уже несколько лет. Но раньше я его не видел и поиском на RSDN не нашел.

... << RSDN@Home 1.2.0 alpha 4 rev. 1419>>

"солёная" расшифровка

Mon, 15 Feb 2010 09:36:36 GMT

Есть аппаратный "пульсирующий" бит. О характере пульсаций можно сказать только следующее: для некоторого интервала времени t гарантируется что число пульсаций будет в интервале [A(t), B(t)]. Можно ли как-нибудь связать этот "пульсатор" с расшифровкой данных ? Предполагается что злоумышленник ничего не знает о характере пульсаций и замерять их не может. Однако алгоритм расшифровки, ключ и зашифрованные данные ему доступны.

15.02.10 12:44: Ветка выделена из темы "солёная" расшифровка — Кодт

Навеяно LensLock-like защитами...

Mon, 15 Feb 2010 09:30:40 GMT

Есть терминал (40 кнопок). Легальный пользователь запускает работу нажатием кнопки. Кнопка запуска назначается случайным образом и отображается пользователю в виде подсказки (а-ля "Press 'S' key to start". Нелегальный пользователь не может увидеть подсказку, но нажимать на клавиши может. Каким образом можно затруднить нелегальному пользователю возможность случайного запуска ? Например нелегальный пользователь может всё время давить одну и ту же кнопку и рано или поздно она будет назначена стартовой. На ум приходят только варианты отслеживать частоту нажатий и уменьшать вероятность выбора часто нажимаемой кнопки. Есть ли идеи получше ?

Вероятность пройти тест

Wed, 10 Feb 2010 10:36:46 GMT

Простенькая задачка на теорвер, который я не знал, еще и забыл.

Есть тест, каждый вопрос которого предполгает единственный правильный ответ из, скажем, трех. Нужно доказать, что вероятность случайно ответить правильно на 10 вопросов из 30 больше, чем на 10 из 20. И что вообще — чем больше вопросов при фиксированной планке прохождения теста, тем легче его сдать, выбрав случайные ответы.

ЕГЭ (Тестовые задания по информатике)

Sun, 07 Feb 2010 21:57:35 GMT

http://habrahabr.ru/blogs/study/83388/

я лучше не буду комментировать это

Лампочка в бесконечной не замкнутой цепи

Sat, 06 Feb 2010 02:21:06 GMT

Случайно увидел исходный вопрос здесь и стало интересно, а взлетит ли?
Здесь хочу немножко перефразировать:

Есть источник питания с любым на выбор напряжением/ёмкостью/сопротивлением переменного/постоянного тока, к которому подключён провод с тоже на выбор любым сопротивлением/ёмкостью длиной, к примеру, 1 световой год/минуту/секунду или просто длиной L (на выбор, значения не имеет). К проводу подключена лампочка (с любыми на выбор характеристиками, также как и сам провод) и к лампочки провод того же типа, но уже бесконечной длины. На вход подают однополярное напряжение N на время T.

Вопрос:
Загорится ли лапочка при подаче напряжения, какого напряжения (постоянного или переменного, отрицательного или положительного), если загорится то потом погаснет, если погаснет, то раньше/позже чем через время Т с момента загорания лампочки, почему? Если напряжения N (гипотетически) не достаточно для загорания, то какое будет достаточно?

Чемпионат по программированию - Финал

Fri, 05 Feb 2010 04:20:49 GMT

В Харбине в данный момент бьются молодые программисты со всего мира.

Читаем вводную: http://cm.baylor.edu

Болеем он-лайн: http://cm.baylor.edu/scoreboard/index.html (Я за Samara State Aerospace University)

Решаем сами: https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/2010WorldFinalProblemSet.pdf

Автопилот

Thu, 04 Feb 2010 17:39:15 GMT

Захотелось мне сделать автопилот для модели вертолёта.
Детали физической реализации мы опустим они не интересны.
Попытался построить хотя бы приближённую физическую модель, и чего-то не смог
Умные книги уже читаю. Но во первых они старые и сильно заточены под возможности 60х годов.
А во-вторых, скажем прямо, не всё могу понять из этих книг.
Давайте рассмотрим абстрактный одномерный случай (с реальными ограничениями),
чтобы понять как такие задачи вообще решаются.

Условие

[-]------------------[0]------------------[+]
                     Az=0                 Aext
                     Vz=0                 Vext
                     Sz=0                 Sext

Имеется некий объект, который может перемещаться в одномерном пространстве.
Он должен оставаться в нейтральном положении, при котором:
Az=0 — ускорение нейтральной точки должно быть равно 0
Vz=0 — скорость нейтральной точки должно быть равно 0
Sz=0 — расстояние от нейтральной точки должно быть равно 0

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

Характеристики двигателя:
Amax — максимальное ускорение, которое может развивать двигатель
dAmax — максимально возможное изменение ускорения в единицу времени.
Т.к. двигатель инертный, он не может мгновенно развивать необходимое ускорение. Точно так же не может мгновенно останавливаться.

Aeng — ускорение (тяга) развиваемая двигателем в текущий момент. Не забываем что оно не может быть больше Amax.
И не может изменяться быстрее чем dAmax.

Через некоторое неопределённое время мы обнаруживаем что наш объект под действием внешних
сил имеет:

Aext — ускорение от внешних сил
Vext — набрал скорость под действием внешних сил
Sext — ушёл на какое-то расстояние от нейтральной точки

Считаем что с момента измерения Aext — константа.
T — расчётное время для возвращения объекта в нейтральное положение. (необходимо найти)

Задача 1
Получить функцию изменения Aeng, для того чтобы вернуть объект в нейтральное положение
(т.е. Az=0,Vz=0,Sz=0) за минимальное время T.

Задача 2
Мы не можем менять значение Aeng чаще чем Tstep. (Двигатели на моделях управляются ШИМ сигналом, и этот сигнал имеет чёткий период)
Это сравнительно маленькая величина, но пренебречь ей нельзя.
Т.е. из непрерывной функции Aeng получить кусочно линейную функцию за минимальное время T.

Может получится что кусочно линейной функцией сводить к нейтральной точке, когда все 3 параметра (Az=0,Vz=0,Sz=0)
можно очень долго, поэтому введём такое ограничение:
Az<=Azmax
Vz<=Vzmax
Sz<=Vzmax

Задача 3
Убираем ограничение, что Aext — константа.
Построить итеративный алгоритм, который на основе измерений, получаемых с периодом Tstep за минимальное время T вернёт
объект в нейтральное положение.

Заполнить массив

Wed, 03 Feb 2010 11:27:12 GMT

Всем привет!

Вот такую задачку получил недавно на собеседовании:
Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].

Заполнить массив числами [0, 99] в случайном порядке так, чтобы числа не повторялись.

Мое решение:
Заполнить массив числами в порядке возрастания: a[i] = i, 0 <= i <= 99.
В цикле на 50 повторений сгенерировать два случайных индекса и поменять значения по этим индексам местами.
Уникальность и случайность есть, работает.

Но экзаменатор ( ) утверждал, что можно сделать это за один проход. То есть каким-то образом сделать так, чтобы сразу получить последовательность уникальных чисел, при том, что rand в общем случае таких чисел не генерирует.
Как это можно сделать?

И еще одна вдогонку

Sun, 31 Jan 2010 03:03:39 GMT

Найти самое большое число такое, что любые первые k цифр этого числа образуют число, делящееся на k. Т.е., например, 1236543 обладает таким свойством, т.к. 1 делится на 1, 12 делится на 2, 123 делится на 3, ..., 1236543 делится на 7. Сколько всего таких чисел?

P.S. Не советую перебирать все числа подряд в поиске ответа -- не дождусь... Проявите фантазию, это ведь Этюд для программиста...

Хитрые квадраты

Sun, 31 Jan 2010 02:27:50 GMT

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

Marble game

Thu, 28 Jan 2010 13:17:29 GMT

Кто-нибудь пробовал решить такую задачку
Интересует не программный код ессесно, а сам метод (алгоритм) решения.

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

Затем из первоначального состояния брать другой шарик и делать то же самое.
Но как мне кажется это не совсем рацианальный метод решения.
Господа, математики, может что подскажете.

28.01.10 19:44: Перенесено модератором из 'Алгоритмы' — Кодт

Бытовой вопрос

Tue, 26 Jan 2010 05:05:26 GMT

Вопрос из области автоматизации технологических процессов, в которой я работаю программистом.
Допустим, вы принимаете душ. Включили горячую и холодную воду, отрегулировали нужный вам напор и температуру, залезли под душ и моетесь, напевая при этом арию герцога из оперы Риголетто. И тут ваш сосед, к которому вода поступает по тому же водопроводу, включает у себя холодную воду.
Как вы думаете, изменится ли при этом температура воды, текущей из вашего душа, если:
a) труба холодной воды соседа врезана в общую трубу холодной воды раньше, чем у вас;
б) труба холодной воды соседа врезана в общую трубу холодной воды позже, чем у вас.
Если хотя бы в одном случае температура изменится (что неприятно), как бы вы модифицировали систему подачи воды, чтобы минимизировать этот эффект?

Поиск места для книги

Mon, 25 Jan 2010 18:52:49 GMT

Встретился на работе с подобной задачкой:

Есть у нас книги, которые относятся к какой-то предметной области, у них есть автор и название.
Есть места, куда мы их кладем. Они имеют опциональные свойства: предметная область, автор, название.
Опциональные, потому что есть места, где к примеру лежит любая фантастика, а есть — где лежат книги на тему программирования авторства Рихтера, и все имеют название "CLR via C#".
Надо найти для недавно принесенной книги место, причем чем больше место соответствует свойствам книги (область, автор, название) — тем оно релевантнее.
Если места в наиболее оптимальном месте нет — проверяем другое, менее оптимальное.

Надо придумать алгоритм поиска места по релевантности

ЗЫ: На работе я подобную задачу уже решил, интересно что придумаете вы, ну и позже свое решение опубликую, если подобного не будет.