ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / максимум без if
23 сообщений из 98, страница 4 из 4
  4  все
максимум без if
    #38814302
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
andreymxнапомните, есть ли алгоритм вычисления максимума из двух чисел без if

вычислить разность двух чисел и поверить знак результата.
...
Рейтинг: 0 / 0
23.11.2014, 09:51
| Ответить | Цитировать | Написать  
максимум без if
    #38814351
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Вася Уткин,

Походу нашелся победитель с правильным решением :)
...
Рейтинг: 0 / 0
23.11.2014, 12:54
| Ответить | Цитировать | Написать  
максимум без if
    #38814364
Вася Уткин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вася Уткин
Гость
Anatoly MoskovskyВася Уткин,

Походу нашелся победитель с правильным решением :)
Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?
...
Рейтинг: 0 / 0
23.11.2014, 13:32
| Ответить | Цитировать | Написать  
максимум без if
    #38814368
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
White OwlМожет вас смущает то что "ассемблером" называют и программу которая переводит из мнемоники в машинные кода? Но эта программа по существу и есть компилятор.
Нет, эта программа по существу не есть компилятор. Она есть по существу транслятор. Надеюсь, разницу объяснять не надо.
...
Рейтинг: 0 / 0
23.11.2014, 13:39
| Ответить | Цитировать | Написать  
максимум без if
    #38814374
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Вася УткинЯ только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?
Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.
...
Рейтинг: 0 / 0
23.11.2014, 13:53
| Ответить | Цитировать | Написать  
максимум без if
    #38814381
Вася Уткин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вася Уткин
Гость
Anatoly MoskovskyВася УткинЯ только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?
Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.
Значит я угадал :)
Но обращение к кэшу L1 все равно будет дольше, чем переходы jg/jl, так что с практической точки зрения это мало имеет смысла. В обоих случаях в конвейере не получится внеочередное выполнение команд завязанных на результат такого сравнения - только в случае с массивом потеряем ещё несколько тактов на обмен с L1.

А других вариантов решения не знаете случайно?
...
Рейтинг: 0 / 0
23.11.2014, 14:15
| Ответить | Цитировать | Написать  
максимум без if
    #38814393
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Вася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)
...
Рейтинг: 0 / 0
23.11.2014, 14:49
| Ответить | Цитировать | Написать  
максимум без if
    #38814476
Вася Уткин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вася Уткин
Гость
Aleksandr SharahovВася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)
А что такое ord? :)


Получается что-то типа:
http://ideone.com/1zCiYa
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
#include <iostream>
#include <cstdlib>
using namespace std;

inline constexpr int func(int a, int b) {
	return a + ((b-a) & ((unsigned)(a>b) - 1));
}
 

int main() {
	
	cout << func(5, 4);
	
	cout << endl << func(rand()%10, rand()%10);
	
	// your code goes here
	return 0;
}



Причем, 1-й раз в compile-time отработает, даже в C++11(не 14), а второй раз в run-time без jump-ов.
...
Рейтинг: 0 / 0
23.11.2014, 17:59
| Ответить | Цитировать | Написать  
максимум без if
    #38814660
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Вася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)
...
Рейтинг: 0 / 0
24.11.2014, 00:38
| Ответить | Цитировать | Написать  
максимум без if
    #38814667
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskyВася Уткин,

Походу нашелся победитель с правильным решением :)

нет, там есть сравнение, причём явное.

Anatoly Moskovsky
Сорри, приз переходит к Aleksandr Sharahov :)
а знак больше это не if разве ?


Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)
...
Рейтинг: 0 / 0
24.11.2014, 01:48
| Ответить | Цитировать | Написать  
максимум без if
    #38814706
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryа знак больше это не if разве ?
Нет конечно. Там же нет ветвления.
...
Рейтинг: 0 / 0
24.11.2014, 06:49
| Ответить | Цитировать | Написать  
максимум без if
    #38814709
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryнет, там есть сравнение, причём явное.

Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)
Поясню. Сравнение - это просто вычитание, а вовсе не if где требуется проверка на 0 и условный переход.
Таким образом в коде который предложил Aleksandr Sharahov есть операции "-", "+", "&".
А в вашем коде есть в разных его вариантах были операция * и даже % которые медленнее на порядки.

Если сравнивать алгоритмы по скорости выполнения (а других причин для такого идиотского условия задачи нет) то самый быстрый будет код от Aleksandr Sharahov.
...
Рейтинг: 0 / 0
24.11.2014, 07:07
| Ответить | Цитировать | Написать  
максимум без if
    #38814711
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SSmiksoftПридумать-то можно, но зачем?

