Reptor Oct 31 2018 at 13:53

Интересная задачка на С

2 min

9.4K

Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу: "Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет)". Несмотря на то, что ко мне эта задача не имела отношения, она меня заняла и я решил подумать над способами ее решения (хотя, кому и при решении какой задачи может понадобиться такой метод оптимизации кода, мне осталось неизвестно, но тем не менее ).

Первое, что пришло на ум, — попытаться использовать шаблоны. Например так

template<int n> 
void print()
{
    printf("%d\n", n);
    print<n - 1>();
}

template<>
void print<0>()
{
    printf("0\n");
}

int main(int argc, char* argv[])
{
    print<N>();
    return 0;
}

Проблема в том, что программирование это инженерная дисциплина, а не оккультная, и если "что-то" должно в системе происходить, то "оно" должно быть описано и под это должны быть выделены ресурсы, и в данном случае, поскольку отработка шаблонов происходит на этапе компиляции, есть ограницения на вложенность подобного рода конструкций (и это хорошо и правильно, и Слава Богу, что так есть), и компилятор совершенно справедливо выдал "fatal error C1202: recursive type or function dependency context too complex" при размере N больше 2000.

Следующее, что пришло в голову, использовать классический метод с указателями на функции.

typedef void(*PrintFunc)(int);

void printZero(int);
void printNumber(int n);

PrintFunc g_functors[] = {printZero, printNumber};

void printZero(int)
{
    printf("0\n");
}

void printNumber(int n)
{
    printf("%d\n", n--);
    g_functors[!!n](n);
}

int main(int argc, char* argv[])
{
    printNumber(N);
    return 0;
}

Но и тут ограничения, накладываемые на нас законом природы, дали о себе знать, и поскольку вложенность вызовов функций ограничена размерами стека, то при значении N > 4630 был получен законный "Stack overflow".

На этом месте разочарование и злоба полностью завладели мной и я понял, что для полноценного решения этой задачи не стоит гнушаться ни чем, в том числе самыми грязными трюками. Проблема в том, что при определенных значениях N нам нужно передавать управление на нужные участки кода. И в этом нет никаких проблем, когда у нас в распоряжении есть условные операторы, но когда их нет, приходиться прибегать к колдовству. В стародавние времена это можно было решить методом goto, но с тех пор охотники на ведьм и другие драконоборцы сильно ограничили его функциональность (и это также хорошо и правильно) и мы бы хотели написать что то типа этого

g_functors[0] = [](int){print("0\n"); goto end; }
g_functors[1] = [](int n){print("%d\n", n); goto begin; }
begin:
    g_functors[!!n](n--);
end:

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

void printZero(int);
void printNumber(int n);

PrintFunc g_functors[] = {printZero, printNumber};

void printZero(int)
{
    printf("0\n");
    throw 0;
}

void printNumber(int n)
{
    printf("%d\n", n);
}

int main(int argc, char* argv[])
{
    int  n = N;
    try{
        begin:
        g_functors[!!n](n--);
        goto begin;
    }
    catch (...){}
    return 0;
}

И это полностью решило проблему (при любых N).

P.S.: Буду рад услышать о других методах решения этой задачи

Tags:

с++

Hubs: