Правильный ли алгоритм?

Question

[Андрей]

Условие:

Вычеркнуть цифру в числе так чтобы число осталось наибольшим.

Алгоритм:

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

Нужно написать на BASH.

Comments

[jcmvbkbc]

Если числа имеют разумную длину, то можно испольовать алгоритм попроще:
- сравнить значения чисел полученных из исходного вычёркиванием 1-й, 2-й, ..., последней цифры. Выбрать из них максимальное.
- повторить k раз.

Нужно написать на BASH.

Не имеет никакого отношения к алгоритму.

[Андрей]

jcmvbkbc, вот я точно так и хотел написать, но у меня не получилось на BASH это реализовать (из-за нехватки знаний). Поэтому и нашел другой алгоритм в просторах.

[jcmvbkbc]

Андрей, я думаю, что в любом случае тебе придётся использовать выделение подстрок -- ${parameter:offset:length}, а больше, как будто, тут ничего и не надо:

#! /bin/bash

k=$1
V=$2

for (( i=0 ; i < $k; ++i )) ; do
    Vi=${V:1}
    for (( j=1 ; j < ${#V} ; ++j )) ; do
        Vj=${V:0:$j}${V:$(($j + 1))}
        if [ $Vj -gt $Vi ] ; then
            Vi=$Vj
        fi
    done
    V=$Vi
done
echo $V

из-за нехватки знаний

man bash полезен для борьбы с нехваткой знаний

[Андрей]

jcmvbkbc, спасибо большое)

[Alexej Simakov]

jcmvbkbc если попытаться обойтись без полного перебора, разве не будет достаточным в верхнем триплете удалить наименьшую цифру? Разумеется, учитывая следующие особые случаи:
а) Если триплет состоит из одинаковых цифр - сдвинуть "окно" на один порядок вправо и повторить, пока таким образом не найдется кандидат для удаления, либо
б) Если в триплете две наименьших цифры - удалить ту которая старше разрядом.

пример для правила б) 4642464 - удаляем первую четверку, получаем 64246
пример для правила а) 9992464 - сдвигаем "окно" на один порядок вправо и удаляем двойку, получаем 999464

[jcmvbkbc]

Alexej Simakov, достаточно удалить первую цифру, которая меньше следующей за ней (или последнюю, если цифры монотонно не возрастают). Но это не меняет сути алгоритма: в худшем случае он всё равно остаётся линейным по цифрам.