Follow along with the video below to see how to install our site as a web app on your home screen.
Примечание: This feature may not be available in some browsers.
Тут интересно было бы найти максимальное количество знаков в таком числе, ежели таковое существует. Писать программу для тупого перебора чуть более полутысячи чисел смысла мало.
И что получилось для пятизначного? Тут еще вроде надо учесть, что левые цифры в не могут быть нулями, хотя это можно и вручную отбросить.void FindSolutions(unsigned int n, char* szSol, unsigned int iPos = 0, int diff = 0, unsigned int k = 1)
{
if (n == iPos)
{
if (!diff)
{
szSol[n] = 0;
OutputDebugF("*** %s\n" << szSol);
}
}
else
{
unsigned int fact = 1;
for (unsigned int dig = 0; dig < 10; )
{
szSol[n - iPos - 1] = dig + '0';
FindSolutions(n, szSol, iPos + 1, diff + dig * k - fact, k * 10);
fact *= ++dig;
}
}
}
И что получилось для пятизначного? Тут еще вроде надо учесть, что левые цифры в не могут быть нулями, хотя это можно и вручную отбросить.
О, значит я правильно в уме прикинул, что кроме пятизначного больше ничего интересного нет.40585
Ничего принципиально не изменится. Перебор как был NP, так и останется.Кстати, я тут подумал, что перебор можно сильно сократить если перебирать всевозможные наборы из различных пятерок чисел - брать сумму их факториалов и смотреть состоит ли получившееся число из того же набора цифр.
Перебор сильно сокращается, т.к. допустим (1, 2, 3, 4, 5) это то же что и (5, 4, 3, 2, 1) или ( 2, 3, 1, 4, 5) и т.д. То есть достаточно проверить лишь один раз такой набор.
Осюда еще одна задачка: сколько таких различных наборов из 5 цифр? Из N цифр?
Кстати, я тут подумал, что перебор можно сильно сократить если перебирать всевозможные наборы из различных пятерок чисел - брать сумму их факториалов и смотреть состоит ли получившееся число из того же набора цифр.
Перебор сильно сокращается, т.к. допустим (1, 2, 3, 4, 5) это то же что и (5, 4, 3, 2, 1) или ( 2, 3, 1, 4, 5) и т.д. То есть достаточно проверить лишь один раз такой набор.
Осюда еще одна задачка: сколько таких различных наборов из 5 цифр? Из N цифр?
Эээ, есть большая разница между 10^k и k^9, а сортировка это вообще семечки по сравнению с остальным - домножаем лишь на k log k.Ничего принципиально не изменится. Перебор как был NP, так и останется.
В обоих случаях экспонента.Эээ, есть большая разница между 10^k и k^9, а сортировка это вообще семечки по сравнению с остальным - домножаем лишь на k log k.
Тем более и сортировать не надо - у нас всего десять цифр - bucket sort рулит. Так что прямой выигрыш начиная с трехзначных чисел.
Та ты шо? Со степенной не путаем?В обоих случаях экспонента.
Я имею в виду, что количество шагов, требуемое для решения перебором, не полиномиально по отношению к величине исходных данных. Насколько именно не полиномиально не имеет значения, потому что всегда можно будет взять такое количество исходных данных, перебор которых займет годы.Та ты шо? Со степенной не путаем?
А по твоему x^9, что если не полином?не полиномиально по отношению к величине исходных данных
Твоя правда, торможу.А по твоему x^9, что если не полином?
Ну @valdo же дал решение о количестве вариантов - C(9+k, 9). Там еще надо поделить на 9!, но то константа, которая, впрочем, легко перекрывает все издержки на работу с десятичными цифрами.Твоя правда, торможу.
А как ты получил x^9?
Точно торможу.Ну @valdo же дал решение о количестве вариантов - C(9+k, 9). Там еще надо поделить на 9!, но то константа, которая, впрочем, легко перекрывает все издержки на работу с десятичными цифрами.