Статья Автор: Лебедев Дмитрий

TUZ_3-03. Извлечение возрастающих чисел

TUZ_3-03. Извлечение возрастающих чисел

TUZ_3-03. Извлечение возрастающих чисел.
3. Извлечение возрастающих чисел
В этой задаче дается строка цифр и гарантируется, что в строке присутствуют только цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Требуется разбить строку на последовательность возрастающих чисел.
Например, число 457990 можно представить в виде последовательности возрастающих чисел 4, 5, 7, 9 и 90.
Ваша задача: написать функцию, которая принимает строку из цифр и возвращает список возрастающих чисел.
Список должен быть максимальной длины, а количество используемых знаков минимальным
В табл. 3.3 показаны ожидаемые результаты для некоторых входных данных.
Таблица 3.3. Некоторые ожидаемые результаты для задачи извлечения возрастающих чисел
Digits Ожидаемый результат
'457990' [4, 5, 7, 9, 90]
'1' [1]
'13900456' [1, 3, 9, 45]
27811700 [2, 7, 8, 11, 70]

 

Алгоритм
Алгоритм состоит из двух блоков проверки возрастающих чисел. 
Сначала определяется пустая строка concatnumbers и переменная b со значением 1.
Если b = 1, выполняется вход в первый блок, а если b = 0, выполняется вход во второй блок.
Для каждой цифры в данной строке в первом блоке производится линейный поиск, пока следующее число больше предыдущего и b = 1,
и каждое следующее такое число добавляется в массив storage, после чего оно становится предыдущим числом.
Во втором блоке, если условия входа в первый блок не выполняются, переменной b присваивается 0,
затем текущее число объединяется со следующей цифрой и помещается в concatnumbers.
Если значение concatnumbers больше предыдущего числа, то оно сохраняется в storage
и переменной concatnumbers присваивается пустая строка.
Пока объединение следующих цифр меньше или равно предыдущему числу, объединение повторяется для следующих цифр.
Когда b = 0, алгоритм ни за что не сможет войти в первый блок, поскольку ни одна цифра не будет больше предыдущих чисел и 
входить в первый блок бессмысленно.


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать