Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110

Написать Input и Output для алгоритма

05.01.2020, 13:18. Показов 2634. Ответов 18
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вот Алгоритм:
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
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
98
99
100
101
102
103
104
105
106
#include "pch.h"
#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;
 
static const int N = INT_MAX / 2;
 
// все 8 возможных движений
// для шахматного коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;
 
    return true;
}
 
// алгоритм BFS
struct Node
{
    // (x, y) координаты шахматной доски
    // dist - минимальное расстояние из предварительной точки к финальной
    int x, y, dist;
 
    // Node конструктор
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
 
     
    // оператор перегрузки < operator
    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};
 
// Находим минимальное количество шагов, предпринятых конем
// из предварительной точки к финальной, используем BFS
int BFS(Node src, Node dest)
{
    // проверяем была ли посещена ячейка матрицы или нет
    set<Node> visited;
 
    // создаем очередь и ставим в очередь первый узел
    queue<Node> q;
    q.push(src);
 
    // запустить до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть dist
        if (x == dest.x && y == dest.y)
            return dist;
 
        // пропускаем, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометим текущий узел как посещенный
            visited.insert(node);
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию коня из текущей
                // позиция на шахматной доске и поставить ее в очередь,
                // очередь с расстоянием +1
                int x1 = x + row[i];
                int y1 = y + col[i];
 
                if (valid(x1, y1))
                    q.push({ x1, y1, dist + 1 });
            }
        }
    }
 
    // вернуть бесконечность, если путь не возможен
    return INT_MAX;
}
 
 
int main()
{
    // исходные координаты
    Node src = { 0, 1 };
 
    // координаты пункта назначения
    Node dest = { 1, 1 };
 
    cout << "Минимальное количество шагов :" << BFS(src, dest);
 
    return 0;
}
Вот что должно быть в Input и Output

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

Вот как должно выглядеть:
2 - количество примеров
1 - количество шахматных коней
5 5 - начальная точка
5 6 - финальная точка
2 - количество шахматных коней
0 0 - начальная точка первого коня
1 0 - начальная точка второго коня
0 1 - финальная точка первого коня
1 1 - финальная точка второго коня

Ответ:
3 - ответ для первого коня
4 - ответ для второго коня


ПОМОГИТЕ ПОЖАЛУЙСТА СДЕЛАТЬ, БУДУ ОЧЕЕНЬ БЛАГОДАРЕН!!!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
05.01.2020, 13:18
Ответы с готовыми решениями:

Output/Input в консоль без C Run-Time (CRT)
Добрый день! Пишу небольшой загрузчик без CRT с использованием некоторых Nt-функций. Как таковой вывод информации на обозрение не так...

Пустые INPUT и OUTPUT
Задача: Напечатать текст из файла, подчёркивая (ставя минусы в соответствующих позициях следующей строки) все входящие в него заглавные...

Input < jpg | output > code
Недавно начал изучать программирование, но никогда не выходил за просторы консоли, однако сейчас нужно написать программу, которая получает...

18
913 / 339 / 135
Регистрация: 18.07.2017
Сообщений: 1,485
05.01.2020, 17:13
C++
1
2
3
4
5
6
7
8
int hourses;
int ansver;
cout << "input count hourses: ";
cin >> hourses;
...
// подобным образом вводишь все остальные значения
// вычисляешь свои вычисления
cout << "answer for 1 hourse: " << ansver; // вывод значений
Если этого мало, можешь заюзать библиотеку ncurses.
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
09.01.2020, 11:42  [ТС]
assemberist, я знаю как писать cout, cin.
я не знаю как правильно прописать их(через какой то может List?)
потому что если я просто пропишу, как вы написали сверху, то оно не сработает
0
913 / 339 / 135
Регистрация: 18.07.2017
Сообщений: 1,485
09.01.2020, 18:47
Цитата Сообщение от Programist_r Посмотреть сообщение
я не знаю как правильно прописать их(через какой то может List?)
С чем удобнее, с тем и работай: vector, list, stack.
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
09.01.2020, 19:50  [ТС]
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
int main()
{
 
 
    int number_of_examples;
    int number_of_horse;
    int x, y;
    int a, b;
 
    Node src = { x,y };
    Node dest = { a,b };
    
 
    cin >> number_of_examples;                             //Число примеров
 
    for (int i = 1; i <= number_of_examples; i++)
    {
        cin >> number_of_horse;                         //Число коней
 
        for (int i = 1; i <= number_of_horse; i++)
        {
            cin >> x >> y;                            //Вписываем исходные координаты
            
        }
 
        for (int i = 1; i <= number_of_horse; i++)
        {
            cin >> a >> b;                            //Вписываем координаты пункта назначения
            
        }
 
        cout << "Минимальное количество шагов :" << BFS(src, dest);
 
    }
 
 
 
 
 
 
 
    //// исходные координаты
    //Node src = { 0, 1 };
 
    //// координаты пункта назначения
    //Node dest = { 1, 1 };
 
    //cout << "Минимальное количество шагов :" << BFS(src, dest);
 
    return 0;
}
должно получиться примерно такое, но у меня оно не правильно работает
Можете помочь с Node, что бы оно правильно записывалось
0
913 / 339 / 135
Регистрация: 18.07.2017
Сообщений: 1,485
09.01.2020, 21:26
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
#include <iostream>
#include <vector>
 
using namespace std;
 
struct Node
{
    int x, y, dist;
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
};
 
int main()
{
    int number_of_examples;
    cin >> number_of_examples;                             //Число примеров
 
    for (int i = 1; i <= number_of_examples; i++){
        int number_of_horse;
        cin >> number_of_horse;                         //Число коней
        vector<Node> src(number_of_horse);
        vector<Node> dest(number_of_horse);
 
        int x, y;
        for (int i = 1; i <= number_of_horse; i++)
            cin >> x >> y;
        src.push_back(Node(x,y));
 
        for (int i = 1; i <= number_of_horse; i++) 
            cin >> x >> y;
        dest.push_back(Node(x,y));
    }
    return 0;
}
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
09.01.2020, 23:35  [ТС]
assemberist,
выдает ошибку
Миниатюры
Написать Input и Output для алгоритма  
0
913 / 339 / 135
Регистрация: 18.07.2017
Сообщений: 1,485
10.01.2020, 09:09
Значит ты где-то пытаешься использовать конструктор, который не определен для Node. Скорее всего конструктор по умолчанию.
Programist_r, ты про конструкторы читал хоть раз?
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
10.01.2020, 09:16
Цитата Сообщение от assemberist Посмотреть сообщение
Значит ты где-то пытаешься использовать конструктор, который не определен для Node.
вот тут
Цитата Сообщение от assemberist Посмотреть сообщение
C++
1
2
vector<Node> src(number_of_horse);
vector<Node> dest(number_of_horse);
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
10.01.2020, 14:11  [ТС]
zayats80888,
вот у меня есть такой конструктор

C++
1
2
3
4
5
6
 // (x, y) координаты шахматной доски
    // dist - минимальное расстояние из предварительной точки к финальной
    int x, y, dist;
 
    // Node конструктор
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
теперь нужно прописать конструктор, в котором от количество коней зависит число src и dest?
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
10.01.2020, 14:30
Цитата Сообщение от Programist_r Посмотреть сообщение
теперь нужно прописать конструктор, в котором от количество коней зависит число src и dest?
Нужно написать конструктор по умолчанию, или подправить существующий
C++
1
Node(int x = 0, int y = 0, int dist = 0) : x(x), y(y), dist(dist) {}
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
10.01.2020, 14:39  [ТС]
zayats80888,
а чтобы подставить значения src и dest в сам алгоритм BFS, нужно ли их как то конвертировать?

C++
1
cout << "Минимальное количество шагов :" << BFS(src, dest);
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
10.01.2020, 14:51
Programist_r, если ты про вектора, то в каком нибудь цикле перебирать BFS(src[i], dest[j])
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
10.01.2020, 15:03  [ТС]
zayats80888, про вектор

Добавлено через 11 минут
zayats80888,
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
int main()
{
    int number_of_examples;
    cin >> number_of_examples;                             //Число примеров
 
    for (int i = 1; i <= number_of_examples; i++) {
        int number_of_horse;
        cin >> number_of_horse;                         //Число коней
        vector<Node> src(number_of_horse);
        vector<Node> dest(number_of_horse);
        
 
        int x, y;
        for (int i = 1; i <= number_of_horse; i++)
            cin >> x >> y;
        src.push_back(Node(x, y));
 
        for (int i = 1; i <= number_of_horse; i++)
            cin >> x >> y;
        dest.push_back(Node(x, y));
 
        for (int i = 0; i < src.size(); i++)
        {
            for (int j = 0; j < dest.size(); j++)
            {
                cout << BFS(src[i], dest[j]);
            }
        }
        
    }
    
    
    return 0;
}
получилось так, но ответ какой то странный
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
10.01.2020, 15:33
Цитата Сообщение от Programist_r Посмотреть сообщение
получилось так, но ответ какой то странный
мне вникать в задачу лень, единственное что скажу, исправь строки 9 и 10 на
C++
1
2
        vector<Node> src;
        vector<Node> dest;
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
10.01.2020, 16:00  [ТС]
zayats80888,
а как сделать чтобы ответ BFS для каждого коня был отделен и в конце ответ BFS всех коней данного числа примеров суммировался

2 - количество примеров
1 - количество шахматных коней
5 5 - начальная точка
5 6 - финальная точка (сумма = 3)
2 - количество шахматных коней
0 0 - начальная точка первого коня
1 0 - начальная точка второго коня (первый ответ коня) 2
0 1 - финальная точка первого коня +
1 1 - финальная точка второго коня (ответ второго коня) 2 = их сумма 4

Ответ:
3 - ответ для первого примера
4 - ответ для второго примера
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
10.01.2020, 16:08
Цитата Сообщение от Programist_r Посмотреть сообщение
а как сделать
...
Цитата Сообщение от zayats80888 Посмотреть сообщение
мне вникать в задачу лень
0
1 / 1 / 0
Регистрация: 05.04.2019
Сообщений: 110
10.01.2020, 17:47  [ТС]
Кто нибудь помогите доделать, сижу над этой проблемой уже фиг знает сколько, мне уже эти кони сняться по ночам!!!
0
913 / 339 / 135
Регистрация: 18.07.2017
Сообщений: 1,485
10.01.2020, 19:14

Не по теме:

Цитата Сообщение от Programist_r Посмотреть сообщение
сижу над этой проблемой уже фиг знает сколько, мне уже эти кони сняться по ночам!!!
Может потому, что язык надо учить, вместо того, чтобы ждать пока за тебя код напишут?



И там не одно видео, а целый курс. Смотри и вникай, пока на начнешь понимать, что сам пишешь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
10.01.2020, 19:14
Помогаю со студенческими работами здесь

Отсортировать элементы файла input и вывести их в файл output
Здравствуйте. Помогите решить. Есть файл input, в котором элементы располагаются столбцом. Нужно отсортировать элементы файла input и...

Переписать данные файла input.txt в файл output, отсортировав их по возрастанию средней оценки методом выбора
В файле input.txt содержатся сведения о группе студентов в формате: номер группы; запись о каждом студенте группы содержит следующие...

Драйвет Input-Output для USB
Подскажите, пожалуйста, есть ли универсальный драйвер для простого доступа к регистру USB порта. Если нет, расскажите то с чего начать,...

написать программу, которая берёт данные из input.txt решает их по формуле и ответ заносит в output.txt
Помогите пожалуйста разобраться с input.txt и output.txt Допустим, надо написать программу, которая берёт данные из input.txt решает их...

Написать программу, которая создает текстовый файл Output.txt, содержащий все числа файла Input.txt, кратные 5
уважаемые программисты помогите пожалуйста сделать задание из контрольной работы. Текстовый файл Input.txt содержит целые числа....


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

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru