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

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

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

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

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

О том, как я «ломал» 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? Зря!

Лекции из MIT

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

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

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

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

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

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

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

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

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

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

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

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

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

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