Напомню требования к программе.
- Входные данные — последовательность строк; каждая строка начинается с прописной буквы, остальные буквы строчные.
- Входную последовательность всегда можно переупорядочить в допустимую последовательность, в которой у каждой пары смежных строк первая буква второй строки, переведенная в нижний регистр, совпадает с последней допустимой буквой первой строки. Допустимая буква — это буква, с которой начинается хотя бы одно слово последовательности.
- Требуется написать кратчайшую программу, находящую любую допустимую перестановку входной последовательности.
Как это часто бывает, есть два очевидных способа решения этой задачи: один быстрый, другой простой.
Суть быстрого алгоритма: возьмем все первые и последние допустимые буквы всех слов и сделаем их вершинами в графе. Сами слова будут представлены дугами. Теперь достаточно в этом графе найти эйлерову цепь или эйлеров цикл. Если кто не помнит, эйлерова цепь/цикл проходит через каждую дугу графа ровно один раз. В честь Эйлера, который желал странного, бродя по кенигсбергским мостам.
Быстрый алгоритм хорош тем, что он быстрый. И плох тем, что трудно его реализовать компактно. Такое случается с быстрыми алгоритмами, ничего не поделаешь… Из-за этого многие им предпочитают медленные и простые, но ради справедливости код все равно пишут длинный и сложный. И комментарии к нему не пишут. А потом увольняются, а новый разработчик все переписывает заново. Используя тот же алгоритм. Да… О чем я говорил?
К счастью, в требованиях к программе ничего не сказано про время работы, что совершенно развязывает нам руки и позволяет использовать Его Величество Полный Перебор. К слову, полный перебор часто недооценивают, и он играет роль этакого алгоритмического goto — подходит не везде, но во многих случаях сильно упрощает жизнь, хотя и сильно нелюбим большинством.
Идея простого алгоритма в том, чтобы рассмотреть все перестановки входной последовательности и проверить каждую на допустимость. Одна из них, согласно условию, обязательно подойдет.
От алгоритма перебора всех перестановок требуется только одно: как можно более короткая реализация. Концептуально наиболее просто способ — перемешивать последовательность случайным образом, как карты в колоде. При идеальном генераторе случайных чисел случайный перебор потребует столько же времени, сколько и «честный». К сожалению, в стандартной библиотеке C нет функций вроде shuffle, поэтому напишем честный перебор руками. Я взял кнутовское «Искусство программирования», том 4, выпуск 2, главу 7.2.1.2 и нашел там на странице 71 (в русскоязычном издании) алгоритм генерации перестановок с помощью циклических сдвигов. Автор уверял, что алгоритм отличается чертовски простой реализацией. Итак, имея исходную последовательность $x_1\ldots x_n$:
- Установить $a_i = x_i$, $1 \leq i \leq n$.
- Посетить перестановку $a_1 \ldots a_n$ и установить $k = n$.
- Заменить $a_1a_2\ldots a_k$ на $a_2\ldots a_ka_1$ (циклический сдвиг). Если $a_k \neq x_k$, перейти к п. 2.
- Уменьшить $k$ на 1. Если $k > 1$, вернуться к п. 3 (мы будем возвращаться на п.3 без выполнения этой проверки, т.к. знаем, что одна из перестановок нам точно подойдет).
Проверка перестановки на допустимость выполняется элементарно. Построим множество первых букв всех слов. Для каждой пары соседних слов в перестановке:
- Отбрасываем с конца первого слова буквы до тех пор, пока последняя буква не будет присутствовать в множестве первых букв. Такая буква всегда существует: в худшем случае это будет первая буква слова.
- Сравниваем последнюю оставшуюся букву первого слова с первой буквой второго слова.
Поскольку первые буквы — прописные, их надо преобразовать в строчные. Проще всего это делается для букв в кодировке ASCII или CP1251: нужно просто прибавить к коду буквы 32.
Итак, первый вариант программы:
#include <stdio.h>
#include <string.h>
int main(int argc, char** argv){
int k, i, match, first[256];
char *r, *permut[256];
int maxidx;
// обнуляем множество первых букв
for (i = 0; i < 256; i++)
first[i] = 0;
// входная последовательность задана в командной строке, поэтому
// пропускаем находящееся в начале массива argv имя программы
argv++;
// проходим по входным словам (argv завершается нулевым указателем)
for (i = 0; argv[i]; i++) {
permut[i] = argv[i]; // начальная перестановка равна исходной
first[permut[i][0] + 32] = 1; // добавляем первую букву слова в множество
}
maxidx = i - 1; // максимальный индекс слова в последовательности
k = maxidx;
// когда match станет 1, допустимая последовательность найдена
for (match = 0; !match;) {
// циклический сдвиг элементов массива permut с 0 по k-1
r = permut[k];
memmove(permut + 1, permut, k*sizeof(char*));
permut[0] = r;
// см. алгоритм сдвига
if (permut[k] == argv[k])
k--;
else
k = maxidx;
// проверка перестановки на допустимость
for (i = 0, match = 1; i < maxidx - 1 && match; i++) {
// получим указатель на последнюю букву первого слова
r = permut[i] + strlen(permut[i]) - 1;
// сдвигаем указатель, пока не найдем букву из множества первых букв
while (!first[*r])
r--;
// проверяем совпадение
match = (*r == *permut[i + 1] + 32);
}
}
for (i = 0; i <= maxidx; ++i)
printf("%s\n", permut[i]);
return 0;
}А дальше дело техники — надо сжимать программу:
- Всем переменным — кратчайшие имена.
- Убираем включения заголовочных файлов, оператор return (компилятор сам вставит), все упоминания типа int (это тип по умолчанию, его можно не указывать).
- Вспоминаем, что глобальные переменные инициализируются нулями.
- Заменим sizeof(char*) на 4 или 8, если компилируем, соответственно, на 32- или 64-разрядной системе.
- Используем argc в качестве одной из нужных нам переменных, например, maxidx.
Получим:
k, i, b, f[256];
char *r, *q[256];
main(int l, char** x){
x++;
for (i = 0; x[i]; i++) {
q[i] = x[i];
f[*q[i] + 32] = 1;
}
l = i - 1;
k = l;
for (; !b;) {
r = q[k];
memmove(q + 1, q, k*4);
q[0] = r;
if (q[k] == x[k])
k--;
else
k = l;
for (i = 0, b = 1; i < l - 1 && b; i++) {
r = q[i] + strlen(q[i]) - 1;
while (!f[*r])
r--;
b = (*r == *q[i + 1] + 32);
}
}
for (i = 0; i <= l; ++i)
printf("%s\n", q[i]);
}Ну, и остается только
- Избавиться от strlen — указатель на последнюю букву можно найти и короче.
- Выполнить кое-какие перестановки присваиваний и инкрементов, использовать разыменование вместо индексации.
- Убрать пробелы и переводы строк.
Получим итоговый вариант (разбиение на строки оставлено для читабельности):
k,i,b,f[256];
char*r,*q[256];
main(int l,char**x){
for(x++;q[k]=x[k];f[*q[k++]+32]++);
for (l=--k;!b;){
r=q[k];
memmove(q+1,q,k*4);
*q=r;
k=q[k]==x[k]?k-1:l;
for (i=0,b=1;i<l&&b;){
for(r=q[i++];*r++;);
while(!f[*--r]);
b=*r==*q[i]+32);
}
}
for (i = 0; i <= l; ++i)
printf("%s\n", q[i]);
}Вот и все. Должен только заметить, что даже если все допустимые буквы — последние, все равно время работы алгоритма будет что-то вроде $O(n\cdot n!)$, где $n$ — количество строк во входной последовательности. Время работы сильно зависит от порядка слов во входной последовательности и от порядка перебора. На моем компьютере на 14 словах алгоритм работал более 10 минут! Добавить 15-е слово я не решился. Так что с общечеловеческой точки зрения это очень плохой алгоритм.
Кстати, в предыдущем посте у меня в код закралась неиспользуемая переменная, что позволяет сократить решение еще на 2 символа.
(Еще не оценили)
Loading ...
