Форум: "Начинающим";
Текущий архив: 2011.06.12;
Скачать: [xml.tar.bz2];
ВнизПоиск 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) [31]Соглашусь с Противным (С) - ох тоскливо взирать на код, тем более чужой, с кучей абы как разбросанных проверяемых флажков.
Флажки хороши и нужны там, где без них попросту нельзя обойтись "малой кровью", т.е. без ущерба читабельности кода и сквозной производительности алгоритма.
← →
Противный (2011-03-03 23:51) [32][30] Не громоздко, но уродливо... :о(
← →
Andy BitOff © (2011-03-03 23:52) [33]> Противный (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.
> Все остальное суть происки нечестивцев.
Истину глаголишь, сын мой, ибо от лукавого остальное фсе.
← →
Игорь Шевченко © (2011-03-03 23:52) [34]Сергей М. © (03.03.11 23:22) [24]
Противный (03.03.11 23:49) [30]
Убивать надо за такой код. Медленно и с наслаждением.
← →
Сергей М. © (2011-03-03 23:53) [35]
> Да, кстати:
>
> 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:07) [38]
> Противоречит Торе - да. Но прав, как всегда, заказчик,
> а не Святое писание. Как ТЗ поставит - так и будет.
Да он не только Торе противоречит, но и Корану, Шариату и Тарикату вместе взятым.
Неужели есть заказчики, которые в ТЗ детали быдлокода оговаривают ?
← →
Противный (2011-03-04 00:13) [39]> Сергей М. © (03.03.11 23:53) [35] но мы тут за брейк толкуем вроде бы
Break, Continue, Exit - рулят.
Goto и суррогатные флажки - отстой.
P. S. Гы...
P. P. S. Интересно это обсуждение выглядит с точки зрения программиста C сотоварищи...
← →
Сергей М. © (2011-03-04 00:26) [40]
> Игорь Шевченко © (04.03.11 00:07) [38]
> Неужели есть заказчики, которые в ТЗ детали быдлокода оговаривают
> ?
Ага, есть такие)
Надысь расчитался с Заказчиком за один такой образчик.
Портировал ему в Delphi чей-то там BCB-проект, с незначительными функциональными дополнениями.
Так вот там, в портируемом оригинале, такое было понахреноверчено - волосы дыбом встают)
Я честно спросил Заказчика - ты, мол, как потом все это разгребать-то будешь ? И, мол, зачем его дважды разгребать - мне а потом тебе, если достаточно мне одному один раз помучаться, чтобы тебе потом было спокойно и легко ориентироваться в проекте ? Давай, мол, малясь деньжат еще подкинь - и я приведу этот кошмар в божеский вид)
Заказчик, не отрицая что портируемый проект выглядит безобразно, заявил : бабла, мол, больше не дам, мол, самому мало, если берешься за работу, то делай чего говорят и не рассуждай про высокие материи)
← →
Игорь Шевченко © (2011-03-04 01:08) [41]Сергей М. © (04.03.11 00:26) [40]
СлучАи, они, конечно, завсегда разные бывают :)
← →
Германн © (2011-03-04 03:08) [42]
> Игорь Шевченко © (04.03.11 01:08) [41]
>
> Сергей М. © (04.03.11 00:26) [40]
>
> СлучАи, они, конечно, завсегда разные бывают :)
>
Это точно!
Но твой взгляд на эти "случАи" меня смущает.
Никак не могу тебя понять. И не только в данном сабже.
← →
Jeer © (2011-03-04 09:24) [43]
> Я все таки goto считаю большим убожеством пограммирования.
Считай, но про себя.
P.S.
Случаи разные бывают, буквально вчера перекидывал с Фортрана на Pascal.
Там штук 50 было goto. Зачем мне алгоритм ломать, который работает, да еще и ошибки свои отлавливать ?
Сделал с goto и ничего, Бог Кару не прислал.
← →
Противный (2011-03-04 09:43) [44]>> Случаи разные бывают, буквально вчера перекидывал с Фортрана на Pascal.
Одно дело - рутинный перевод больших объемов кода с языка, в котором goto является реально необходимой командой. А другое дело - перенос привычек программирования из одного языка программирования в другой.
"Настоящий программист может писать фортрановские программы на любом языке программирования" (С)
Значок хочешь? Голубой? Или красный? Или нет, лучше... коричневый. Со статусом "Мастер Фортрана".
P.S. Ты бы еще Бейсик вспомнил...
← →
Anatoly Podgoretsky © (2011-03-04 10:14) [45]> Andy BitOff (03.03.2011 23:52:33) [33]
Именно так, при правильной технологии это можно делать быстрее, чем на
указаных языках, но придется много потрудиться над разработкой макросов
← →
Jeer © (2011-03-04 10:19) [46]
> Противный (04.03.11 09:43) [44]
>
> P.S. Ты бы еще Бейсик вспомнил...
За меня решать не надо, что я хочу.
Что хочу, то и делаю по ситуации, но при этом не даю советы, что это путь к счастью.
> с языка, в котором goto является реально необходимой командой.
Ну ты еще Fortran 66 вспомни.
Сейчас goto не является необходимой, но пользуется.
← →
Противный (2011-03-04 10:35) [47]> Jeer © (04.03.11 10:19) [46] Сейчас goto не является необходимой, но пользуется
Повторюсь: "Настоящий программист может писать фортрановские программы на любом языке программирования" (С)
Ковыряние в носу тоже не является необходимым.
Но ковыряются ведь.
По той простой причине, что нос есть.
Не было бы носа - не ковырялись бы.
Такая же ситуация и с goto.
P.S. Да простят меня любители ковыряться в носу, если я невольно ущимил их права.
← →
Anatoly Podgoretsky © (2011-03-04 11:00) [48]
> Сейчас goto не является необходимой, но пользуется.
Гены
← →
Jeer © (2011-03-04 15:11) [49]Удалено модератором
← →
clickmaker © (2011-03-04 15:28) [50]Удалено модератором
← →
Противный (2011-03-04 15:52) [51]Удалено модератором
← →
Jeer © (2011-03-04 16:30) [52]Удалено модератором
← →
clickmaker © (2011-03-04 16:31) [53]Удалено модератором
← →
Jeer © (2011-03-04 16:41) [54]Удалено модератором
Страницы: 1 2 вся ветка
Форум: "Начинающим";
Текущий архив: 2011.06.12;
Скачать: [xml.tar.bz2];
Память: 0.6 MB
Время: 0.004 c