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

Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу: "Предложите код, который бы выводил на печать числа в убывающем порядке от 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.: Буду рад услышать о других методах решения этой задачи

Поделиться публикацией

Комментарии 89

    +5

    Интересное решение, хотя при использовании C extensions (gcc), можно обойтись без функторов вообще — за счет Label Values. Эта функциональность применяется в низкоуровневых модулях высоконагруженных приложений для организации переходов без ветвления, хотя в зависимости от ситуации может быть оптимальнее использовать if в сочетании с builtin_expect для мануальной настройки branch prediction. Вместо отрицания, возможно, применить более подходящий оптимальный intrinsic


    int main() {
      int n = 100500;
      void* refs [] = { &&work, &&done };
      work:
        printf("%d ", n);
        n--;
        goto *refs[!n];
      done:
      return 0;
    }
      +1
      Спасибо за интересную возможность. Не знал.
      –2
      Я не знаю, как работает перехват деления на 0 в С. Да и синтаксис С — не очень помню.
      Циклов нет, значит только goto. Печатаем i вычитаем единичку, делим любое число на i. При перехвате деления на 0 — заканчиваем программу, если нет перехвата — переходим в начало.
      {
      :begin
      println i
      i=i-1
      try {j=10/i}
      catch {goto end}
      goto begin
      :end
      }
        +1
        Проблема в том, что в С нет исключений, т.е. Ваш код не компилируется. Но даже и в C++, где есть исключения, деление на ноль — UB и может не бросать исключений (обычно и не бросает)
          0
          Мы не знаем условий задачи. А раз не знаем, то почему мы должны ограничиваться стандартом? SEH на Windows, и сигналы на Linux должны дать требуемый результат. В реальных проектах такого использовать, конечно же, нельзя, но почему на идиотскую задачу нельзя дать соответствующий ответ?
            0
            Нет обработки исключений? Не беда. Вот вариант без синтаксического сахара, макросов и т.д.
            #include <stdio.h>
            #include <stdlib.h>
            
            void theEnd(void) {  printf("the end");   exit(1); }
            void theDummy(void) {}
            int main()
            {
                long i, j, k, t;
                void (*operations[2])(void) = {theEnd, theDummy};
                i = 20; // в условии не было ограничений, не будем загоняться
            begin:
                j = i - 1; 
                k = (i-j)*j*i-(j-i)*i*j;
                t = (k && 1) || (i && 1);
                printf("i = %d,  \n", i);
                operations[t]();
                i = i - 1;
                goto begin;
            end:
                return 0;
            }
            

            Результат
            i = 13,
            i = 12,
            i = 11,
            i = 10,
            i = 9,
            i = 8,
            i = 7,
            i = 6,
            i = 5,
            i = 4,
            i = 3,
            i = 2,
            i = 1,
            i = 0,
            the end

            ...Program finished with exit code 1
            Press ENTER to exit console

            Здесь нет оптимизации, проверок переполнения и т.д. Да и Си я не знаю.
              0
              и опять поспешил. вот так будет правильно.
              int main()
              {
                  long i, t;
                  void (*operations[2])(void) = {theEnd, theDummy};
                  i = 2165;
              begin:
                  t = i && 1;
                  printf("i = %d \n", i);
                  operations[t]();
                  i = i - 1;
                  goto begin;
              end:
                  return 0;
              }
          +7
          Выражение !!n — это и есть неявное сравнение n==0. А циклы по условию задачи никто использовать не запрещал, так что если предположить, что разрешено !!n — можно написать
          while( !!n ) printf( "%d ", n-- );
          или, что то же самое,
          while( n ) printf( "%d ", n-- );
            +3
            Но в while-то тоже происходит неявное сравнение.

            Более того, что подразумевается под «реализация функции вывода на печать не в счет»?
            Предлагается ещё реализовать функцию отрисовки что ли? Если нет, то тогда в чём вообще проблема? В функции, осуществляющей печать, можно делать что угодно.
              +2
              С каких пор в циклах не происходит сравнения?
              Странно
                +3

                Так оно и не в цикле происходит вон у вас в main, компилятор радостно генерирует cmp.


                Смысл утверждения был не в том, что можно использовать циклы, а в том, что если можно использовать !!n, то от использования циклов вы уже ничего не теряете.

                  0

                  А лямбды на сишке можно полноценно эмулировать без условий? Тогда можно просто задачу в кодировке Черча переписать.

                    0
                    Ну, на плюсах я бы ковырял в сторону дженерик лямбд (собственно, я так туплы делал через Church encodings ещё до того, как узнал про Church encodings туплов, оказалось существенно эффективнее std::tuple с точки зрения времени компиляции). На сишечке, наверное, можно там void* обмазаться и передавать указатели на функции туда-сюда и кастовать их.
                    +1

                    Вы же понимаете что оно неявно преобразуется к виду `!!n == true. Аналогично if и switch, хотя для switch clang умеет генерировать таблицу сдвигов

                      +2

                      Я понимаю, и поэтому я согласен, что !!n — это читерство в любом виде.

                        –1
                        Не, сама конструкция с преобразованием нормально, но в цикле оно неявно сравнивается
                    +1
                    В while сравнение неявное, так же как в !!n, это прекрасно видно в ассемблерной выдаче, которую Вы привели в пример. А цикл без сравнения — запросто:
                    #include <stdio.h>
                    #include <stdlib.h>
                    #include <stdint.h>
                    union Index
                    { int32_t n;
                      struct
                      {int32_t       : 31,
                               sign  : 1;
                      };
                    };
                    void dummy(int){}
                    typedef void (*F)(int);
                    F check[2] = { dummy, exit };
                    int main() 
                    { Index index;
                      for( index.n = 100500;;index.n-- )
                      { check[ index.sign ](0);
                         printf( "%d ", index.n );
                      }
                      return 0;
                    }
                    Вместо exit можно использовать longjmp. Хотя, конечно, — это платформо-зависимый код.
                    +1
                    Дорогие друзья, это задание пришло ко мне так же как и к Вам, поэтому не могу дать ему более внятные разъяснения чем понял сам. Я рассудил так, что в самом коде получения числа и выбор ветки кода не должно встречаться условных операторов т.е. if, for, while, do...while(скрытые операторы) и т.д., а вот за код отвечающий за печать (внутренности printf и пр.) мы не отвечаем.
                    Если бы можно было использовать for, while и прочее, то задачи бы не было.
                      0

                      А почему нельзя for? Ведь в виде for(;;) это всё равно, что goto label: скрытого сравнения нет, явного тоже нет.

                        0
                        Я полагаю, что в данном случае for(;;) тоже самое goto label. Для решения задачи нам нужно какое-то циклическое выражение (главное чтобы не использовать сравнений). В любом случае, когда мы говорим про что-то вроде for(infinity_and_beyond), goto infinity_and_beyond, while(not_reached_infinity_and_beyond) и пр., мы имеем ввиду jmp to_infinity_and_beyond. Так что, я думаю, использовать for(;;) большого греха не будет (если только вы удержитесь и по привычке не напишите for( n=N; n>0;n--); ).
                      0
                      Условие «реализация функции вывода на печать не в счет» подразумевает, что ее возвращаемое значение тоже часть реализации и можно использовать саму функцию printf как условие.
                      int main()
                      {
                      	int n = 9;
                      	while (printf("%.d", n--));
                      	printf("0");
                      
                      	return 0;
                      }
                      


                      Однако тут используется цикл с условием. Если брать в широком смысле, то так или иначе задача не решаема без цикла или рекурсии, но рекурсия ограничена. Если исключить любое сравнение то подходит только бесконечный цикл.
                      Прервать его можно следующими способами:
                      1. break
                      2. return из main фунции
                      3. Бросить исключение
                      4. goto
                      5. Функция exit() или ее аналоги

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

                      #include <cstdio>
                      #include <stdlib.h>
                      
                      void print(int n) { printf("%d\n", n); }
                      void printAndExit(int n) { print(n); exit(0); };
                      void(*f[])(int) = { printAndExit, print };
                      
                      int main()
                      {
                      	int n = 9;
                      	for (;;)
                      	{
                      		f[bool(n)](n);
                      		--n;
                      	}
                      
                      	return 0;
                      }
                      
                      +1
                      #include <stdio.h>
                      #include <stdlib.h>
                      
                      void not0(int i) {printf("%d\n", i);}
                      void is0(int i) {printf("0\n"); exit(0); }
                      void (*func[2])(int)={is0,not0};
                      
                      void main()
                      {
                          for (int i=100;;i--) {
                              unsigned int j=((unsigned short*)&i)[0] | ((unsigned short*)&i)[1];
                              j=((unsigned char*)&j)[0] | ((unsigned char*)&j)[1];
                              j=(j&1)|((j&2)>>1)|((j&4)>>2)|((j&8)>>3)|((j&0x10)>>4)|((j&0x20)>>5)|((j&0x40)>>6)|((j&0x80)>>7);
                              func[j](i);
                              }
                      }
                      
                        0
                        Вообще, вызов func[(int)(bool)i](i) должен работать куда лучше этого странного кода. Но идея вполне здравая.
                          0
                          А разве (bool)i не является неявным сравнением?
                            0
                            Нет, это тайпкаст. Да, мы здесь пользуемся тем, что ((bool)i == true) === (i != 0), но сравнением это не является, мало того, даже при трансляции этого куска в асм в коде может не оказаться jz/jnz (например, четыре раза вызвать popcnt eax, eax приведет к переводу любого не-нуля в 1, хотя скорее всего код будет похож на or eax, eax; jz всторону; inc ebx и дальше).
                          0
                          да exit(0) пожалуй здравое решение. В остальном это тоже решение. Спасибо.
                          –1
                          Добавим чуть фантазии и дотошности, вместо "!!" вспомним математику:

                          int isNonNull (float n)    { return (int)(n / (n + 0.1) + 0.1); }
                          int isNegative(int n)      { return (int)(n - sqrt(n*n)); }
                          
                          int main()
                          {
                              int n = 3;
                              while(isNonNull(n) && !isNegative(n)) 
                                  printf("%d", n--);
                          }


                          Куда слать резюме?
                            +1
                            а циклы использовать можно? цикл ведь это по сути if + goto
                              0

                              Нельзя использовать явное и неявное сравнение. В while и do..while оно есть, в for(;<пусто>;) — нет. Всё, что не запрещего — разрешено. По сути, такой for ничем не отличается от goto label_back.

                              +4
                              while( condition )
                              сравнение в чистом виде, поэтому «мы вам позвоним».
                                0
                                удалено
                              +8
                              Подход с шаблонами сразу не прокатит, т.к. нужно знать n именно во время компиляции. А если мы знаем n во время компиляции, то мы просто можем написать
                              print(n--);
                              n+1 раз.

                              Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу

                              Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании), поэтому давать её на собеседовании, конечно, можно, но ИМХО только в случае собеседования в клуб извращенцев.
                                0
                                > Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании)

                                Ограничение вполне-таки естественное, просто сформулировано упрощено, чтобы кандидат не парил голову понапрасну. Ветвления меняют время выполнения, а это часто недопустимо.
                                +3
                                Преобразуем текущее n в отрицательное, берем знак и используем его в качестве индекса по массиву из двух функций.
                                Рабочий код
                                #include <stdio.h>
                                #include <stdlib.h>
                                
                                typedef void (*Funcs)(int);
                                
                                void printZero(int)
                                {
                                    printf("0\n");
                                    exit(0);
                                }
                                
                                void printNumber(int n)
                                {
                                    printf("%d\n", n);
                                }
                                
                                Funcs g_functors[] = {printZero, printNumber};
                                
                                #define N 100000
                                
                                int main(int argc, char* argv[])
                                {
                                    int n = N;
                                begin:
                                    unsigned index = (unsigned(-n))>>(8*sizeof(n)-1);
                                    g_functors[index](n--);
                                    goto begin;
                                
                                    return 0;
                                }
                                

                                  +1
                                  отличный вариант. я думаю лучший.

                                  PS для тех кто не понял, преобразования к отрицательному будет давать в старшем бите 1 в любом случае кроме того когда изначальное значение 0. Следовательно, сдвинут на (8*sizeof(n)-1) мы получим либо 0 в случае когда изначально был 0 либо 1 в случае любого другого числа. Дальше просто при вызове «нулевой» функции делаем exit.
                                    –1
                                    "!!" выполняет туже функцию. Если > 0 то 1 если == 0 то 0
                                    0
                                    Спасибо. exit(0) — делает все гораздо более элегантным, но в остальном это решение того же качества, оно не дает ничего нового. Это тот же метод. Но все равно спасибо за улучшение.
                                      0
                                      Есть новый подход в честь наступающей пятницы, моего провала с while() и тяги к прекрасному:
                                      * без выделения памяти и конструирования объектов
                                      * без exit(), чтобы не нарушать красивый ход исполнения кода
                                      * без функторов и ограничения глубины рекурсии
                                      * без явных и неявных сравнений включая, но не ограничиваясь: приведения к bool, operator!(), и всякие cmovz / jcxz в ассемблерном коде.

                                      Расплатиться пришлось небольшой ассемблерной вставкой, 1 WinAPI, капелькой магии и крупинкой надежды:
                                      #include <cstdio>
                                      #include <cstdint>
                                      #include <windows.h>
                                      
                                      int isNegative(int n)
                                      {
                                          return (unsigned int)n >> (sizeof(n) * 8 - 1);
                                      }
                                      
                                      void f(int number)
                                      {
                                          uint16_t hope = 0;
                                      
                                      m1:
                                          int isNeg = isNegative(number);
                                          uint32_t fmt = 0x000a6400 | ((1 - isNeg) * '%');
                                          printf((char*)&fmt, number--);
                                      
                                          uint16_t magic = hope ^ (0x6F6F * isNeg + 0x0100);
                                      
                                          __asm
                                          {
                                              mov ecx, m2;
                                              mov ax, [magic];
                                              or  [hope], ax;
                                              xor [ecx], ax;
                                              mov eax, m1;
                                      
                                          m2: jmp ecx;
                                          }
                                      }
                                      
                                      
                                      int main()
                                      {
                                          DWORD old;
                                          VirtualProtect(GetModuleHandle(nullptr), 0x16000, PAGE_EXECUTE_READWRITE, &old);   // this might work
                                          VirtualProtect(GetModuleHandle(nullptr), 0x2000,  PAGE_EXECUTE_READWRITE, &old);   // ... this one will fix when previous fails
                                          int n = 30;
                                          f(n);
                                      }

                                      Тестировал на msvc 2017 Win7, debug и release сборки, на n = -3, 0, 3, 1000, ...;
                                      Вдохновлялся кодом masterspline
                                        0
                                        Полиморфный код? Мило :) Правда, это уже не Си.
                                          0
                                          Спасибо Ваша решимость делает Вам честь. Надо сказать, доля юмора в коде, говорит о том, что современные программисты, как и программисты прошлого не только прагматики — бездушные машины по написанию кода, но и поэты.
                                        0

                                        Не работает для отрицательных N.


                                        мой вариант: https://godbolt.org/z/aPF4HE


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

                                          0
                                          Спасибо за решение. Очень тщательно подошли к задаче + познакомили с интересным сервисом. Спасибо.
                                        0
                                        *всегда буду читать комментарии
                                          0
                                          Без сравнений — хорошо, код будет только описан, и работать мы будем в BareMetal x86, ну или под ДОСом, или в Ring-0
                                          1) Пишем свой обработчик на ошибку division by zero, оный должен увеличить сохраненный адрес возврата на длину команд присваивания, деления и безусловного перехода(надо посмотреть в листинге)
                                          2) Закидываем его в таблицу прерываний
                                          3) Далее адов говнокод:
                                          void destroy (int n)
                                          {
                                          	int i=99;
                                          	int j;
                                          	n++;
                                          hitbyvelociraptor:
                                          	n--;
                                          	printf("%x\n",n);
                                          	j=i/n;
                                          	goto hitbyvelociraptor;
                                          	printf("done\n");
                                          }
                                          


                                          Задачей обработчика деления на ноль будет перепрыгнуть через goto. И никаких сравнений тут вообще нигде не будет делаться.
                                            +1
                                            Я бы написал так
                                            begin:
                                            print(N);
                                            N=N/N*(N-1);
                                            goto begin;

                                            Программа напечатает числа от N до 0, а потом прекратит работу.
                                              +1
                                              Неа. Последним числом будет "-1"
                                                0
                                                Действительно, не заметил. Исправил, спасибо.
                                                0
                                                Но завершение будет аварийным, хотя в ТЗ про то, что выход должен быть штатным
                                                  0
                                                  Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет)
                                                    0
                                                    Ага, так и получается
                                                0
                                                удалено
                                                  0
                                                  g_functors!!n;

                                                  Разве! не нарушает требования об отсутствии скрытых сравнений? В! ведь присутствует сравнение.

                                                    0
                                                    g_functors[!!n] — это упрощение. Идея в том, чтобы любое число не 0 преобразовать в 1, а 0 в 0, но, согласен, более чисто с математической (и программно-ассемблерной) точки зрения это сделано в комментариях других авторов.
                                                    +1
                                                    Можно добавить немного С++
                                                    struct Item
                                                    {
                                                        Item() { printf ("%d ", N - (this - items)) - 1; }
                                                    
                                                        static void Do() { exit(0)}
                                                    
                                                        static const size_t N = 100;
                                                        static const Item items[N+ 1];
                                                    };
                                                    
                                                    const Item Item::items[] = {};
                                                    
                                                    void main()
                                                    {
                                                    Item::Do();
                                                    }
                                                      0
                                                      Спасибо. Использовать конструктор + массив, это, пожалуй, еще один способ. Хотя для верности, есть смысл проверить на N = INT_MAX.
                                                        0
                                                        На VS2013 работает на 32 битной конфигурации
                                                          0
                                                          Как говорит древнее поверье «если что то работает, то оно работает». Спасибо за вариант.
                                                      +1
                                                      И на шаблонах тоже можно для любого N:
                                                      Заголовок спойлера
                                                      #include <stdio.h>
                                                      
                                                      template <int N> void print(int base)
                                                      {
                                                          print<N/2>(base);
                                                          print<N-N/2>(base-N/2);
                                                      }
                                                      
                                                      template <> void print<0>(int)
                                                      {}
                                                      
                                                      template <> void print<1>(int base)
                                                      {
                                                          printf("%d\n", base);
                                                      }
                                                      
                                                      
                                                      #define N 100
                                                      
                                                      int main()
                                                      {
                                                          print<N+1>(N);
                                                          return 0;
                                                      }
                                                      

                                                        0
                                                        Попробуйте для N = INT_MAX
                                                        +4
                                                        С++ без извращений
                                                        #include <iostream>
                                                        
                                                        struct printnum
                                                        {
                                                          printnum()
                                                          {
                                                             std::cout << nump-- << "\n";
                                                          }
                                                        
                                                          static unsigned nump;
                                                        };
                                                        
                                                        unsigned printnum::nump;
                                                        
                                                        int main()
                                                        {
                                                          printnum::nump = 10000000;
                                                          printnum * pa = new printnum[printnum::nump+1];
                                                        }
                                                        

                                                        динамическое выделения памяти, чтобы обойти ограничение по стеку
                                                        static не разрешит задавать размер динамичски
                                                          +1
                                                          Придумал С++ решение без реального выделения памяти и без ограничений по размеру
                                                          C++ без извращений и без ограничений по памяти
                                                          #include <iostream>
                                                          
                                                          struct printnum
                                                          {
                                                            printnum()
                                                            {
                                                               std::cout << nump-- << "\n";
                                                            }
                                                          
                                                            static unsigned long nump;
                                                          };
                                                          
                                                          unsigned long printnum::nump;
                                                          
                                                          char* memory[10];
                                                          
                                                          int main()
                                                          {
                                                            printnum::nump = 10000000000000;
                                                            printnum * pa = new(memory) printnum[printnum::nump+1];
                                                          }
                                                          

                                                            0
                                                            На самом деле, «скрытая» проверка условий таки есть — в реализации оператора new. тут вопрос к применимости исходного ограничения — где таки можно иметь эти самые сравнения — в коде генерации самого компилятора? рантайма? стандартной библиотеки?
                                                            А то я тоже могу просто написать std::transform(nullptr, nullptr + n, (ничего не делающий output it), (функция вывода))

                                                            (но за хак я плюс поставил)
                                                              0
                                                              В условии стоит запрет на неявное сравнение, так что этот вариант (а равно и все остальные варианты с массивами и контейнерами) нарушают это условие.
                                                              0
                                                              Это, похоже, UB.
                                                                0

                                                                Удалено.

                                                                  0
                                                                  Спасибо за решение.
                                                                  0
                                                                  Почти 1:1 подход который я решил применить — конструкторы в динамической памяти. Разница в том что я не делал статичную переменную, а передавал в конструктор ссылку на коллбек:
                                                                  #include <iostream>
                                                                  #include <vector> 
                                                                  #include <functional>
                                                                  
                                                                  struct Caller
                                                                  {
                                                                    std::function<void()> & m_f;
                                                                    Caller( std::function<void()> & f) : m_f(f) {}
                                                                    ~Caller() { m_f(); }
                                                                  };
                                                                  
                                                                  int main()
                                                                  {
                                                                      int n = 500;
                                                                      std::function<void()> counter ([&n] {
                                                                          std::cout << n-- << std::endl;
                                                                      });
                                                                      std::vector<Caller> v(n, Caller(counter));
                                                                      return 0;
                                                                  }
                                                                  
                                                                  
                                                                  0
                                                                  с89:
                                                                  void main (int n, char **argv)
                                                                  {
                                                                  void (*f[])()={&exit,&printf};
                                                                  int func_n;
                                                                  loop:
                                                                  func_n= n;
                                                                  func_n|=func_n>>1;
                                                                  func_n|=func_n>>2;
                                                                  func_n|=func_n>>4;
                                                                  func_n|=func_n>>8;
                                                                  func_n|=func_n>>16;
                                                                  f[func_n&1]("%d ",--n);
                                                                  goto loop;
                                                                  }
                                                                    0
                                                                    Сразу подумал, что на С++ элементарно, а вот на С нужно подумать. Но вижу, что все пишут на плюсах, поэтому мой вариант:
                                                                    #include <iostream>
                                                                    
                                                                    class A {
                                                                    public:
                                                                    	A() {
                                                                    		std::cout << n << "\n";
                                                                    		--n;
                                                                    	}
                                                                    	static void set(size_t i) {
                                                                    		n = i;
                                                                    	}
                                                                    private:
                                                                    	static size_t n;
                                                                    };
                                                                    
                                                                    size_t A::n;
                                                                    
                                                                    void print_n_0(size_t n) {
                                                                    	A::set(n);
                                                                    	delete[] new A[n+1];
                                                                    }
                                                                    
                                                                    int main() {
                                                                    	print_n_0(10);
                                                                    	return 0;
                                                                    }
                                                                    
                                                                      0
                                                                      Это мой вариант, но тут ограничение по памяти — лучше память вообще не выделять, как здесь.
                                                                      –1
                                                                      #include <stdio.h>
                                                                      
                                                                      int step(int i) {
                                                                          printf("%d\n", i--);
                                                                          return (i && step(i)) || 0;
                                                                      }
                                                                      
                                                                      int main(void) {
                                                                          printf("%d\n", step(5));
                                                                          return 0;
                                                                      }
                                                                      
                                                                        +1
                                                                        Если уж использовать С++, то все проще некуда.

                                                                        int main()
                                                                        {
                                                                        const int n = 10;
                                                                        int count = n;
                                                                        std::generate_n(std::ostream_iterator(std::cout, " "), n, [&count]() { return count--; });
                                                                        
                                                                        return 0;
                                                                        }
                                                                        


                                                                          0
                                                                          На первый взгляд конечно да, запрета на использование стандартных библиотек не было, но всё же запрет на неявный оператор сравнения всё портит — внутре он там конечно есть.
                                                                          0
                                                                          Если уж падать в stack overflow, то зачем так переусложнять? Почему просто не написать что-то вроде:
                                                                          int prt(int n)
                                                                          {
                                                                          	std::cout << n << "\t";
                                                                          	return n && prt(n - 1);
                                                                          }


                                                                          Можно, конечно, сказать, что && — скрытый оператор сравнения. Ну так, например, изначальный вариант автора поста на шаблонах — это, фактически, составное определение функции Haskell-style (отдельно для нуля, отдельно для всего остального, не помню уже, как именно оно называется в функциональных языках, нувыпонели), там тоже по-любому скрытый оператор сравнения (сравнить аргумент с нулём, по результатам выполнить либо то, либо это).
                                                                            0
                                                                            Давно не трогал руками C и C++, такой вариант первым пришел в голову:
                                                                            void print_a(int len){
                                                                            	cout << "\n===" << len << "\n";
                                                                            	float tmp = 5 / (len);
                                                                            	print_a(len - 1);
                                                                            }
                                                                            
                                                                            void handler(int a) {
                                                                            	exit (0);
                                                                            }
                                                                            
                                                                            int main ( ) {
                                                                            	int len = 100000;
                                                                            	signal(SIGFPE, handler);
                                                                            	print_a(len);
                                                                            	return 0;
                                                                            }
                                                                            


                                                                              0
                                                                              Только len нужно передавать по ссылке внутрь print_a, и не len-1, а len--.
                                                                                0
                                                                                Да, так будет даже лучше.
                                                                                Добавлено чуть позже — В смысле меньше локальных переменных вызвать. Но не факт что вообще лучше — все же по ссылке и с len-- мы будем менять переменную извне, что может быть не гуд. Можно и еще компактнее и надежнее(в память не упремся из-за рекурсии):
                                                                                void handler(int a) {
                                                                                	exit (0);
                                                                                }
                                                                                
                                                                                int main ( ) {
                                                                                	int len = 100000;
                                                                                	signal(SIGFPE, handler);
                                                                                	l1:
                                                                                		cout << "\n===" << len-- << "\n";
                                                                                		float tmp = 5 / len;
                                                                                	goto l1;
                                                                                }
                                                                                
                                                                                  0
                                                                                  А, тормознул, у вас же там рекурсия, там пофиг как передавать, зато можно зациклить внутри print_a через goto, все равно выход из цикла по сигналу.
                                                                              0

                                                                              Цикл for с тем же !!n, и нет сравнения ведь?


                                                                              for (int n = N; !!n; --n)
                                                                                printf("%d\n", n);
                                                                              printf("%d\n", 0);
                                                                              

                                                                              Можно было просто написать рекурсивную функцию


                                                                              void out(int n) {
                                                                                if (!n)
                                                                                  return;
                                                                                  printf("%d\n", n);
                                                                                out(n-1);
                                                                              }
                                                                              printf("%d\n", 0);

                                                                              Хвостовая рекурсия оптимизируется, и не будет никакой рекурсии в ассемблере.

                                                                                0
                                                                                Как же нет сравнения, если оно есть: godbolt.org/z/QAM3jR
                                                                                !n это то же самое, что n==0;

                                                                                А еще, среди целых чисел бывают такие, как -1, -2…
                                                                                0
                                                                                А что, с exception нельзя?
                                                                                int main()
                                                                                {
                                                                                   int n = 10;
                                                                                   try
                                                                                   {
                                                                                      while(1)
                                                                                      {
                                                                                         printf("%d\n", n);
                                                                                         n -= n / n;
                                                                                      }
                                                                                   }
                                                                                   catch(...){}
                                                                                   return 0;
                                                                                }
                                                                                
                                                                                  0
                                                                                  Не знаю как дела обстоят сейчас, но раньше такой код не работал. Точнее работал не так, как ожидается — при делении на ноль программа вылетала. Не отлавливается такое исключение — неопределенное поведение по стандарту.
                                                                                    0
                                                                                    Действительно, неопределенное поведение, но в VS 2008 почему-то прекрасно работает.
                                                                                    По-идее, при делении на 0, CPU должен сгенерировать INT 0 и windows должна завершить процесс.
                                                                                    Но этого не происходит.
                                                                                      0
                                                                                      Это исключение не определено, уберите обёртку из try catch и программа должна упасть.
                                                                                        0
                                                                                        У Вас в настройках преобразование SEH в C++ исключение стоит, скорее всего.
                                                                                    0
                                                                                    Так всё-таки C или C++?
                                                                                      0
                                                                                      Никто не предложил решение на макросах С в стиле boost.preprocessor. Стесняетесь?
                                                                                      #include <stdio.h>
                                                                                      #include "p99/p99.h"
                                                                                      
                                                                                      #define STARTVAL 10 
                                                                                      //Given explicitly since brackets block recursive macro expansion
                                                                                      //Sure that a couple more wraps can be derived from STARTVAL, but I'm too sleepy
                                                                                      #define NUMIT 11 //TODO
                                                                                      #define P00_DPRTINT(NAME, X, I) printf("%d\n",NAME-I)
                                                                                      
                                                                                      int main(void) {
                                                                                        P99_FOR(STARTVAL, NUMIT, P00_SEP, P00_DPRTINT);
                                                                                        return 0;
                                                                                      }

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

                                                                                        В нем ответ:
                                                                                        1. Есть основная программа и есть функция печати, где можно делать, что угодно;
                                                                                        2. Ограничений на язык нет;
                                                                                        3. Я бы приравнял исключение возбуждаемое делением на 0 к неявному сравнению, выполняемому ЦПУ аппаратно.

                                                                                        В целом задача на сообразительность, не на знание языка, просто посмотреть как человек мыслит, что делает в нестандартной ситуации в сложной ситуации, работает ли на результат.
                                                                                          0
                                                                                          Еще варианты над которыми я думал:
                                                                                          1. вместо рекурсии — порождать новый процесс, передавать ему хендл на ту же консоль, а текущий процесс завершать
                                                                                          2. примерно то же самое можно попробовать с потоками, но я чет зафейлил задачу по join-у thread из следующего в цепочке (но вроде формально это не запрещено).
                                                                                          Т.о. цикл будет за счет средств порождения нового потока/процесса.
                                                                                          Хз насколько это соответствует условию «нет скрытых условий», ибо в ОС этих условий дофига, но в коде программы вроде как и нет

                                                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                          Самое читаемое