Вот.
Как-то написал один чел рекурсивную программу.
Он в ней ошибся, кстати
Собственно два вопроса:
1) Что должна была делать функция GopSwap
2) Где и какая ошиька?
/* Пример того, как не надо писать читабельные программы */
/* В этой переменной лежит второй результат ReplWordPos */static int ResultLen;
static int iMax(int i1, int i2)
{
return i1 > i2 ? i1 : i2;
}
static BOOL cEqu(char c1, char c2)
{
return c1 == c2;
}
/* Кусок функции iter */#define _iter_(fn, a, len, s, sh, res) \
iter(fn, a + len - len / 2, len / 2, s, sh, iter(fn, a, len / 2, s, sh, res))
/* Несомненно iter -- это самая важная функция в этом файле. */static int iter(int (*fn)(int, char*, int, int), int a, int len, char* s, int sh, int res)
{
assert(len >= 0);
return (len - len / 2 > len / 2) ? (*fn)(a + len / 2, s, sh, _iter_(fn, a, len, s, sh, res))
: len > 0 ? _iter_(fn, a, len, s, sh, res)
: res;
}
static int smLen(int i, char* s, int sh, int res)
{
return (!cEqu(s[i], s[i + sh]) && i < res) ? i : res;
}
static int smWrd(int i, char* s, int len, int res)
{
return i == 0 ? res : iMax(res, iter(smLen, 0, len - i, s, i, len - i));
}
static int smWdth(int i, char* s, int len, int res)
{
return iter(smLen, 0, len, s, i, len) == len ? i : res;
}
static int resLen(int i, char* s, int len, int res)
{
return iter(smWrd, 0, len - i, s + i, len - i, res);
}
static int resPos(int i, char* s, int len, int res)
{
return iter(smWdth, 0, len - ResultLen - i, s + i, ResultLen, res);
}
/* Возвращает пару чисел, одно как значение, а другое в ResultLen, но вот что это за числа? */static int ReplWordPos(char* str, int len)
{
len -= (ResultLen = iter(resLen, 0, len, str, len, 0));
return iter(resPos, 0, len, str, len, 0);
}
static int gopSwap(int i, char* s, int what, int res)
{
s[i] = (char)what;
return res;
}
/* Что делает эта функция? */void GopSwap(char* str)
{
str += ReplWordPos(str, strlen(str));
iter(gopSwap, 0, ResultLen, str, '*', 0);
}
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>1) Что должна была делать функция GopSwap E>2) Где и какая ошиька?
Можно заметить, что iter в связке с её аргументами-функциями выполняет обход диапазона [a,a+len) в затейливом порядке (делением напополам), применяя к аргументу-функции кортеж (s,sh,i,res) где i — текущее значение, res — последействие предыдущего вызова.
Причём сама логика функций такова, что порядок обхода не влияет на результат. (Ну почти не влияет).
То есть, можно заменить эту жуткую функцию на вот такую:
typedef int(*FN)(int i, char* s, int sh, int res);
int iter(FN fn, int a, int len, char* s, int sh, int res)
{
for(int i=0; i<len; ++i)
res = fn(i, s, sh, res);
return res;
}
Далее будем искать логику.
iter(smLen...) находит крайне левую позицию i такую, что s[i]==s[i+sh]
(по всей видимости, sh означает shift).
То есть первую букву, которая повторяется через sh.
iter(smWrd...) ищет максимум (т.е. среди iter(smLen...) с разными значениями sh.
То есть самый длинный префикс без повторений. Точнее, длина префикса минус 1.
iter(smWdth...) ищет значение сдвига, при котором нет ни одной буквы, повторившейся через этот сдвиг.
Кстати, реальный диапазон поиска — 2*len.
iter(resLen...) ищет максимум среди префиксов подстрок — то есть, попросту, самую длинную подстроку без повторений.
На остальное — пока фантазии не хватило. Какие-то безумные побочные эффекты...
К>typedef int(*FN)(int i, char* s, int sh, int res);
К>int iter(FN fn, int a, int len, char* s, int sh, int res)
К>{
К> for(int i=0; i<len; ++i)
К> res = fn(i, s, sh, res);
К> return res;
К>}
К>
А где используется параметр a? Скорей:
typedef int(*FN)(int i, char* s, int sh, int res);
int iter(FN fn, int a, int len, char* s, int sh, int res)
{
for(int i=0; i<len; ++i)
res = fn(a+i, s, sh, res);
return res;
}
Попробуем избавиться от рекурсии.
Функция iter(smLen, 0, len, s, sh, len) ищет минимальный индекс i символа, который не совпадает с символом i+sh. Можно заменить на:
for(res = 0; res < len; res++)
if (s [res] != s [res+sh])
break;
Функцию smWrd можно переписать так:
static int smWrd(int i, char *s, int len, int res)
{
if (i == 0)
return res;
for (int j = 0; j < len-i; j++)
if (s [j] != s [j+i])
break;
return max (res, j);
}
Функция iter(smWrd, 0, len, s, len, res) проверяет на одинаковость цепочек, следующих непосредственно друг за другом, общей длиной len. Длина одной цепочки меняется от 0 до len. Если неодинаковые, возвращает индекс отличного символа или res, что больше.
for (int i = 1; i < len; i++)
{
for (int j = 0; j < len-i; j++)
if (s [j] != s [j+i])
break;
res = max (res, j);
}
Перекуём баги на фичи!
