Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Язык без оператора сравнения
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Among Among вне форума
Member
 
Сообщений: 27
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2006
По умолчанию 08.11.2006, 07:05

Тут такую головоломку задали :shock:
Написать программу сортирующую массив целых чисел x[s] x[i]=n...m если в данном языке программирования отсутствует оператор сравнения....
Ответить с цитированием
  (#2 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 08.11.2006, 07:58

Можно использовать xor
Если a = b, то bool(a xor b) = false
Ответить с цитированием
  (#3 (permalink)) Старый
SiMM SiMM вне форума
Member
 
Сообщений: 1,961
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.08.2003
По умолчанию 08.11.2006, 08:28

Цитата:
Можно использовать xor
Если a = b, то bool(a xor b) = false
И как это поможет в сортировке?
Among, а какие ещё ограничения?
Если язык - C-подобный, sign(a-b)+1 даёт false (0), если a<b, где y=sign(x) - операция получения знака числа:
y=-1, если x<0
y=0, если x=0
y=1, если x>0
Ответить с цитированием
  (#4 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 08.11.2006, 08:50

Точно, протупил

У нас, кстати, тут целый топик был на эту тему (только что-то найти не могу)

Цитата:
y=-1, если x<0
y=0, если x=0
y=1, если x>0
А тут точно оператора сравнения не нужно?
Ответить с цитированием
  (#5 (permalink)) Старый
Among Among вне форума
Member
 
Сообщений: 27
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2006
По умолчанию 08.11.2006, 09:40

Язык не определен. Условие единственное без оператора сравнения.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
kelz kelz вне форума
Member
 
Сообщений: 511
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.05.2004
По умолчанию 08.11.2006, 10:27

Цитата:
Условие единственное без оператора сравнения.
Интересно, а такое вообще возможно?
Ответить с цитированием
  (#7 (permalink)) Старый
SiMM SiMM вне форума
Member
 
Сообщений: 1,961
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.08.2003
По умолчанию 08.11.2006, 10:46

Цитата:
А тут точно оператора сравнения не нужно?
Подразумевается, что sign - функция встроенная :) Ну и конечно проверка на false всё же имеется, хоть и неявно ;) А чтобы уж совсем без сравнения (имеется в виду, чтобы его не происходило в сгенерированном коде) - это невозможно :)
Ещё вариант -
Код:
tmp = max(a,b);
a = min(a,b);
b = tmp;
думаю, идея понятна :)
Ответить с цитированием
  (#8 (permalink)) Старый
Among Among вне форума
Member
 
Сообщений: 27
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2006
По умолчанию 08.11.2006, 12:08

Цитата:
Подразумевается, что sign - функция встроенная :) Ну и конечно проверка на false всё же имеется, хоть и неявно ;) А чтобы уж совсем без сравнения (имеется в виду, чтобы его не происходило в сгенерированном коде) - это невозможно :)
Ещё вариант -
Код:
tmp = max(a,b);
a = min(a,b);
b = tmp;
думаю, идея понятна :)
у меня тоже что то в этом роде получалось:
min= (a+b-|a-b|)/2
max=(a+b)-min
соответственно (min, max)...но это для 2-х чисел а как вот поставить условие для массива :upset: x[s]: x[i]=n...m

