Определить наибольшее количество шашек которое можно съесть за ход

@lengrab · Регистрация: 09.11.2013

Студворк — интернет-сервис помощи студентам

Добрый вечер, пожалуйста помогите написать программу ,что бы определить наибольшее количество шашек которое можно съесть за ход.
Конкретно дан входной файл в котором первая строка число N- далее как бы доска NXN
вот пример
7
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0
0 0 2 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0
0 0 0 0 0 0 0 0

2-наша шашка
1-чужие шашки
0-пустые клетки

Я начал ,но все мои идеи заходят в тупик

Visual Basic

Dim f(999, 999) As String
s = 1
Open "input.txt" For Input As #1
Line Input #1, p
For i = 1 To p
Line Input #1, x
s = 1
For n = 1 To p
If Mid(x, s, 1) = "1" Then raz = raz + 1
f(i, n) = Mid(x, s, 1)
If Mid(x, s, 1) = "2" Then vert = i: gor = n
s = s + 2
Next n
Next i
Close #1

до этого я считываю файл в двумерный массив далее надо определить куда ходить .
Пожалуйста помогите.

@Alex77755 · 09.11.2013, 21:49

В принципе интересная задачка!
Надо же учесть, что шашка может зайти в дамки и после этого у неё изменится алгоритм поиска возможных ходов!
А так, по большому счёту, просчитать все варианты и выбрать лучший.
И притом, думаю, с рекурсией будет красивее

@lengrab · 10.11.2013, 18:54 **[ТС]**

Сообщение от Alex77755

В принципе интересная задачка!
Надо же учесть, что шашка может зайти в дамки и после этого у неё изменится алгоритм поиска возможных ходов!
А так, по большому счёту, просчитать все варианты и выбрать лучший.
И притом, думаю, с рекурсией будет красивее

Я понимаю ,что нужна рекурсия ,но у меня не получаеться организовать сохранение предыдущих вариантов что из них вытекали последующие.

@~~JoraVoenyjHaker~~ · 10.11.2013, 19:31

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

Добавлено через 6 минут

Visual Basic

Sub myPrim(optional ChVz&)
 
 if ChVz<10 then myPrim ChVz+1
end sub

Добавлено через 7 минут
таким способом можно построить
многоуровневые многоходовые операции
там помоему допустимое значение для создание очередной копии около 6450
тоесть на столько ходов можно организовать работу

@The trick · 10.11.2013, 19:36

Сообщение от lengrab

Я понимаю ,что нужна рекурсия ,но у меня не получаеться организовать сохранение предыдущих вариантов что из них вытекали последующие.

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

@~~JoraVoenyjHaker~~ · 10.11.2013, 19:48

Сообщение от The trick

Создавай локальный массив

Да объяви массив данных на уровне модуля для хранения промежуточных данных
64*64(клетки)=4096 в принципе хватает для рекурсии...

Добавлено через 7 минут
The trick привет !!!

@The trick · 10.11.2013, 19:48

Сообщение от JoraVoenyjHaker

Да объяви массив данных на уровне модуля для хранения промежуточных данных
64*64(клетки)=4096 в принципе хватает для рекурсии...

Задача простая, сохранять предыдущее состояние и просчитывать в нем 4 хода, и т.д.

Добавлено через 27 секунд
JoraVoenyjHaker, Привет!

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:01

8*8 это 64 клетки
а количество вероятных состояний тоже 64
иначе любой школьник обыграет такой комп
у каторого только 4 хода в уме )))

Добавлено через 3 минуты
вернее для шашек надо 4*4
они же только по чёрным клеткам ходят )))

Добавлено через 2 минуты
последний раз я в шашки играл в пионер лагере с вожаткой
и то в чипая...

@lengrab · 10.11.2013, 20:06 **[ТС]**

Сообщение от The trick

Задача простая, сохранять предыдущее состояние и просчитывать в нем 4 хода, и т.д.

Это хорошо ,но можешь код набрасать?)
Просто я уже пробовал так сделать,но у меня не вышло.

@The trick · 10.11.2013, 20:06

Сообщение от JoraVoenyjHaker

иначе любой школьник обыграет такой комп
у каторого только 4 хода в уме )))

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

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:09

А если мухлевать )))

@The trick · 10.11.2013, 20:10

Сообщение от lengrab

Это хорошо ,но можешь код набрасать?)
Просто я уже пробовал так сделать,но у меня не вышло.

Если никто не поможет, позже набросаю, сейчас нет под рукой VB

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:16

массив Kletki( 1 to 32, 1 to 4 )

32 шашки
4 возможных состояния так ?

@The trick · 10.11.2013, 20:20

Т.к. за одину итерацию мы не можем уничтожить больше одной шашки, то можно и вовсе не хранить состояние всех клеток, а только измененной. Это будет намного быстрей работать.

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:26

Добавлено через 2 минуты

Сообщение от JoraVoenyjHaker

32

вернее не 32 а 24
не поленился посмотрел в википедии
12 черных
12 белых

Добавлено через 2 минуты
массив Kletki( 1 to 24, 1 to 2 )
2 состояния в массиве на уровне процедуры ?

@lengrab · 10.11.2013, 20:30 **[ТС]**

Забыл сказать что дамка учитывать не надо=)

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:31

вот именно что дамка резко увеличивает число состояний

@The trick · 10.11.2013, 20:35

Сообщение от JoraVoenyjHaker

вот именно что дамка резко увеличивает число состояний

Шашка по-прежнему может только в 4-х направлениях ходить, только на разные дистанции.

@~~JoraVoenyjHaker~~ · 10.11.2013, 20:55

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

Добавлено через 9 минут
Kletki( 1 to 24, 1 to 4 )
или Kletki( 23,3 )

