Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Даша Ермичева
2 / 2 / 0
Регистрация: 13.02.2019
Сообщений: 8
1

Робот перемещается из точки (0;0) в точку (х;у) за k шагов

13.02.2019, 22:25. Просмотров 856. Ответов 8

Добрый вечер. Помогите, пожалуйста, с программой на С++.

Ваня создал модель робота. Робот движется по алгоритму, которые содержит инструкции из набора:
  • 1 шаг на юг
  • 1 шаг на север
  • 1 шаг на запад
  • 1 шаг на восток
После завершения программы робот останавливается. Координатные оси параллельны географическим, единица измерения совпадает с шагом робота. Определите, сколько алгоритмов из точного количества k инструкций (0 ≤ k ≤ 16) перемещает робота из точки (0;0) в точку (х;у), где (|x|,|y| ≤ 16).

Буду очень благодарна!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2019, 22:25
Ответы с готовыми решениями:

Попасть из точки A в точку B за наименьшее количество шагов
Дано игровое поле (массив размерностью MxN). Каждая клетка игрового поля может быть либо...

Определить, сколько шагов Робот К-79 сделает прежде, чем впервые вернется место, где уже был
Петя написал программу движения робота К-79. Программа состоит из следующих команд: S — сделать...

Определить вероятность, что расстояние от точки, где окажется робот, до исходной точки окажется ровно 5
Дано множтво точек 8x8, которые имеют вид (рис. 1). Расстояние от одной точки до соседней по...

За сколько шагов объект достигнет точки с координатами (n, m)
Помогите пожалуйста с задачей, уже час кручусь вокруг неё, не могу сообразить как написать. Пишу...

Найти точку B, зная: необходимое расстояние для перемещения с точки A, направление и координаты точки A
Известно: Vector3 A = new Vector3(x,y,z); // С какой точки двигаться float b = distance; // На...

8
ReDoX
420 / 315 / 164
Регистрация: 01.07.2015
Сообщений: 1,113
13.02.2019, 23:03 2
Если время выполнения не критично, то можно просто перебрать рекурсивной функцией все возможные пути
0
Байт
Эксперт C
20450 / 12980 / 2728
Регистрация: 24.12.2010
Сообщений: 27,157
13.02.2019, 23:09 3
Имхо, эту задачу лучше опубликовать в этом разделе http://www.cyberforum.ru/combinatorics/
Там вам быстренько найдут точный ответ.
Наверное, следует использовать троичную сбалансированную систему счисления. А может быть и проще... Но ощущение такое, что программировать ничего не надо. Есть конечная формула. Навярняка.

Добавлено через 2 минуты
Цитата Сообщение от ReDoX Посмотреть сообщение
Можно просто перебрать рекурсивной функцией все возможные пути
Это самый простой, но и самый неэффективный брутфорс.
Меня просто удивляет. Почему с появлением ЭВМ люди стали себе отказывать в удовольствии подумать?
0
valen10
Параллельный Кот
1259 / 529 / 209
Регистрация: 25.03.2016
Сообщений: 1,186
Завершенные тесты: 1
14.02.2019, 01:18 4
Что-то очень знакомое, даже какие-то воспоминания зашевелились в дальних уголках моей памяти. Уже точно не помню, как называется такой способ решения, но попробую объяснить его.

Пусть рассматривается количество шагов k. Если k = 0, в какие клетки поля и сколькими способами можно попасть? Очевидно, только в (0,0) одним единственным способом. В остальные клетки попасть невозможно, т.е. 0 способов.
Робот перемещается из точки (0;0) в точку (х;у) за k шагов


Увеличим шаг до k = 1. В какие клетки теперь можно попасть? В соседние, количество способов - 1, т.к. есть только один возможный вариант. За один шаг попасть в начальную клетку невозможно, значит теперь там тоже 0 (не буду писать нули в таблице, чтобы не загромождать ее).
Робот перемещается из точки (0;0) в точку (х;у) за k шагов


Еще увеличим шаг, k = 2. Куда может пойти робот? Во, первых, обратно в (0,0) четырьмя возможными путями. Во-вторых, в клетки (1,1) (-1,-1) (-1,1) (1,-1) двумя возможными путями. И, наконец, дальше по полю, возможных способов - по одному.
Робот перемещается из точки (0;0) в точку (х;у) за k шагов


И так далее. Очевидно, что количество способов попасть в какую-либо клетку за k шагов равно сумме способов попасть в соседние от неё клетки за k-1 шагов. Таблица для k = 3, без комментариев.
Робот перемещается из точки (0;0) в точку (х;у) за k шагов


Код для ленивых

Размер поля выбран больше на 1 клетку в каждом направлении, чтобы вокруг была зона, куда робот не дойдет за указанные в условии максимум 16 шагов. Это чтобы не проверять координаты на выход за границы.
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
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
#include <iostream>
using namespace std;
 
const size_t n = 35;
const int offset = 17;
 
void clear_field(unsigned (&field)[n][n]) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            field[i][j] = 0;
        }
    }
}
 
void copy_field(unsigned (&dst)[n][n], unsigned (&src)[n][n]) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            dst[i][j] = src[i][j];
        }
    }
}
 