что то вроде
i=1
k=0
пока k<>m! делай
min[i]=(x[i]+x[i+1]-|x[i]-x[i+1]|)/2
max[i+1]=(x[i]+x[i+1])-min[i]
i=i+1
k=k+1
выводи (min[i], max[i])
Ответить с цитированием
  (#9 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 08.11.2006, 12:11

я знаю эту задачу..
Функциями макс и мин пользоваться нельзя...

А вот собрать их самому можно:
модуль (суммы двух чисел) минус (модуль их разности) возвращает удвоенное (минимальное из этих чисел)

Гы.. опередили..


импортирован с progz.ru
Ответить с цитированием
  (#10 (permalink)) Старый
SiMM SiMM вне форума
Member
 
Сообщений: 1,961
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.08.2003
По умолчанию 08.11.2006, 13:06

Цитата:
но это для 2-х чисел а как вот поставить условие для массива :upset: x[s]: x[i]=n...m
Ну Вы хоть про сортировку пузырьком что-ли почитайте, алгоритм сортировки не зависит от реализации функции сравнения.
Цитата:
модуль (суммы двух чисел) минус (модуль их разности) возвращает удвоенное (минимальное из этих чисел)
Ну да. Для целой арифметики - сгодится.
Ответить с цитированием
  (#11 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 08.11.2006, 13:08

Цитата:
А чтобы уж совсем без сравнения (имеется в виду, чтобы его не происходило в сгенерированном коде) - это невозможно
Думешь?
Есть ещё альтернативный вариант sing() без сравнения
Ответить с цитированием
  (#12 (permalink)) Старый
SiMM SiMM вне форума
Member
 
Сообщений: 1,961
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.08.2003
По умолчанию 08.11.2006, 13:09

Цитата:
Есть ещё альтернативный вариант sing() без сравнения
А sign внутри, думаешь, без сравнения обходится? А if? :)
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
kelz kelz вне форума
Member
 
Сообщений: 511
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.05.2004
По умолчанию 08.11.2006, 13:50

А инструкции ja/jb/jz и им подобные относятся к сравнению? Можно например сделать sub eax,edx (два элемента массива) и по одной из этих команд уйти на соответствующую ветку алгоритма. Но если они все-же считаются сравнением и не удовлетворяют условию, то ответ одназначен: такое невозможно (по крайней мере на известных на настоящее время миру процессорах)
Ответить с цитированием
  (#14 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 08.11.2006, 16:34

Цитата:
А sign внутри, думаешь, без сравнения обходится? А if?
Стандартный - со сравнением, это точно. Но я-то выше писал про альтернативный. А идея его в том, чтобы взять знаковый бит. Такая реализация , кстати, эффективней стандартной (нет перехода, меньше инструкций)
Код:
 
; => eax - input argument
; <= 1 - if is less than zero, 0 otherwise
rol eax, 1
and eax, 1
Цитата:
А if?
Пузырек можно собрать без if. В этом случае код выше как раз к месту будет
Цитата:
А инструкции ja/jb/jz и им подобные относятся к сравнению?
Разумеется, самое что ни на есть сравнение
Ответить с цитированием
  (#15 (permalink)) Старый
kelz kelz вне форума
Member
 
Сообщений: 511
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.05.2004
По умолчанию 08.11.2006, 19:14

Цитата:
Разумеется, самое что ни на есть сравнение
Ну, тогда я не знаю. Может у MaMaV-а спросить - он все таки армию роботов собирает, наверняка у него есть секретные алгоритмы...
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Утилита сравнения двух каталогов Matematic Офтопик 49 20.12.2013 11:38
Программа для сравнения двух BMP-файлов 5neverthesame94 Вопросы начинающих программистов 9 02.04.2012 22:29
Сортировка слиянием - количество операций сравнения Rizza Вопросы начинающих программистов 0 30.06.2011 14:22
Программа для сравнения фотографий одного человека валерьич Вопросы начинающих программистов 1 11.12.2010 07:34
Цены в моем городе. Зацените для сравнения? ELECTRONIC Процессоры 2 03.04.2010 17:17
Функция сравнения ячеек Nagv Visual Basic 4 09.06.2006 15:37
Операции сравнения и приведения типов imported_Ferz Вопросы начинающих программистов 17 29.03.2006 17:56
Алгоритм сравнения двух текстов :shock: rutman Visual Basic 0 28.10.2004 14:41
Скриптовый язык vs Язык программирования relonar Мысли вслух 4 24.09.2004 02:14
По умолчанию язык ввода стоит английский, то в паскале язык не переключается imported_Liliya Pascal 17 16.01.2004 03:36
Операция сравнения в классе AnsiString Templar C++ Builder 5 18.01.2003 17:08
Команда сравнения в INTEL 8085 ortho Assembler 5 18.06.2002 18:08



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов