Поиск 2 одинаковых элементов в массиве.

← →
Leon-Z © (2011-03-03 20:35) [0]

Дан массив - Mas: array [1..10] of Integer;

В нем 2 числа одинаковые. Как максимально быстро найти их.
Я знаю 1 метод:
var mas: array [1..10] of Integer; i, j, index1, index2: Integer; begin index1 := 0; index2 := 0; // заполним массив случайными значениями Randomize; for i := 1 to 10 do mas[i] := Random(100); i := Random(9) + 1; mas[i] := 8; i := Random(9) + 1; mas[i] := 8; // собственно поиск for i := 1 to 9 do for j := i + 1 to 10 do if mas[i] = mas[j] then begin index1 := i; index2 := j; end; end;
Есть другие методы ?

← →
Oleg_teacher (2011-03-03 21:01) [1]

если согласно условия два одинаковых елемента есть точно, тогда может быстрее использовать два while. Будет меньше операций в общем случае.

← →
И. Павел © (2011-03-03 21:06) [2]

Если нужно искать только одну пару одинаковых чисел, то после того, как их найдете, не забудьте поставить break, чтобы цикл не продолжился впустую.

← →
Oleg_teacher (2011-03-03 21:11) [3]

> не забудьте поставить break

Скажите, а как вы считаете использовать break, exit - ето нормальный тон программирования? (ето не упрек, ето ничего плохого сказать вам не хочу... просто так, для общего развития. Я например всегда стараюсь обходитсься без етих двух команд)

← →
Leon-Z © (2011-03-03 21:11) [4]

Замечания приняты.
А насчет алгоритма - существуют ли другие алгоритмы, быстрее этого ?
(написать на assembler"e - не предлогать).

← →
Oleg_teacher (2011-03-03 21:14) [5]

> А насчет алгоритма - существуют ли другие алгоритмы, быстрее
> этого ?

Ну я так не вспомню... нужно более детально знать условие задачи. Если ето в программе только один раз делать (поиск) - тогда наверное ето и будет намного ефективнее.

← →
KilkennyCat © (2011-03-03 21:19) [6]

> for i := 1 to 9 do
> for j := i + 1 to 10 do

неверно.

← →
Oleg_teacher (2011-03-03 21:20) [7]

к чему я веду... ну например, рассмотрим задачу поиска элемента в массиве. По количеству операций для меня самый ефективный способ есть последовательное сравнение елементов. Но когда в одном и том же масиве (большом) нам надо будет находить много раз разные елементы - тогда я предпочитаю сначала его быстрым методом отсортировать и использовать например бинарный поиск. Как на меня при таком варианте прога работает быстрее...

← →
KilkennyCat © (2011-03-03 21:23) [8]

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

← →
Сергей М. © (2011-03-03 21:23) [9]

> всегда стараюсь обходитсься без етих двух команд

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

← →
Oleg_teacher (2011-03-03 21:28) [10]

> для отсортированных бинарный поиск не нужен, под такую задачу.

мы наверное про разные задачи думаем... написал в посте:

> рассмотрим задачу поиска элемента в массиве

ето была совсем отличная задача от задачи автора (я просто привел пример)
Так вот бинарный поиск - же и предназначен исключительно для отсортированных данных.

← →
Oleg_teacher (2011-03-03 21:30) [11]

> Вот как раз без них-то зачастую сложно обойтись

а я че то привык только условиями обходится (ну например для выхода из цикла).

← →
Противный (2011-03-03 21:31) [12]

> Leon-Z © (03.03.11 20:35) В нем 2 числа одинаковые <...>
> Randomize;
> for i := 1 to 10 do mas[i] := Random(100);
> i := Random(9) + 1;
> mas[i] := 8;
> i := Random(9) + 1;
> mas[i] := 8;

Не факт.

> Leon-Z © (03.03.11 21:11) [4] А насчет алгоритма - существуют ли другие алгоритмы, быстрее этого ?

Если массив изначально отсортировать, то задача решается за максимум один полный проход.

> Oleg_teacher (03.03.11 21:11) [3] Скажите, а как вы считаете использовать break, exit - ето нормальный тон программирования?

Goto, Break, Exit, Continue, While-Do, Repeat-Until - моветон. Всякие Pascal, C, C++ по сути - моветон. Я даже не упоминаю C#, Basic и Java. Настоящие джедаи пишут только на Assembler. И даже там стараются избегать всяких Loop"ов. Есть только семь истинных мнемоник: Mov, Add, Or, And, Shr, Shl и JmpX. Все остальное суть происки нечестивцев.

← →
KilkennyCat © (2011-03-03 21:31) [13]

> бинарный поиск - же и предназначен исключительно для отсортированных
> данных.

я в курсе.

> мы наверное про разные задачи думаем

наверное. для единственной пары - да. если найти все пары - только бинарный поиск будет медленней.

← →
Leon-Z © (2011-03-03 22:00) [14]

> Противный (03.03.11 21:31) [12]
> > Leon-Z © (03.03.11 20:35)
> > В нем 2 числа одинаковые.
> > Randomize;> for i := 1 to 10 do mas[i] := Random(100);
> > i := Random(9) + 1;> mas[i] := 8;> i := Random(9) + 1;
> > mas[i] := 8;
> Не факт.

Вижу. А сразу не заметил.

← →
И. Павел © (2011-03-03 22:39) [15]

> Oleg_teacher (03.03.11 21:11) [3]

Конечно, break, exit и raise противоречат принципам структурного программирования, но без них, ИМХО, иногда код может стать намного сложнее для восприятия, чем с ними. Например, если проверяется много условий, мне кажется, что код выглядит понятнее, если при невыполнении условия делать exit, а не создавать цепочку else if. А цикл for в Delphi вообще не позволяет добавлять условия выхода, так что, чтобы прервать его, без break не обойтись. Ну а без raise обработка ошибок превращается в кошмар :)

← →
Сергей М. © (2011-03-03 22:40) [16]

> че то привык только условиями обходится (ну например для
> выхода из цикла).

Это как ?)
if Выражение then Выйти_из_цикла ?
А Выйти_из_цикла - это, надо понимать, не Break, а goto куда_то_за_пределы_тела_цикла ?)

← →
Oleg_teacher (2011-03-03 22:57) [17]

нет, посему же. Допустим while использую тогда когда нада.... не обезательно if goto. Допустим с goto вообще не дружу категорически!!!

← →
Oleg_teacher (2011-03-03 22:59) [18]

> а не создавать цепочку else if

реально так и делал, когда нада была такая необходимость.

> А цикл for в Delphi вообще не позволяет добавлять условия
> выхода

а зачем только к for быть привязаным?

← →
Oleg_teacher (2011-03-03 23:05) [19]

хотя я так понял ето все на любителя.... вот на одном из сайтов нашел описание:
Описание
Процедура Exit немедленно завершает выполнение текущей функции или процедуры.

При выходе из функции, результат содержит последнее значение.

Предупреждение: используйте с предостережением - это делает обслуживание кода трудным.

← →
Сергей М. © (2011-03-03 23:06) [20]

> while использую тогда когда нада

Было бы странным если бы его можно было использовать тогда когда "ненада"

Но я вообще-то о другом.
Предположим "алгоритмическая диспозиция" у тебя сложилась такова что нет ни никакой возможности условие выхода из цикла определить пред- либо пост-условием соответственно цикла while или repeat.

И что будешь делать ?)

← →
Сергей М. © (2011-03-03 23:07) [21]

> это делает обслуживание кода трудным

Кому и невеста кобыла)

← →
Oleg_teacher (2011-03-03 23:09) [22]

непонимаю тогда куда то в цикл нада будет вставить exit? Всеравно что бы его использовать... нужно будет достичь какое то условие, так почему бы ето условие и не выбрать условием выхода из цыкла while или repeat.

← →
Сергей М. © (2011-03-03 23:19) [23]

Exit - это не выход из цикла, причем он здесь ?
Речь идет о Break - операторе прерывания выполнения цикла, передающем управление оператору, следующему за "закрывающей скобкой" цикла.

> почему бы ето условие и не выбрать условием выхода из цыкла
> while или repeat.

Потому что нередко приключаются ситуации , когда цикл должен быть прерван во время УЖЕ выполняющейся его очередной итерации

← →
Сергей М. © (2011-03-03 23:22) [24]

Вот простейший пример:

> while True do
> try
> DoSomething;
> except
> Break;
> end;

Перепиши его без использования Break - и получишь громоздкий и уродливый код.

← →
Oleg_teacher (2011-03-03 23:25) [25]

> Речь идет о Break

угу, извините неправильно выразился.

> быть прерван во время УЖЕ выполняющейся его очередной итерации

ну немогу представить даже как ето должно быть и где применяется. Ну в общем понятно, что данные команды использовать можно, и ничего плохого в етом нет. Главное самому не запутаться.

← →
Oleg_teacher (2011-03-03 23:28) [26]

> Перепиши его без использования Break - и получишь громоздкий
> и уродливый код.

несоглашусь:
f:=True;
while f do
try
DoSomething;
except
f:=False;
end;

← →
Противный (2011-03-03 23:38) [27]

А как по мне, так очень даже ничего:

function DoSomething: boolean; begin try <...> except Result := false; end; end; while DoSomethig do;

А если еще try-except-end убрать внутри DoComething(), так и вовсе сплошной кошер...

← →
Сергей М. © (2011-03-03 23:39) [28]

> несоглашусь

