*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

четверг, 29 июля 2010 г.

Блог о Великобритании глазами программиста

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

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

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

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

понедельник, 19 июля 2010 г.

О том, как я «ломал» RSA

Решал я как-то очередную задачу:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5). Найдите такой его делитель (само число n и единица считаются делителями числа n), который лучше любого другого делителя числа n.


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

Я все сделал, и решение прошло.

Далее была вторая задача:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5000). Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.


По сути, такая же задача, что и предыдущая – просто нужно в паре мест поменять «больше» на «меньше» и наоборот. Я поменял, и на небольших тестах решение прошло.

Но тут я замечаю, что в это задаче верхнее ограничение на n какое-то очень большое. Я заменяют тип «int» на класс «длинной» арифметики (5000 тысяч знаков – пустяк, было и более) и пробую: на малых тестах работает, значит, алгоритм верный.

Посылаю решение, и конечно, получаю ответ «Time limit exceeded». После небольшого раздумья становится ясно, что слишком много надо считать, и подход в целом неправильный.

Пишу письмо Leonid’у с просьбой прояснить ситуацию.

Приходит ответ типа, что моя попытка, ища все делители громадного числа, взломать RSA брутборсом конечно похвальная, но исполнена жиденько, да и врядли она вообще под силу современным компьютерам. К тому я же ищу все делители, а не только простые, а их будет еще больше.

В итоге выяснилось, что данная задача решается не только без «длинной» арифметики, но даже и без короткой, одним циклом в пару строк. Просто надо понять, что за тип чисел просят найти.

Нулевые ссылки в С++

Началось с того, что мне предложили взглянуть некий на "интересный" код. Там было что-то вроде:

...
class A { virtual void f() {} };
class B {};

int main() {
  A a;
  try {
    B& b = dynamic_cast<B&>(a);
    if (&b == 0) {
      // ...
    }
  } catch (...) {
    std::cout << "Got it!" << std::endl;
  }
  return 0;
}

Я слегка выпал в осадок от уведенного, а в частности, от строки "if (&b == 0) {". До сего времени я пребывал в осознании факта, что ссылка в С++ либо существует и указывает на реальный объект, либо ее нет вообще. И если тут приведение типа к "B&" не срабатывает, то будет исключение, и управление все равно улетит в другое место, и проверять как-либо "b" бессмысленно.

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

Ну да ладно. Оставим это на откуп странным компиляторам на AIX и SUN, и людям, использующим исключения, но почему-то компилирующие с принудительным их выключением в компиляторе.

Меня заинтересовал другой вопрос: как вообще ссылка может существовать отдельно от объекта. Оказывается, может:

int& a = *(int*)0;
int main() { a = 123; }

Данный код прекрасно компилируется Студией (2010) и компилятором SUN (этот хоть предупреждение выдает), и также прекрасно падается при запуске по понятой причине.

Вы получили ссылку в качестве параметра и думаете, что она лучше чем указатель, так как ее не надо проверять на null? Зря!

пятница, 9 июля 2010 г.

Лекции из MIT

На сайте MITа лежит множество лекций из различных разделов науки. Например, раздел Computer science.

В частности, курс Introduction to Algorithms.

Все сделано максимально удобно: в добавок к видео (некоторые идут сразу с субтитрами) еще есть и транскрипт каждой лекции.

Я еще рекомендую заценить примеры экзаменационных задач.

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

четверг, 1 июля 2010 г.

Неконстантные ссылки в аргументах функций

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

Например, вместо:

void f(T& t) {
  // change ‘t’
}
...
T a;
f(a);

я предпочту передачу по указателю:

void f(T* t) {
  // change ‘*t’
}
...
T a;
f(&a);

Мой основной мотив – наглядность в вызывающем коде. Когда я вижу «&» перед аргументом, я точно знаю, что это возвращаемый параметр, и он может измениться после вызова. И мне не надо постоянно помнить, какие именно агрументы у этой функции ссылки, а какие нет.

Конечно тут есть и минусы: корявость текста в вызываемом коде, так как надо таскать за собой «*» или «->». Также неплохо бы проверять указатель на ноль.

А у вас есть предпочтения в этом вопросе?