void next_step(unsigned (&field)[n][n]) {
    unsigned old_field[n][n];
 
    copy_field(old_field, field);
    clear_field(field);
 
    for (size_t i = 1; i < (n - 1); ++i) {
        for (size_t j = 1; j < (n - 1); ++j) {
            field[i][j] += old_field[i - 1][j];
            field[i][j] += old_field[i + 1][j];
            field[i][j] += old_field[i][j - 1];
            field[i][j] += old_field[i][j + 1];
        }
    }
}
 
int main() {
    unsigned field[n][n];
    clear_field(field);
    field[0 + offset][0 + offset] = 1;
 
    unsigned k;
    cout << "k = ";
    cin >> k;
 
    int x, y;
    cout << "x = ";
    cin >> x;
    cout << "y = ";
    cin >> y;
 
    for (unsigned i = 0; i < k; ++i) {
        next_step(field);
    }
 
    cout << "Result: " << field[x + offset][y + offset] << endl;
 
    return 0;
}
1
14.02.2019, 01:18
Байт
Эксперт C
20450 / 12980 / 2728
Регистрация: 24.12.2010
Сообщений: 27,157
14.02.2019, 11:46 5
Обозначим n - количество шагов на север, z - на юг, w - на запад, e - на восток
e - w = x
n - z = y
e + w + n + z = k
2w + 2z = k - x - y
Перебрать все решения (если они есть) - это весьма несложно. И только здесь нужен какой-то код с циклами. Далее - прямой счет. (Хотя для подсчета биномальных коэфициентов тоже понадобятся циклы)
Теперь начинаем считать способы
Выбрать те шаги (нумера ихние), которые ведут на юг можно http://www.cyberforum.ru/cgi-bin/latex.cgi?C_k^z способами.
Из оставшихся ведут на север http://www.cyberforum.ru/cgi-bin/latex.cgi?C_{k-z}^n
На запад http://www.cyberforum.ru/cgi-bin/latex.cgi?C_{k-z - n}^w
Остальные ведут на восток (1 способ)
Перемножаем.
Суммируем по всем решениям
1
XLAT
179 / 143 / 68
Регистрация: 23.09.2014
Сообщений: 556
Записей в блоге: 3
14.02.2019, 13:13 6
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
///----------------------------------------------------------------------------|
/// Движение без препятствий.
///----------------------------------------------------------------------------|
#include <iostream>
 
struct scoord
{   scoord(int _x, int _y) : x(_x), y(_y) {}
    int x, y;
}
P (10, -12), /// Точка назначения.
Ro(0 ,   0); /// Координаты робота.
 
int test(scoord s) /// Тест количества минимальных шагов до цели.
{   return abs(P.x - s.x) + abs(P.y - s.y);
}
 
bool foot()
{   std::cout << "\n=======================================\n";
 
    int t = test(Ro);
    std::cout << "Осталось сделать "<< t << " шагов..." <<"\n";
 
    if (t == 0) return false;
 
    Ro.x++;
    if (t > test(Ro))
    {   std::cout << "Шаг вправо\n";
        return true;
    }
 
    Ro.x--; Ro.x--;
    if (t > test(Ro))
    {   std::cout << "Шаг влево\n";
        return true;
    }
 
    Ro.x++; Ro.y++;
    if (t > test(Ro))
    {   std::cout << "Шаг вверх\n";
        return true;
    }
 
    Ro.y--; Ro.y--;
    std::cout << "Шаг вниз\n";
 
}
 
int main()
{
    setlocale(LC_CTYPE, ".1251");
 
    int i;
    for (i = 0; foot(); i++);
    std::cout << "Робот достиг цели за " << i << " шагов!\n";
 
    system("pause");
    return 0;
}
///----------------------------------------------------------------------------|
0
Байт
Эксперт C
20450 / 12980 / 2728
Регистрация: 24.12.2010
Сообщений: 27,157
14.02.2019, 13:18 7
XLAT,
Цитата Сообщение от Даша Ермичева Посмотреть сообщение
сколько алгоритмов
0
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
14.02.2019, 13:44 8
Очевидно что (0,5) робот пройдет за 5, . (2,0) робот пройдет за 2 шага, (2,7) робот пройдет за 9 шагов => нужно сложить координаты х и у и получите число шагов
0
ReDoX
420 / 315 / 164
Регистрация: 01.07.2015
Сообщений: 1,113
14.02.2019, 16:29 9
Михаиллллллл,
Цитата Сообщение от Даша Ермичева Посмотреть сообщение
сколько алгоритмов из точного количества k инструкций
0
14.02.2019, 16:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.02.2019, 16:29

Найти точку из базы с наименьшим расстоянием от заданной точки до точки из базы и вывести эти координаты на экран
Здравствуйте. Помогите пожалуйста, надо сделать задание для небольшого проекта в рамках курсовой...

Из точки А в точку В
Добрый день. Взялся за .. как мне показалось вначале .. легкую задачу и что-то засел над ней второй...

Движение из точки А в точку Б
Здравствуйте. Есть 2 ключевых кадра, 1ый и последний. У 1-го кадра координаты 0, у последнего 100....


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru