IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
Closed Topic Открыть новую тему 
> 2 задачки, 1-вставка числа в массив, 2-строки
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Еще раз здраствуйте! и еще раз 10000 извинений!
вот тут задали, помогите кто чем может...плиз...
Цитата
Задан отсортированный одномерный массив чисел. Добавить введенное
пользователем число в массив таким образом, чтобы массив остался
отсортированным. Использовать минимальное количество сравнений.

так вот, вроде по условию массив уже отсортирован, на крайняк отсортирую, проблема со вставкой и минимальным кол-вом сравнений...если мона то сразу дайте процедуру, если нет...то хотя бы на словах и по доступней.
Поиск не помог, мож не те слова вводил... unsure.gif ...
Цитата
Ввести массив строк. Отсортировать строки в алфавитном порядке.

2-я залачка, знаю что должна тут быть где-то, но не нашел, уж не ругайте пожалуйста...а в инете, какие то сложные программы...
Помогите плиз... wink.gif ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Помогите пожалуйста... mega_chok.gif ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Полагаю, нужно основываться на методе деления отрезка пополам ...


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 82
Пол: Женский

Репутация: -  0  +


задача: 42. Дан одномерный упорядоченный по неубыванию массив А(N). Вставить элемент Х в этот массив таким образом, чтобы не нарушить упорядоченность массива А.

var i,n,x,j: integer;
A: array [1..100] of integer;
begin
write ('vvedite n');
readln (n);
writeln ('vvedite elementi');
for i:=1 to n do
read (a[i]);
writeln ('vvedite X');
readln (x);
if x>a[n] then a[n+1]:=x;
if x<a[1] then begin
for j:=n downto 1 do
a[j+1]:=a[j];
a[1]:=x;
end
else begin
i:=n;
while x<a[i] do
begin
a[i+1]:=a[i];
i:=i-1;
end;
a[i+1]:=x; end;
for i:=1 to n+1 do
write (' ',a[i]);
readkey;
end.



у тебя кажется примерно такая же
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
у тебя кажется примерно такая же
Только примерно... У тебя в программе производится далеко не минимум сравнений... В худшем случае переберутся все элементы...

klem4 уже написал, куда смотреть - надо делать аналог бинарного поиска:
Бинарный (двоичный) поиск
, с небольшим изменением: если элемента НЕТ в массиве, надо возвращать не отрицательное число, а позицию, в которую надо этот элемент занести (в зависимости от того, упорядочен ли массив по убыванию или по возрастанию)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Volvo
А мона переделаеть программу, которую дала Екатерина, но переделав, просто она попонятней, чем та которую дал ты...Если мона переделать, скажи плиз что и как...Если нет, то нет...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Ну, скажем, так:

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.
Не забудь, массив упорядочен. Мой пример - для случая, когда он упррядочен по неубыванию...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Volvo
Несколько вопросов:
1-
Цитата
Мой пример - для случая, когда он упррядочен по неубыванию...

А как? Просто Я вообще не понял по какому принципу твоя прога вставляет элемент
2-Массив может быть отсортирован толлько по возрастанию или убыванию, других принципов надеюсь нет?
3-Если нет, то Я немного догадываюсь как переделать жту прогу чтобы она массив сохраняла отсортированным...но все равно помогите плиз...
4-ЧТо там насчет строк в алфавитном порядке...?... unsure.gif ...

И еще, Я заметил у Екатерина, когда вводиш массив по убыванию все ОК...а вот с если по возрастаню-беда... yes2.gif ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Цитата
по какому принципу твоя прога вставляет элемент
методом бинарного поиска ищет позицию, на которой новый элемент должен стоять (или уже стоит элемент с таким же значением), и все остальные СПРАВА от этой позиции сдвигает на один еще правее, на "освободившееся" место ставится элемент X...

Цитата
Массив может быть отсортирован толлько по возрастанию или убыванию, других принципов надеюсь нет?
Отсортирован - да, только так. Я говорил про "упорядочен". То есть, после сортировки массив упорядочен как-то, верно? Ибо его элементы идут в определенном порядке. Вот для того, чтобы моя программа работала, требуется, чтобы массив был упорядочен по НЕубыванию, то есть, для каждого элемента массива (кроме последнего) выполнялось условие: A[i] <= A[i+1]

Я проверял программу на таком массиве:
const
size = 20;
A: array [1..size+1] of integer = (
1, 3, 5, 6, 7, 7, 12, 14, 19, 26,
28, 30, 33, 37, 40, 44, 49, 55, 69, 78, 0);


Цитата
Я немного догадываюсь как переделать жту прогу чтобы она массив сохраняла отсортированным
А тебе не надо ничего сохранять... У тебя по условию уже
Цитата
Задан отсортированный одномерный массив чисел
, вот и вводи его уже отсортированный в программу.

Цитата
ЧТо там насчет строк в алфавитном порядке
Есть в FAQ-е раздел "Методы Сортировок", вот оттуда возьми любой способ, и он будет работать с массивом строк...

Цитата
когда вводиш массив по убыванию все ОК...а вот с если по возрастаню-беда...
А я тебя предупреждал, что надо заранее знать, как будет упорядочен массив. Или придется усложнять программу проверками, во-первых, вообще, упорядочен ли он, а во-вторых - как именно...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Volvo
Пасибо огромное за ответы, что все по полочкам разложил, за строки отдельно пасибо... good.gif ...
Только вот как с прогой быть, Я думаю придется условие усложнять, про то как ты писал
Цитата
Или придется усложнять программу проверками, во-первых, вообще, упорядочен ли он, а во-вторых - как именно..

