Можно ли посчитать количество цифр в документе, в котором содержатся результаты подсчёта?

Question

[Артём Н]

Недавно я придумал задачу, которую не могу решить. Мне интересно, есть ли у неё решение в виде универсального алгоритма.

Есть документ, который содержит случайные данные в виде букв и цифр. Необходимо дописать в конец данного документа таблицу или гистограмму использования цифр таким образом, чтобы она учитывала саму себя.

Например, исходный документ:
Варгхарбл 012

Документ с результатами:

Варгхарбл 012
+-----+------+
|Цифра|Кол-во|
+-----+------+
|  0  |  2   |
+-----+------+
|  1  |  7   |
+-----+------+
|  2  |  5   |
+-----+------+
|  3  |  1   |
+-----+------+
|  4  |  1   |
+-----+------+
|  5  |  2   |
+-----+------+
|  6  |  1   |
+-----+------+
|  7  |  2   |
+-----+------+
|  8  |  1   |
+-----+------+
|  9  |  1   |
+-----+------+

Answer 1

[Mrrl]

Я не уверен, можно ли решить эту задачу, если документ состоит из 97 девяток.
Ещё одна девятка будет в левом столбце таблицы. Какая-нибудь из цифр от 0 до 8 вряд ли встретится 9 раз. Так что девяток будет 98+ число девяток в последней клетке таблицы. Вот и получается:
Если в последней клетке 0 девяток, то в ней число 98+0=98
Если в ней одна девятка, то в ней 98+1=99
Если в ней две девятки, то в ней 98+2=100
Во всех случаях получаем противоречие.

UPD. Задача решается довольно просто.
Пусть у нас уже собрана статистика о числе разных цифр в теле документа (B[0] нулей, B[1] единиц...)
Сразу прибавим к этим числам по единичке, чтобы учесть левый столбик.
Оценим сверху число цифр в правой части таблицы. Например, как S=10*(log_10(B[0]+..+B[9])+2).
Каждая цифра в полном документе встретится не более B[n]+S раз, значит, в правой части таблицы для неё будет число, лежащее от D0[n]=B[n] до D1[n]=B[n]+S.
Прооптимизируем диапазоны D0..D1. Для этого для каждой цифры переберём все числа от D0[n] до D1[n], посмотрим количество разных цифр в каждом из этих чисел, возьмём минимальное и максимальное значение вхождений. Например, если D0[n]=997, D1[n]=1013, то в клетке, соответствующей n, 0,1 и 9 могут встретиться от 0 до 3 раз, а остальные цифры - 0 или 1 раз.
Просуммируем полученные диапазоны по всем n - получим новую таблицу диапазонов D0n,D1n. Пересечём их с D0,D1.
Есть 3 варианта.
Все полученные диапазоны совпали с D0..D1. Выходим из цикла.
Один из новых диапазонов пуст. В этой ветке решений нет, возвращаемся из функции.
Какой-то диапазон изменился. Продолжаем оптимизировать.

После того, как диапазоны стабилизировались, смотрим их длины. Если все они длины 1 (т.е. D0=D1), то мы нашли решение. Если нет - то берём самый короткий диапазон длины больше 1, перебираем все его значения D0[n]<=u<=D1[n], подставляем каждое из них в копию таблицы диапазонов (D0n[n]=D1[n]=u) и рекурсивно вызываем функцию оптимизации.
Перебор оказывается небольшим, вот примеры (ncall - число рекурсивных вызовов):

For 1 2 3 4 5 6 7 8 9 10
0->5 1->7 2->5 3->5 4->6 5->10 6->9 7->10 8->10 9->12
ncall=696

For 1 1 1 0 0 0 0 0 0 0
0->2 1->7 2->5 3->1 4->1 5->2 6->1 7->2 8->1 9->1
ncall=486

For 0 0 0 0 0 0 1 0 0 0
ncall=464

For 0 0 0 0 0 0 0 1 0 0
0->1 1->7 2->2 3->3 4->1 5->1 6->1 7->3 8->1 9->1
0->1 1->6 2->3 3->3 4->1 5->1 6->2 7->2 8->1 9->1
0->1 1->6 2->4 3->1 4->2 5->1 6->2 7->2 8->1 9->1
ncall=482

For 3997 19995 5677 998 799996 392 7 94 8998 99985
0->4014 1->20000 2->5679 3->1000 4->800001 5->394 6->10 7->96 8->9000 9->99994
0->4013 1->20001 2->5679 3->1001 4->800000 5->394 6->10 7->96 8->9000 9->99994
ncall=47356

Comments

[Артём Н]

Да, такое бывает. Но иногда задача может быть решена, как в примере (хотя там мало цифр). Интересно, решается ли она вообще.

[uvelichitel]

мне почему то кажется, что с пустым документом таблица не решаема...

[Артём Н]

uvelichitel: Таблица для пустого документа:

0 : 1
1 : 7
2 : 3
3 : 2
4 : 1
5 : 1
6 : 1
7 : 2
8 : 1
9 : 1

У меня есть подозрение, что задача решаема до тех пор, пока количество цифр не двузначно. Пока нет времени проверить эту догадку, к сожалению.

[pestilent]

Для документа из одной 6 уже нет решений.

Answer 2

[Spetros]

Можно ли посчитать количество цифр в документе, в котором содержатся результаты подсчёта?

Можно. Сама задача сбора статистики - довольно тривиальна.
Если речь о практической реализации, то, например, в msword возможно скриптами на VB такое сделать.

UPD Пять минут гугления и выясняем, что это было придумано до нас и называется "A self-referencing number problem"

Comments

[Артём Н]

Не совсем то. Цифры статистики должны учитываться в статистике.

[Spetros]

Это сделает дополнительный проход по таблице с первичными результатами.

[Артём Н]

При повторном подсчёте результаты изменятся, поэтому придётся пересчитывать снова, затем снова и т. д. до бесконечности (наверно). Я попробовал записывать округлённое мат. ожидание на место количества, но погрешность всё ещё присутствует.

[Spetros]

nobr: пишете либо цикл, либо рекурсию: на этапе когда значения подсчета перестают изменяться - выходите.

[uvelichitel]

Spetros Где вы черпаете уверенность в сходимости рекурсии?

[Spetros]

uvelichitel: А почему вы решили,что она никогда не сойдется?
Решение в таблице-примере выше - сошлось.