Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.05.2019, 23:12   #1
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию Соответствие Входа и Примера

Здравствуйте
Сам алгоритм я понимаю как написать.
Я не понимаю соответствие Входа и Примера. Что за что отвечает. Подскажите пожалуйста.

Задания:
Одно движение шахматного прыгуна (лошади) - это прыжок на два поля вертикально или горизонтально, а затем на один квадрат под прямым углом. Такое движение создает букву «Л». Все поля, доступные одним движением перемычки, отмечены крестиком на диаграмме ниже.
Рассмотрим неограниченную шахматную доску, на которой стоит несколько перемычек и на которой выделено одинаковое количество целевых полей. После выполнения определенного количества ходов (описанных выше) перемычки должны находиться на целевых полях. Как это сделать, выполнив минимальное количество ходов? Задача Напишите программу, которая для заданного распределения выходных N перемычек и N целевых полей найдет минимальное количество ходов, после которого перемычки окажутся на целевых полях.
Входные данные В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных, размещенных в следующих строках. Каждый набор состоит из строки, содержащей количество N перемычек (1≤N≤ 1000), и из следующих 2N строк, содержащих координаты выходных полей перемычек (N строк), а затем расположение целевых полей (следующие N строк). Каждая из 2N строк, содержащих координаты поля (выходной или целевой), содержит две, разделенные одним пробелом целые числа x, y (-2000000000≤x, y ≤ 2 000 000 000), обозначающие номера столбца и строки, соответственно, на пересечении какого поля. Выходные данные Стандартный выходной файл должен содержать D задач для последующих наборов данных. Каждое решение должно быть записано в одну строку, в которой должно быть одно положительное целое число K - обозначающее минимальное количество движений, необходимое для перемещения всех перемычек из начальной позиции в целевую позицию.


//4
//1
//5 5
//5 6
//2
//0 0
//1 0
//0 1
//1 1
//13
//4 1
//4 2
//3 3
//0 7
//4 3
//6 1
//3 5
//6 3
//5 4
//2 7
//3 7
//5 6
//7 5
//1 1
//3 0
//4 0
//1 4
//3 2
//0 7
//3 5
//7 3
//6 6
//7 5
//5 7
//7 6
//6 7
//15
//0 0
//0 1
//1 1
//2 0
//0 3
//3 3
//5 2
//7 0
//1 7
//3 6
//6 4
//7 4
//7 5
//6 7
//7 7
//1 1
//0 3
//4 0
//3 2
//2 3
//6 1
//0 7
//1 6
//3 5
//5 3
//4 4
//7 3
//4 7
//5 7
//7 7
правильный ответ:
//3
//4
//18
//24
Programist_r вне форума Ответить с цитированием
Старый 21.05.2019, 09:25   #2
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

Цитата:
Я не понимаю соответствие Входа и Примера. Что за что отвечает. Подскажите пожалуйста.
Входные данные
В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных
D=//4
Каждый набор состоит из ...
строки, содержащей количество N перемычек (1≤N≤ 1000)
N[1]=//1
из следующих 2N строк 2*N[1]=2*1 =2
содержащих координаты выходных полей перемычек (N строк) N[1]=1
//5 5
а затем расположение целевых полей (следующие N строк) N[1]=1
//5 6
---конец набора N[1]
N[2]=//2
...
N[3]=...
....
N[4{=D}]=...
...
--конец данных

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

Цитата:
выходной файл должен содержать...
D задач для последующих(?) наборов данных.
D=//3 ??? видимо один из наборов НЕ ИМЕЕТ решения. (а какой?.. X) и о таком поведении вывода правильно предупреждать в описании(постановке задачи).
N[1?] =//4 хода
N[2?] =//18
N[3?] =//24
N[4?X] --------
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 21.05.2019 в 09:36.
evg_m на форуме Ответить с цитированием
Старый 21.05.2019, 09:37   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от evg_m Посмотреть сообщение
перемычки выше речь шла о коне.
похоже на автоматизированный перевод.
один из вариантов перевода "перемычка" на английский - "Jumper" - это "Прыгун" (в начале упоминается шахматный прыгун).

Цитата:
Сообщение от Programist_r Посмотреть сообщение
Такое движение создает букву «Л».
тут буква L
Serge_Bliznykov вне форума Ответить с цитированием
Старый 21.05.2019, 21:49   #4
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Забыл добавить)
Изображения
Тип файла: jpg Screenshot_2.jpg (23.1 Кб, 101 просмотров)
Programist_r вне форума Ответить с цитированием
Старый 21.05.2019, 21:51   #5
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Цитата:
Сообщение от evg_m Посмотреть сообщение
Входные данные
В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных
D=//4
Каждый набор состоит из ...
строки, содержащей количество N перемычек (1≤N≤ 1000)
N[1]=//1
из следующих 2N строк 2*N[1]=2*1 =2
содержащих координаты выходных полей перемычек (N строк) N[1]=1
//5 5
а затем расположение целевых полей (следующие N строк) N[1]=1
//5 6
---конец набора N[1]
N[2]=//2
...
N[3]=...
....
N[4{=D}]=...
...
--конец данных


Всё равно не понял)
Programist_r вне форума Ответить с цитированием
Старый 21.05.2019, 23:16   #6
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Есть неограниченное шахматное поле, на котором задано положение нескольких коней и соответствующее им число позиций, на которые кони должны встать за минимальное число ходов.
Координаты полей задаются в системе XY. Левое нижнее поле имеет координаты - 0 0.
Первым числом задаётся число вариантов размещения коней.
В каждом варианте задаётся число коней, координаты их начальных положений и координаты полей, на которые кони должны переместиться за минимальное число ходов.
В примере:
Первое поле - число вариантов - 4.
Вариант 1: Число коней - 1.
Конь находится в позиции - 5 5
Конь должен оказаться в позиции 5 6
Вариант 2: число коней - 2.
Конь 1 находится в позиции - 0 0
Конь 2 находится в позиции - 1 0
Кони должны оказаться в позициях 0 1 и 1 1
Каким образом кони займут эти позиции неважно. Важно, что бы число ходов было минимальным.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 22.05.2019, 09:21   #7
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Каким образом кони займут эти позиции неважно. Важно, что бы число ходов было минимальным.
Кстати, в задаче абсолютно не ясно, имеют ли кони уникальность.
ну, должен ли именно первый конь оказаться на первом целевом поле
а второй - на втором.
Рискну предположить, что нет, кони вообще не различаются.
Т.е. может быть, что быстрее поставить второго коня на первое целевое поле, а второго - на первое.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 22.05.2019, 20:08   #8
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Спасибо, теперь всё понял.
Буду думать теперь как решить
Programist_r вне форума Ответить с цитированием
Старый 22.05.2019, 20:52   #9
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Добавлю ещё немного.
При перемещении коней может случиться так, что конь должен пройти через поле, на котором уже или ещё стоит конь.
Из условия неясно, как это должно учитываться.
Если конь может ходить только по свободным полям, то как вариант, надо смотреть и возможность смены порядка ходов.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 23.05.2019, 19:45   #10
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

У меня появился вопрос
Что должно быть в ответе?
Например в первом наборе данных всё правильно, конь достигает цели за три хода, выписывается 3.
Во втором наборе не понятно откуда взялось 4, потому что первый конь достигает цели за 3 хода и второй тоже за 3.
Откуда взялось 4?
Programist_r вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Prolog. Задачи на соответствие C++++ Помощь студентам 0 06.01.2016 23:22
Неточное соответствие ВПР s8259 Microsoft Office Excel 11 11.12.2015 01:18
Соответствие условию netfilter Общие вопросы C/C++ 1 10.12.2012 14:00
проверить XML на соответствие схеме XSD LISTAT Общие вопросы Delphi 0 24.09.2012 14:22
не соответствие типов amandra SQL, базы данных 6 30.06.2008 18:04