Расширяем свой багаж

29.01.19

Разработка - Математика и алгоритмы

Алгоритм решения возможной нетиповой задачи на собеседовании.

Разумеется, значительно легче отвечать на вопрос, если ты заранее знаешь ответ. В этом и кроется причина популярности сервисов, которые предлагают список возможных тестов и задач.   Не знаю, встречалась ли такая задача на собеседовании, но расширить свой багаж не будет лишним. Необходимо найти выражение для суммы квадратов N первых положительных целых чисел, используя Excel. Формула эта давно известна, но вряд ли большинство людей держат ее в памяти. Выводится она с помощью следующего равенства:

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

 В задании надо эту формулу подобрать. Итак, открываем Excel, строим следующую таблицу.

В первой колонке число, во второй его квадрат, в третьей идет сумма квадратов. В колонке Первая разность хранится разность соседних ячеек из колонки Сумма. Это квадраты числа из первой колонки, так оно и должно быть, это очевидно.  В колонке Вторая разность отображается разность соседних ячеек из колонки Первая разность. Это нечетные числа, и это говорит о том, что квадрат любого числа, есть сумма последовательных нечетных чисел. Теперь несложно догадаться, что находится в колонке Третья разность.  Тот факт, что все значения в этой колонке одинаковые, говорит нам о том, что зависимость выражения для суммы квадратов от верхнего предела N есть многочлен третьей степени. И это действительно так. 

В общем случае в формуле должен присутствовать свободный член, но так как при N=0 сумма равна нулю, то он отсутствует. Первое следствие из данной формулы - сумма делится на число N. Проверяем по нашей таблице и убеждаемся, что это не так. Ошибка в формуле ? Нет, формула верна. Все дело в том, что наше первоначальное предположение справедливо, если только все числа A,B и C целые. А это, по-видимому, не так. Верным будет следующее утверждение - сумма умноженная на целое число делится на N. И это число находится простым перебором, оно равно 6.

Ну и заключительный шаг. Разложим число из колонки 6*Сумма/N на два множителя. Первые числа небольшие и сделать это нетрудно.

Уже после первых трех строк становится понятна итоговая зависимость.

Ну и ответ на вопрос "Какое это имеет отношение к 1С ?". Дело в том, что периодически я сталкиваюсь с ситуацией, когда на собеседовании задают вопросы, которые предполагают не кодирование в "лоб", ибо это приведет к тому, что время выполнения задачи станет неразумно большим, а применение, зачастую, элементарного математического аппарата, что позволяет достигнуть значительного ускорения.  Согласитесь, что цикл от единицы до миллиарда для нахождения суммы квадратов будет выполняться очень долго. 

