Как решить задачу объединения чисел по префиксу? Суть задачи:
Есть случайный список префиксов телефонных номеров, т. е. чисел в диапазоне от 1 до 99 999 999 999 (максимальная длина 11 знаков), представленных в виде строки.
Необходимо привести номера в этом списке к наибольшему префиксу, а именно:
- например, если в списке есть префиксы 1230, 1231, 1232 ... 1239, они удаляются и вместо них добавляется префикс 123;
- далее цикл повторяется - если в списке есть префиксы 120, 121, 122, 123 ... 129, они объединяются к 12.
- и так пока все элементы списка не объединяться к наибольшему префиксу.
- префиксы начинающиеся с 0 объединять не нужно.
Ткните, пожалуйста, в алгоритм решения этой задачи. Вижу, что вроде перебор и рекурсия, но с какого конца начать не понимаю.
Как решить задачу объединения чисел по префиксу? Суть задачи:
Есть случайный список префиксов телефонных номеров, т. е. чисел в диапазоне от 1 до 99 999 999 999 (максимальная длина 11 знаков), представленных в виде строки.
Необходимо привести номера в этом списке к наибольшему префиксу, а именно:
- например, если в списке есть префиксы 1230, 1231, 1232 ... 1239, они удаляются и вместо них добавляется префикс 123;
- далее цикл повторяется - если в списке есть префиксы 120, 121, 122, 123 ... 129, они объединяются к 12.
- и так пока все элементы списка не объединяться к наибольшему префиксу.
- префиксы начинающиеся с 0 объединять не нужно.
Ткните, пожалуйста, в алгоритм решения этой задачи. Вижу, что вроде перебор и рекурсия, но с какого конца начать не понимаю.
Есть случайный список префиксов телефонных номеров, т. е. чисел в диапазоне от 1 до 99 999 999 999 (максимальная длина 11 знаков), представленных в виде строки.
Необходимо привести номера в этом списке к наибольшему префиксу, а именно:
- например, если в списке есть префиксы 1230, 1231, 1232 ... 1239, они удаляются и вместо них добавляется префикс 123;
- далее цикл повторяется - если в списке есть префиксы 120, 121, 122, 123 ... 129, они объединяются к 12.
- и так пока все элементы списка не объединяться к наибольшему префиксу.
- префиксы начинающиеся с 0 объединять не нужно.
Ткните, пожалуйста, в алгоритм решения этой задачи. Вижу, что вроде перебор и рекурсия, но с какого конца начать не понимаю.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться следующим алгоритмом:
Создать пустой словарь, где ключом будет являться префикс, а значением - список всех номеров с таким префиксом.Пройти по каждому номеру в исходном списке и добавить его в словарь, используя подходящий префикс. (например, для номера 1234 нужно добавить его в список префикса 123)Пройти по словарю и для каждого префикса проверить, есть ли в нем номера. Если номера есть, то необходимо удалить последний символ префикса и добавить номеры в список префикса на один уровень выше. (например, если есть префикс 123 и номера в нем есть, то нужно объединить их с префиксом 12)Повторить шаг 3, пока в словаре не останутся только префиксы без номеров.Таким образом, после завершения алгоритма в списке останутся только номера с наибольшим префиксом.