Форум программистов, компьютерный форум, киберфорум
VBA
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
0 / 0 / 0
Регистрация: 26.02.2012
Сообщений: 7

Обход с возвратом, указать стартовую ячейку

25.03.2012, 22:58. Показов 2507. Ответов 9
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Необходимо создать программу, реализующую обход с возвратом. Но стартовать нужно не с ячейки
А(1,1), а , например, с А(5,7).

Подскажите, пожалуйста, как это сделать
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
25.03.2012, 22:58
Ответы с готовыми решениями:

Обход шахматной доски конём, используя метод перебора с возвратом
На шахматной доске n×m в первой строке в первом столбце находится конь. Составьте план перемещения коня по шахматной доске таким образом,...

Указать стартовую директорию для диалога выбора файла
здравствуйте, помогите разобраться с запросом. Я сделал форму в VBA, сделал там кнопку, по нажатии которой появляется окно открытия...

Указать ячейку в макросе
Здравствуйте! Возможно не знаю как правильно спросить, потому ни где не могу найти ответ: По ходу выполнения макроса открываю другую...

9
15155 / 6428 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
25.03.2012, 23:29
Покажите обход с возвратом, который стартует с ячейки А(1,1) (кстати, что это за ячейка? ), а мы подскажем, как сделать обход с другой ячейки.
0
0 / 0 / 0
Регистрация: 26.02.2012
Сообщений: 7
26.03.2012, 00:13  [ТС]
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Public Function Kon(A)
    Dim B() As Integer
    Dim i As Integer, j As Integer, k As Integer, m As Integer, n As Integer, start As Integer, finish As Integer, l As Integer, c As Integer
    start = A(5, 7)
    finish = A(6, 2)
    n = A.Rows.Count
    m = A.Columns.Count
    ReDim B(1 To n, 1 To m)
    B(5, 7) = start
    B(6, 2) = finish
    For i = 1 To n
        For j = 1 To m
            If A(i, j) = 1 And B(i, j) = 0 Then
                    k = k + 1
                B = KonRekurs(A, B, n, m, i, j, k)
            End If
        Next j
    Next i
    Kon = k
End Function
 
Public Function KonRekurs(A, B, n, m, l, c, k)
    Dim dl(1 To 8) As Integer, dc(1 To 8) As Integer, i As Integer, nl As Integer, nc As Integer, finish As Integer
    dl(1) = -2: dl(2) = -2: dl(3) = -1: dl(4) = 1: dl(5) = 2: dl(6) = 2: dl(7) = 1: dl(8) = -1
    dc(1) = 1: dc(2) = -1: dc(3) = 1: dc(4) = 2: dc(5) = 1: dc(6) = -1: dc(7) = -2: dc(8) = -2
    B(l, c) = k
    For i = 1 To 8
        nl = l + dl(i)
        nc = c + dc(i)
        If (nl > 0) And (nl <= n) And (nc > 0) And (nc <= m) Then
            If (A(nl, nc) <> 5) And (B(nl, nc) = 0) And (B(nl, nc) <> 4) Then
            k = k + 1
            B = KonRekurs(A, B, n, m, nl, nc, k)
            End If
        End If
    Next i
    KonRekurs = B
End Function
обход начинается с ячейки A(1,1), а нужно с A(5,7) до встречи с А(6,2)
0
0 / 0 / 0
Регистрация: 26.02.2012
Сообщений: 7
26.03.2012, 00:41  [ТС]
Это вид исходной матрицы
Миниатюры
Обход с возвратом, указать стартовую ячейку  
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18031 / 7734 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
26.03.2012, 01:55
Я так понял A=Selection. Получил ответ 33 А что если не секрет эта функция подсчитывает?
Делал раньше что-то подобное без рекурсии.

И как тут вообще понять в какие переменные смотреть за фишкой, не зная условия задачи и смыслового значения меток.

Не по теме:

Сорри за повтор).
Делал раньше что-то подобное без рекурсии.
Перемещение фишки в поиске другой фишки

Вложения
Тип файла: xls Recurs.xls (28.5 Кб, 11 просмотров)
0
0 / 0 / 0
Регистрация: 26.02.2012
Сообщений: 7
26.03.2012, 02:24  [ТС]
Это задача про шахматного коня. Конь стоит на (5,7). Есть клетки, на которые он не может наступать (5) и те, на которые он может (1). Ему нужно дойти до короля (6,2) и вернуться назад.
Проблема в том, что не могу начать с клетки (5,7)
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18031 / 7734 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
26.03.2012, 10:55
Ясно. Это абсолютно аналогичная задача. Но уж больно большой результат количества ходов? выдает функция. Спасибо. Поизучаем.
А каким образом Вы отслеживаете откуда он начинает ходить?

Вероятно i,j в функции kon отвечают за это и достаточно убрать циклы и назначить им 5; 7 соответственно. Не проверял.
0
0 / 0 / 0
Регистрация: 26.02.2012
Сообщений: 7
26.03.2012, 10:59  [ТС]
Вот ещё как пробую:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
Option Explicit
 
Public Function Kon(A)
    Dim B() As Integer
    Dim i As Integer, j As Integer, k As Integer, m As Integer, n As Integer, start As Integer
    n = A.Rows.Count
    m = A.Columns.Count
    ReDim B(1 To n, 1 To m)
    B(6, 2) = A(6, 2)
    For i = 1 To n
        For j = 1 To m
            If A(i, j) = 1 And B(i, j) = 0 Then
                k = k + 1
                B = KonRekurs(A, B, n, m, i, j, k)
            End If
        Next j
    Next i
    Kon = k
End Function
 
Public Function KonRekurs(A, B, n, m, l, c, k)
    Dim dl(1 To 8) As Integer, dc(1 To 8) As Integer, i As Integer, nl As Integer, nc As Integer, j As Integer
    dl(1) = -2: dl(2) = 2: dl(3) = 1: dl(4) = -1: dl(5) = -2: dl(6) = -1: dl(7) = 1: dl(8) = 2
    dc(1) = -1: dc(2) = -1: dc(3) = -2: dc(4) = -2: dc(5) = 1: dc(6) = 2: dc(7) = 2: dc(8) = 1
    B(l, c) = k
    If B(l, c) = 4 Then
        l = 6
        c = 2
    End If
    If B(l, c) = 1 Then
        l = 5
        c = 7
    End If
    B(l, c) = k
    For i = 1 To 8
        nl = l + dl(i)
        nc = c + dc(i)
        If (nl > 0) And (nl <= n) And (nc > 0) And (nc <= m) Then
            If (A(nl, nc) <> 5) And (B(nl, nc) = 0) Then
            k = k + 1
            B = KonRekurs(A, B, n, m, nl, nc, k)
        End If
        End If
    Next i
    KonRekurs = B
End Function
Но проблема в том, что он обходит все возможные варианты, обходя короля
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18031 / 7734 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
27.03.2012, 02:32
Стартовая поисковая позиция задается в точности как я сказал выше.
(нужно закомментировать двойной цикл и IF, задав i, j).

Какой результат должен выдать этот код кроме движений? - поиск минимального числа ходов?
Я увидел, что все завершается, как только находит первый вариант!

Не по теме:

ИМХО, считаю свой алгоритм растущего дерева гораздо быстрее такой рекурсии.



Добавлено через 1 час 59 минут
Я так понял изначально алгоритм вообще не предназначался под эту задачу.

Так будет на много понятнее:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
Option Explicit
 
Sub Рекурсивный_конь()
Dim A As Range, s As Integer
Set A = [A1:H8]
s = Kon(A)
Stop
End Sub
 
Public Function Kon(A)
    Dim B() As Integer 'Virt.MASS
    Dim i As Integer 'Start.Seek.y.pos
    Dim j As Integer 'Start.Seek.x.pos
    Dim k As Integer 'steps.count
    Dim m As Integer 'x.max
    Dim n As Integer 'y.max
    Dim start As Integer 'start.number.descriptor
    Dim finish As Integer 'end.number.descriptor
    'Dim l As Integer ' - not used!
    'Dim c As Integer ' - not used!
    
    start = A(5, 7)
    finish = A(6, 2)
    n = A.Rows.Count 'размерность доски y
    m = A.Columns.Count 'размерность доски x
    ReDim B(1 To n, 1 To m)
    B(6, 2) = finish 'можно и без этого
    B(5, 7) = start 'аналогично
    i = 5
    j = 7
    
    'For i = 1 To n
    '    For j = 1 To m
            'If A(i, j) = 1 And B(i, j) = 0 Then
                    
                B = KonRekurs(A, B, n, m, i, j, k)
                'k = k + 1
            'End If
    '    Next j
    'Next i
    Kon = k
End Function
 