Excel тестовое задание

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8835    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7801    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. wowik 885 29.01.19 15:04 Сейчас в теме
это где такое задают? чтобы не попасть туда случаем)
creatermc; le_; lunjio; acanta; +4 Ответить
3. Sapiens_bru 4 29.01.19 17:24 Сейчас в теме
(1)Собеседование процесс взаимный. На нём можно и нужно испытывать работодателя. Я на следующем планирую задать вопросы типа "Кем вы меня видите через 5 лет в вашей компании?" и "Почему вы пригласили именно меня?"
Batman; creatermc; Olenevod; nyam-nyam; Natain14; Andreeei; +6 Ответить
9. A_Max 19 31.01.19 13:34 Сейчас в теме
(3) На самом деле второй вопрос очень даже правильный. ТОлько я его обычно задаю в виде "опишите какие проблемы у вас есть, а я расскажу чем огу помочь в их решении".
7. TODD22 18 30.01.19 11:41 Сейчас в теме
(1)там где 1сники не нужны.
2. acanta 29.01.19 15:17 Сейчас в теме
Представьте себе зелененький он был сохраняет коллега файл в екселе без формул, только значения и отправляет вам по почте.
Вам предлагается на основании данных определить зависимости, написать формулы и проверить арифметику файла, а после этого такой же файл, но уже с формулами отправить другому коллеге, к которому так же поступил первоначальный вариант.
Задают такое обычно там, где с таким работают каждый день.
4. nyam-nyam 30.01.19 09:20 Сейчас в теме
Сколько потребовалось времени чтобы додуматься сравнивать первые, вторые и третьи разницы? Почему не произведения или корни сумм? На алгоритм не тянет, максимум пример решения, увы.
5. scientes 288 30.01.19 10:46 Сейчас в теме
(4) Контроль разностей - это стандартный метод проверки наличия полиномиальной зависимости.
6. nyam-nyam 30.01.19 11:24 Сейчас в теме
(5)Ок. Но кто сказал что она будет полиномиальной? А потом, сначала мы складываем квадраты, потом их же вычитаем - и получаем первую разность равной колонке N*N. А уже потом начинаем искать зависимость (N+1)*(N+1) и N*N. А будь А,B или C ирациональным? Или получили бы вместо 6 что-нибудь типа 5 млн - сколько времени на перебор ушло бы Excel? Как по мне, то в виде формул задача решается куда логичнее. :)
8. Bеgemoth 31.01.19 12:38 Сейчас в теме
Получить сумму квадратов - это оказывается нетиповая задача... дожили..

(0) если запомнить вот такую мысль:

"Если формулу последовательности A(n) можно представить в виде выражения B(n) - B(n-1), тогда S(A)[N1..N2] = B(N2) - B(N1-1), где S(A)[N1..N2] - сумма элементов A(n), для n=N1..N2"

тогда на собеседованиях можно будет найти формулу суммы квадатов, кубов, да и вообще любых полиномиальных последовательностей, всё будет упираться только в количество отведенного на решение задачи времени.
KapasMordorov; lefthander; +2 Ответить
10. scientes 288 31.01.19 15:08 Сейчас в теме
(8) Спрашивать на собеседовании о сумме квадратов, с моей точки зрения, неправильно. Подавляющее большинство соискателей на это не ответит, что не умаляет их достоинств, как разработчиков.


"Специалист подобен флюсу полнота его одностороння" (Козьма Прутков)

11. acanta 31.01.19 15:15 Сейчас в теме
(10)
Подавляющее большинство соискателей на это не ответит, что не умаляет их достоинств, как разработчиков.

Подавляющему большинству работодателей не требуется подавляющее большинство разработчиков.
12. scientes 288 31.01.19 15:18 Сейчас в теме
(11) С этим не поспоришь.
13. Bеgemoth 01.02.19 07:20 Сейчас в теме
(10)
Подавляющее большинство соискателей на это не ответит, что не умаляет их достоинств, как разработчиков.


Поспорю. Я не работодатель, с этой стороны никогда не был, но регулярно участвую в совместных разработках. И если для предполагаемого участника проекта задача о сумме квадратов(или подобная) покажется нетиповой, то, либо этот участник не будет участвовать в проекте (если я могу влиять на состав проекта), либо я сам откажусь от участия. Это проверено почти парой десятилетий опыта. Каким бы крутым разработчиком такой человек не казался со стороны, но лучше сразу показать ему на дверь, а иначе загребёшься потом разгребать килотонны его альтернативной логики, которой он пытался решить подобные "нетиповые" задачи.
plat-nik; +1 Ответить
14. plat-nik 01.02.19 18:27 Сейчас в теме
(13)
иначе загребёшься потом разгребать килотонны его альтернативной логики, которой он пытался решить подобные "нетиповые" задачи.

Поддерживаю, решение такой крутой специалист найдет, но сделает это отнюдь не локанично, что обеспечит потом "взрыв мозга" и потерю времени, которое могло быть реализовано на других задачах.
15. lvictor58 135 02.02.19 20:47 Сейчас в теме
Это явно чел адресом ошибся. Здесь не кружок юных математиков!
Оставьте свое сообщение