Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
 Аватар для sashqqqa
2 / 1 / 1
Регистрация: 22.03.2021
Сообщений: 9

Найти количество способов которыми пчёлка может переместиться из клетки A в клетку B по указанным правилам

19.06.2022, 19:37. Показов 5252. Ответов 24
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Приветствую Вас, уважаемые форумчане! Помогите пожалуйста решить данную задачу.
Мучаюсь над ней уже несколько дней

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

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

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

Единственная строка содержит единственное число N
— размеры шестиугольного поля (2 ≤ N ≤ 12).

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

Выведите единственное целое число — количество способов.

Пример ввода/вывода:
Ввод: 2    Вывод: 11
Ввод: 3  ᅠ  Вывод: 291

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

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
27
#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) return;
 if (y - dstY > dstX - x) 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);
}
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.06.2022, 19:37
Ответы с готовыми решениями:

Найти количество способов, которыми фишка может дойти до последней клетки
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти количество способов, которыми фишка может дойти до...

Посчитать количество способов, которыми конь может попасть в правую нижнюю клетку
В левом верхнем углу прямоугольной доски NxM находится шахматный конь. Перемещаться по доске он может только двумя способами: на две клетки...

Кузнечик прыгает из клетки 1 в клетку n , длина прыжка может быть от 1 до 3. У каждой клетки есть стоимость. Найти путь
Кузнечик прыгает из клетки 1 в клетку n , длина прыжка может быть от 1 до 3. У каждой клетки есть стоимость. Найти путь с максимальной...

24
 Аватар для PencilTorch
90 / 60 / 32
Регистрация: 06.08.2020
Сообщений: 220
20.06.2022, 12:25
Не удивительно. Я вот не могу представить шестиугольное поле размером 2 из шестиугольных клеток.
0
Заблокирован
20.06.2022, 13:10
Цитата Сообщение от PencilTorch Посмотреть сообщение
Не удивительно. Я вот не могу представить шестиугольное поле размером 2 из шестиугольных клеток.
Написано же, сторона поля равна N, поле будет NxN.
Хоть и косо-криво написано )

sashqqqa,
Тут бы картинку, расположения сот на поле. Их же можно вертеть как хочешь.
Можете посмотреть тему по поиску пути
Игра - 4 «Кота в угол»

Хотя ваша задачу узкоспециализированная, и не требует общих алгоритмов.
А писать однодневный код, который мне не принесет ни опыта ни удовольствия, нет никакого желания.
0
518 / 410 / 188
Регистрация: 08.04.2013
Сообщений: 1,749
20.06.2022, 13:42
PencilTorch, Я тоже не представляю такое поле
0
Заблокирован
20.06.2022, 13:51
marat_miaki, оно не шестиугольное, это выдумка PencilTorch.
Пройдите по ссылке выше, посмотрите представление поля там.
Вот для этого и нужно либо более точное описание, либо графическое представление поля, что бы было понятно и однозначно.
0
 Аватар для PencilTorch
90 / 60 / 32
Регистрация: 06.08.2020
Сообщений: 220
20.06.2022, 13:59
Цитата Сообщение от SmallEvil Посмотреть сообщение
это выдумка PencilTorch.
Чёйта?
Цитата Сообщение от sashqqqa Посмотреть сообщение
— размеры шестиугольного поля (2 ≤ N ≤ 12).
0
Заблокирован
20.06.2022, 14:10
Цитата Сообщение от sashqqqa Посмотреть сообщение
поле из шестиугольных клеток со стороной
А тут ничего нет про шестиугольность поля.
Но и шестиугольное поле, тоже даже очень легко представляется.
Изображения
 
