задачи на динамику

@tennisru · Регистрация: 10.09.2011

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

Представьте себе пчелиные соты – поле из шестиугольных клеток со стороной N. В верхней левой клетке A находится пчелка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчелка не ползает).

Требуется написать программу, которая найдет количество способов, которыми пчелка может доползти из клетки A в противоположную клетку B
Входные данные

Входной файл INPUT.TXT содержит единственное число N – размеры шестиугольного поля (2 <= N <= 12).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать единственное целое число – количество способов.
http://acmp.ru/index.asp?main=task&id_task=187
подскажите как решить

@Igor3D · 01.03.2013, 13:24

Обычный алгоритм с возвратом. Ход - выбираете клетку и маркируете ее как занятую. Откат - убираете флаг "занято". Ну и крутите цикл for

@tennisru · 01.03.2013, 14:02 **[ТС]**

мне непонятно, можете поподробней

@Igor3D · 01.03.2013, 14:22

C++
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
#include <stdio.h>
 
const int N = 10;
const int srcX = 0, srcY = 0;
const int dstX = 5, dstY = 5;
int numPath = 0;
 
void Move( int x, int y )
{
 if (x < 0 || x >= N) return;
 if (y < 0 || y >= N) return;
 if (x == dstX && y == dstY) {
  ++numPath;
  return;
 }
 if (x >= dstX || y >= dstY) return;
 Move(x, y + 2);
 Move(x + 1, y + 1);
 Move(x + 1, y - 1);
}
 
void main( void )
{
 Move(srcX, srcY);
 printf("numPath = %d\n", numPath);
}

Тут еще проще - маркировать ничего не надо т.к. пчелка и сама не может второй раз попасть на то же поле

@tennisru · 02.03.2013, 20:59 **[ТС]**

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

@Izual · 02.03.2013, 22:15

из клетки A в противоположную клетку B

Если в противоположную, значит все N (от 2 до 12) расположены в 1 ряду? - тогда 1 способ.

Входной файл INPUT.TXT содержит единственное число N

Если бы чисел было 2, то можно было бы чтоб поле имело много рядов, тогда способов было бы больше 1.
Можно конешно - имея число, построить смежныеячейки, но не ясно в какое направление пойдёт следующяя ячейка, а если правильно, то кол-во ячеек должно быть: 1 - 6(в середине 1 и вокруг 5) - 18(1\5\12) и далее, а если ещё правильнее то, 1 - 6(1\5) - 24 (1\5\18)... - начертите на листочке =)

размеры шестиугольного поля

- невозможно! Если сотка одна - то да, но 2 сотки - 10 углов, и т.д.

Опишите задачу точнее, тогда можно будет и по колдовать.

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

6(в середине 1 и вокруг 5)

Не так =) В середине 1 и вокруг 6... Посчитал не верно. Ну суть осталась не изменной.

Если тупо добавлять от 2 и далее сотки, то каждая последующяя должна быть либо смежна с 2 или более прежними, а это значит что уже при N от 4 можно разные карты составлять, т.к. вариантов расположений будет масса... А "противоположные" два элемента между которыми искать - число будет N-1.
Пример:
2 сотки (по 1 ряду) - 1.
3 сотки (2по 1 и 1 вверху или в низу) - 2; если все 3 по 1 ряду - 1.
4 сотки (2по 1 и 1вверху и 1 внизу) - 3(т.к. ряд > 1 только один); если 2 по 1 и 2 по 1(2 ряда), то результат 2, т.к. противоположные элементы в одном ряду смежны только с 1 элементом.
Кстати в последнем предложении ответ на решение твоего алгоритма, если ты его правильно сформулируеш =)

@tennisru · 02.03.2013, 22:20 **[ТС]**

прилагаеться ссылка, она оказалась не рабочей
http://acmp.ru/index.asp?main=task&id_task=187
просто кликайнье не приводит к результату , нужно скопировать и вставить в браузер, задача решена

@Igor3D · 03.03.2013, 09:16

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

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

Не "просто". На каждом шаге путь разветвляется на 3 возможных, в результате все пути будут проверены.
А вот здесь помарка

C++
1
2
3
4
5
6
// неверно т.к. может ползти по диагонали вверх
//  if (x >= dstX || y >= dstY) return;
 
// правильно так 
if (x > dstX) return;   // уже справа от целевой
if (y - dstY > dstX - x) return;  // внизу и не хватает диагонали вверх

@tennisru · 03.03.2013, 16:09 **[ТС]**

Igor3D, попробуйте проверить на тестах

@Igor3D · 03.03.2013, 16:47

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

Igor3D, попробуйте проверить на тестах

Наблюдаю во всяком случае разумные результаты

(src)(dst)= numPath
(0, 0)(5, 5) = 909
(0, 0)(6, 6) = 4704
(1, 1)(6, 6) = 1405

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера 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. Пошагово создадим проект для загрузки изображения. . .

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179

	задачи на динамику 01.03.2013, 01:59. Показов 8170. Ответов 9 Метки нет (Все метки) Представьте себе пчелиные соты – поле из шестиугольных клеток со стороной N. В верхней левой клетке A находится пчелка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчелка не ползает). Требуется написать программу, которая найдет количество способов, которыми пчелка может доползти из клетки A в противоположную клетку B Входные данные Входной файл INPUT.TXT содержит единственное число N – размеры шестиугольного поля (2 <= N <= 12). Выходные данные Выходной файл OUTPUT.TXT должен содержать единственное целое число – количество способов. http://acmp.ru/index.asp?main=task&id_task=187 подскажите как решить 0

@Igor3D 1969 / 825 / 115 Регистрация: 01.10.2012 Сообщений: 4,893 Записей в блоге: 2
	01.03.2013, 13:24
	Обычный алгоритм с возвратом. Ход - выбираете клетку и маркируете ее как занятую. Откат - убираете флаг "занято". Ну и крутите цикл for 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	01.03.2013, 14:02 [ТС]
	мне непонятно, можете поподробней 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	02.03.2013, 20:59 [ТС]
	по-моему ваш алгоритм не решает данную задачу, вы просто идете из левой верзнего угла в правый нижний, неправильно. Попробуйте подставить исходное значение 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	02.03.2013, 22:20 [ТС]
	прилагаеться ссылка, она оказалась не рабочей http://acmp.ru/index.asp?main=task&id_task=187 просто кликайнье не приводит к результату , нужно скопировать и вставить в браузер, задача решена 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	03.03.2013, 16:09 [ТС]
	Igor3D, попробуйте проверить на тестах 0