gifts2017

Проект Эйлер в 1С

Опубликовал Валерий (scientes) в раздел Программирование - Практика программирования

Платформа 1С:Предприятие, как инструмент для решения нестандартных вычислительных задач.

Во все времена были люди, которые увлекались  математикой. Для небольшой части  математика являлась средством к существованию, для оставшегося большинства - зарядкой для ума, формой досуга. Если мы вспомним относительно недавнее прошлое, а именно докомпьютерную эру, то увидим, что на протяжении веков  математические игры разума обходились только бумагой и карандашом. При этом, рассматриваемые задачи не требовали сложных, многостраничных расчетов. Разумеется, такие вычисления производились, но этим занимались профессионалы. После того, как вычислительные мощности значительно подешевели, ситуация изменилась. Класс задач, который требовал многократных вычислений или перебора  огромного количества вариантов, стал доступен массовому пользователю и среди них оказались те, кому это было интересно. Так, в частности, возник Проект Эйлер (здесь можно найти его русскую версию). Проект - это набор задач, которые можно решить,как правило, только с применением вычислительной техники. При этом, метод прямого перебора требует такого количества времени, что делает его использование бессмысленным. Поэтому участникам необходимо знание разнообразных методов и алгоритмов, которые относятся к соответствующему разделу математики. Как показывает практика, большинство задач требует применения длинной математики, поскольку результаты расчетов выходят за ограничения, которые присутствуют в вычислительных системах с побайтным хранением целых чисел. Если обратиться к статистике того какие языки программирования используют  участники проекта, то обнаружится, что на первом месте  по количеству пользователей идет Python, совсем немного отстает C/C++, на третьей позиции находится Java.  1С в этом списке не значится. Между тем платформа позволяет эффективно решать самые разнообразные задачи, которые представлены на сайте проекта. Во первых, в 1С уже реализована длинная математика для операций сложения и умножения. Поэтому, например, задача 20, в которой надо найти сумму цифр в числе 100! решается элементарно.  Впрочем, ограничения на длину чисел в 1С есть. Запустите у себя на машине следующий код и посмотрите что получится.

        н=10;разрядов=2;
	пока ИСТИНА цикл
		разрядов=разрядов+1;
		н=н*10;
		если СтрДлина(Формат(н,"ЧГ=0"))<>разрядов тогда
			сообщить("Предел "+разрядов);
			прервать;
		конецесли;	
	конеццикла;	

Смею полагать, что данной точности достаточно для большинства задач, которые предлагаются к решению  (но ,например, для Задачи 25 этой точности, увы, не достаточно). Во вторых, скорость исполнения при выборе правильного метода, позволяет во многих случаях уложиться в одну минуту. О том насколько важен выбор алгоритма говорит пример 66 задачи. В ней предлагается найти такой коэффициент D<=1000  для квадратного Диофантового уравнения, чтобы соответствующее ему решение х было максимальным. Максимальное решение в этом случае будет 16 421 658 242 965 910 275 055 840 472 270 471 049. Разумеется, никаким перебором до этого значения не дойти.  

Поделюсь несколькими наблюдениями. Если говорить об объектах языка, то как показал мой опыт, самым используемым оказался массив и один раз я обращался к Таблице значений. Когда участник проекта успешно решил задачу, то он может оставить к ней комментарий, в частности разместить свой вариант решения.  Задача № 9 относится к простым, что подтверждает количество решивших (168213). Заглянув в комментарии, я обнаружил одно решение на ассемблере, решения в которых просто перебирались все числа из диапазона от 1 до 1000, и одно решение без программирования. Это был участник из Италии, он использовал представление для троек Пифагора и его решение уложилось в 8 строк. Молодец !  

Проект Эйлер существует уже 13 лет. За это время список задач вырос до 476. Надеюсь, что когда-нибудь они все будут решены на платформе 1С:Предприятие.




См. также

Подписаться Добавить вознаграждение

Комментарии

1. Павел И. (3.14159) 18.08.14 15:08
Надеюсь, что когда-нибудь они все будут решены на платформе 1С:Предприятие


- доктор! я буду жить?
- а смысл?
2. Валерий (scientes) 18.08.14 15:14
Смысл - популяризация платформы, изменение скептического отношения части IT сообщества к разработчикам на языке 1С.
wunderland; DrAku1a; Makushimo; gubanoff; kostyaomsk; davealone; +6 Ответить 1
3. Константин Юрин (kostyaomsk) 19.08.14 09:04
Хороший проект. Где можно посмотреть методы решения вычислительных задач на 1С 8.
Интересует технология решения СЛАУ (систем линейных алгебраических уравнений) в запросе 1С 8 для расчета себестоимости по РАУЗ.
4. Антон Рощин (wolfsoft) 20.08.14 08:40
(2) scientes, во-первых, это не изменит "скептического отношения части IT" (дурака учить - только портить), во-вторых, каждый инструмент предназначен для своих задач (микроскопом можно забивать гвозди, но не нужно), в-третьих, не вижу никакого практического смысла в решении абстрактных задач (когда коту нечего делать, он... ну, дальше вы знаете).
5. Илья Фамилия (m191) 20.08.14 09:59
А я думаю, что данная статья это популизация "научного" программирования среди кодеров 1С :).
Думаю не секрет, что большинство из них не имеют специального образования и для некоторых не знакомы такие слова как рекурсия, декомпозиция и т.п.

6. Валерий (scientes) 20.08.14 10:30
(4) wolfsoft, Разумеется, платформа 1С:Предприятие создавалась для своей предметной области. Тем удивительнее тот факт, что разработчикам удалось, в том числе, создать чрезвычайно удобный инструмент для решения таких абстрактных задач, как Проект Эйлер. Игра в шахматы лишена какого-либо практического смысла, это вопрос личных интересов. Спортивным программирование увлекаются единицы и это нормально. На мой взгляд,решить пару расчетных задач никому не повредит, а только повысит самооценку и расширит кругозор.
monkbest; help1Ckr; +2 Ответить
7. ффф ыыы (zqzq) 21.08.14 09:00
Между тем платформа позволяет эффективно решать самые разнообразные задачи
Такие заявления неплохо бы подтверждать замерами времени в cравнении, например, с C++ или Java. Эффективность встроенного интерпретируемого языка вызывает сомнения. Те замеры, что мне попадались, показывали отставание 1С где-то в 100 раз от С++.
8. Валерий (scientes) 21.08.14 09:41
(7) zqzq, Авторы задач утверждают, что при выборе правильного алгоритма, поиск решения будет занимать не больше минуты. Под эффективностью я понимаю скорость формирования и отладки кода и возможность уложиться в отведенную минуту. Кроме этого, реализованная в 1С длинная математика позволяет не тратить время на процедуры длинного сложения и умножения. Безусловно, скорость выполнения расчетов на С выше, есть участники проекта, которые кодируют на ассемблере, там скорость , возможно,еще выше. Уложился расчет в минуту или пару секунд, в данном случае не важно. Как показывает мой небольшой опыт, 1С успешно справляется с подобным классом задач.
9. VVV (V_V_V) 21.08.14 12:56
(5) m191, среди математиков тоже не все Эйлеры - и что теперь, это недонаука? :)
Не святые горшки лепят, кому сегодня не знакомы рекурсия, декомпозиция, завтра смогут не хуже ildarovich разгребать графы... :)
Понятно что 1С не для высоких математических материй, тем не менее совсем недавно никто не мог предположить, что из 1С можно будет позвонить, обработать почту, получить 3Д-модель, модифицировать мультимедиа-файлы и т.п. - а сейчас многое из перечисленного в категории банальных вещей.
Нормальная статья, спасибо автору.
vittany; wunderland; Sitex; +3 Ответить
10. г. Казань Рустем Гумеров (Rustig) 24.08.14 19:20
(0) можно создать свой проект Эйлера, связанный напрямую с предметной областью и платформой 1С.
Задачи будем брать из практики. Понимаете, о чем я пишу? Примеры:
а) все, что не реализовано в типовых, но порой приходится дорабатывать
б) все, что реализовано в типовых, но есть шанс улучшить
в) что-то новое - чего нет в типовых
только нужен движок (сайт), на котором можно было бы развивать этот проект
11. г. Казань Рустем Гумеров (Rustig) 24.08.14 19:30
есть ребята, создающие системы автопилотирования транспортных средств http://robocv.ru/products/
они говорят, что оснастить технику датчиками просто, а самое сложное - написать алгоритмы определения местоположения в пространстве. в общем, еще есть темы, в которых сложные алгоритмы будут играть ключевую роль ноу-хау
12. Oleg Solovyeff (Solovyeff) 24.08.14 20:10
Мисье знает толк) Можно хоть счеты использовать, но творческая составляющая исчезнет, для решения математики есть очень хорошие среды, и спец. языки. Мне например понравился Wolfram Language.
13. ффф ыыы (zqzq) 25.08.14 08:23
(12) Solovyeff, мне в студенческие годы Matlab очень понравился, практически "1С для математиков". Также 1С-у многому стоило бы у них поучиться (встроенная java как 2-й альтернативный язык, человеческий настраиваемый интерфейс, божественная встроенная справка с картинками и видео и введением для начинающих).
14. Антон Антонов (monkbest) 27.08.14 10:48
(4) wolfsoft, скептическое отношения не потому, что скептики дураки, а потому, что среди нашего брата полно сброда, окончившего 1С курсы по тыканью мышкой и побежавших зарабатывать деньги, назвав себя 1Сниками. Настоящие 1Сники - это все таки математики, прикладные математики, прикладные до мозга костей. Мы этим и отличаемся от С++ников, что в нашей работе прикладные знания имею больший вес, чем математика. Но как настоящим математикам нам должно быть интересно решать задачки подобные проекту Эйлер. А сообщить всему миру, что в среде 1С работают программисты, а не только бухгалтера - идея хорошая.
15. Антон Антонов (monkbest) 27.08.14 10:53
(13) zqzq, извиняюсь, я в институте тоже на матлабе решал задачки и там действительно хорошая справка, хоть я с инглиш и не дружил, все было понятно, но справка в 1С - это самая офигенная справка. До появления 8.2 кроме хелпа никакой литературы или гугла мне не требовалось, все ответы на вопросы быстро находил в синтаксис помощнике.
16. Александр Пузаков (puzakov) 29.08.14 02:33
Мне вот не очень понятны попытки скрестить 1С с математикой. Ну, допустим, свершилось: в 1С:Предприятии появились механизмы, позволяющие выполнять сложные математические вычисления. Для кого это? Даже если в многотысячной армии 1Сников и найдутся математики-практики, способные использовать эти механизмы в полный рост, то конечным пользователям это зачем?
17. Анастасия Гусельникова (An@st@si) 31.08.14 15:52
Как раз для того, чтобы меньше работать им "ЛЮБИМЫМ"...))))
Например, необходимо пропорционально от остатка рассчитать какую то сумму по данным, чтобы эта сумма не превышала базовую сумму, заданную в параметрах. Простой пример, два остатка 13000 и 14000, каждый месяц рассчитывается коэффициент, и по этому коэффициенту считаем сумму удержаний. Самое главное необходимо, чтобы эта сумма не превышала базу для удержаний.
18. Анастасия Гусельникова (An@st@si) 31.08.14 16:10
Пример только для обоснования, к задачам не имеет отношения.
Смысл: для облегчения труда конечного пользователя.
19. Антон Антонов (monkbest) 02.09.14 21:32
(16) puzakov, Вы не правы потому, что не с той точки зрения смотрите на проблему. Периодически решать алгоритмические задачи надо всем программистам. Это тренировка для ума. И если программист 1С работает в среде 1С, зачем ему ставить другую среду разработки, если 1С под рукой.
Решение задач на проекте Эйлер - вообще не имеет практического выхода для пользователей. Но сказать, что это никому не нужно = никому не нужно высшее образование IT. Всем нам нужно тренировать мозги.
В 1С есть все операторы структурного языка, это полноценный язык, на котором можно решить любую задачу. Пусть это не исполняемый код, пусть это скрипт, но никто и не гонится за сверхбыстрыми вычислениями. Суть правильного решения задач - уйти от перебора в лоб, занимающего нереальное кол-во итераций, к оптимальному алгоритму. Что это выполнится за 30 секунд на С++, что 2 минуты на 1С, разницы нет. Главное не три часа/дня.
Люди не шарящие в программировании (составлении алгоритмов на любом языке, математиков по своей сути) это - недо1Сники, закончившие пару курсов по бухучету. Разработать оптимальный код они не способны, они по любому пустяку сначала лезут в гугл, и только в крайнем случае пишут свой код с нуля.
20. Анастасия Гусельникова (An@st@si) 03.09.14 02:38
Вы правы, но со стороны бухгалтера, стараюсь все применять в чем разобралась)
А мозг всегда полезно потренировать...) спасибо)
21. Михаил Гусев (Идальго) 22.12.14 00:50
(16) puzakov, вы правы, что 1С для сложных расчетов не особо эффективен. Это нормально. Для сложных расчетов следует использовать специальные математические библиотеки, и передавать туда лишь параметры для расчета и получая обратно в 1С-ку уже готовый результат.

Теперь про конечных пользователей. Пользователям нужны отчёты, аналитика, прогнозирование. Например, в задачах управления запасами и прогнозирования спроса может потребоваться целая гора вычислений различных вероятностей, трендов и т.д. и т.п., причём в различных разрезах учёта. Можно конечно пользоваться более простыми методами, не требующими много вычислений, но на практике такой подход зачастую далеко не самый оптимальный. Рынок требует более точных и сложных инструментов для анализа.
22. Михаил Гусев (Идальго) 22.12.14 01:00
(19) monkbest, да какже нету разницы то? Сами пишите - 30 секунд или 2 минуты. А если разница во времени получения результата пара дней?

По моему, разница в эффективности. Для той или иной задачи в зависимости от цели и возможностей следует подбирать оптимальное решение. Однако, я также как и вы считаю, что ум следует тренировать.
23. Антон Антонов (monkbest) 22.12.14 09:18
(22) Идальго, если разница в пару дней, то это уже заведомом неверное решение задачи. Почитайте, что такое проект Эйлера:
Каждая задача подчиняется "правилу одной минуты", которое гласит: несмотря на то, что на построение алгоритма решения могут уйти часы, эффективная реализация позволяет получить ответ на компьютере средней вычислительной мощности меньше, чем за одну минуту.

Поэтому я и пишу, что нет разницы. 1С напорядок уступает C++, но не настолько, чтобы минуту превратить в дни :)
Возможно, вы говорите о вычислительных задачах в целом, а не конкретно о проекте
24. Антон Антонов (monkbest) 22.12.14 10:26
Наверное автор ждал на проекте Эйлера потока подобных записей:)
Я в теме, старт дан!
25. Валерий (scientes) 22.12.14 12:59
(24) monkbest,
Приятно, что не я один продвигаю 1С, как платформу для решения математических задач на данном проекте.
26. Михаил Гусев (Идальго) 26.12.14 09:03
(23) monkbest, угу, я о вычислительных задачах вцелом.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа