Страница: 1 |
Вопрос: Математика | Добавлено: 18.11.03 22:18 |
Автор вопроса: ![]() |
Есть набор чисел. Числа двенадцатизначные, расположены в произвольном порядке. Число элементов в наборе может достигать нескольких десятков тысяч.Как можно быстро определить минимальное свободное значение, не встречающееся в наборе? Например: 311928374667 029384756473 798765432765 . . . 319283700919 чтобы получить 029384756474 ( второе значение +1) Последовательный перебор всех значений набора с последующим сравнением с каждым значением набора на предмет а=а+1 в самом неблагоприятном случае потребует при количестве элементов в наборе 50000 пройти весь набор 2500000000 раз. Может кто знает какой-нибудь алгоритм получения минимального неиспользуемого в наборе значения? Подскажите что-нибудь по этому поводу ![]() |
Ответы | Всего ответов: 9 |
Номер ответа: 1 Автор ответа: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ICQ: 176176951 Вопросов: 14 Ответов: 655 |
Профиль | Цитата | #1 | Добавлено: 19.11.03 10:03 |
Попробуй сначала отсортировать список. |
Номер ответа: 2 Автор ответа: ![]() ![]() ![]() Вопросов: 117 Ответов: 1538 |
Профиль | Цитата | #2 | Добавлено: 19.11.03 12:53 |
Если отсортировать имеется ввиду выстроить по возрастанию, то это как-раз и есть собственно говоря, конечная задача ![]() |
Номер ответа: 3 Автор ответа: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ICQ: 176176951 Вопросов: 14 Ответов: 655 |
Профиль | Цитата | #3 | Добавлено: 19.11.03 13:22 |
Существует метод быстрой сортировки, т. н. Quiсk Sort. Сам не реализовывал, но принцип такой: 1. Выбираем число в центре массива. 2. Последовательно сравниваем с ним все числа массива, если число, стоящее выше, больше среднего, меняем их местами (для второй половины, соответственно, наоборот). Таким образом получаем в первой половине массива все числа меньше среднего, во второй половине - больше среднего. 3. Повторяем пп. 1, 2 для каждой половины массива (среднее число можно исключить из рассмотрения), потом для каждой четверти и т. д. до упора. Весь алгоритм, как правило выполняют в виде рекурсивной процедуры. P. S. Насколько я знаю, более быстрого способа сортировки пока не придумали. |
Номер ответа: 4 Автор ответа: ![]() ![]() ![]() Вопросов: 117 Ответов: 1538 |
Профиль | Цитата | #4 | Добавлено: 19.11.03 15:40 |
Попробую, спасибо![]() |
Номер ответа: 5 Автор ответа: ![]() ![]() ![]() ![]() ![]() ![]() ![]() Администратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | Цитата | #5 | Добавлено: 19.11.03 16:37 |
Гениально! Тогда ему нужно сортироват не весь массив, а после первого прохода сортировать первую половину, потом первую четверть и т.д. Получится намного быстрее! А вообще, наверное, сущесвуют математические методы (я недавно походую олимпиадную задачу видел). |
Номер ответа: 6 Автор ответа: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ICQ: 176176951 Вопросов: 14 Ответов: 655 |
Профиль | Цитата | #6 | Добавлено: 19.11.03 17:00 |
> нужно сортироват не весь массив, а после первого прохода сортировать первую половину, потом первую четверть и т.д. Вообще говоря, рекурсивный алгоритм подразумевает именно такой порядок перебора. |
Номер ответа: 7 Автор ответа: ![]() ![]() ![]() Вопросов: 117 Ответов: 1538 |
Профиль | Цитата | #7 | Добавлено: 19.11.03 18:17 |
Что-то посмотрел я на Quick Sort и мне показалось что этот метод только усугу[sensored]ет Public Function findFreeCode() As String И ещё будет ли такой вариант цикла работать быстрее(т.е. количество проходов меньше For i = 0 To recCount - 1 step 10 'просмотр массива на присутствие кода FreeCode +1...+10 |
Номер ответа: 8 Автор ответа: ![]() ![]() ![]() ![]() ![]() ![]() ![]() Администратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | Цитата | #8 | Добавлено: 26.11.03 08:48 |
Тут мне такое письмо пришло: --------- если можете, то добавьте в http://vbnet.ru/forum/show.asp?id=27174 такой ответ почему-то у меня не получилось я думаю автору надо было уточнить вопрос Как можно быстро определить минимальное свободное значение, не встречающееся в наборе, но больше минимального встречающегося ? Задача решается за три сканирования: 1.ищем минимальное число в массиве 2.заполняем еще один массив отметками о числах не больших (минимальное+количество чисел) 3.ищем в этом массиве отсутствие отметки вот пример Public Function funPoiskNovogoChisla() As Currency 'подготовительная работа - создадим массив и заполним его Dim Kolvo As Long 'количество чисел в массиве Kolvo = 100000 'пусть будет, например, 100 тысяч Dim Massiv() As Currency 'объявляем массив ReDim Massiv(Kolvo) 'UBound массива устанавливаем равным Kolvo Dim i As Long, x1 As Currency, x2 As Currency 'вспомогательные переменные For i = 1 To UBound(Massiv) 'заполним массив случайными числами Randomize x1 = Int(1000000 * Rnd) Randomize x2 = Int(1000000 * Rnd) Massiv(i) = x1 * 1000000 + x2 Next i 'переходим к решению задачи - поиску минимального свободного значения, 'не встречающееся в наборе 'сначала найдем наименьшее число в массиве Dim MinChislo As Currency 'наименьшее число в массиве MinChislo = Massiv(1) 'пусть будет равно первому числу в массиве For i = 2 To UBound(Massiv) If MinChislo > Massiv(i) Then MinChislo = Massiv(i) Next i Dim NovChislo As Currency 'число которое надо найти Dim NovMassiv() As Boolean 'создадим еще один массив ReDim NovMassiv(Kolvo + 1) 'UBound нового массива устанавливаем равным (Kolvo+1) For i = 1 To UBound(Massiv) 'просканируем исходный массив If Massiv(i) - MinChislo <= UBound(Massiv) Then 'если число не больше минимального 'на количество чисел в массиве NovMassiv(Massiv(i) - MinChislo + 1) = True 'то в новом массиве отметим End If 'что такое число есть Next i For i = 1 To UBound(NovMassiv) 'просканируем новый массив If NovMassiv(i) = False Then 'незанятое место! NovChislo = MinChislo + i - 1 'вот и новое число Exit For 'выходим из сканирования End If Next i funPoiskNovogoChisla = NovChislo End Function --------- |
Номер ответа: 9 Автор ответа: ![]() ![]() ![]() Вопросов: 117 Ответов: 1538 |
Профиль | Цитата | #9 | Добавлено: 26.11.03 13:04 |
Павел, спасибо что переслали сообщение. А быстрый поиск я реализовал, использовав метод RS.Sort и вместо массива использовав переменную типа Variant, т.к. переменная заполняется очень быстро и без цикла, на что уходило немало времени. Может кому пригодится: Private function Свободный_Номер() as Double Свободный_Номер=i: Exit Function Помогло наличие RecordSet.Sort и нещадно ругаемая всеми переменная типаVariant. Результат-просмотр 50000 записей в самом неблагоприятном случае занимает ок.2сек. Спасибо всем. |
Страница: 1 |
|