Deep1992 Ответов: 2

Как решить проблему круга друзей с помощью динамического программирования?

2N friends(A,B,C...,2N) are standing in the Circle.There is exactly one person standing opposite of one other person. Some of them are facing inward and some of them are facing outwards. given some facts our task is to build standing positions and answer a few questions. If Arrangement not possible or more than one arrangement possible then print "ARRANGEMENT NOT POSSIBLE"



Facts
"1AB" means : A and B are standing adjacent to each other 
"2AB" means : A and B are standing opposite to each other 
"3AB" means : A is standing to the immediate left of B
"4AB" means : A is standing to the immediate right of B
"5A" means : A is facing inwards
"6A" means : A is facing outwards
"7n" means : n peoples are facing inwards, where n is a number
"8n" means : n peoples are facing outwards, where n is a number


Questions
"?2A" means : who is standing opposite of A
"?3A" means : who is standing to the immediate left of A
"?4A" means : who is standing to the immediate right of A
"?5A" means : is A facing inwards?Ans: Y/N
"?6A" means : is A facing outwards?Ans: Y/N

Constraints
1<N<10
1< TOTAL FACTS < 30
1 < Total Questions < 20


Input Format
N multiple facts, separated by semicolon multiple questions separated by semicolon

Explanation

Example 1

Input
2
2AB;72;1AC;6D;4BD;6C
?2D;?3C;?4B;?5A;?6B

output
C;B;D;Y;N

Explanation
4 people are A, B, C and D are standing in a circle
There are 6 facts separated by semicolon
2AB > A and B are standing opposite
72 >  2 people are facing inwards
1AC >  A and C are standing nearby
6D > D is facing outwards
4BD > B is standing immediate right of D
6C > C is facing outwards


Что я уже пробовал:

Я понятия не имею, как это решить

2 Ответов

Рейтинг:
14

OriginalGriff

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

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

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

Deep1992

Просто дайте мне отправную точку, как начать ... отдыхайте, я справлюсь с этим

OriginalGriff

Буквально: попробуйте это на бумаге и посмотрите, как это должно работать.

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

Deep1992

ладно я пытаюсь

Рейтинг:
1

Patrice T

Цитата:
Я понятия не имею, как это решить

Во-первых, вы должны понять проблему. Единственный способ-это многократно решать задачу вручную с разными примерами, придумывать какие-то примеры данных, так как вам нужно охватить все случаи.
Итак, возьмите лист бумаги и карандаш, а затем попробуйте решить задачу вручную.
Это процесс проб и ошибок, вот как вы будете учиться.

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

- Изучите один или несколько методов анализа, E. W. Djikstra/N. Уирт Stepwize уточнение/метод сверху вниз это хорошее начало.
Структурного Программирования.формат PDF[^]
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
https://en.wikipedia.org/wiki/Structured_programming[^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]
- Изучайте алгоритмы и структуры данных.

Динамическое программирование - Википедия[^]