Задачи, головоломки, загадки

Тут интересно было бы найти максимальное количество знаков в таком числе, ежели таковое существует. Писать программу для тупого перебора чуть более полутысячи чисел смысла мало.
 
Тут интересно было бы найти максимальное количество знаков в таком числе, ежели таковое существует. Писать программу для тупого перебора чуть более полутысячи чисел смысла мало.
Ну так может стОит найти более интеллигентный алгоритм чем тупо перебор.

А насчёт максимального кол-ва знаков: можно дать верхнюю оценку. Известно что a,b,c,d,... - цифры, т.е. не больше 9.

9! = 362,888

Так что верхняя граница (необязательно достижимая) - 7 знаков.
 
Перебором задача решается легко (на компьютере). Интересно, есть ли достаточно короткий способ решения задачи без перебора?

Для трёх знаков - есть относительно короткое решение. Для пяти - лично я не нашёл, там надо отдельно рассматривать (и перебирать) варианты где есть 1 восьмёрка, 2 восьмёрки, или 2,3,4 семёрки, а также варианты где первая цифра 0, и т.п. Долго и запутано.
 
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;
}
}
}
 
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;
}
}
}
И что получилось для пятизначного? Тут еще вроде надо учесть, что левые цифры в не могут быть нулями, хотя это можно и вручную отбросить.
 
И что получилось для пятизначного? Тут еще вроде надо учесть, что левые цифры в не могут быть нулями, хотя это можно и вручную отбросить.
На самом деле это не было оговорено в условии. Разумеется если левая цифра не может быть 0, то нет смысла проверять более 7 знаков (т.к. 9! - шестизначное число).

Вот то перебор до 9 знаков:

1 digits: 1, 2
2 digits:
3 digits: 145
4 digits:
5 digits: 00125, 40585, 01466
6 digits: 000034, 081368
7 digits: 0372970, 0041068
8 digits: 00372971, 00372972, 00000013
9 digits: 000001566

Так что если отбросить всё что начинается на 0, то остаётся: 1, 2, 145, 40585
 
Кстати, я тут подумал, что перебор можно сильно сократить если перебирать всевозможные наборы из различных пятерок чисел - брать сумму их факториалов и смотреть состоит ли получившееся число из того же набора цифр.
Перебор сильно сокращается, т.к. допустим (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 цифр?
Ничего принципиально не изменится. Перебор как был NP, так и останется.
Что же касается количества таких наборов, то тут все решено до нас: C(n+k-1,k)
Для комбинации длиной k получается: C(10+k-1,k)
 
Кстати, я тут подумал, что перебор можно сильно сократить если перебирать всевозможные наборы из различных пятерок чисел - брать сумму их факториалов и смотреть состоит ли получившееся число из того же набора цифр.
Перебор сильно сокращается, т.к. допустим (1, 2, 3, 4, 5) это то же что и (5, 4, 3, 2, 1) или ( 2, 3, 1, 4, 5) и т.д. То есть достаточно проверить лишь один раз такой набор.
Осюда еще одна задачка: сколько таких различных наборов из 5 цифр? Из N цифр?
В этом случае усложняется проверка того состоит ли число из данного набора цифр. Скажем, надо разложить число на цифры (что для машины работающей в бинарной арифметике не так уж и просто, для этого надо делить на 10), цифры отсортировать, и затем проверить. Поскольку мы говорим о малок кол-ве цифр - ИМХО это того не стОит.
 
Ничего принципиально не изменится. Перебор как был NP, так и останется.
Эээ, есть большая разница между 10^k и k^9, а сортировка это вообще семечки по сравнению с остальным - домножаем лишь на k log k.

Тем более и сортировать не надо - у нас всего десять цифр - bucket sort рулит. Так что прямой выигрыш начиная с трехзначных чисел.
 
Последнее редактирование:
Эээ, есть большая разница между 10^k и k^9, а сортировка это вообще семечки по сравнению с остальным - домножаем лишь на k log k.

Тем более и сортировать не надо - у нас всего десять цифр - bucket sort рулит. Так что прямой выигрыш начиная с трехзначных чисел.
В обоих случаях экспонента.
 
Та ты шо? Со степенной не путаем?
Я имею в виду, что количество шагов, требуемое для решения перебором, не полиномиально по отношению к величине исходных данных. Насколько именно не полиномиально не имеет значения, потому что всегда можно будет взять такое количество исходных данных, перебор которых займет годы.
 
Твоя правда, торможу.
А как ты получил x^9?
Ну @valdo же дал решение о количестве вариантов - C(9+k, 9). Там еще надо поделить на 9!, но то константа, которая, впрочем, легко перекрывает все издержки на работу с десятичными цифрами.
 
Ну @valdo же дал решение о количестве вариантов - C(9+k, 9). Там еще надо поделить на 9!, но то константа, которая, впрочем, легко перекрывает все издержки на работу с десятичными цифрами.
Точно торможу.
C(9+k, 9) дал я сам, но не втыкаю как из этого получается k^9