Добавлено через 2 минуты
массив на уровне процедуры
+счетчик ходов если ему надо получить число

Добавлено через 6 минут
Всё медаль мне пора довать )))

@Alex77755 · 11.11.2013, 09:45

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

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 20:20	14
	Т.к. за одину итерацию мы не можем уничтожить больше одной шашки, то можно и вовсе не хранить состояние всех клеток, а только измененной. Это будет намного быстрей работать. 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:26	15
	Добавлено через 2 минуты Сообщение от JoraVoenyjHaker 32 вернее не 32 а 24 не поленился посмотрел в википедии 12 черных 12 белых Добавлено через 2 минуты массив Kletki( 1 to 24, 1 to 2 ) 2 состояния в массиве на уровне процедуры ? 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:31	17
	вот именно что дамка резко увеличивает число состояний 0

@Alex77755 11487 / 3774 / 678 Регистрация: 13.02.2009 Сообщений: 11,153
	09.11.2013, 21:49	2
	В принципе интересная задачка! Надо же учесть, что шашка может зайти в дамки и после этого у неё изменится алгоритм поиска возможных ходов! А так, по большому счёту, просчитать все варианты и выбрать лучший. И притом, думаю, с рекурсией будет красивее 0

@lengrab 2 / 2 / 2 Регистрация: 09.11.2013 Сообщений: 16
	10.11.2013, 18:54 [ТС]	3
	Сообщение от Alex77755 В принципе интересная задачка! Надо же учесть, что шашка может зайти в дамки и после этого у неё изменится алгоритм поиска возможных ходов! А так, по большому счёту, просчитать все варианты и выбрать лучший. И притом, думаю, с рекурсией будет красивее Я понимаю ,что нужна рекурсия ,но у меня не получаеться организовать сохранение предыдущих вариантов что из них вытекали последующие. 0

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 19:36	5
	Сообщение от lengrab Я понимаю ,что нужна рекурсия ,но у меня не получаеться организовать сохранение предыдущих вариантов что из них вытекали последующие. Создавай локальный массив, и в него копируй который передаешь в качестве параметра. 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 19:48	6
	Сообщение от The trick Создавай локальный массив Да объяви массив данных на уровне модуля для хранения промежуточных данных 6464(клетки)=4096 в принципе хватает для рекурсии... Добавлено через 7 минут* The trick привет !!! 0

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 19:48	7
	Сообщение от JoraVoenyjHaker Да объяви массив данных на уровне модуля для хранения промежуточных данных 6464(клетки)=4096 в принципе хватает для рекурсии... Задача простая, сохранять предыдущее состояние и просчитывать в нем 4 хода, и т.д. Добавлено через 27 секунд* JoraVoenyjHaker, Привет! 1

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:01	8
	88 это 64 клетки а количество вероятных состояний тоже 64 иначе любой школьник обыграет такой комп у каторого только 4 хода в уме ))) Добавлено через 3 минуты* вернее для шашек надо 44 они же только по чёрным клеткам ходят ))) Добавлено через 2 минуты* последний раз я в шашки играл в пионер лагере с вожаткой и то в чипая... 0

@lengrab 2 / 2 / 2 Регистрация: 09.11.2013 Сообщений: 16
	10.11.2013, 20:06 [ТС]	9
	Сообщение от The trick Задача простая, сохранять предыдущее состояние и просчитывать в нем 4 хода, и т.д. Это хорошо ,но можешь код набрасать?) Просто я уже пробовал так сделать,но у меня не вышло. 0

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 20:06	10
	Сообщение от JoraVoenyjHaker иначе любой школьник обыграет такой комп у каторого только 4 хода в уме ))) За один просчет - один ход, шашка может сделать 4 хода, 2 - вперед и если сзади нее враги и есть куда идти то еще + 2 (также нужно учитывать свободу на краях и если это дамка, то еще и шаги) - это уже отдельная ветвь и ее надо продумывать пока можно убить шашку. 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:09	11
	А если мухлевать ))) 0

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 20:10	12
	Сообщение от lengrab Это хорошо ,но можешь код набрасать?) Просто я уже пробовал так сделать,но у меня не вышло. Если никто не поможет, позже набросаю, сейчас нет под рукой VB 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:16	13
	массив Kletki( 1 to 32, 1 to 4 ) 32 шашки 4 возможных состояния так ? 0

@lengrab 2 / 2 / 2 Регистрация: 09.11.2013 Сообщений: 16
	10.11.2013, 20:30 [ТС]	16
	Забыл сказать что дамка учитывать не надо=) 0

@The trick Модератор 9235 / 3453 / 854 Регистрация: 22.02.2013 Сообщений: 5,229 Записей в блоге: 78
	10.11.2013, 20:35	18
	Сообщение от JoraVoenyjHaker вот именно что дамка резко увеличивает число состояний Шашка по-прежнему может только в 4-х направлениях ходить, только на разные дистанции. 0

@~~JoraVoenyjHaker~~ Заблокирован
	10.11.2013, 20:55	19
	У меня схема примерно нарисовалась, пришлось вспомнить правила игры там вообще небольшой код получится если правильно организовать рекурсию и массив Добавлено через 9 минут Kletki( 1 to 24, 1 to 4 ) или Kletki( 23,3 ) Добавлено через 2 минуты массив на уровне процедуры +счетчик ходов если ему надо получить число Добавлено через 6 минут Всё медаль мне пора довать ))) 0

@Alex77755 11487 / 3774 / 678 Регистрация: 13.02.2009 Сообщений: 11,153
	11.11.2013, 09:45	20
	В качестве параметра в процедуру, я думаю, можно передавать адрес поля, с которого необходимо начинать проверку, и агрумент пешка-дамка для изменения параметров проверки нахождения на линии боя шашек противника и пустых клеток за ними. 0