Добро пожаловать! Это — архивная версия форумов на «Хакер.Ru». Она работает в режиме read-only.
 
журналы новости статьи video форум подписка на «Хакер»

Задача: минимум двух чисел

Пользователи, просматривающие топик: none

Зашли как: Guest
Все форумы >> [Компилируемые языки] >> Задача: минимум двух чисел
Имя
Сообщение << Старые топики   Новые топики >>
Задача: минимум двух чисел - 2010-11-01 06:18:01.306666   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
 На разминочку.
Написать функцию нахождения минимального из двух чисел, то есть функцию min(x, y), принтмающую два аргумента и возвращающую тот из них, который меньше другого. Есть только одно условие: не использовать операторов ветвления, то есть никаких if, while, for и т.д.
Развлекайтесь ;)
Post #: 1
RE: Задача: минимум двух чисел - 2010-11-01 10:01:04.210000   
ShyRka

Сообщений: 235
Оценки: 0
Присоединился: 2010-07-09 10:55:56.626666
 а если так)) когда меньше 0, больше 1 :)
int min(int x,int y) { return (x&lt;y); }

Ну еще так ( но наверно так нельзя )8D
int min (int x, int y) { return x&lt;y ? x:y; }
Post #: 2
RE: Задача: минимум двух чисел - 2010-11-01 10:46:01.330000   
katangawise

Сообщений: 23
Оценки: 0
Присоединился: 2010-02-14 16:27:58.953333
 Привет!
Написал на C#:

int min(int a, int b)
{
int[] arr = new int[2];
int index = 0;
arr[0] = a;
arr[1] = b;
index = Convert.ToInt32(a >= b);
return arr[index];
}
Post #: 3
RE: Задача: минимум двух чисел - 2010-11-01 16:57:07.413333   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: ShyRka

а если так)) когда меньше 0, больше 1 :)
int min(int x,int y) { return (x&lt;y); }


Вернёт true или false, а не минимальное из двух чисел.

quote:

ORIGINAL: ShyRka

Ну еще так ( но наверно так нельзя )8D
int min (int x, int y) { return x&lt;y ? x:y; }

Конечно нельзя, однострочные условные операторы - это всё ещё условные операторы ;)
Post #: 4
RE: Задача: минимум двух чисел - 2010-11-01 17:00:14.590000   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: katangawise

int min(int a, int b)
{
int[] arr = new int[2];
int index = 0;
arr[0] = a;
arr[1] = b;
index = Convert.ToInt32(a &gt;= b);
return arr[index];
}

Уже лучше. А без использования дополнительной памяти сможешь?
Post #: 5
RE: Задача: минимум двух чисел - 2010-11-01 17:10:19.480000   
katangawise

Сообщений: 23
Оценки: 0
Присоединился: 2010-02-14 16:27:58.953333
 Please:

int min(int a, int b)
{
return ( (a+b) - ABS(a-b) ) / 2; //ABS - absolut —> |a-b|
}
Post #: 6
RE: Задача: минимум двух чисел - 2010-11-01 17:49:07.120000   
ShyRka

Сообщений: 235
Оценки: 0
Присоединился: 2010-07-09 10:55:56.626666
quote:

ORIGINAL: katangawise

Please:

int min(int a, int b)
{
return ( (a+b) - ABS(a-b) ) / 2; //ABS - absolut —&gt; |a-b|
}

Хех … реально .. вот мля завтикал :))
++ тебе :)
Post #: 7
RE: Задача: минимум двух чисел - 2010-11-01 19:06:22.470000   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: katangawise

int min(int a, int b)
{
return ( (a+b) - ABS(a-b) ) / 2; //ABS - absolut —&gt; |a-b|
}

Отлично. Ещё варианты? :)
Post #: 8
RE: Задача: минимум двух чисел - 2010-11-01 19:35:43.866666   
Sрam

Сообщений: 2863
Оценки: 372
Присоединился: 2009-01-16 15:23:43.276666
quote:

ORIGINAL: kreol

quote:

ORIGINAL: katangawise

int min(int a, int b)
{
return ( (a+b) - ABS(a-b) ) / 2; //ABS - absolut —&gt; |a-b|
}

Отлично. Ещё варианты? :)

Что характерно она еще и с вещественным типом данных легко работает.
+1

PS Креол давай еще че-нить для разминки)
Post #: 9
RE: Задача: минимум двух чисел - 2010-11-01 20:08:02.706666   
katangawise

Сообщений: 23
Оценки: 0
Присоединился: 2010-02-14 16:27:58.953333
 И на последок (уже голова болит) :), еще одно решение:

int min(int a, int b)
{
int x = a-b;
x=x>>(sizeof(int)-1);
return (x*a+(1-x)*b);
}

Это, помоему, самое изящное…
Но если бы спросили на интервью, я бы ответил первым способом с arr[index]..
Больше опыта в C# просто :))
Post #: 10
RE: Задача: минимум двух чисел - 2010-11-02 01:34:41.620000   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: katangawise

int min(int a, int b)
{
int x = a-b;
x=x&gt;&gt;(sizeof(int)-1);
return (x*a+(1-x)*b);
}

Немного запутано, но похоже да, должно работать. И ты снова срываешь банк :)
Post #: 11
RE: Задача: минимум двух чисел - 2010-11-02 02:03:23.533333   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
 .globl min min: cmpl %edi, %esi movl %edi, %eax cmovle %esi, %eax ret Конвенция вызова amd64, то есть аргументы в %edi и %esi.
Post #: 12
RE: Задача: минимум двух чисел - 2010-11-02 06:13:23.990000   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: rgo

.globl min min: cmpl %edi, %esi movl %edi, %eax cmovle %esi, %eax ret

Читерство! Я, конечно, понимаю, что с чисто формальной точки зрения оператора ветвления здесь нет, но всё-таки давай в том числе и без условно выполняемых операций вроде cmovle? ;)
Post #: 13
RE: Задача: минимум двух чисел - 2010-11-02 15:04:16.906666   
Genco

Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
 double a,b,ans; cin &gt;&gt; a; cin &gt;&gt; b; ans= ((int)(a&lt;=b) )*a + ((int)(a&gt;b) )*b; cout &lt;&lt; ans&lt;&lt; endl; Не уверен,что всё корректно, но…
Post #: 14
RE: Задача: минимум двух чисел - 2010-11-02 15:28:30.033333   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: Genco

double a,b,ans; cin &gt;&gt; a; cin &gt;&gt; b; ans= ((int)(a&lt;=b) )*a + ((int)(a&gt;b) )*b; cout &lt;&lt; ans&lt;&lt; endl; Не уверен,что всё корректно, но…

Покатит, я думаю. Но я бы сделал чуть иначе, надо избавиться от тормозного умножения:int tmp = ((a &lt;= b) - 1); return (~tmp & a) + (tmp & b);
Post #: 15
RE: Задача: минимум двух чисел - 2010-11-03 22:00:34.023333   
kreol

Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
quote:

ORIGINAL: Genco

double a,b,ans; cin &gt;&gt; a; cin &gt;&gt; b; ans= ((int)(a&lt;=b) )*a + ((int)(a&gt;b) )*b; cout &lt;&lt; ans&lt;&lt; endl;

По сути, то же самое решение, что было на C# у katangawise.
Post #: 16
RE: Задача: минимум двух чисел - 2010-11-05 23:40:23.880000   
Sunzer

Сообщений: 253
Оценки: 31190
Присоединился: 2007-06-15 19:23:32.436666
 Я так понял эти задачи нужны только для развития математических способностей?

Скорость исполнения, или размер кода ведь не уменьшится.
Post #: 17
RE: Задача: минимум двух чисел - 2010-11-06 00:05:25.520000   
Genco

Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
 Не, ну почему. Избавиться от лишних условных переходов - это полноценная оптимизация, особенно если грамотно избавляться.
Post #: 18
RE: Задача: минимум двух чисел - 2010-11-06 00:11:53.873333   
Sunzer

Сообщений: 253
Оценки: 31190
Присоединился: 2007-06-15 19:23:32.436666
 От одного условного перехода, заместо кучи арифметических операций, ты таким образом что оптимизируешь, про размер понятно что нет, а про скорость я готов поспорить даже, хотя чистый экспиремент не поставишь.
Post #: 19
RE: Задача: минимум двух чисел - 2010-11-06 00:29:16.710000   
disCoverall

