Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Общий форум

Страница: 1 |

 

  Вопрос: Математика Добавлено: 18.11.03 22:18  

Автор вопроса:  cresta
Есть набор чисел. Числа двенадцатизначные, расположены в
произвольном порядке. Число элементов в наборе может достигать
нескольких десятков тысяч.Как можно быстро определить минимальное свободное значение,
не встречающееся в наборе?
Например:
311928374667
029384756473
798765432765
.
.
.
319283700919
чтобы получить 029384756474 ( второе значение +1)
Последовательный перебор всех значений набора с последующим сравнением с
каждым значением набора на предмет а=а+1 в самом неблагоприятном случае потребует
при количестве элементов в наборе 50000 пройти весь набор 2500000000 раз.
Может кто знает какой-нибудь алгоритм получения минимального неиспользуемого в наборе
значения? Подскажите что-нибудь по этому поводу

Ответить

  Ответы Всего ответов: 9  

Номер ответа: 1
Автор ответа:
 Pashenko



ICQ: 176176951 

Вопросов: 14
Ответов: 655
 Профиль | | #1 Добавлено: 19.11.03 10:03
Попробуй сначала отсортировать список.

Ответить

Номер ответа: 2
Автор ответа:
 cresta



Вопросов: 117
Ответов: 1538
 Профиль | | #2 Добавлено: 19.11.03 12:53
Если отсортировать имеется ввиду выстроить по возрастанию, то это как-раз и есть собственно говоря, конечная задача т.к. потом пробежать отсортированный набор и проверить каждый номер на существование номер+1 дело недолгое.

Ответить

Номер ответа: 3
Автор ответа:
 Pashenko



ICQ: 176176951 

Вопросов: 14
Ответов: 655
 Профиль | | #3 Добавлено: 19.11.03 13:22
Существует метод быстрой сортировки, т. н. Quiсk Sort.
Сам не реализовывал, но принцип такой:

1. Выбираем число в центре массива.
2. Последовательно сравниваем с ним все числа массива, если число,
стоящее выше, больше среднего, меняем их местами (для второй половины,
соответственно, наоборот). Таким образом получаем в первой половине
массива все числа меньше среднего, во второй половине - больше среднего.
3. Повторяем пп. 1, 2 для каждой половины массива (среднее число можно
исключить из рассмотрения), потом для каждой четверти и т. д. до упора.

Весь алгоритм, как правило выполняют в виде рекурсивной процедуры.

P. S. Насколько я знаю, более быстрого способа сортировки пока не
придумали.

Ответить

Номер ответа: 4
Автор ответа:
 cresta



Вопросов: 117
Ответов: 1538
 Профиль | | #4 Добавлено: 19.11.03 15:40
Попробую, спасибо

Ответить

Номер ответа: 5
Автор ответа:
 Павел



Администратор

ICQ: 326066673 

Вопросов: 368
Ответов: 5968
 Web-сайт: www.vbnet.ru
 Профиль | | #5
Добавлено: 19.11.03 16:37
Гениально! Тогда ему нужно сортироват не весь массив, а после первого
прохода сортировать первую половину, потом первую четверть и т.д.
Получится намного быстрее!

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

Ответить

Номер ответа: 6
Автор ответа:
 Pashenko



ICQ: 176176951 

Вопросов: 14
Ответов: 655
 Профиль | | #6 Добавлено: 19.11.03 17:00
> нужно сортироват не весь массив, а после первого прохода сортировать
первую половину, потом первую четверть и т.д.
Вообще говоря, рекурсивный алгоритм подразумевает именно такой порядок
перебора.

Ответить

Номер ответа: 7
Автор ответа:
 cresta



Вопросов: 117
Ответов: 1538
 Профиль | | #7 Добавлено: 19.11.03 18:17

Что-то посмотрел я на Quick Sort и мне показалось что этот метод только усугу[sensored]ет
положение т.к. кроме самого просмотра необходимо ещё и переставлять элементы набора,
 что скорости не прибавляет никак
Короче состряпал такую функцию

Public Function findFreeCode() As String
    Dim recCount As Integer, i As Integer, j As Integer
    Dim Min  As Double, FreeCode As Double
    Dim arr() As Double
    Adodc1.Recordset.MoveLast
    recCount = Adodc1.Recordset.RecordCount
    ReDim arr(recCount - 1) As Double ' определяем количество элементов в массиве
    Adodc1.Recordset.MoveFirst
    While Not Adodc1.Recordset.EOF 'заполнение массива кодами
        arr(Adodc1.Recordset.AbsolutePosition - 1) = CDbl(Adodc1.Recordset.Fields(0).Value)
        Adodc1.Recordset.MoveNext
    Wend
    Adodc1.Recordset.MoveFirst
    FreeCode = 0 'поиск свободного кода начиная с 1
lbl_reSearch:
    For i = 0 To recCount - 1 'просмотр массива на присутствие кода FreeCode +1
            If FreeCode + 1 = arr(i) Then ' если искомый код существует,
                FreeCode = arr(i) ' запоминаем его
                GoTo lbl_reSearch' ищем следующий
            End If
    Next i
    FreeCode = FreeCode + 1
    findFreeCode = PadToString(Trim$(Str(FreeCode)), 12)
End Function

И ещё будет ли такой вариант цикла работать быстрее(т.е. количество проходов меньше
в 10 раз, но за каждый проход проверяется 10 значений):

For i = 0 To recCount - 1 step 10  'просмотр массива на присутствие кода FreeCode +1...+10
 If FreeCode + 1 = arr(i) Then ' если искомый код существует,
                FreeCode = arr(i) ' запоминаем его
                GoTo lbl_reSearch' ищем следующий
        End If
 If FreeCode + 2 = arr(i) Then ' если искомый код существует,
                FreeCode = arr(i) ' запоминаем его
                GoTo lbl_reSearch' ищем следующий
        End If
 ...
 ...
  If FreeCode + 10 = arr(i) Then ' если искомый код существует,
                FreeCode = arr(i) ' запоминаем его
                GoTo lbl_reSearch' ищем следующий
        End If
    
Next i

Ответить

Номер ответа: 8
Автор ответа:
 Павел



Администратор

ICQ: 326066673 

Вопросов: 368
Ответов: 5968
 Web-сайт: www.vbnet.ru
 Профиль | | #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
Автор ответа:
 cresta



Вопросов: 117
Ответов: 1538
 Профиль | | #9 Добавлено: 26.11.03 13:04

Павел, спасибо что переслали сообщение. А быстрый поиск я реализовал, использовав метод RS.Sort  и вместо массива использовав переменную типа Variant, т.к. переменная заполняется очень быстро и без цикла, на что уходило немало времени. Может кому пригодится:

Private function Свободный_Номер() as Double
Dim i As Long
Dim varDataRows As Variant
RS.Sort = "Code" 'сортировка RS по полю "Код"    RS.MoveLast
    recCount = RS.RecordCount
    RS.MoveFirst
    varDataRows = RS.GetRows(recCount) ' делаем снимок со всего рекордсета сразу                           For i = 1 To recCount
        If i < CDbl(varDataRows(0, i - 1)) Then 'если условие верно, значит есть пропущеное в наборе кодов
            'обозначаем пропущеное как свободный номер 

           Свободный_Номер=i: Exit Function
        End If
    Next i
End Function

Помогло наличие RecordSet.Sort и нещадно ругаемая всеми переменная типаVariant. Результат-просмотр 50000 записей в самом неблагоприятном случае занимает ок.2сек. Спасибо всем.

Ответить

Страница: 1 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам