| Вопрос: Помогите с алгоритмом | Добавлено: 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 'индекс числа в исходном массиве  iff 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() 'делаем исходный массив (сортированный!!!) igits(0) = 1: Digits(1) = 3: Digits(2) = 6: Digits(3) = 9
igits(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 Вопросов: 236 Ответов: 8362 |
Профиль | | #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 Вопросов: 236 Ответов: 8362 |
Профиль | | #6 | Добавлено: 21.03.06 01:36 |
учту, пасиб 
|
||
|
Номер ответа: 7 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #7 | Добавлено: 21.03.06 18:05 |
| Дисперсия вычисляется для набора чисел, а здесь нужно для одного. Сортировка по модулю разности рулит. | ||
|
Номер ответа: 8 Автор ответа: SergeyICQ: 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 Вопросов: 236 Ответов: 8362 |
Профиль | | #9 | Добавлено: 21.03.06 21:46 |
|
Сергей, спасибо за интерес, но я задачу решил именно так как подсказал
HOOLIGAN. Мне совсем ненужно было сохранять исходный массив... |
||
|
Номер ответа: 10 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #10 | Добавлено: 21.03.06 22:16 |
| Sergey, сравни порядок алгоритмов и задайся вопросом "А смысл?" | ||
Страница: 1 |