Если мы посмотрим, как работает алгоритм Look-and-Say, мы обнаружим, что каждый символ (или последовательность одинаковых символов) создает пару символов в выходных данных. Таким образом, если длина ввода составляет N символов, длина вывода составляет не более 2 N символов.
Давайте рассмотрим функцию, которая генерирует строку next в последовательности Look-and-Say:
#include <stdlib.h>
#include <string.h>
char *look_and_say(const char *src)
{
const size_t srclen = (src) ? strlen(src) : 0;
char *dst;
if (srclen < 1) {
/* Nothing to look or say. */
return NULL;
}
/* The result can be up to twice as long as the source,
plus the string-terminating nul char. */
dst = malloc(2*srclen + 1);
if (!dst) {
/* Not enough memory for the result. */
return NULL;
}
{
const char *const end = src + srclen;
char *pos = dst;
while (src < end) {
const char *const was = src;
/* Skip repeated source characters. */
do {
src++;
} while (src < end && *src == *was);
/* The longest allowed sequence is 9. */
if ((size_t)(src - was) > 9) {
free(dst);
return NULL;
}
*(pos++) = '0' + (size_t)(src - was);
*(pos++) = *was;
}
*pos = '\0';
return dst;
}
}
Выше неважно, что является входной строкой; Вы можете поставить что угодно. Если входная строка NULL или пуста, она вернет NULL. Если он не может выделить память (вдвое больше длины входной строки, плюс один символ для завершающего строку символа nul '\0'), он возвращает NULL. Если символ повторяется более 9 раз подряд, функция возвращает NULL.
Последовательность Look-and-Say - OEIS A005150 в Онлайн-энциклопедии целочисленных последовательностей, которая указывает на то, что RG Wilson v показал в 2004 году только цифры 1, 2, и 3 существуют в последовательности. Таким образом, для целочисленной последовательности можно открыть код проверки, повторяется ли цифра (два или три раза).
Длина каждого члена в этой последовательности образует другую целочисленную последовательность, OEIS A005341 . Оказывается, что длина члена i составляет примерно 1,56 × 1,304 i (т.е. (size_t)(1.0 + 1.56*exp(0.26544*i)). 30-й член в последовательности составляет 4462 символа.
Если бы мы хотели сгенерировать каждое значение в последовательности, мы могли бы использовать один динамически управляемый буфер (для хранения генерируемого значения) и сохранить дубликат каждого результата:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
char *sdup(const char *src, const size_t len)
{
char *s;
s = malloc(len + 1);
if (!s) {
fprintf(stderr, "sdup(): Not enough memory for a duplicate of %zu-character string.\n", len);
return NULL;
}
memcpy(s, src, len);
s[len] = '\0';
return s;
}
/* Initial buffer size, at least 1. */
#ifndef INITIAL_BUFFER_SIZE
#define INITIAL_BUFFER_SIZE 1
#endif
char **look_and_say(const size_t count)
{
char **table;
char *src, *end;
char *dst, *pos;
size_t len, max = INITIAL_BUFFER_SIZE;
size_t i, k;
if (count < 1) {
fprintf(stderr, "look_and_say(): Count is less than 1.\n");
return NULL;
}
/* Allocate memory for the array of pointers. */
table = calloc(count + 2, sizeof *table);
if (!table) {
fprintf(stderr, "look_and_say(): Not enough memory for an array of %zu strings.\n", count);
return NULL;
}
/* First and last entries are NULLs; sentinels, if you will. */
table[0] = NULL;
table[count + 1] = NULL;
/* Allocate memory for the dynamic buffer. */
dst = malloc(max);
if (!dst) {
fprintf(stderr, "look_and_say(): Not enough memory for a %zu-character work buffer.\n", max);
free(table);
return NULL;
}
/* The sequence starts with "1". */
dst[0] = '1';
len = 1;
/* Save that. */
table[1] = sdup(dst, len);
/* Loop over the rest of the entries to be generated. */
for (i = 2; i <= count; i++) {
/* The source is the last item in the sequence. */
src = table[i - 1];
end = table[i - 1] + len;
/* Ensure we have enough room for the next value in the sequence. */
if (2*len > max) {
/* TODO: Better growth policy! */
max = 2*len;
pos = realloc(dst, max);
if (!pos) {
fprintf(stderr, "look_and_say(): Not enough memory to grow work buffer to %zu chars.\n", max);
free(dst);
for (k = 1; k < i; k++)
free(table[k]);
free(table);
return NULL;
}
dst = pos;
} else
pos = dst;
/* Source is [src, end[. pos is the next position in work buffer. */
while (src < end) {
const int nc = *(src++);
int nn = '1';
/* Skip if source is repeated twice or three times. */
if (*src == nc) {
src++;
nn++; /* 2 */
if (*src == nc) {
src++;
nn++; /* 3 */
}
}
*(pos++) = nn;
*(pos++) = nc;
}
/* Length of the generated value. */
len = (size_t)(pos - dst);
/* Save to table. */
table[i] = sdup(dst, len);
if (!table[i]) {
free(dst);
for (k = 1; k < i; k++)
free(table[i]);
free(table);
return NULL;
}
}
/* Dynamic buffer is no longer needed. */
free(dst);
return table;
}
#ifndef LIMIT
#define LIMIT 30
#endif
int main(void)
{
char **sequence;
size_t i;
sequence = look_and_say(LIMIT);
if (!sequence)
exit(EXIT_FAILURE);
for (i = 1; i <= LIMIT; i++)
printf("%zu. %s\n", i, sequence[i]);
for (i = 1; i <= LIMIT; i++)
free(sequence[i]);
free(sequence);
return EXIT_SUCCESS;
}
На этом этапе мы должны отметить, что у нас уже есть алгоритм O ( N ) для генерации следующего значения в последовательности, где N является длина предыдущего значения. Чтобы достичь лучшей производительности, чем линейная, требуется лучший алгоритм, но, насколько мне известно, для этого не существует тривиального решения, лучше линейного.
Конечно, мы можем оптимизировать приведенный выше код на уровне кода; но его временная сложность уже достаточно хороша.
Если бы мы хотели «обмануть», мы могли бы заметить, что длины первых тридцати членов в последовательности составляют 1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904, 1182, 1540, 2012, 2606, 3410, 4462. Это означает, что если мы выделим достаточно памяти для указателей и 19019 символов (сумма длин + 30 для символов конца строки), нам нужно только одно выделение. Если мы зарезервируем нулевой указатель для NULL, то это распределение будет malloc(19019 + 31 * sizeof (char *)).
Однако, продолжая этот путь, мы получаем следующий код или что-то очень похожее:
static const char term_1[] = "1";
static const char term_2[] = "11";
static const char term_3[] = "21";
static const char term_4[] = "1211";
static const char term_5[] = "111221";
/* term_6[] through term_30[] omitted */
static const char *sequence[31] = {
NULL,
term_1, term_2, term_3, term_4, term_5,
term_6, term_7, term_8, term_9, term_10,
term_11, term_12, term_13, term_14, term_15,
term_16, term_17, term_18, term_19, term_20,
term_21, term_22, term_23, term_24, term_25,
term_26, term_27, term_28, term_29, term_30
};
Это генерирует около 19 КиБ только для чтения (неизменяемых) данных в сгенерированном двоичном файле. Это не будет проблемой даже для многих микроконтроллеров, если эта последовательность будет иметь решающее значение для работы.
Если использование памяти является проблемой, можно просто упаковать каждую отдельную цифру в два бита, сохраняя разумное время доступа, и в этом случае для данных используется только около 5 КиБ памяти.