Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: < 1 2 3
Leon-Z © (2011-03-03 20:35:00)
Дан массив - 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;
Есть другие методы ?

Leon-Z (2011-03-03 22:00:00) [41]

> Противный (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;
> Не факт.

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

KilkennyCat (2011-03-03 21:31:00) [42]

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

я в курсе.

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

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

Противный (2011-03-03 21:31:00) [43]
> 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. Все остальное суть происки нечестивцев.

Oleg_teacher (2011-03-03 21:30:00) [44]

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

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

Oleg_teacher (2011-03-03 21:28:00) [45]

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

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

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

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

Сергей М. (2011-03-03 21:23:00) [46]

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

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

KilkennyCat (2011-03-03 21:23:00) [47]
для отсортированных бинарный поиск не нужен, под такую задачу. достаточно сдвигать один относительного другого, сравнивая элементы.

Oleg_teacher (2011-03-03 21:20:00) [48]
к чему я веду... ну например, рассмотрим задачу поиска элемента в массиве. По количеству операций для меня самый ефективный способ есть последовательное сравнение елементов. Но когда в одном и том же масиве (большом) нам надо будет находить много раз разные елементы - тогда я предпочитаю сначала его быстрым методом отсортировать и использовать например бинарный поиск. Как на меня при таком варианте прога работает быстрее...

KilkennyCat (2011-03-03 21:19:00) [49]

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

неверно.

Oleg_teacher (2011-03-03 21:14:00) [50]

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

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

Leon-Z (2011-03-03 21:11:00) [51]
Замечания приняты.
А насчет алгоритма - существуют ли другие алгоритмы, быстрее этого ?
(написать на assembler'e - не предлогать).

Oleg_teacher (2011-03-03 21:11:00) [52]

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

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

И. Павел (2011-03-03 21:06:00) [53]
Если нужно искать только одну пару одинаковых чисел, то после того, как их найдете, не забудьте поставить break, чтобы цикл не продолжился впустую.

Oleg_teacher (2011-03-03 21:01:00) [54]
если согласно условия два одинаковых елемента есть точно, тогда может быстрее использовать два while. Будет меньше операций в общем случае.

Страницы: < 1 2 3

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »