Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ сортировка вставками с двоичным поиском,

Автор: Dima_SLV 29.11.2006 22:28

Добрый день!Помогите плиз надо сделать прогу на паскале.
Метод СОРТИРОВКА ВСТАВКАМИ.Дана возраст. посл-ть a1<a2<..<an.Берем новое число an+1 и помещаем его в исход. посл-ть так,чтоб новая посл. тоже была возраст-ей.
Место помещения очередного элемента в отсортир-ую часть производить с помощью двоич. поиска!двоичный поиск оформить в виде отдельной функции!


var i,x,j, count: integer; size, left, right, center: integer; a:
array[1 .. 100]
of integer;
begin
write('vvedite size'); readln(size); writeln('vvedite elementi');
for i:=1
to size
do readln(a[i]); writeln ('vvedite X'); readln (x);
if x>a[size]
then a[size+1]:=x;
if x<a[1]
then
begin
for j:=size
downto 1
do a[j+1]:=a[j]; a[1]:=x;
end
else
begin left := 1; right := size;
repeat center := (right + left)
div 2; inc(count);
if a[ center ] >= X
then right := center
else left := center;
until (right - left = 1)
or (a[ center ] = X);
for i := size + 1
downto center
do a[i] := a[i - 1]; a[ center ] := X;
end; writeln('count = ', count);
for i:=1
to size+1
do
write (' ',a[i]); writeln; readln;
end.


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

Автор: мисс_граффити 29.11.2006 23:26

а что ты пробовал делать?
чтобы говорить, что не получается, надо хотя бы начать.

Автор: Dima_SLV 30.11.2006 0:44

Цитата(мисс_граффити @ 29.11.2006 21:26) *

а что ты пробовал делать?
чтобы говорить, что не получается, надо хотя бы начать.


я пытался выделить часть содер. двоичный поиск,вот как я это вижу!
Если эту часть перенести в подрограмму(в моем случае функцию)

if x<a[1]
then
begin
for j:=size
downto 1
do a[j+1]:=a[j]; a[1]:=x;
end
else
begin left := 1; right := size;
repeat center := (right + left)
div 2; inc(count);
if a[ center ] >= X
then right := center
else left := center;
until (right - left = 1)
or (a[ center ] = X);
for i := size + 1
downto center
do a[i] := a[i - 1]; a[ center ] := X;
end; writeln('count = ', count);


А в качестве фактических параметров-переменных передавать в функцию(где они форм. параметры) наш введенный с клавы упоряд. массив и переменнную х(т.е. число которое надо вставить в массив)!Но функция неможет возвращать результат-диапозон(т.е наш изменив. массив)!
Может я иду не в том направлении???

Автор: мисс_граффити 30.11.2006 0:52

ты путаешь массив и диапазон.
диапазон - это вот так: 1..5, 9..17
возвращать массив вполне можно. и передавать тоже... как это сделать ты можешь прочитать в FAQ
хотя в моем понимании двоичный поиск должен возвращать номер позиции, на которую надо вставить элемент.

Автор: Dima_SLV 30.11.2006 1:36

Цитата(мисс_граффити @ 29.11.2006 22:52) *

ты путаешь массив и диапазон.
диапазон - это вот так: 1..5, 9..17
возвращать массив вполне можно. и передавать тоже... как это сделать ты можешь прочитать в FAQ
хотя в моем понимании двоичный поиск должен возвращать номер позиции, на которую надо вставить элемент.

Но чтобы функция возвратила номер позиции,надо передать в нее исходный массив!Как передавать массив я знаю!Массив взять открытый или явно указать его размерность?
Я на словах понимаю как сделать,а на практике уже бьюсь целый день!А завтра после обеда надо уже показывать готовое задание!

Автор: Dima_SLV 30.11.2006 3:09

Ура прога работает,сделал!!!

Uses Crt;
type
arrtype=array[1 .. 100] of integer;

Function Bin_Search(a:arrtype;size,x:integer):integer;
Var left, right, center: integer;
begin
left := 1; right := size;
repeat center := (right + left)
div 2;
if a[ center ] >= X
then right := center
else left := center;
until (right - left = 1) or (a[ center ] = X);
bin_search:=center;
end;

var a:arrtype; i,x,j,center: integer; size: integer;
begin ClrScr;
write('vvedite size '); readln(size); writeln('vvedite elementi');
for i:=1
to size
do readln(a[i]); writeln ('vvedite X'); readln (x);
if x>a[size]
then a[size+1]:=x;
if x<a[1]
then
begin
for j:=size
downto 1
do a[j+1]:=a[j]; a[1]:=x;
end
else
begin
center:=Bin_Search(a,size,x);
for i := size + 1
downto center
do a[i] := a[i - 1];
a[ center ] := X;
end;
for i:=1
to size+1
do
write (' ',a[i]); writeln; readln;
end.


Но от первоначальной версии(которая от Volvo,код в начале этой темы) остался один глюк помогите срочно его исправить после обеда надо прогу предодам показывать!
Описание глюка:когда вставляемый элемент приходится на отрезок м/у предпоследним и последним эл-ом массива,то этот элемент(вставляемый) ловит место на одну позицию ближе положенной!т.е он должен встать м/у предпосл. и посл. эл-ми,а реально встает перед предпоследним!
И может найдете че улучшить в проге?