Псевдокод:
Код: sql
1.
2.
3.
4.
5.
6.
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}

sign можно реализовать без if, например, сдвигами и бинарными операциями.

тогда уже
Код: plaintext
1.
 a*sign[a-b]+b*(1-sign[a-b]);


так читабельней.


Чем тогда плох этот пример(приводил его намного раньше) ? Выше псевдокод и использованием нотации Айверсона, присутствующей в Си/С++ по умолчанию, вот код на С++.
Код: plaintext
1.
int max=a*(a>b)+b*(1-(a>b));
...
Рейтинг: 0 / 0
24.11.2014, 07:16
| Ответить | Цитировать | Написать  
максимум без if
    #38814712
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly Moskovsky,

не знал что операция сравнения это разность.
Но тем не менее, позже был показан вариант включающий только & >> и +, без умножения и %
...
Рейтинг: 0 / 0
24.11.2014, 07:24
| Ответить | Цитировать | Написать  
максимум без if
    #38814716
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryЧем тогда плох этот пример
Я не говорю что он плох. Я говорю что есть лучше :)
...
Рейтинг: 0 / 0
24.11.2014, 07:47
| Ответить | Цитировать | Написать  
максимум без if
    #38814721
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

Код: plaintext
1.
2.
int t=a>b;
nt max=a&t+b&(1-t);



мне эти ord непонятны, поверю вам, лучше так лучше :)
...
Рейтинг: 0 / 0
24.11.2014, 07:58
| Ответить | Цитировать | Написать  
максимум без if
    #38814736
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryмне эти ord непонятны, поверю вам, лучше так лучше :)
Не надо мне верить.
Я же не проверял экспериментом :)

А ord это просто приведение типа к числу.
...
Рейтинг: 0 / 0
24.11.2014, 08:41
| Ответить | Цитировать | Написать  
максимум без if
    #38814751
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Развели тут длинное обсуждение, а при этом современный компилятор сгенерирует код для такого "if(a) b=c" без условных переходов, используя conditional move
...
Рейтинг: 0 / 0
24.11.2014, 09:12
| Ответить | Цитировать | Написать  
максимум без if
    #38815019
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryAnatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

Код: plaintext
1.
2.
int t=a>b;
nt max=a&t+b&(1-t);



мне эти ord непонятны, поверю вам, лучше так лучше :)
Это из Паскалей . ИМХО.

Автор некисло вбросил навоза на реактивную турбину. Он в сабже не указал язык
программирования. Перечислил какой-то сомнительный список операций (или функций)
или макросов типа and or xor.

Вот мы и крутимся то в ассемблер то в С++ то в математику.

О базисах и минимизации я уже писал. Так что добавить нечего.
...
Рейтинг: 0 / 0
24.11.2014, 12:25
| Ответить | Цитировать | Написать  
максимум без if
    #39029821
Гость_11111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость_11111
Гость
Не думаю, что автору было нужно узнать максимум любых двух чисел. Наверное, было достаточно и для положительных. Потому

def f(a, b):
c = - ((a % b - a) // a)
return c * a + (1 - c) * b

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

К примеру

http://informatics.mccme.ru/mod/statements/view3.php?id=2296&chapterid=2958
...
Рейтинг: 0 / 0
14.08.2015, 22:16
| Ответить | Цитировать | Написать  
максимум без if
    #39288305
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskyВася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)

Всё-таки нет. Правильных решений на этих 4х страницах практически нет(в том числе и мое первое рассуждение содержит ошибку)
...
Рейтинг: 0 / 0
08.08.2016, 14:22
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
максимум без if
    #39719150
jksfj23jk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
jksfj23jk
Гость
на Python 3.4.2
Код: python
1.
2.
3.
4.
5.
6.
a = int(input())
b = int(input())
r= a * (a // b)
rr = b * (b // a)
rrr = int((r + rr) / (a//b + b//a))
print(rrr)
...
Рейтинг: 0 / 0
18.10.2018, 01:58
| Ответить | Цитировать | Написать  
максимум без if
    #39720263
Лысый дядька
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лысый дядька
Участник
jksfj23jkна Python 3.4.2

Код: python
1.
max = lambda x, y: (x,0,y)[(y-x)//abs(y-x)+1]
...
Рейтинг: 0 / 0
20.10.2018, 13:35
| Ответить | Цитировать | Написать  
23 сообщений из 98, страница 4 из 4
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / максимум без if
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]