Здравствуйте, UgN, Вы писали:
UgN>Дано:
UgN>Массив из N чисел. Все числа из диапазона от 0 до M.
UgN>Надо:
UgN>Вывести числа отсортированными по возрастанию.
UgN>Ограничение: нельзя пользоваться сравнениями
Завести массив [0..M] счетчиков в диапазоне [0..N] (или 0..1, если числа не повторяются)
За один проход по набору данных — сосчитать.
За один проход по массиву счетчиков — вывести каждое значение индекса столько раз, чему равен счетчик.
(Ранее упоминалось на сайте под названием "сортировка нахаляву")
Здравствуйте, UgN, Вы писали:
UgN>Вроде еще не было...
UgN> UgN>Дано:
UgN>Массив из N чисел. Все числа из диапазона от 0 до M.
UgN>Надо:
UgN>Вывести числа отсортированными по возрастанию.
UgN>Ограничение: нельзя пользоваться сравнениями
UgN>Пример:
UgN>Дано: M = 11, N = 6 : 9 5 10 2 2 7
UgN>Ответ: 2 2 5 7 9 10
нельзя пользоваться операторами сравнения????
тоды их можно заментиь двумя функциями:
int max(int a, int b)
{
return (a+b+abs(a-b))/2;
}
int min(int a, int b)
{
return ((a+b)-abs(a-b))/2;
}
cab>int max(int a, int b)
cab>{
cab> return ((a+b)+abs(a-b))/2;
cab>}
cab>int min(int a, int b)
cab>{
cab> return ((a+b)-abs(a-b))/2;
cab>}
Вообще-то, abs неявно использует сравнение с 0...
Хотя, если использовать представление "знак+величина", можно просто сбрасывать знак...
cab>ну а там дальше все ясно........ cab>все ясно?????
void sort2(int& a, int& b)
{
int mi = min(a,b), ma = max(a,b);
a = mi; b = ma;
}
void sort(int data[], int size)
{
// аналог пузырьковой сортировки
// без смены направления движенияint i,j;
for(i = 0; i<(size-1); i++)
for(j = 0; j<(size-1); j++)
sort2(data[j], data[j+1]);
}
Здравствуйте, m.a.g., Вы писали:
MAG>Здравствуйте, UgN, Вы писали:
MAG> UgN>>Вывести числа отсортированными по возрастанию.
MAG>[Зевая] Сортировка подсчетом.
MAG>
перестали использовать сравнения внутри себя? Или же речь шла только о несравнении значений массива?
Тут возникает вопрос: нельзя ли действительно обойтись каких либо сравнений, ну разве что при проходе массива — не вышли ли мы за его пределы?
Здравствуйте, m.a.g., Вы писали:
MAG>Здравствуйте, DmitryBoboshko, Вы писали:
MAG> DB>>перестали использовать сравнения внутри себя? Или же речь шла только о несравнении значений массива?
MAG>По всей видимости, да. Любое ветвление подразумевает неявное сравнение с нулем А без ветвлений только линейную программу и можно написать.
Самомодифицирующаяся программа — адрес перехода берется из массива, индексом по которому служит "сравниваемая" величина.
Евгений, с приветом (но без остроумной подписи, к сожалению )
И, как оказалось, такая задача уже была...
( Хотел убить ветку, не дали... )
Это, конечно не значит, что кто-то не придумает свое оригинально е решение...
Но все же.
А что касается условия...
Сравнивать числа из массива нельзя. Хоть как.
Даже если ты будешь у разности знаковый бит смотреть...
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, Кодт, Вы писали:
M>...
К>>Вообще-то, abs неявно использует сравнение с 0... К>>Хотя, если использовать представление "знак+величина", можно просто сбрасывать знак...
M>
M> abs( x ) = sqrt( x * x )
К>>
sqrt по идее тоже должен использовать сравнение 0. Иначе как он узнает, что число из котрого извлекается корень больше 0? Или я заблуждаюсь?
Здравствуйте, Karson, Вы писали:
K>Здравствуйте, mrhru, Вы писали:
К>>>Вообще-то, abs неявно использует сравнение с 0... К>>>Хотя, если использовать представление "знак+величина", можно просто сбрасывать знак...
M>>
M>> abs( x ) = sqrt( x * x )
К>>>
K>sqrt по идее тоже должен использовать сравнение 0. Иначе как он узнает, что число из котрого извлекается корень больше 0? Или я заблуждаюсь?
Не обязательно. Это может быть специальная реализация sqrt, явно полагающая, что её аргументы — положительные.
Ну и ещё всегда остается "уловка" в реализации условных переходов в виде выборки адреса перехода из массива по индексу — равному значению аргумента условного перехода.
Евгений, с приветом (но без остроумной подписи, к сожалению )