0
518 / 410 / 188
Регистрация: 08.04.2013
Сообщений: 1,749
20.06.2022, 14:22
SmallEvil, Да я каждый день с этими шестиугольниками встречаюсь. ( вполне представляю при N = 2 (центральная вокруг по кругу еще ряд) Вернее всего здесь не надо алгоритмы придумывать, должна быть мат. формула

Добавлено через 10 минут
только не прокатывает ответ при 2 - 11?
0
Заблокирован
20.06.2022, 14:24
Цитата Сообщение от marat_miaki Посмотреть сообщение
Вернее всего здесь не надо алгоритмы придумывать, должна быть мат. формула
Формулу вы будете месяц высчитывать. Подгонять под правила движения.
Алгоритмом куда проще.

Автор в правильную сторону смотрит, рекурсией проще всего.

Добавлено через 2 минуты
Цитата Сообщение от marat_miaki Посмотреть сообщение
Да я каждый день с этими шестиугольниками встречаюсь.
Где, если не секрет ?
0
518 / 410 / 188
Регистрация: 08.04.2013
Сообщений: 1,749
20.06.2022, 14:44
в естественной среде - на пасеке

Добавлено через 3 минуты
закономерность прогрессии. 1, 7, 19, 37, 61.
1 + 6 = 7 + 12 = 19 + 18 = 37 + 24 = 61.
К каждому последующему числу прибавляется на 6 больше, чем к предыдущему.
количество точек для следующего N
0
 Аватар для sashqqqa
2 / 1 / 1
Регистрация: 22.03.2021
Сообщений: 9
20.06.2022, 17:15  [ТС]
Такая схема
Миниатюры
Найти количество способов которыми пчёлка может переместиться из клетки A в клетку B по указанным правилам  
0
 Аватар для sashqqqa
2 / 1 / 1
Регистрация: 22.03.2021
Сообщений: 9
20.06.2022, 17:17  [ТС]
Цитата Сообщение от SmallEvil Посмотреть сообщение
Тут бы картинку, расположения сот на поле
SmallEvil, получается так вот
0
Заблокирован
20.06.2022, 19:16
Цитата Сообщение от sashqqqa Посмотреть сообщение
SmallEvil, получается так вот
Ну вот. И рисунок есть.

Вообщем при росте N количество путей растет экспоненциально.
Уже для 6 количество путей будет 7997355.

Перебором тут не обойтись.

Добавлено через 21 минуту
Либо разрабатывать формулу.
Либо как то сохранять, частичный, уже сделанный результат.
0
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,720
Записей в блоге: 15
21.06.2022, 05:03
здесь есть динамика. В ячейку А ставим число 1. Тогда значение в любой ячейке равно сумме чисел трёх ячеек: верхней и двух левых
Изображения
 
1
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,720
Записей в блоге: 15
21.06.2022, 06:04
Лучший ответ Сообщение было отмечено SmallEvil как решение

Решение

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
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
 
using ull = unsigned long long;
 
int main()
{
    ull n = 3, m = 2 * n - 1;
    std::vector<std::vector<ull>> mtx{ (unsigned)m, std::vector<ull>(m) };
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            ull a = i > 0 ? mtx[i - 1][j] : 0;
            ull b = j > 0 ? mtx[i][j - 1] : 0;
            ull c = i > 0 && j > 0 ? mtx[i - 1][j - 1] : 0;
            mtx[i][j] = a + b + c;
            if (i == 0 && j == 0)
                mtx[i][j] = 1;
            int ind = m - (m / 2 - j);
            if (ind > m)
                ind -= m;
            if ((j < m / 2 && i >= ind) || (j > m / 2 && i < ind))
                mtx[i][j] = 0;
            //std::cout << std::setw(5) << std::left << mtx[i][j];
        }
        //std::cout << "\n";
    }
 
    std::cout << mtx.back().back() << "\n";
 
}
3
0 / 0 / 0
Регистрация: 08.04.2023
Сообщений: 6
16.07.2023, 19:20
Программа выдаёт неверный ответ
Миниатюры
Найти количество способов которыми пчёлка может переместиться из клетки A в клетку B по указанным правилам  
0
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,720
Записей в блоге: 15
16.07.2023, 19:39
пробуйте питоновский код
Пчелка
У меня с ними выдаёт одинаковый результат для 2<= n <= 12

Добавлено через 11 минут
там надо ввод n сделать
0
0 / 0 / 0
Регистрация: 08.04.2023
Сообщений: 6
16.07.2023, 20:34
Я конечно дико извиняюсь, но я не знаю с++.
0
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,720
Записей в блоге: 15
16.07.2023, 21:49
C++
1
2
3
4
    ull n;
    std::cin >> n;
    ull m = 2 * n - 1; 
    ...
0
0 / 0 / 0
Регистрация: 08.04.2023
Сообщений: 6
16.07.2023, 22:02
Можно весь код?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
16.07.2023, 22:02
Помогаю со студенческими работами здесь

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
кому не трудно помогите сделать. если не трудно вам написать код. Дана прямоугольная таблица nxn клеток. В каждой клетке содержится...

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

В таблице клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки A(1,1) в клетку A(N,N)
В таблице NхN, клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки A(1,1) в клетку A(N,N) такой, что: 1) он...

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы...

Определить количество способов, которыми Коля может уменьшить описанное выше число пар индексов.
Вот кто придумал дарить детям неотсортированные массивы? Мы не знаем, но Коля сегодня получил именно такой подарок. Он даже решил посчитать...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru