Я эту задачу впервые увидел не на этом ресурсе и намного позже, чем она тут обсуждалась. Поэтому пропустил все ваши обсуждения. Начал гуглить решения и наткнулся на англо-язычную статью, где солидные профессора обсуждают на 30-ти стр. эту проблему, выдвигают какие-то гипотезы и строят теоремы, выводят таблицу граничных точек для Max=50000 и т.д. Все это для условия задачи, где сумма чисел не больше заданного Max. Мне стало интересно будет ли кардинально задача отличаться, если в условиях будет каждое число меньше Max и заодно узнать граничные точки для этих условий. Также мне было интересно поупражняться в алгоритмах и проверить себя. Результатом стала эта программа и на многие вопросы я получил ответы.
Когда я захотел поделиться результатами с сообществом, то решил сделать это на этом ресурсе, так как считаю его наиболее подходящим местом. Я прошу прощения, но это был мой первый пост здесь и я не очень знаком с здешними правилами. Неожиданно для себя я нахватал кучу негатива в виде " А кому это надо?". Действительно, никому оно не надо, пускай и дальше этим занимаются только иностранные ученые, им видимо заняться больше нечем.
И наконец вопрос программистам. Если бы, ученые поставили вам задачу, решить эту проблему для наиболее большого числа Max и за наиболее короткое время? Понятно, что эта задача не имеет практического смысла. Но в качестве упражнения по оптимизации алгоритмов?
Ведь в какой-то момент массив чисел размерностью Max*Max не поместится в память. Как можно поднять планку для Max для обычного персонального компьютера?
Запустил я на ночь прогу с Max=60000 — результат 27 пар чисел, время 2часа 28 мин. Интересно какой предел компьютера?
Поразительная по краткости программа! На Delphi такое не написать.
Результаты по парам совпадают. Вот граничное значение не совпало. У меня при Max=866 одна пара, а при Max=867 уже две пары решений. Может быть проверишь еще для 865? Или каким-то способом определи при каком максимальном Max только одно решение имеет задача. Интересно разобраться — может я где-то вместо строго-меньше поставил меньше-равно или еще какая опечатка.
Для ясности — когда я считаю для Max=N, то имею ввиду, что числа строго-меньше этого N.
Немного оптимизировал программу и теперь расчет для Max=5000 длится 8 сек.
У меня просьба к тем у кого есть подобные программы. Могли бы вы отписаться о результатах теста? Это чтобы удостовериться, что и у вас и у меня программы оттестированные и дают одинаковый результат. В качестве теста предлагаю посчитать для следующих условий:
— Числа меньше заданного Max;
— Числа могут быть одинаковые;
Сколько решений для:
1. Для Max = 5000 (и желательно какое время вычислений);
2. Для Max= 866 и для Max=867.
«Готовой компьютерной программы..." — я имею ввиду готовое приложения, которое может запустить любой пользователь (не владеющий навыками программирования и не имеющий никаких компиляторов). При этом можно вводить интересующее максимальное число и получать наглядный результат с комментариями.
Решение для Max=5000 делается за 52 сек. Правда у меня компьютер старенький (i3 2.93Ghz). Вот скриншот программы:
Заголовок спойлера
Предыдущий результат для Max=2000 (за 29 сек) — это поиск граничных решений в заданном диапазоне с стартовым шагом 100. Т.е программа сканирует для разных Max, пока не найдет точное граничное значение (методом половинного деления). Мне вот интересно сравнить ваше решение с моим:
1. Результат для Max=5000 дает те же 10 пар чисел?
2. Какой у вас результат для Max=866 и для Max=867?
Программа, конечно не оптимизирована, и наверняка ее можно дооптимизировать. Особенно мне кажется слабым местом использование динамических массивов и увеличение длины массива на единицу, каждый раз когда нужно.
Все написанные до сих пор варианты решения задачи были не полные и не до конца корректные. Хотя погрешность такая малая, что она не влияет на окончательный результат для чисел меньше 100. Но она может оказать значительный эффект для больших чисел и в любом случае дает не правильные граничные точки для новых решений. Моя же программа учитывает все нюансы и дает точный результат для любых больших чисел. Мы же хотим узнать точные значения граничных точек, а не приблизительные.
В англо-язычной литературе я нашел решение этой задачи (правда там в условиях сумма чисел меньше заданного, а не каждое число меньше, как у нас) рассчитанное для больших чисел. Так вот мои решения совпадают полностью (проверял до числа 10000).
Когда я захотел поделиться результатами с сообществом, то решил сделать это на этом ресурсе, так как считаю его наиболее подходящим местом. Я прошу прощения, но это был мой первый пост здесь и я не очень знаком с здешними правилами. Неожиданно для себя я нахватал кучу негатива в виде " А кому это надо?". Действительно, никому оно не надо, пускай и дальше этим занимаются только иностранные ученые, им видимо заняться больше нечем.
И наконец вопрос программистам. Если бы, ученые поставили вам задачу, решить эту проблему для наиболее большого числа Max и за наиболее короткое время? Понятно, что эта задача не имеет практического смысла. Но в качестве упражнения по оптимизации алгоритмов?
Ведь в какой-то момент массив чисел размерностью Max*Max не поместится в память. Как можно поднять планку для Max для обычного персонального компьютера?
Запустил я на ночь прогу с Max=60000 — результат 27 пар чисел, время 2часа 28 мин. Интересно какой предел компьютера?
Результаты по парам совпадают. Вот граничное значение не совпало. У меня при Max=866 одна пара, а при Max=867 уже две пары решений. Может быть проверишь еще для 865? Или каким-то способом определи при каком максимальном Max только одно решение имеет задача. Интересно разобраться — может я где-то вместо строго-меньше поставил меньше-равно или еще какая опечатка.
Для ясности — когда я считаю для Max=N, то имею ввиду, что числа строго-меньше этого N.
У меня просьба к тем у кого есть подобные программы. Могли бы вы отписаться о результатах теста? Это чтобы удостовериться, что и у вас и у меня программы оттестированные и дают одинаковый результат. В качестве теста предлагаю посчитать для следующих условий:
— Числа меньше заданного Max;
— Числа могут быть одинаковые;
Сколько решений для:
1. Для Max = 5000 (и желательно какое время вычислений);
2. Для Max= 866 и для Max=867.
Предыдущий результат для Max=2000 (за 29 сек) — это поиск граничных решений в заданном диапазоне с стартовым шагом 100. Т.е программа сканирует для разных Max, пока не найдет точное граничное значение (методом половинного деления). Мне вот интересно сравнить ваше решение с моим:
1. Результат для Max=5000 дает те же 10 пар чисел?
2. Какой у вас результат для Max=866 и для Max=867?
Программа, конечно не оптимизирована, и наверняка ее можно дооптимизировать. Особенно мне кажется слабым местом использование динамических массивов и увеличение длины массива на единицу, каждый раз когда нужно.
В англо-язычной литературе я нашел решение этой задачи (правда там в условиях сумма чисел меньше заданного, а не каждое число меньше, как у нас) рассчитанное для больших чисел. Так вот мои решения совпадают полностью (проверял до числа 10000).