просто как быть с бинарным поиском ума не приложу... dry.gif ...
Поэтому если можешь дай алгоритм как это условие усложнить, или если где процедура завалялась... smile.gif ...
Или мож есть другие варианты, как нибудь бинарный поиск передлать и т.д.
Просто массив 100% преподаватель будет вводить как по убыванию, так и наоборот...и тут надо чтото придумать, чтобы прога работала... mega_chok.gif ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата(TOPEHTO @ 24.11.2006 14:00)
Просто массив 100% преподаватель будет вводить как по убыванию, так и наоборот...и тут надо чтото придумать, чтобы прога работала...


Ну, раз будет проверять - пусть проверяет smile.gif Главное - чтобы он вводил (как, собственно, требуется в условии) упорядоченный массив...

Используется очень простой принцип работы - см. комментарии:
var
i,x,j, count: integer;
{ size, }
left, right, center: integer;
is_ascend: boolean;
{ a: array[1 .. 100] of integer; }

const
size = 20;
A: array [1..size+1] of integer = (
(* НЕубывающая последовательность *)
{ 1, 3, 5, 6, 7, 7, 12, 14, 19, 26, }
{ 28, 30, 33, 37, 40, 44, 49, 55, 69, 78, 0 }

(* НЕвозрастающая последовательность *)
78, 69, 55, 49, 44, 40, 37, 33, 30, 28,
26, 19, 14, 12, 7, 7, 6, 5, 3, 1, 0
);

begin
(*
write('vvedite size'); readln(size);
writeln('vvedite elementi');
for i:=1 to size do readln(a[i]);
*)
writeln ('vvedite X');
readln (x);

{
Для начала - найдем 2 различных элемента,
чтобы определить, как отсортирована последовательность...
}
i := 1;
while (i < size) and (a[i] = a[i+1]) do inc(i);
{
Если разные элементы найдены - делаем заключение о том, НЕубывающая это
последовательность или НЕвозрастающая, если не найдены - нам же проще,
значит, вообще ВСЕ элементы - одинаковые, и достаточно сравнить с граничными
}
is_ascend := (a[i] < a[i+1]);

{
А вот начиная отсюда - просто ВСЕ сравнения, которые делаются между элементами
последовательности, надо еще сравнивать с is_ascend, тогда независимо от направления
сортировки мы получим одинаковый (и правильный) результат...
}
if (x>a[size]) = is_ascend then a[size+1]:=x
else
if (x<a[1]) = is_ascend 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);
{ "Двойное" сравнение придется разбить на 2 "одинарных" }
if ((a[ center ] > X) = is_ascend) or (a[ center ] = X) then right := center
else left := center;

until (right - left = 1) or (a[ center ] = X);

{ Это добавлено, чтобы пофиксить глючок, который я раньше не заметил... }
while (a[ center ] < X) = is_ascend do inc(center);

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.


Вот и все... smile.gif Проверялось на двух приведенных массивах (просто закомментируй один и раскомметнируй другой), если надо проверять на вводимой последовательности - убери Const-описания массивов, и раскомментируй описание size и массива A...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Volvo
СпасиБо, тебе огромное...ВЫручил...сейчас буду заценять прогу... blum.gif ...
Слушай, в чем ошибка ввода, знаю что в чемто простом, но никак не соображу
Цитата
uses crt;
Type
arrType = Array[1 .. 100] Of string;
var
ar: arrType;i,n:integer;
Procedure Bubble(Var ar: arrType; n: integer);
Var i, j: Integer;
t:string;
Begin
For i := 1 To n Do
For j := n DownTo i+1 Do
If ar[Pred(j)] > ar[j] Then { < }
Begin
T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T
End
End;
begin
clrscr;
readln(n);
for i:=1 to n do read(ar[i]);
Bubble(ar,n);
for i:=1 to n do write(ar[i]);
readln;
end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Не знаю... У меня нормально работает (после того, как я поменял Read на ReadLN)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Ага, спасибо...во всем разобрался... smile.gif ...
Тут еще 1 беда есть...есть такая вот задачка:
Цитата
В заданной строке символов найти все вхождения заданной подстроки. На
экран вывести номер позиции символа, с которого начинается данное
вхождение, или сообщение о том, что такого вхождения не существует.

есть решение, причем правильное
Цитата
Program Lab_3_3;
uses crt;
var x,y:string;
i,k:word;
h,d,t:boolean;
begin
ClrScr;
Write('Enter string1: ');
Readln(x);
Write('Enter string2: ');
Readln(y);
i:=1;
t:=true;
While (Ord(x[i])<>0) do begin
h:=true;{vxojdenie}
While (h and(Ord(x[i])<>0)) do begin
k:=1;
d:=true;{podstroka so strokoi}
While (d and(Ord(y[k])<>0)) do begin
d:=(y[k]=x[i+k-1])and(Ord(x[i+k-1])<>0);
k:=k+1;
End;
h:=not(d);
i:=i+1;
End;
if not(h) then begin
Writeln('N simvola: ',i-1);
t:=false;
End;
End;

if t then Writeln('Vhogdenii net');
Write('Press any button for exit');
Readkey;
End.

Народ или помогите с алгоритмом разобраться или упростить, потому что тут черт голову сломит цикл на цикле, может у кого что попроще есть, или это упроститься... unsure.gif ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






Зааешь, что? Я, конечно, понимаю, что у тебя может быть бесконечное количество "задачек", но во-первых, первоначально речь шла о двух, а это - уже третья... Во вторых, ЭТА тема тоже должна была быть как минимум закрыта, как неправильно оформленная, ее не закрыли. Так вот ТЕПЕРЬ ("благодаря" твоей тенденции садиться на шею) МАЛЕЙШИЙ конфликт с правилами будет приводить к закрытию твоих тем. Все понятно?

Изначальный вопрос решен, тема закрыта.
 К началу страницы 
+ Ответить 

Closed Topic Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:14
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name