Ну и не соглашайся)
Но тогда не жалуйся на то что этот "заменитель" :
1. Больше в размере исх.текста (+ еще и переменную надо объявлять)
2. Выполняет минимум на одну "лишнюю" проверку больше, т.е. минимально но уступает оригиналу в производительности.

← →
Противный (2011-03-03 23:46) [29]

> Oleg_teacher (03.03.11 23:28) [26] несоглашусь:

Имхо, флажки еще больше убожество, чем Goto. Проще уж в коде Goto визуально найти, чем проанализировать условие выхода из цикла, а потом отыскивать, в каком месте кода устанавливается то или иное значение флажка. А если флажков несколько, так и вовсе вселенская печаль...

← →
Противный (2011-03-03 23:49) [30]

Сергей М. © (03.03.11 23:22) [24]
> while True do
> try
> DoSomething;
> except
> Break;
> end;

Да, кстати:

try while True do DoSomething; except end;

Соглашусь с Противным (С) - ох тоскливо взирать на код, тем более чужой, с кучей абы как разбросанных проверяемых флажков.
Флажки хороши и нужны там, где без них попросту нельзя обойтись "малой кровью", т.е. без ущерба читабельности кода и сквозной производительности алгоритма.

← →
Противный (2011-03-03 23:51) [32]

[30] Не громоздко, но уродливо... :о(

> Противный (03.03.11 21:31) [12]
> Goto, Break, Exit, Continue, While-Do, Repeat-Until - моветон.
> Всякие Pascal, C, C++ по сути - моветон. Я даже не упоминаю
> C#, Basic и Java. Настоящие джедаи пишут только на Assembler.
> И даже там стараются избегать всяких Loop"ов. Есть только
> семь истинных мнемоник: Mov, Add, Or, And, Shr, Shl и JmpX.
> Все остальное суть происки нечестивцев.

Истину глаголишь, сын мой, ибо от лукавого остальное фсе.

> Да, кстати:
>
> try
> while True do
> DoSomething;
> except
> end;

Фаберже-то они те же, но мы тут за брейк толкуем вроде бы)

← →
Oleg_teacher (2011-03-03 23:54) [36]

Противный [29] - таки наверное да! Но может и без них и не обойтись. Я все таки goto считаю большим убожеством пограммирования.

← →
Противный (2011-03-04 00:03) [37]

> Игорь Шевченко © (03.03.11 23:52) [34] Убивать надо за такой код. Медленно и с наслаждением.

Ты противоречишь сам себе. Код в [24] и [30] как раз это и делает. Убивает. Exception. На корню. Хотя да, не медленно, и без наслаждения. Но быстро и без эмоциональной окраски. А задачи разными бывают. Некрасиво - да. Противоречит Торе - да. Но прав, как всегда, заказчик, а не Святое писание. Как ТЗ поставит - так и будет. И если такой код задачу выполняет, то и "Отче наш" читать не придется.

P.S. Так что, когда собирешься убивать - воспользуйся кодом из 24. Только Break убери. Тогда будет медленно. То есть, вечно...

> Противоречит Торе - да. Но прав, как всегда, заказчик,
> а не Святое писание. Как ТЗ поставит - так и будет.

Да он не только Торе противоречит, но и Корану, Шариату и Тарикату вместе взятым.

Неужели есть заказчики, которые в ТЗ детали быдлокода оговаривают ?

← →
Противный (2011-03-04 00:13) [39]

> Сергей М. © (03.03.11 23:53) [35] но мы тут за брейк толкуем вроде бы

Break, Continue, Exit - рулят.
Goto и суррогатные флажки - отстой.

P. S. Гы...

P. P. S. Интересно это обсуждение выглядит с точки зрения программиста C сотоварищи...

> Игорь Шевченко © (04.03.11 00:07) [38]

> Неужели есть заказчики, которые в ТЗ детали быдлокода оговаривают
> ?

Ага, есть такие)
Надысь расчитался с Заказчиком за один такой образчик.
Портировал ему в Delphi чей-то там BCB-проект, с незначительными функциональными дополнениями.
Так вот там, в портируемом оригинале, такое было понахреноверчено - волосы дыбом встают)
Я честно спросил Заказчика - ты, мол, как потом все это разгребать-то будешь ? И, мол, зачем его дважды разгребать - мне а потом тебе, если достаточно мне одному один раз помучаться, чтобы тебе потом было спокойно и легко ориентироваться в проекте ? Давай, мол, малясь деньжат еще подкинь - и я приведу этот кошмар в божеский вид)
Заказчик, не отрицая что портируемый проект выглядит безобразно, заявил : бабла, мол, больше не дам, мол, самому мало, если берешься за работу, то делай чего говорят и не рассуждай про высокие материи)

Поиск 2 одинаковых элементов в массиве. Найти похожие ветки