Public Function KonRekurs(A, B, n%, m%, l%, c%, k%)
'1-свободное поле
'2-стартовое поле
'4-финиш
'5-запрещенное поле
'l - Start.Seek.y.pos
'c - Start.Seek.x.pos
'k - steps.count
'A - Real.map
'B - Virtual map + tracking & steps.count
 
    Dim dl() As Integer
    Dim dc() As Integer
    ReDim dl(1 To n) As Integer 'заменил на букву
    ReDim dc(1 To m) As Integer 'заменил на букву
    Dim i As Integer 'индекс направления хода
    Dim nl As Integer 'поз. Y тестируемого хода
    Dim nc As Integer 'поз. Х тестируемого хода
    'Dim finish As Integer '-not used!
    
    dl(1) = -2: dc(1) = 1 'вверх2-направо
    dl(2) = -2: dc(2) = -1 'вверх2-налево
    dl(3) = -1: dc(3) = 2 'вверх-направо2 'была ошибка!
    dl(4) = 1: dc(4) = 2 'вниз-направо2
    dl(5) = 2: dc(5) = 1 'вниз2-направо
    dl(6) = 2: dc(6) = -1 'вниз2-налево
    dl(7) = 1: dc(7) = -2 'вниз-налево2
    dl(8) = -1: dc(8) = -2 'вверх-налево2
    
    B(l, c) = k 'оставляем метку в вирт. поле на месте, где находимся (в роле метки - кол-во пройденных шагов).
    Cells(10, 1).Resize(8, 8) = B
    MsgBox ""
    
    For i = 1 To 8 'directions (8 шт.)
        nl = l + dl(i) 'двигаем коня по-вертикали
        nc = c + dc(i) 'двигаем коня по-горизонтали
        If nl > 0 And nl <= n And nc > 0 And nc <= m Then 'если не сбежал с поля ->
          If A(nl, nc) = 4 Then 'если увидел финиш (проверяем на реальном поле А,
            k = k + 1: MsgBox "Доехали!!! Ходов - " & k: End 'ведь на виртуальном "4" - может означать число ходов!)
          Else 'если не попал на враж. територию или на свои следы, или на взлетную
            If A(nl, nc) <> 5 And B(nl, nc) = 0 And A(nl, nc) <> 2 Then
              'Stop
              k = k + 1
              B = KonRekurs(A, B, n, m, nl, nc, k)
              'Stop
            End If
          End If
        End If
    Next i
    'Stop
    If i = 9 Then k = k - 1 'если в текущей позиции нет ходов - шаг назад
    If k = -1 Then MsgBox "Ходов нет!": Exit Function
    KonRekurs = B
End Function
Вложения
Тип файла: xls Recurs.xls (36.0 Кб, 16 просмотров)
0
Эксперт WindowsАвтор FAQ
 Аватар для Dragokas
18031 / 7734 / 892
Регистрация: 25.12.2011
Сообщений: 11,502
Записей в блоге: 16
27.03.2012, 02:45
В строке 82 нормально выйти из рекурсии не смог. No Brain!

Не по теме:

Ваша прога такую комбинацию ходов нашла, что я б ни за что не додумался!


Цитата Сообщение от OlePole Посмотреть сообщение
обходя короля
потому что Вы убрали поле № 4 из проверки IF.

Теперь я так понимаю Вам требуется обратные ходы (я называю это "обратный трекинг").
Как это реализовать на рекурсии - я без понятия.
Могу рассказать как это делал я:
2 варианта:
1) ходим от конца к началу, и если номерок шага меньше, чем тот, на котором мы стоим - продвигаемся дальше по нему и т.д.
2) записываем в массив все направления успешных ходов (переменная "i"). А затем прокручиваем циклом в обратном порядке.

Да и еще, предусмотреть бы какую-нибуть пошаговую визуализацию этого процесса. Вот как у меня в примере выше.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
27.03.2012, 02:45
Помогаю со студенческими работами здесь

Указать последнюю не пустую ячейку в столбце
Пожалуйста помогите поправить строчку: ActiveChart.SetSourceData Source:=Sheets(&quot;Results&quot;).Range(&quot;M2:M10&quot;), PlotBy:=xlColumnsвместо...

Функция с возвратом указателя и возвратом ссылки
Найти максимальный и минимальный элемент в двумерном массиве и указать их номера. Указать номер первого отрицательного числа в массиве;...

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

Как в DataGrid можно указать colspan=2 на ячейку таблицы ?
Как в DataGrid (ASP.NET) можно указать colspan=2 на ячейку таблицы ?

Cells(a,b).FormulaR1C1='=????' Как мне вместо вопросов указать найденную ячейку ?
Я Find-ом нахожу ячейку на которую хочу сослатся Find('Чай Липтон').OffSet(-1,0); &lt;--- Это ссылка на ячейку с ценой далее я хочу...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru