Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Помогите с алгоритмом Добавлено: 19.03.06 03:48  

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

И так задача: Найти в массиве N чисел которые наиболее близки к числу
Z

*Массив я отсортировал

Далее пытаюсь по разности элементов в массиве (index + 1) и (index -
1) определить какое число взять, но напарываюсь на кучи "особых"
случаев, которых уже много, и чем дальше тем я понимаю идеального
алгоритма существовать неможет...

*Число Z не обязательно может быть одним из элементов массива.

Пример, массив с числами:

1, 3, 6, 9, 12, 13, 15, 16

При N = 3 и Z = 12, мы должны получить

9, 12, 13 - т.е. всего 3 элемента. 1 искомый + 2 которые наболее
близкие к нему...

Ещё пример:
тот же массив с набором чисел, но
N = 2 и Z = 11, мы должны получить тоже 9, 12, 13 ! т.к. к 11 которой
нет всёравно наиболее близкие 3 эл. это 9, 12, 13

Примечание:
(под индексом понимаю текущий, который проверяется в данный момент)
Если разность (index - (index-1)) = (index - (index+1)) то брать
который больше, т.е. index + 1.

Вот никак неполучается добится работоспособности при любых критериях
отбора.

Вот что у меня получилось, там попутно некоторые функции которые я
небуду приводить, типа добавление в ListView, поиск в нём же,
сортировка массива итп...


Private Sub cmdFind_Click()
    'Подпрограмма поиска по диапазону из главного листа
    
    'Рабочие лошадки :)
    Dim i As Integer, j As Integer, CountGoods As Integer, index As Integer, LV_Index As Integer, _
     LastIndex As Integer, MaxCount As Integer
    Dim lvItm As Object
    Dim DiffSmaller As Single, DiffLarge As Single
    
    Dim myArray() As Single 'динамический массив для хранения цен
    'Устанавливаем размерность массива равное кол-ву записией в ListView - 1,
    'т.к. в ListView записи нумеруются с 1, а в массиве с 1
    ReDim myArray(frmMain.ListView1.ListItems.Count - 1)
    
    ListView1.ListItems.Clear
    
    'Цикл для перебора всех записей на главной форме (формируем массив цен)
    For i = 1 To frmMain.ListView1.ListItems.Count
            myArray(i - 1) = CSng(frmMain.ListView1.ListItems(i).SubItems(1))  'Цена
    Next i
    
    'Например сейчас в массве: 1.50|0.50|0.40|1.00|2.00
    'Теперь сортируем наш массив по возрастанию
    
    index = GetIndexByValue(Val(txtMoney), myArray)
    If index = -1 Then
        ReDim Preserve myArray(UBound(myArray) + 1)
        myArray(UBound(myArray)) = Val(txtMoney)
    End If
    
    
    Call mdlArray.QuickSortNonRecursive(myArray)
    
    For i = 0 To UBound(myArray)
        Debug.Print myArray(i)
    Next i
    
    'После сортировки будет: 0.40|0.50|1.00|1.50|2.00
    index = GetIndexByValue(Val(txtMoney), myArray)
    MaxCount = Val(txtCountGoods)
    
        ListView1.ListItems.Clear
    
        For i = 0 To UBound(myArray)
        'On Error Resume Next
            DiffSmaller = Round(myArray(index) - myArray(IIf(index - i < 0, 0, index - i)), 5)
            If Err.Number = 0 Then
                DiffLarge = Round(myArray(index + i) - myArray(index), 5)
            Else
                DiffLarge = DiffSmaller + 1
            End If
            If DiffSmaller = DiffLarge And i = 0 Then
               LV_Index = FindIndexByStringInListView(frmMain.ListView1, CStr(myArray(index - i)), 2)
               If LV_Index <> 0 And LV_Index <> LastIndex Then
                    Call AddToLV(frmMain.ListView1.ListItems(LV_Index), frmMain.ListView1.ListItems(LV_Index).SubItems(1))
                    CountGoods = CountGoods + 1
                    LastIndex = LV_Index
               End If
            ElseIf DiffSmaller = DiffLarge And i <> 0 Then
                 LV_Index = FindIndexByStringInListView(frmMain.ListView1, CStr(myArray(index + i)), 2)
                    If LV_Index <> 0 And LV_Index <> LastIndex Then
                          Call AddToLV(frmMain.ListView1.ListItems(LV_Index), frmMain.ListView1.ListItems(LV_Index).SubItems(1))
                          CountGoods = CountGoods + 1
                          LastIndex = LV_Index
                          If CountGoods >= MaxCount Then GoTo exitfor
                    End If
                LV_Index = FindIndexByStringInListView(frmMain.ListView1, CStr(myArray(index - i)), 2)
                    If LV_Index <> 0 And LV_Index <> LastIndex Then
                        Call AddToLV(frmMain.ListView1.ListItems(LV_Index), frmMain.ListView1.ListItems(LV_Index).SubItems(1))
                        CountGoods = CountGoods + 1
                        LastIndex = LV_Index
                        If CountGoods >= MaxCount Then GoTo exitfor
                    End If
            ElseIf DiffSmaller > DiffLarge Then
                LV_Index = FindIndexByStringInListView(frmMain.ListView1, CStr(myArray(index + i)), 2)
                If LV_Index <> 0 And LV_Index <> LastIndex Then
                    Call AddToLV(frmMain.ListView1.ListItems(LV_Index), frmMain.ListView1.ListItems(LV_Index).SubItems(1))
                    CountGoods = CountGoods + 1
                    LastIndex = LV_Index
                    If CountGoods >= MaxCount Then GoTo exitfor
                End If
                    
            ElseIf DiffSmaller < DiffLarge Then
                LV_Index = FindIndexByStringInListView(frmMain.ListView1, CStr(myArray(index - i)), 2)
                If LV_Index <> 0 And LV_Index <> LastIndex Then
                    Call AddToLV(frmMain.ListView1.ListItems(LV_Index), _
                    frmMain.ListView1.ListItems(LV_Index).SubItems(1))
                    CountGoods = CountGoods + 1
                    LastIndex = LV_Index
                    If CountGoods >= MaxCount Then GoTo exitfor
                End If
            End If
        Next i
exitfor:
End Sub

Public Function FindIndexByStringInListView(ListView As ListView, strFindString As String, IndexColumn As Byte) As Integer
'Возвращает индекс элемента с указанными в ListView по указанному столбцу
'Если не нашли возвращает 0
    Dim i As Integer
    For i = 1 To ListView.ListItems.Count
        If IndexColumn = 1 Then
            If strFindString = ListView.ListItems(i).Text Then FindIndexByStringInListView = i: Exit Function
        Else
            If strFindString = ListView.ListItems(i).SubItems(IndexColumn - 1) Then FindIndexByStringInListView = i: Exit Function
        End If
    Next i
    FindIndexByStringInListView = 0
End Function

Public Function GetIndexByValue(DataToFind As Single, sArray() As Single) As Long
'Находит в массиве данные и возвращает их индекс, если не нашли -1
    Dim i As Long
    For i = LBound(sArray) To UBound(sArray)
        If sArray(i) = DataToFind Then
            GetIndexByValue = i
            Exit Function
        End If
    Next i
    GetIndexByValue = -1
End Function









Ответить

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

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



Вопросов: 0
Ответов: 1066
 Профиль | | #1 Добавлено: 19.03.06 05:03
Чё-то наворотил ты здесь непонятностей.
Если массив исходных чисел сортированный, то делаем так:

Private Type ElementData
   Value As Long        'значение числа из исходного массива
   index As Long        'индекс числа в исходном массиве
   ;Diff  As Long        'разница между числом и эталоном
End Type

Dim NArr() As ElementData       'выходной массив структур
Dim Digits(0 To 7) As Long      'исходный массив чисел
Dim Z As Long

Sub Insert(ByVal pos As Long, ByVal index As Long)
    Dim i As Long
    i = pos
    For i = 0 To pos - 1
        NArr(i) = NArr(i + 1)
    Next i
    NArr(pos).Diff = Abs(Digits(index) - Z)
    NArr(pos).index = index
    NArr(pos).Value = Digits(index)
End Sub

Private Sub Form_Load()
    'делаем исходный массив (сортированный!!!)
    ;Digits(0) = 1: Digits(1) = 3: Digits(2) = 6: Digits(3) = 9
    ;Digits(4) = 12: Digits(5) = 13: Digits(6) = 15: Digits(7) = 16
    Dim N As Long, i As Long
    'кол-во отбираемых чисел и эталон для сравнения
    N = 3: Z = 12
    ReDim NArr(0 To N - 1)
    For i = 0 To N - 1
        NArr(i).Value = Digits(i)
        NArr(i).index = i
        NArr(i).Diff = Abs(Z - NArr(i).Value)
    Next i
    
    For i = N To UBound(Digits())
        For j = N - 1 To 0 Step -1
            If Abs(Digits(i) - Z) < NArr(j).Diff Then
                Insert j, i
                Exit For
            End If
        Next j
    Next i
    
    For i = 0 To UBound(NArr())
        Debug.Print "--------"
        Debug.Print NArr(i).Value
        Debug.Print NArr(i).index
        Debug.Print NArr(i).Diff
    Next i
    
End Sub


В массиве NArr будут сидеть твои N отобранных из исходного массива чисел (со всеми их характеристиками), сортированные в порядке убывания разности с эталоном.

Если исходный массив не сортированный, то сначала сортировать.

Ответить

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



Вопросов: 0
Ответов: 1066
 Профиль | | #2 Добавлено: 19.03.06 15:06
Если задача олимпиадная, то скорее она не на программирование, а на сообразительность: если сообразить, что сортировать нужно не по значению элементов массива, а по разности элементов с числом Z, то решение предельно простое:

Sub sort(arr() As Long, Val As Long)
    Dim i As Long, t As Long, s As Long
    Do
    s = 0
    For i = LBound(arr()) To UBound(arr()) - 1
        If Abs(arr(i) - Val) > Abs(arr(i + 1) - Val) Then
            t = arr(i): arr(i) = arr(i + 1): arr(i + 1) = t
            s = 1
        End If
    Next
    Loop While s
End Sub

Private Sub Form_Load()
    Dim A(0 To 7) As Long
    A(0) = 4: A(1) = 14: A(2) = 6: A(3) = 9
    A(4) = 12: A(5) = 8: A(6) = 16: A(7) = 13
    sort A(), 12
End Sub


Исходный массив несортированый.
После обработки массива первые N элементов содержат числа, наиболее близкие к Z.

Ответить

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



ICQ: 225421504 

Вопросов: 8
Ответов: 60
 Профиль | | #3 Добавлено: 19.03.06 15:24

или вот так:
Dim m(7), r(7) As Double
        Dim i, n, z, s, b As Double
        Dim it As String
        m(0) = 1 : m(1) = 3 : m(2) = 6 : m(3) = 9
        m(4) = 12 : m(5) = 13 : m(6) = 15 : m(7) = 16
        n = 3 : z = 11
        For i = 0 To 7
            r(i) = Math.Abs(Math.Abs(m(i)) - Math.Abs(z))
        Next
        Do
            s = 0
            For i = 0 To 6
                If r(i) > r(i + 1) Then
                    b = r(i) : r(i) = r(i + 1) : r(i + 1) = b
                    b = m(i) : m(i) = m(i + 1) : m(i + 1) = b
                    s = s + 1
                End If
            Next
        Loop Until s = 0
        For i = 0 To n - 1
            it = it + " " + m(i).ToString
        Next
        TextBox1.Text = it
    End Sub

Ответить

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


 

Разработчик Offline Client

Вопросов: 235
Ответов: 8360
 Профиль | | #4 Добавлено: 19.03.06 17:10
HOOLIGAN!!!!!1 Большое спасибо! Я даже не думал сортировать по разности! Respect!


Wolfrt, тоже спасибо!

Ответить

Номер ответа: 5
Автор ответа:
 Fever



Вопросов: 60
Ответов: 808
 Профиль | | #5 Добавлено: 20.03.06 10:27
Разность? Близкость к числу это матожидание:
D=sqr((p-x1)^2+(p-x2)^2+...+(p-xn)^2)
где p=(x1+x2+...+xn)/n

Ответить

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


 

Разработчик Offline Client

Вопросов: 235
Ответов: 8360
 Профиль | | #6 Добавлено: 21.03.06 01:36
учту, пасиб :)

Ответить

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


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #7
Добавлено: 21.03.06 18:05
Дисперсия вычисляется для набора чисел, а здесь нужно для одного. Сортировка по модулю разности рулит.

Ответить

Номер ответа: 8
Автор ответа:
 Sergey



ICQ: 283551900 

Вопросов: 1
Ответов: 74
 Профиль | | #8 Добавлено: 21.03.06 19:09
И так задача: Найти в массиве N чисел которые наиболее близки к числу Z


Где сказано, что элементы должны быть отсортированы?

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

Алгоритм: (подразумевается, что знаете быструю сортировку).
Подразумевается что сравнение везде происходит по модулю(элемент -Z).

Шаг 1) также как и в быстрой сортировке выбирается число P относительно которого будем разбивать на 2 группы.
Шаг 2) массив разбивается на 2 группы в первой элементы меньше или равны P а во второй больше P.
Шаг 3)
Если в левой группе меньше N элементов то забываем про правую часть и для левой части выполняем все заново с шага 1.
Если в левой части N элементов то нашли все N элементов ‘выход’.
Если в левой части K элементов K<N то нашли K элементов осталось N–K. Повторяем все с шага 1 для правой части и ищем уже N-K элементов.
Шаг 4) вроде все.

Ответить

Номер ответа: 9
Автор ответа:
 HACKER


 

Разработчик Offline Client

Вопросов: 235
Ответов: 8360
 Профиль | | #9 Добавлено: 21.03.06 21:46
Сергей, спасибо за интерес, но я задачу решил именно так как подсказал
HOOLIGAN. Мне совсем ненужно было сохранять исходный массив...

Ответить

Номер ответа: 10
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #10
Добавлено: 21.03.06 22:16
Sergey, сравни порядок алгоритмов и задайся вопросом "А смысл?"

Ответить

Страница: 1 |

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





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