Для программистов.
Набрел тут на задачки по программированию на сайте Interviewstreet, и уже два часа зависаю над одной из самых простых, за которую дают всего 25 очков.
Все просто. Счастливым числом назовем такое, у которого сумма цифр и сумма квадратов цифр будут простыми. Нужно посчитать количество счастливых цифр в некоем диапазоне. Решение пишется на коленке ну, скажем, минут за 20.
Запускаем… Программа падает на втором тесте из девяти — превышен лимит времени выполнения.
Смотрим условие. Тесты могут быть весьма объемистыми — до 10000 диапазонов в одном тесте и числа до 1018, нужна оптимизация. И сижу я уже почти два часа, пытаясь сделать эту элементарную, в общем-то, задачу.
Ок, максимальное число, которое будем проверять, простое оно или нет — 1458, можно по таблице. Сумму цифр и сумму квадратов цифр можно менять нехитрым инкрементальным алгоритмом. Но дальше-то оптимизировать уже совсем некуда! Числа в диапазоне все равно нужно перебирать циклом, как ни крутись…
Up: Сделал у себя нагрузочный тест. Первоначальный вариант выполняется 51 секунду, теперешний — 4.5 секунды.
а почему превышен лимит-то? тут же простая переборка с двумя условиями и двумя инками!?
Самому жутко интересно.
может ты список чисел хранишь, а не только их количество?
Нет, конечно
может код покажешь? там три строки должно быть же.
// run test for(c = b - 1; c >= a; c--) { k = &d[0]; while(true) { (*k)--; if(*k >= 0) { // sd--; // sum of digits is decremented by one sq -= tsq[*k]; // sum of squares is decremented by magic value // do not decrement other digits break; } else { // decrement next digit *k = 9; k++; // sd += 9; // sum of digits is incremented by 9 sq += 81; // sum of squares is incremented by 81 } } if(prime_grid[sd] && prime_grid[sq]) cnt++; }Массив d — это число по разрядам
честно говоря не могу определить что за си-образный язык, поэтому tsq[*k] не понял, видимо поэтому не очень понятно причём тут разряды, и зачем под них массив.
если я правильно всё расшифровал — ты надеешься, что он прям вот так вот массивами и будет проверять, а затем массивы будет сравнивать.
Я уже сто лет не порграммил серьёзно, поэтому судить не буду критично, но не легче ли линейным перебором сделать, чтобы — сейчас числодробилки работают быстрее, поэтому возможно, что сделать наглядно деление массива будет быстрее, чем командой . ну так — имхо.
Это С++.
Линейный перебор работает дольше, я проверял.
давно не брал я в руки шашек/шку!
ну хоть не подвисает. ;)
я думаю тут надо не перебором, а как минимум предсказывать размер чанки (у тебя цикл за базывым действием заткнётся).
Я прошёлся по задачам и там есть несколько странное «K Difference» на 50 очков, там задача на 15 строк без оптимизации с первого раза отработала все тесты :)
Спасибо за подборку, надо будет взять себе для кандидатов
Да, я уже дошёл до этой мысли вручную расписав первую сотню :) Полное решение пока руки не дошли оформить.
Подборка и правда, хорошая.
Я не безнадежно тупой :) K-Difference я сделал с третьей попытки