#algorithm #sorting
#алгоритм #сортировка
Вопрос:
я программирую карточную игру, и мне нужно отсортировать стопку карт по их рангу. так, чтобы они образовывали последовательность без пробелов. в этой специальной игре карта со значением 2 может быть использована в качестве подстановочной карты, так что, например, карты
2 3 5
должно быть отсортировано следующим образом
3 2 5
потому что 2 заменяет 4, иначе это была бы недопустимая последовательность.
однако карточки
2 3 4
должно остаться как есть.
ограничение: в качестве подстановочного знака может использоваться только один ‘2’.
2 2 3 4
также останется как есть, потому что первые 2 заменят туза (или 1, как вы это называете).
следующая последовательность ввода не будет допустимой, поскольку один из двух символов должен использоваться в качестве подстановочного знака, а другой — нет. тогда невозможно составить последовательность без пробелов.
2 4 2 6
теперь мне трудно понять, используется ли 2 в качестве подстановочного знака или нет. как только я это получу, я думаю, что смогу выполнить остальную сортировку
спасибо за любую алгоритмическую помощь в решении этой проблемы!
Комментарии:
1. Если у вас есть карточки
2,2,4,6, должна ли результирующая последовательность быть2,4,2,6или4,2,6,2?2. хороший вопрос! в качестве подстановочной карты может использоваться только одна ‘2’. таким образом, этот случай изначально не является допустимой последовательностью. я соответствующим образом отредактирую свой вопрос.
3. Измените первый встреченный
2символ на0(или какой-либо другой символ, который не используется) и используйте его в качестве подстановочного знака. Затем преобразуйте его обратно в2перед отображением.4. Итак, каким был бы ответ на вопрос @Jim’s?
Invalid data?6, 2?4, 2, 6? Можно ли с уверенностью предположить, что ваша программа никогда не получит неверные данные? Существуют ли какие-либо другие данные о входных данных, которые мы можем использовать?5. @clamp, ты не ответил на мой вопрос. Можете ли вы предположить, что вы никогда не получите неверные данные? Обязательно ли проверять недопустимый ввод? Что еще, если вообще что-либо, мы можем предположить о состоянии программы?
Ответ №1:
РЕДАКТИРОВАТЬ в ответ на ваше разъяснение к вашему новому требованию:
Вы подразумеваете, что вы никогда не получите данные, для которых не может быть сформирована последовательность без пробелов. (Если бы только я мог иметь такие гарантии в реальном мире.) Итак:
- У вас есть 2?
- Нет: ваша последовательность уже должна быть без пробелов.
- Да: Вам нужно выяснить, куда это поместить.
- Сортируйте свои входные данные. Вы видите пробел? Поскольку вы можете использовать только один 2 в качестве подстановочного знака, может быть не более одного пробела.
- Нет: рассматривайте 2 как законное число два.
- Да: переместите 2 в пробел, чтобы заполнить его.
ОТРЕДАКТИРУЙТЕ в соответствии с вашим новым требованием:
В этом случае просто найдите наибольший одиночный пробел и замените его на 2, если у вас есть 2 в наличии.
Оригинальный ответ:
Поскольку ваша последовательность должна быть без пробелов, вы могли бы подсчитать количество имеющихся у вас двоек и размеры всех имеющихся пробелов. Затем просто заполните самый большой пробел, для которого у вас есть достаточное количество двоек.
Комментарии:
1. спасибо, что наставил меня на правильный путь. я не упоминал об этом, но вы не можете опускаться ниже 1, поэтому в случае двух двоек также обязательно переместите wild 2 в конец, если присутствует 1 (туз). пример: 1 2 3 2