Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
Хаб: .NET
Как так то??
Готов выложить листинги программы и саму программу (написана на Delphi), если это возможно.
Как так то??
Задача уже была на хабре, habrahabr.ru/post/256023, от 17 апреля 2015
Неужели задача такая сложная чтобы про неё писать по 2 раза в месяц?
Неужели задача такая сложная чтобы про неё писать по 2 раза в месяц?
Как видно из той статьи — предложенное решение было неверно.
Там есть
Те, думаю этого достаточно для одной задачи
UPD2: Для полноты приведу взятый из этой статьи ответ. Исходные числа — 13 и 4. Ответ единственен.
P.S. Идите в статью, там еще и сорцы есть.
Те, думаю этого достаточно для одной задачи
Все написанные до сих пор варианты решения задачи были не полные и не до конца корректные. Хотя погрешность такая малая, что она не влияет на окончательный результат для чисел меньше 100. Но она может оказать значительный эффект для больших чисел и в любом случае дает не правильные граничные точки для новых решений. Моя же программа учитывает все нюансы и дает точный результат для любых больших чисел. Мы же хотим узнать точные значения граничных точек, а не приблизительные.
В англо-язычной литературе я нашел решение этой задачи (правда там в условиях сумма чисел меньше заданного, а не каждое число меньше, как у нас) рассчитанное для больших чисел. Так вот мои решения совпадают полностью (проверял до числа 10000).
В англо-язычной литературе я нашел решение этой задачи (правда там в условиях сумма чисел меньше заданного, а не каждое число меньше, как у нас) рассчитанное для больших чисел. Так вот мои решения совпадают полностью (проверял до числа 10000).
Моя же программа учитывает все нюансы и дает точный результат для любых больших чисел
не будьте в себе так уверены! Мантисса у вас бесконечная? Почитайте любую книжку по численным методам(того же Вержбицкого) и вы узнаете, что ваше «точное» решение является не таким уж и точным. То, что программу вы до 10 тыс. проверили это не говорит о том, что она на 40 тыс. не отвалится ;) Ограничение памяти, ограничение языковое…
ЗЫ Старайтесь уходить от острых моментов)
Решения данной задачи уже были на гиктаймсе, правда в комментариях к статье про др Шерил: моё и товарища omikad.
Лично я считаю, что задача действительно простовата для отдельной статьи. А мне вот интересен факт, имеется ли максимальное решение у данной задачи? И если есть/нет, то как доказать?
И еще интересно, как вы умудрились написать код на делфи, который решает задачу для Max=2000 за 29 секунд? Самый тупой брутфорс на C# у меня решил задачу за 30 сек для Max=5000 (на i5 4590). Время для 2000 — 2,5с.
Лично я считаю, что задача действительно простовата для отдельной статьи. А мне вот интересен факт, имеется ли максимальное решение у данной задачи? И если есть/нет, то как доказать?
И еще интересно, как вы умудрились написать код на делфи, который решает задачу для Max=2000 за 29 секунд? Самый тупой брутфорс на C# у меня решил задачу за 30 сек для Max=5000 (на i5 4590). Время для 2000 — 2,5с.
Нужно еще больше статей про эту задачу!
Вот тут решения на разных языках habrahabr.ru/post/256293
«Готовой компьютерной программы, позволяющей решать такие задачи при любом заданном максимальном числе, обнаружить не удалось.»
Из статьи не понятно, что за ограничения других программ не позволяют решать эту задачу при любом заданном максимальном числе. Вот возьми, например, любое решение из приведенной мной ссылки и объясни, чем плохо решение.
Вот тут решения на разных языках habrahabr.ru/post/256293
«Готовой компьютерной программы, позволяющей решать такие задачи при любом заданном максимальном числе, обнаружить не удалось.»
Из статьи не понятно, что за ограничения других программ не позволяют решать эту задачу при любом заданном максимальном числе. Вот возьми, например, любое решение из приведенной мной ссылки и объясни, чем плохо решение.
Решение для Max=5000 делается за 52 сек. Правда у меня компьютер старенький (i3 2.93Ghz). Вот скриншот программы:
Предыдущий результат для Max=2000 (за 29 сек) — это поиск граничных решений в заданном диапазоне с стартовым шагом 100. Т.е программа сканирует для разных Max, пока не найдет точное граничное значение (методом половинного деления). Мне вот интересно сравнить ваше решение с моим:
1. Результат для Max=5000 дает те же 10 пар чисел?
2. Какой у вас результат для Max=866 и для Max=867?
Программа, конечно не оптимизирована, и наверняка ее можно дооптимизировать. Особенно мне кажется слабым местом использование динамических массивов и увеличение длины массива на единицу, каждый раз когда нужно.
Заголовок спойлера
Предыдущий результат для Max=2000 (за 29 сек) — это поиск граничных решений в заданном диапазоне с стартовым шагом 100. Т.е программа сканирует для разных Max, пока не найдет точное граничное значение (методом половинного деления). Мне вот интересно сравнить ваше решение с моим:
1. Результат для Max=5000 дает те же 10 пар чисел?
2. Какой у вас результат для Max=866 и для Max=867?
Программа, конечно не оптимизирована, и наверняка ее можно дооптимизировать. Особенно мне кажется слабым местом использование динамических массивов и увеличение длины массива на единицу, каждый раз когда нужно.
У меня изначально не было цели написать решение для диапазона в 5000 чисел. Программа быстро решала для 100 и этого было достаточно. Чтобы решить для 5000 пришлось запросы немного переделать. Но опять же, цели написать оптимальное решение нет. Цель — написать код в несколько строк :)
Результаты:
Max=5000 (~19,1 сек)
4 13, 4 61, 4 229, 16 73, 16 111, 32 131, 32 311, 64 73, 64 309, 67 82
Max=2000 (~2,2 сек)
4 13, 4 61, 16 73, 32 131
Max=866
4 13, 4 61
Max=867
4 13, 4 61
Решение на C#
using System;
using System.Collections.Generic; // for HashSet
using System.Diagnostics;
using System.Linq;
class Program
{
static void Main()
{
var birthDays = Enumerable.Range(2, 4999)
.Join(
Enumerable.Range(2, 4999), n => 1, n => 1,
(n1, n2) => new {D = n1*n2, M = n1 + n2, N1 = n1, N2 = n2})
.Where(d => d.N2 >= d.N1).ToList();
var x1 = birthDays.GroupBy(d => d.D).Where(g => g.Count() == 1).SelectMany(g => g).ToList();
var monthWithUniqueDays = new HashSet<int>(x1.Select(d => d.M));
var x2 = birthDays.Where(d => !monthWithUniqueDays.Contains(d.M)).ToList();
var x3 = x2.GroupBy(d => d.D).Where(g => g.Count() == 1).SelectMany(g => g).ToList();
var solve = x3.GroupBy(d => d.M).Where(g => g.Count() == 1).SelectMany(g => g).ToList();
Console.WriteLine(string.Join(", ", solve.Select(d => d.N1 + " " + d.N2)));
}
}
Результаты:
Max=5000 (~19,1 сек)
4 13, 4 61, 4 229, 16 73, 16 111, 32 131, 32 311, 64 73, 64 309, 67 82
Max=2000 (~2,2 сек)
4 13, 4 61, 16 73, 32 131
Max=866
4 13, 4 61
Max=867
4 13, 4 61
Поразительная по краткости программа! На Delphi такое не написать.
Результаты по парам совпадают. Вот граничное значение не совпало. У меня при Max=866 одна пара, а при Max=867 уже две пары решений. Может быть проверишь еще для 865? Или каким-то способом определи при каком максимальном Max только одно решение имеет задача. Интересно разобраться — может я где-то вместо строго-меньше поставил меньше-равно или еще какая опечатка.
Для ясности — когда я считаю для Max=N, то имею ввиду, что числа строго-меньше этого N.
Результаты по парам совпадают. Вот граничное значение не совпало. У меня при Max=866 одна пара, а при Max=867 уже две пары решений. Может быть проверишь еще для 865? Или каким-то способом определи при каком максимальном Max только одно решение имеет задача. Интересно разобраться — может я где-то вместо строго-меньше поставил меньше-равно или еще какая опечатка.
Для ясности — когда я считаю для Max=N, то имею ввиду, что числа строго-меньше этого N.
Вот картинка:
Заголовок спойлера
«Готовой компьютерной программы..." — я имею ввиду готовое приложения, которое может запустить любой пользователь (не владеющий навыками программирования и не имеющий никаких компиляторов). При этом можно вводить интересующее максимальное число и получать наглядный результат с комментариями.
Немного оптимизировал программу и теперь расчет для Max=5000 длится 8 сек.
У меня просьба к тем у кого есть подобные программы. Могли бы вы отписаться о результатах теста? Это чтобы удостовериться, что и у вас и у меня программы оттестированные и дают одинаковый результат. В качестве теста предлагаю посчитать для следующих условий:
— Числа меньше заданного Max;
— Числа могут быть одинаковые;
Сколько решений для:
1. Для Max = 5000 (и желательно какое время вычислений);
2. Для Max= 866 и для Max=867.
У меня просьба к тем у кого есть подобные программы. Могли бы вы отписаться о результатах теста? Это чтобы удостовериться, что и у вас и у меня программы оттестированные и дают одинаковый результат. В качестве теста предлагаю посчитать для следующих условий:
— Числа меньше заданного Max;
— Числа могут быть одинаковые;
Сколько решений для:
1. Для Max = 5000 (и желательно какое время вычислений);
2. Для Max= 866 и для Max=867.
Вот вам покоя не было от этой задачи.
У меня с предыдущего подхода код на JavaScript оставался. Так и пришлось тоже доделать.
Полным перебором решается. Через консоль что-то тормозит (полминуты примерно), а на странице секунды за 3 считает.
Можно ещё тут попробовать.
У меня с предыдущего подхода код на JavaScript оставался. Так и пришлось тоже доделать.
Код
<document html><head>
<script>
var MAX=5000;
var P, W, i, j, k, A, B;
var M=[], Z=[];
for (i=0; i<(MAX*MAX); i++) M[i]=0;
for (i=2; i<MAX; i++) for (j=i; j<MAX; j++) { P=i*j; M[P]++; }
for (W=4,k=0; W<(2*MAX-2); W++) {
P=0;
for (j=2; j<=W/2; j++) if (M[j*(W-j)] === 1) { P=1; break; }
if (P===0) { Z[k]=W; k++; }
}
/*Здесь k - количество уникальных сумм*/
for(i=0; i<(MAX*MAX); i++) M[i]=0;
/*Массив количеств возможных произведений*/
for(i=0; i<k; i++) for(j=2; j<=Z[i]/2; j++) M[(Z[i]-j)*j]++;
/*Вывод списка*/
for(i=0; i<k; i++) {
W=0;
for(j=2; j <= Z[i]/2; j++) if (M[(Z[i]-j)*j] === 1) {
W++; P=(Z[i]-j)*j; A=j; B=Z[i]-j;
}
if (W===1) {
document.write("A=",A,", B=",B,", Sum=",Z[i],", Mul=",P);
document.write("<br>");
//console.log("A="+A+", B="+B+", Sum="+Z[i]+", Mul="+P);
}
}
</script>
</head><body></body></html>
Полным перебором решается. Через консоль что-то тормозит (полминуты примерно), а на странице секунды за 3 считает.
Можно ещё тут попробовать.
Я эту задачу впервые увидел не на этом ресурсе и намного позже, чем она тут обсуждалась. Поэтому пропустил все ваши обсуждения. Начал гуглить решения и наткнулся на англо-язычную статью, где солидные профессора обсуждают на 30-ти стр. эту проблему, выдвигают какие-то гипотезы и строят теоремы, выводят таблицу граничных точек для Max=50000 и т.д. Все это для условия задачи, где сумма чисел не больше заданного Max. Мне стало интересно будет ли кардинально задача отличаться, если в условиях будет каждое число меньше Max и заодно узнать граничные точки для этих условий. Также мне было интересно поупражняться в алгоритмах и проверить себя. Результатом стала эта программа и на многие вопросы я получил ответы.
Когда я захотел поделиться результатами с сообществом, то решил сделать это на этом ресурсе, так как считаю его наиболее подходящим местом. Я прошу прощения, но это был мой первый пост здесь и я не очень знаком с здешними правилами. Неожиданно для себя я нахватал кучу негатива в виде " А кому это надо?". Действительно, никому оно не надо, пускай и дальше этим занимаются только иностранные ученые, им видимо заняться больше нечем.
И наконец вопрос программистам. Если бы, ученые поставили вам задачу, решить эту проблему для наиболее большого числа Max и за наиболее короткое время? Понятно, что эта задача не имеет практического смысла. Но в качестве упражнения по оптимизации алгоритмов?
Ведь в какой-то момент массив чисел размерностью Max*Max не поместится в память. Как можно поднять планку для Max для обычного персонального компьютера?
Запустил я на ночь прогу с Max=60000 — результат 27 пар чисел, время 2часа 28 мин. Интересно какой предел компьютера?
Когда я захотел поделиться результатами с сообществом, то решил сделать это на этом ресурсе, так как считаю его наиболее подходящим местом. Я прошу прощения, но это был мой первый пост здесь и я не очень знаком с здешними правилами. Неожиданно для себя я нахватал кучу негатива в виде " А кому это надо?". Действительно, никому оно не надо, пускай и дальше этим занимаются только иностранные ученые, им видимо заняться больше нечем.
И наконец вопрос программистам. Если бы, ученые поставили вам задачу, решить эту проблему для наиболее большого числа Max и за наиболее короткое время? Понятно, что эта задача не имеет практического смысла. Но в качестве упражнения по оптимизации алгоритмов?
Ведь в какой-то момент массив чисел размерностью Max*Max не поместится в память. Как можно поднять планку для Max для обычного персонального компьютера?
Запустил я на ночь прогу с Max=60000 — результат 27 пар чисел, время 2часа 28 мин. Интересно какой предел компьютера?
Добрый день. Для предела на сумму в 20 000 я получил следующие числа.
num a b sum mult
1 32 131 163 4192
2 4 181 185 724
3 4 61 65 244
4 8 239 247 1912
5 4 229 233 916
6 512 911 1423 466432
7 32 311 343 9952
8 4 13 17 52
9 16 111 127 1776
10 64 127 191 8128
11 256 13 269 3328
12 64 73 137 4672
13 16 163 179 2608
14 64 241 305 15424
15 8 419 427 3352
16 32 641 673 20512
17 32 701 733 22432
18 8 449 457 3592
19 512 71 583 36352
20 16 73 89 1168
21 512 101 613 51712
22 32 821 853 26272
Совпадают ли мои результаты с Вашими?
Нетрудно заметить, что пары образованы числами (2^n, простое число). Есть ли решения другого вида ?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о двух мудрецах. Компьютерная программа для решения