Сообщений: 32
Оценки: 0
Присоединился: 2010-10-31 00:43:50.613333
 с самого начал просто ввести числа в функцию Add() и все
Post #: 20
RE: Задача: минимум двух чисел - 2010-11-06 01:08:35.916666   
Genco

Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
quote:

От одного условного перехода, заместо кучи арифметических операций, ты таким образом что оптимизируешь, про размер понятно что нет, а про скорость я готов поспорить даже, хотя чистый экспиремент не поставишь.
Ну вот в лучшем из вариантов katangawise этих самых операций всего ~4. *кстати да, клевое решение* А If внутри циклов - это всегда проседающая скорость. Не скажу что при любом раскладе, но ,наверняка, заменить в определенных случаях будет производительнее.
Post #: 21
RE: Задача: минимум двух чисел - 2010-11-06 02:17:02.566666   
_SaZ_

Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
 Проседание скорости в условных операторах вещь очень вероятностная. Скорость ведь проседает не из-за самой проверки условия, а из-за того, что устройство предсказания ветвлений не справилось (не угадало) и процессору приходится заново загружать в кэш команды из другой ветки условного оператора.
Post #: 22
RE: Задача: минимум двух чисел - 2010-11-06 02:32:49.423333   
Sunzer

Сообщений: 253
Оценки: 31190
Присоединился: 2007-06-15 19:23:32.436666
quote:

ORIGINAL: _SaZ_

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

Вот вот, я про это и думал когда свой пост выше писал.
Post #: 23
RE: Задача: минимум двух чисел - 2010-11-06 02:38:26.780000   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
 Когда знание способа сосчитать минимум без условий будет полезно – действительно тайна покрытая мраком. Ведь, в данном случае, вариант с if – самый лучший. Поскольку компилятор (по-крайней мере gcc -O2) компилирует его в код, аналогичный тому, что привёл я, а это, имхо, наибыстрейший из возможных. И решение с if'ом, в отличие от моего примера, кроссплатформенно. И кроме того понятно, читабельно для любого программиста владеющего любым C-like языком.

Так что решение данной задачи, пожалуй, – это действительно задачка для развития математических способностей. Или не математических: ведь для решения её, надо мыслить алгоритмически. Никто не знает, где она грань между теорией-математикой и практикой-программированием.
Post #: 24
RE: Задача: минимум двух чисел - 2010-11-06 02:42:17.406666   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: _SaZ_
Проседание скорости в условных операторах вещь очень вероятностная. Скорость ведь проседает не из-за самой проверки условия, а из-за того, что устройство предсказания ветвлений не справилось (не угадало) и процессору приходится заново загружать в кэш команды из другой ветки условного оператора.

В случае написания функции min, мы можем предполагать, что a будет меньше b в 50% случаев, так? Значит процессор будет угадывать правильно в 50% случаев. В другой половине случаев, он будет сбрасывать конвейер и заполнять его снова. Процессорный предсказатель ведь очень туп: он считает что если переход назад, то он выполнится, если же вперёд, то он не выполнится. Может современные процессоры ещё и кешируют предыдущие результаты, но в данной ситуации типа 50/50 это не поможет ни коим образом.

upd. Я тут подумал слегка, и честно говоря – чёрть его знает. Заполнение конвейера современного процессора должно быть очень долгой процедурой: конвейер-то длинный. Половина этого времени, конечно же меньше, но… Короче я отказываюсь верить без доказательств в утверждения о том, что использование условного перехода будет быстрее.
Post #: 25
RE: Задача: минимум двух чисел - 2010-11-06 02:45:57.450000   
_SaZ_

Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
 rgo, задача хороша именно, чтобы начинать тренировать мозг. Мне на собеседовании, недавно, для разминки, попросили написать рекурсивное нахождение факториала, с прототипом void fact( int_type * n );. Практической пользы никакой, но соображалка шевелиться начинает. Не все с ходу решат.

А про нахождение минимума - вопрос уже скорее для области применения. Если критично быстродействие - то тогда стоит загоняться (и хорошо комментировать код), в противном же случае - однозначно if.
Post #: 26
RE: Задача: минимум двух чисел - 2010-11-06 02:49:33.913333   
_SaZ_

Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
quote:

ORIGINAL: rgo
В случае написания функции min, мы можем предполагать, что a будет меньше b в 50% случаев, так? Значит процессор будет угадывать правильно в 50% случаев.

Так, только практический процент успешных угадываний будет повыше. Если верить интернетам - то с современными процессорами будет под 90%. Статическое предсказание примитивно.
Post #: 27
RE: Задача: минимум двух чисел - 2010-11-06 03:04:27.853333   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: _SaZ_
quote:

ORIGINAL: rgo
В случае написания функции min, мы можем предполагать, что a будет меньше b в 50% случаев, так? Значит процессор будет угадывать правильно в 50% случаев.

Так, только практический процент успешных угадываний будет повыше. Если верить интернетам - то с современными процессорами будет под 90%. Статическое предсказание примитивно.

Неа. 90% это по всему коду. Который где-то соптимизирован компилятором, чтобы лучше предсказывалось, где-то программист подсказал компилятору, что "условие будет скорее истинным чем ложным". 90% это с учётом циклов, которые в конце тела имеют условный перехо назад, который процессором однозначно предсказывается как "скорее да, чем нет".
А в данном конкретном случае больше 50% вероятности не получить. Если только программист не будет располагать аргументы min при вызове так, чтобы повлиять на вероятность. Но и это не всегда возможно.
Post #: 28
RE: Задача: минимум двух чисел - 2010-11-06 03:33:21.906666   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: _SaZ_
rgo, задача хороша именно, чтобы начинать тренировать мозг. Мне на собеседовании, недавно, для разминки, попросили написать рекурсивное нахождение факториала, с прототипом void fact( int_type * n );. Практической пользы никакой, но соображалка шевелиться начинает. Не все с ходу решат.

Думал-думал, но не понял: а в чём подвох? Имея указатель вместо передачи по значению, легко перейти именно к значению:void fact( int_type * n ) { int_type arg = *n; return fact (&arg - 1) * arg; } Или там какая-то хитрость, типа не создавая локальной переменной, чтобы по сравнению с классическом рекурсивным факториалом, расход стека был бы в два раза меньше?
Post #: 29
RE: Задача: минимум двух чисел - 2010-11-06 13:42:11.576666   
_SaZ_

Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
 Не не, почти так, только тип возвращаемого void и не нужно от адреса локальной переменной отнимать значение, а нужно декрементить *n.
Задача простая, но нетривиальная. Самое то для собеседований. Более просто можно решить при помощи статической переменной, попутно рассказав, что это решение будет однопоточным.
Просто Беларусь становится аутсорсной страной и средний скилл С++ программистов, особенно свежевыпущенных оставляет желать лучшего (не все всегда справляются). Но это отдельная тема.
Post #: 30
RE: Задача: минимум двух чисел - 2010-11-06 16:06:07.790000   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: _SaZ_
Не не, почти так, только тип возвращаемого void

А. Точно. Не обратил внимания.
Post #: 31
RE: Задача: минимум двух чисел - 2010-11-08 08:48:06.180000   
dimonix6

Сообщений: 11
Оценки: 0
Присоединился: 2010-11-08 08:44:44.413333
 int min(int a, int b)
{
    int m;

    a < b && (m = a);
    a > b && (m = b);

    return m;
}
Post #: 32
RE: Задача: минимум двух чисел - 2010-11-08 09:14:10.720000   
rgo

Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
quote:

ORIGINAL: dimonix6
int min(int a, int b)
{
   int m;

   a &lt; b && (m = a);
   a &gt; b && (m = b);

   return m;
}

А если a==b, то твоя функция вернёт неопределённое значение. ;)
Post #: 33
RE: Задача: минимум двух чисел - 2010-11-09 03:38:12.726666   
nicea

Сообщений: 25
Оценки: 0
Присоединился: 2009-05-09 19:41:22.990000
 Только сейчас заметил что такой вариант уже был. Жаль…

#include &lt;stdio.h&gt; int min(int a,int b) { return a*(a&lt;b)+b*(b&lt;a)+a*(a==b); } int main() { printf("%i",min(7,2)); return 0; }
Post #: 34
Страниц:  [1]
Все форумы >> [Компилируемые языки] >> Задача: минимум двух чисел







Связаться:
Вопросы по сайту / xakep@glc.ru

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