Comments 95
Интересное решение, хотя при использовании 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;
}UFO just landed and posted this here
Проблема в том, что в С нет исключений, т.е. Ваш код не компилируется. Но даже и в C++, где есть исключения, деление на ноль — UB и может не бросать исключений (обычно и не бросает)
Мы не знаем условий задачи. А раз не знаем, то почему мы должны ограничиваться стандартом? SEH на Windows, и сигналы на Linux должны дать требуемый результат. В реальных проектах такого использовать, конечно же, нельзя, но почему на идиотскую задачу нельзя дать соответствующий ответ?
UFO just landed and posted this here
Выражение !!n — это и есть неявное сравнение n==0. А циклы по условию задачи никто использовать не запрещал, так что если предположить, что разрешено !!n — можно написать
while( !!n ) printf( "%d ", n-- );while( n ) printf( "%d ", n-- );
Но в while-то тоже происходит неявное сравнение.
Более того, что подразумевается под «реализация функции вывода на печать не в счет»?
Предлагается ещё реализовать функцию отрисовки что ли? Если нет, то тогда в чём вообще проблема? В функции, осуществляющей печать, можно делать что угодно.
Более того, что подразумевается под «реализация функции вывода на печать не в счет»?
Предлагается ещё реализовать функцию отрисовки что ли? Если нет, то тогда в чём вообще проблема? В функции, осуществляющей печать, можно делать что угодно.
С каких пор в циклах не происходит сравнения?
Странно
Странно
UFO just landed and posted this here
В 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;
}
Дорогие друзья, это задание пришло ко мне так же как и к Вам, поэтому не могу дать ему более внятные разъяснения чем понял сам. Я рассудил так, что в самом коде получения числа и выбор ветки кода не должно встречаться условных операторов т.е. if, for, while, do...while(скрытые операторы) и т.д., а вот за код отвечающий за печать (внутренности printf и пр.) мы не отвечаем.
Если бы можно было использовать for, while и прочее, то задачи бы не было.
Если бы можно было использовать for, while и прочее, то задачи бы не было.
А почему нельзя for? Ведь в виде for(;;) это всё равно, что goto label: скрытого сравнения нет, явного тоже нет.
Я полагаю, что в данном случае 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--); ).
Условие «реализация функции вывода на печать не в счет» подразумевает, что ее возвращаемое значение тоже часть реализации и можно использовать саму функцию printf как условие.
Однако тут используется цикл с условием. Если брать в широком смысле, то так или иначе задача не решаема без цикла или рекурсии, но рекурсия ограничена. Если исключить любое сравнение то подходит только бесконечный цикл.
Прервать его можно следующими способами:
1. break
2. return из main фунции
3. Бросить исключение
4. goto
5. Функция exit() или ее аналоги
Первые четыре варианта требуют какого то условия что бы не выйти из цикла раньше чем нужно, а это неизбежное сравнение. Остается только четвертый вариант, в комментариях уже оставляли подобный пример, вот мой:
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;
}
#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);
}
}
Вообще, вызов func[(int)(bool)i](i) должен работать куда лучше этого странного кода. Но идея вполне здравая.
А разве (bool)i не является неявным сравнением?
Нет, это тайпкаст. Да, мы здесь пользуемся тем, что ((bool)i == true) === (i != 0), но сравнением это не является, мало того, даже при трансляции этого куска в асм в коде может не оказаться jz/jnz (например, четыре раза вызвать popcnt eax, eax приведет к переводу любого не-нуля в 1, хотя скорее всего код будет похож на or eax, eax; jz всторону; inc ebx и дальше).
да exit(0) пожалуй здравое решение. В остальном это тоже решение. Спасибо.
Добавим чуть фантазии и дотошности, вместо "!!" вспомним математику:
Куда слать резюме?
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--);
}Куда слать резюме?
Подход с шаблонами сразу не прокатит, т.к. нужно знать n именно во время компиляции. А если мы знаем n во время компиляции, то мы просто можем написать
Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании), поэтому давать её на собеседовании, конечно, можно, но ИМХО только в случае собеседования в клуб извращенцев.
print(n--);Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу
Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании), поэтому давать её на собеседовании, конечно, можно, но ИМХО только в случае собеседования в клуб извращенцев.
UFO just landed and posted this here
отличный вариант. я думаю лучший.
PS для тех кто не понял, преобразования к отрицательному будет давать в старшем бите 1 в любом случае кроме того когда изначальное значение 0. Следовательно, сдвинут на (8*sizeof(n)-1) мы получим либо 0 в случае когда изначально был 0 либо 1 в случае любого другого числа. Дальше просто при вызове «нулевой» функции делаем exit.
PS для тех кто не понял, преобразования к отрицательному будет давать в старшем бите 1 в любом случае кроме того когда изначальное значение 0. Следовательно, сдвинут на (8*sizeof(n)-1) мы получим либо 0 в случае когда изначально был 0 либо 1 в случае любого другого числа. Дальше просто при вызове «нулевой» функции делаем exit.
Спасибо. exit(0) — делает все гораздо более элегантным, но в остальном это решение того же качества, оно не дает ничего нового. Это тот же метод. Но все равно спасибо за улучшение.
Есть новый подход в честь наступающей пятницы, моего провала с while() и тяги к прекрасному:
* без выделения памяти и конструирования объектов
* без exit(), чтобы не нарушать красивый ход исполнения кода
* без функторов и ограничения глубины рекурсии
* без явных и неявных сравнений включая, но не ограничиваясь: приведения к bool, operator!(), и всякие cmovz / jcxz в ассемблерном коде.
Тестировал на msvc 2017 Win7, debug и release сборки, на n = -3, 0, 3, 1000, ...;
Вдохновлялся кодом masterspline
* без выделения памяти и конструирования объектов
* без 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
Не работает для отрицательных N.
мой вариант: https://godbolt.org/z/aPF4HE
заодно можно посмотреть на наличие неявных сравнений уже в сгенерированном коде.
*всегда буду читать комментарии
Без сравнений — хорошо, код будет только описан, и работать мы будем в BareMetal x86, ну или под ДОСом, или в Ring-0
1) Пишем свой обработчик на ошибку division by zero, оный должен увеличить сохраненный адрес возврата на длину команд присваивания, деления и безусловного перехода(надо посмотреть в листинге)
2) Закидываем его в таблицу прерываний
3) Далее адов говнокод:
Задачей обработчика деления на ноль будет перепрыгнуть через goto. И никаких сравнений тут вообще нигде не будет делаться.
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. И никаких сравнений тут вообще нигде не будет делаться.
Я бы написал так
Программа напечатает числа от N до 0, а потом прекратит работу.
begin:
print(N);
N=N/N*(N-1);
goto begin;
Программа напечатает числа от N до 0, а потом прекратит работу.
удалено
g_functors!!n;
Разве! не нарушает требования об отсутствии скрытых сравнений? В! ведь присутствует сравнение.
Можно добавить немного С++
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();
}И на шаблонах тоже можно для любого 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;
}
С++ без извращений
динамическое выделения памяти, чтобы обойти ограничение по стеку
static не разрешит задавать размер динамичски
#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 не разрешит задавать размер динамичски
Придумал С++ решение без реального выделения памяти и без ограничений по размеру
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];
}
На самом деле, «скрытая» проверка условий таки есть — в реализации оператора new. тут вопрос к применимости исходного ограничения — где таки можно иметь эти самые сравнения — в коде генерации самого компилятора? рантайма? стандартной библиотеки?
А то я тоже могу просто написать std::transform(nullptr, nullptr + n, (ничего не делающий output it), (функция вывода))
(но за хак я плюс поставил)
А то я тоже могу просто написать std::transform(nullptr, nullptr + n, (ничего не делающий output it), (функция вывода))
(но за хак я плюс поставил)
UFO just landed and posted this here
Удалено.
Спасибо за решение.
Почти 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;
}
UFO just landed and posted this here
Сразу подумал, что на С++ элементарно, а вот на С нужно подумать. Но вижу, что все пишут на плюсах, поэтому мой вариант:
#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;
}
Это мой вариант, но тут ограничение по памяти — лучше память вообще не выделять, как здесь.
#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;
}
Если уж использовать С++, то все проще некуда.
int main()
{
const int n = 10;
int count = n;
std::generate_n(std::ostream_iterator(std::cout, " "), n, [&count]() { return count--; });
return 0;
}
Если уж падать в stack overflow, то зачем так переусложнять? Почему просто не написать что-то вроде:
Можно, конечно, сказать, что && — скрытый оператор сравнения. Ну так, например, изначальный вариант автора поста на шаблонах — это, фактически, составное определение функции Haskell-style (отдельно для нуля, отдельно для всего остального, не помню уже, как именно оно называется в функциональных языках, нувыпонели), там тоже по-любому скрытый оператор сравнения (сравнить аргумент с нулём, по результатам выполнить либо то, либо это).
int prt(int n)
{
std::cout << n << "\t";
return n && prt(n - 1);
}Можно, конечно, сказать, что && — скрытый оператор сравнения. Ну так, например, изначальный вариант автора поста на шаблонах — это, фактически, составное определение функции Haskell-style (отдельно для нуля, отдельно для всего остального, не помню уже, как именно оно называется в функциональных языках, нувыпонели), там тоже по-любому скрытый оператор сравнения (сравнить аргумент с нулём, по результатам выполнить либо то, либо это).
Давно не трогал руками 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;
}
Только len нужно передавать по ссылке внутрь print_a, и не len-1, а len--.
Да, так будет даже лучше.
Добавлено чуть позже — В смысле меньше локальных переменных вызвать. Но не факт что вообще лучше — все же по ссылке и с len-- мы будем менять переменную извне, что может быть не гуд. Можно и еще компактнее и надежнее(в память не упремся из-за рекурсии):
Добавлено чуть позже — В смысле меньше локальных переменных вызвать. Но не факт что вообще лучше — все же по ссылке и с 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;
}
Цикл 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);Хвостовая рекурсия оптимизируется, и не будет никакой рекурсии в ассемблере.
Как же нет сравнения, если оно есть: godbolt.org/z/QAM3jR
!n это то же самое, что n==0;
А еще, среди целых чисел бывают такие, как -1, -2…
!n это то же самое, что n==0;
А еще, среди целых чисел бывают такие, как -1, -2…
А что, с exception нельзя?
int main()
{
int n = 10;
try
{
while(1)
{
printf("%d\n", n);
n -= n / n;
}
}
catch(...){}
return 0;
}
Не знаю как дела обстоят сейчас, но раньше такой код не работал. Точнее работал не так, как ожидается — при делении на ноль программа вылетала. Не отлавливается такое исключение — неопределенное поведение по стандарту.
Так всё-таки C или C++?
Никто не предложил решение на макросах С в стиле boost.preprocessor. Стесняетесь?
p99 library
#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
Читаем задание внимательно: Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет).
В нем ответ:
1. Есть основная программа и есть функция печати, где можно делать, что угодно;
2. Ограничений на язык нет;
3. Я бы приравнял исключение возбуждаемое делением на 0 к неявному сравнению, выполняемому ЦПУ аппаратно.
В целом задача на сообразительность, не на знание языка, просто посмотреть как человек мыслит, что делает в нестандартной ситуации в сложной ситуации, работает ли на результат.
В нем ответ:
1. Есть основная программа и есть функция печати, где можно делать, что угодно;
2. Ограничений на язык нет;
3. Я бы приравнял исключение возбуждаемое делением на 0 к неявному сравнению, выполняемому ЦПУ аппаратно.
В целом задача на сообразительность, не на знание языка, просто посмотреть как человек мыслит, что делает в нестандартной ситуации в сложной ситуации, работает ли на результат.
Еще варианты над которыми я думал:
1. вместо рекурсии — порождать новый процесс, передавать ему хендл на ту же консоль, а текущий процесс завершать
2. примерно то же самое можно попробовать с потоками, но я чет зафейлил задачу по join-у thread из следующего в цепочке (но вроде формально это не запрещено).
Т.о. цикл будет за счет средств порождения нового потока/процесса.
Хз насколько это соответствует условию «нет скрытых условий», ибо в ОС этих условий дофига, но в коде программы вроде как и нет
1. вместо рекурсии — порождать новый процесс, передавать ему хендл на ту же консоль, а текущий процесс завершать
2. примерно то же самое можно попробовать с потоками, но я чет зафейлил задачу по join-у thread из следующего в цепочке (но вроде формально это не запрещено).
Т.о. цикл будет за счет средств порождения нового потока/процесса.
Хз насколько это соответствует условию «нет скрытых условий», ибо в ОС этих условий дофига, но в коде программы вроде как и нет
Вариант с указателями на функции:
Вариант с циклом без проверок:
typedef void (*func_t)(void);
void fex(){printf("0\n"); exit(0);}
void fvd(){}
int main(){
func_t arr[2] = {fex, fvd};
int n=10;
while(1){
printf("%i ", n);
n--;
arr[!!n]();
}
printf("\n");
}Вариант с циклом без проверок:
int main(){
int n=10;
while(1){
printf("%i ", n);
n--;
n || ({break;n=0;});
}
}На С, без плюсов и извращений.
#include "stdio.h"
int print_number(int n)
{
printf("%d ", n);
return (n && print_number(n - 1));
}
int main(void)
{
return print_number(100000);
}
Вот так работает точно
Зачтется?
int ex()
{
exit(0);
}
int main()
{
int i = 1000;
while(1)
{
printf("%d\n", i);
i || ex();
i --;
}
return 0;
}Зачтется?
Может как-то так?
#include <iostream>
typedef void(*Func)(int);
void printValue(int32_t value) {
std::cout << value << std::endl;
}
void end(int32_t value) {
exit(0);
}
int main()
{
int32_t N = 100;
Func funcs[] = {printValue, end};
begin:
funcs[((uint32_t)N) >> 31](N);
N--;
goto begin;
}
На Си:
void printntoz( unsigned int n )
{
Repeat:
printf("%u ", n);
n--;
switch( n >> sizeof(int) * 8 - 1 )
{ case 0: goto Repeat;
case 1: goto End;
}
End:{}
}
Ну если задача именно не использовать операторы сравнения то почему нельзя просто сделать в цикле?
int main() {
int n = 1234;
while(n)
printf("%d\n", n--);
printf("0");
return 0;
}
Sign up to leave a comment.
Интересная задачка на С