Dale
Участник
|
       
DivByZero
А просто отсортировать нельзя?
|
Всего сообщений: 139 | Присоединился: май 2009 | Отправлено: 2 нояб. 2009 16:08 | IP
|
|
DivByZero
Новичок
|
Ну там же это условие... Количество перемещений не должно превосходить n-1 и сравнений тоже. Я пока такого метода сортировки не видел... Может проглядел?
|
Всего сообщений: 6 | Присоединился: октябрь 2009 | Отправлено: 2 нояб. 2009 18:16 | IP
|
|
KMA 
Долгожитель
|
Пусть дан массив А1, ..., Аn. Требуется переставить А1, ..., Аn так, чтобы в начале в массиве шла группа элементов, больших того элемента, который в исходном массиве располагался на первом месте, затем сам этот элемент, потом - группа элементов, меньших или равных ему.
И теперь гадкие дополнительные условия этой задачи - количество сравнений и перемещений не должно превосходить (n-1).
Мда, не повезло тебе с этим условием. На самом деле, задача не может быть решена при данном условии (если я его правильно понял, т. е. если число перестановок p и число сравнений l, то p+l <= (n-1), где n число элеметов последовательности).
Доказывается просто:
Пусть дана последовательность чисел n. Для того, чтобы знать отношения (больши либо меньше) заданного числа требуется min(p) = n-1 сравнений. В случае если все элементы не меньше заданного числа требуется хотя бы 1 перестановка, т.е. min(l) = 1. Проверяя тождество p+l = n-1 +1 = n.
Пример:
10 12 15 17 8, n = 5
Для того, чтобы узнать какие числа больше, а какие нет, требуется 4 сранвнения, в результате получим маску:
x > > > <
Для перестановки требуется 1 действие (10 поменять с 17). Получаем l=1. Итого 5 действий, а требуется 4.
Минимальных действий потребуется еще больше, если в конце я добавлю число большее 10 (как минимум 2 перестановки).
Так что не зря ты две ночи не спишь  пытаясь добыть философский камень или изобрести перпетум мобиле.
(Сообщение отредактировал KMA 2 нояб. 2009 18:41)
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 2 нояб. 2009 18:40 | IP
|
|
DivByZero
Новичок
|
Извиняюсь за неточную формулировку... Каждое в отдельности не должно превосходить n-1. То есть сравнений должно быть не больше n-1 и перестановок не больше n-1.
А так естественно что-то из области фантастики получается...
И меня начала терзать мысль что это очень просто реализуется, а я как всегда в дебри забрался.
(Сообщение отредактировал DivByZero 2 нояб. 2009 19:40)
(Сообщение отредактировал DivByZero 2 нояб. 2009 19:41)
|
Всего сообщений: 6 | Присоединился: октябрь 2009 | Отправлено: 2 нояб. 2009 19:37 | IP
|
|
KMA
Долгожитель
|
И меня начала терзать мысль что это очень просто реализуется, а я как всегда в дебри забрался.
Тогда это действительно быстро реализуется
Начинается все довольно просто.
1. Сравниваем наше число в позиции nowpos (в начальном состоянии равном 1) с рядом стоящим. Если число больше заданного идем к шагу 2, если нет к шагу 3.
2. Прибавляем к счетчику maxpos единицу (первоначально maxpos=0). Возвращаемся к шагу 1.
3. Итак наступил момент, когда число меньше заданного, значит нужно данные числа переставить [позиция первого элемента должна измениться, но переставлять, мы пока его не будем]. Для этого переставляем наш элемент с nowpos на место maxpos (nowpos = maxpos + 1). Счетчик minpos будет показывать текущую позицию минимального элемента (в данном случае это будет minpos = nowpos + 1). Переходим к шагу 4.
4. Если элемент minpos + 1 меньше заданного, то идем на шаг 5, иначе на 6.
5. Прибавить к minpos единицу (предусмотреть вариант, когда minpos+1 == n). Идти на шаг 4.
6. Поскольку далее возможна последовательность больших элементов, сосчитаем вподряд стоящие элементы (которые больше заданного). Пусть будет счетчик kmax = 1. Двигаемся пока не будет меньше заданного числа (предусмотреть вариант, когда kmax + minpos == n). Если встретился меньше элемент, тогда идем на шаг 7.
7. Поскольку минимальные элементы должны стоять в хвосте, начинаем с хвоста и ищем там первый максимальный элемент. (счетчик endpos вначале равен n). Если элемент меньше чем заданное, тогда вычитаем из endpos единицу. Иначе на шаг 8. (Внимание здесь должна быть проверка minpos + kmax + 1 == endpos, то значит так же идем на шаг 9).
8. Теперь надо переставить элемент с nowpos +1 на endpos. nowpos прибавить 1,а из endpos вычесть 1. Проверить является ли minpos == nowpos. Если да, то к minpos прибавляем kmax + 1, а к nowpos прибавим kmax, если нет то идем на шаг 7.
9. Собственно последний шаг, осталось переставить элементы с последнего хвоста максимальных на свои места. Действия схожие с шагом 8.
Примерно такой алгоритм . Может я чего-то и намудрил, тут главное разобраться с указателями позиций, или можно как-то оптимизировать.
Логика работы в следующем: ищем те элементы которые больше заданного в подряд идующие. Если встречается меньший (или последовательность меньших, то считаем их позицию), а за ними большие, то перекидываем из самого конца максимальные на место тех минимальных.
Выданный алгоритм можно немного сократить, не считая kmax, а просто перекидывая с конца максимальные элементы и снова переходя к шагу 1.
Главное внимательно разобраться что делает каждый индекс и проследить за ними. Так что отладчик в руки цикл while и условие if в тебе в руки.
Работает примерно так (x означает текущий элемент, > элементы больше, < элементы меньше):
x>><>>><<<><>>
x>>>>>><<<><><
x>>>>>>><<><<<
x>>>>>>>><<<<<
>>>>>>>>x<<<<<
Как видно перестановок не так много. Вот только вопрос, если разговор о сравнении элементов массива, то их ровно n-1 (по другому вообще никак), но вот сравнение endpos с maxpos, minpos и т.д. будет очень много, но по другому никак.
Буду вопросы или не понятки, спрашивай
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 3 нояб. 2009 12:12 | IP
|
|
Kurvochka
Новичок
|
Цитата: Kurvochka написал 2 нояб. 2009 8:27
Привет еще раз! Мне еще задали пару задач и я сразу к вам!
Задача1. Если значения функции у1=х*х*х+8х и у2=2*х*х+8 при одному и томже значению аргумента имеют одинаковые знаки, то показать текст "знаки одинаковые". в противоположном случае написать значение аргумента и функции.
Задача 2. решить систему У= (знак системы)
е в степени -(х+3) + arctg(x) при условии х>0 и второе уравнение этой системы 2х/Ln(х*х+3) при условии х< или равно 0.
Ну помогите. Плизз.бо сдавать завтра нада.
|
Всего сообщений: 7 | Присоединился: октябрь 2009 | Отправлено: 3 нояб. 2009 14:07 | IP
|
|
Dale
Участник
|
Kurvochka
1)
Code Sample:
readln(x);
y1:=х*х*х+8*х;
y2:=2*х*х+8;
if ((y1<0 and y2<0) or (y1>=0 and y2>=0)) then
writeln('Одинаковые')
else
writeln('разные');
(Сообщение отредактировал Dale 3 нояб. 2009 17:18)
|
Всего сообщений: 139 | Присоединился: май 2009 | Отправлено: 3 нояб. 2009 17:15 | IP
|
|
DivByZero
Новичок
|
Цитата: KMA написал 3 нояб. 2009 12:12
Примерно такой алгоритм . Может я чего-то и намудрил, тут главное разобраться с указателями позиций, или можно как-то оптимизировать.
Спасибо большое за помощь! Этот алгоритм натолкнул на пару очень хороших мыслей... Решние получилось коротким(запехнулось в один цикл while) и даже возможно красивым Вот, если интересно:
Code Sample:
leftpos:=2;
rightpos:=n;
positive:=true;
while positive do begin
while a[1]<a[leftpos] do begin
inc(leftpos);
end;
while a[1]>=a[rightpos] do begin
dec(rightpos);
end;
if (rightpos-leftpos)>0 then begin
t:=a[leftpos];
a[leftpos]:=a[rightpos];
a[rightpos]:=t;
end
else begin
positive:=false;
end;
end;
t:=a[1];
a[1]:=a[leftpos-1];
a[leftpos-1]:=t;
Как только не мучал - всегда правду говорит 
(Сообщение отредактировал DivByZero 4 нояб. 2009 4:15)
|
Всего сообщений: 6 | Присоединился: октябрь 2009 | Отправлено: 4 нояб. 2009 4:14 | IP
|
|
KMA
Долгожитель
|
Главное что натолкнул. Я написал, что первое в голову пришло
Молодец у тебя фактическая реализация моей мысли, может более правильная в результате кодирования...
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 4 нояб. 2009 14:08 | IP
|
|
DivByZero
Новичок
|
(Сообщение отредактировал DivByZero 6 нояб. 2009 4:40)
|
Всего сообщений: 6 | Присоединился: октябрь 2009 | Отправлено: 5 нояб. 2009 5:39 | IP
|
|
|
Форум
Решение задач на Pascal. Форум 3.
