Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Информационные технологии
        Решение задач на Pascal. Форум 3.
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Информационные технологии" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ]
Модераторы: paradise, KMA
  

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)

-----
Gentoo, FreeBSD 7.2, PHP, JavaScript (jQuery), Python, Shell
Помогаю с задачами только на форуме.
Все мои действия четко согласуются с правилами раздела. Поэтому никаких претензий и обид.

Всего сообщений: 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 и т.д. будет очень много, но по другому никак.

Буду вопросы или не понятки, спрашивай

-----
Gentoo, FreeBSD 7.2, PHP, JavaScript (jQuery), Python, Shell
Помогаю с задачами только на форуме.
Все мои действия четко согласуются с правилами раздела. Поэтому никаких претензий и обид.

Всего сообщений: 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



Долгожитель

Главное что натолкнул. Я написал, что первое в голову пришло

Молодец у тебя фактическая реализация моей мысли, может более правильная в результате кодирования...

-----
Gentoo, FreeBSD 7.2, PHP, JavaScript (jQuery), Python, Shell
Помогаю с задачами только на форуме.
Все мои действия четко согласуются с правилами раздела. Поэтому никаких претензий и обид.

Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 4 нояб. 2009 14:08 | IP
DivByZero


Новичок



(Сообщение отредактировал DivByZero 6 нояб. 2009 4:40)

Всего сообщений: 6 | Присоединился: октябрь 2009 | Отправлено: 5 нояб. 2009 5:39 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ]

Форум работает на скрипте © Ikonboard.com