Вычеркнуть цифру в числе так чтобы число осталось наибольшим
Добавлено: 03 апр 2015, 18:53
В положительном целом числе N ≤ 1000000 вычеркнуть цифру так, чтобы число, которое осталось, было наибольшим.
Проблемы с алгоритмом, если действовать по нему то в результате получается не правильный результат.
Алгоритм:
Пусть n-количество цифр в искомом числе, а k=1 - сколько надо вычеркнуть.
1. Ишем максимальную (если их несколько, то берем самую левую) цифру среди всех цифр. Пусть цифра стоит на позиции i.
Если i < k+1, то вычеркиваем все, что слева, выводим эту цифру и решаем задачу для оставшейся части числа (от i+2 до n).
Если i = k+1, то вычеркиваем все, что слева, и ответ уже получен - вывести полученное число.
Если i > k+1, то решаем эту задачу для оставшейся слева части (так как все оттуда вычеркнуть не можем), и выводим цифры [i..n].
Проблемы с алгоритмом, если действовать по нему то в результате получается не правильный результат.
Алгоритм:
Пусть n-количество цифр в искомом числе, а k=1 - сколько надо вычеркнуть.
1. Ишем максимальную (если их несколько, то берем самую левую) цифру среди всех цифр. Пусть цифра стоит на позиции i.
Если i < k+1, то вычеркиваем все, что слева, выводим эту цифру и решаем задачу для оставшейся части числа (от i+2 до n).
Если i = k+1, то вычеркиваем все, что слева, и ответ уже получен - вывести полученное число.
Если i > k+1, то решаем эту задачу для оставшейся слева части (так как все оттуда вычеркнуть не можем), и выводим цифры [i..n].