2. Вычеркните из числа 74263198 четыре цифры, чтоб получился наибольший возможный результат.

Question

Вопрос:

2. Вычеркните из числа 74263198 четыре цифры, чтоб получился наибольший возможный результат.

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Решение:

Чтобы получить наибольшее возможное число, нужно оставить как можно больше большие цифры в начале числа. Для этого мы будем вычеркивать меньшие цифры, которые стоят перед большими.

Исходное число: 74263198. Нужно вычеркнуть 4 цифры.

Сравниваем первую цифру '7' со следующими. '4' меньше '7', вычеркиваем '4'. Число: 7263198. Вычеркнуто 1 цифра.
Сравниваем '7' со следующей '2'. '2' меньше '7', вычеркиваем '2'. Число: 763198. Вычеркнуто 2 цифры.
Сравниваем '7' со следующей '6'. '6' меньше '7', вычеркиваем '6'. Число: 73198. Вычеркнуто 3 цифры.
Теперь у нас осталось число 73198, и нам нужно вычеркнуть еще одну цифру. Сравниваем '7' со следующей '3'. '3' меньше '7', вычеркиваем '3'. Число: 7198. Вычеркнуто 4 цифры.

Получилось число 7198.

Но нужно получить НАИБОЛЬШИЙ результат. Значит, нужно оставлять большие цифры в начале.

Исходное число: 74263198. Нужно вычеркнуть 4 цифры.

Ищем первую цифру, которую можно вычеркнуть, чтобы получить наибольшее число. Это самая левая цифра, которая меньше следующей.
Смотрим на '7'. Следующая цифра '4' меньше '7'. Мы можем вычеркнуть '4', чтобы оставить '7' на первом месте. (7_263198)
Смотрим на '2'. Следующая цифра '6' больше '2'. Значит, '2' не выгодно вычеркивать, так как '6' идет позже.
Смотрим на '6'. Следующая цифра '3' меньше '6'. Вычеркиваем '3'. (7426_198)
Смотрим на '1'. Следующая цифра '9' больше '1'. Выгодно оставить '1' перед '9'.
Смотрим на '9'. Следующая цифра '8' меньше '9'. Выгодно оставить '9' перед '8'.

Алгоритм: ищем цифру, которую можно вычеркнуть. Это самая левая цифра, которая меньше следующей. Если такой нет, вычеркиваем самую правую (последнюю).

Исходное число: 74263198. Вычеркнуть 4 цифры.

Сравниваем '7' и '4'. '4' < '7'. Мы можем вычеркнуть '4', чтобы '7' осталось первым. Число: 7263198. (1 вычеркнута)
Сравниваем '2' и '6'. '6' > '2'. Мы не будем вычеркивать '2', так как '6' больше.
Смотрим на '3'. '3' < '6'. Вычеркиваем '3'. Число: 7426198. (2 вычеркнуты)
Смотрим на '1'. '1' < '9'. Вычеркиваем '1'. Число: 7426398. (3 вычеркнуты)
Смотрим на '8'. '8' < '9'. Вычеркиваем '8'. Число: 7426319. (4 вычеркнуты)

Получилось: 7426319. Это не наибольшее.

Правильный подход: для получения наибольшего числа, мы хотим, чтобы на каждой позиции стояла максимально возможная цифра, начиная слева.

Исходное число: 74263198. Нужно вычеркнуть 4 цифры.

Шаг 1: Ищем первую цифру, которую можно вычеркнуть. Это самая левая цифра, которая меньше следующей. В паре '74', '4' меньше '7'. Вычеркиваем '4'. Осталось: 7263198. (1 вычеркнута)

Шаг 2: Теперь смотрим на '7'. Следующая цифра '2'. '2' меньше '7'. Вычеркиваем '2'. Осталось: 763198. (2 вычеркнуты)

Шаг 3: Теперь смотрим на '7'. Следующая цифра '6'. '6' меньше '7'. Вычеркиваем '6'. Осталось: 73198. (3 вычеркнуты)

Шаг 4: Теперь смотрим на '7'. Следующая цифра '3'. '3' меньше '7'. Вычеркиваем '3'. Осталось: 7198. (4 вычеркнуты)

Получилось 7198.

Давайте пересмотрим. Мы хотим оставить как можно больше больших цифр в начале. Ищем первые 4 цифры, которые меньше следующих.

Число: 74263198. Вычеркнуть 4 цифры.

Смотрим на '7'. Следующая цифра '4'. '4' < '7'. Вычеркиваем '4'. Остается: 7263198. (1 вычеркнута)
Смотрим на '2'. Следующая цифра '6'. '6' > '2'. Мы не вычеркиваем '2'.
Смотрим на '6'. Следующая цифра '3'. '3' < '6'. Вычеркиваем '3'. Остается: 7426198. (2 вычеркнуты)
Смотрим на '1'. Следующая цифра '9'. '9' > '1'. Мы не вычеркиваем '1'.
Смотрим на '9'. Следующая цифра '8'. '8' < '9'. Вычеркиваем '8'. Остается: 7426319. (3 вычеркнуты)

Мы вычеркнули 3 цифры. Нам нужно вычеркнуть еще одну. В оставшемся числе 7426319, какая цифра самая маленькая в начале?

Нам нужно вычеркнуть 4 цифры, чтобы оставшиеся составили наибольшее число.

Смотрим слева направо. Если текущая цифра меньше следующей, то мы вычеркиваем текущую цифру (или следующую, в зависимости от того, что даст больший результат).

Ищем первую цифру, которую нужно вычеркнуть. Это самая левая цифра, которая меньше следующей. Если таких нет, то вычеркиваем последнюю.

Число: 74263198. Вычеркиваем 4 цифры.

'7' > '4'. Вычеркиваем '4'. Остается: 7263198. (1 вычеркнута)
'2' < '6'. Значит, '2' не будет первым. Чтобы увеличить число, нужно вычеркнуть '2'. Остается: 763198. (2 вычеркнуты)
'6' > '3'. Вычеркиваем '3'. Остается: 76198. (3 вычеркнуты)
'1' < '9'. Вычеркиваем '1'. Остается: 7698. (4 вычеркнуты)

Число: 7698.

Проверим еще раз:

Число: 74263198. Вычеркнуть 4 цифры.

Чтобы получить наибольшее число, мы должны стремиться к тому, чтобы наибольшие цифры стояли как можно левее.

1. Ищем первую цифру, которую можно вычеркнуть, чтобы получить большее число. Это самая левая цифра, которая меньше следующей. '4' меньше '7'. Вычеркиваем '4'. Число: 7263198. (1 вычеркнута)

2. Теперь смотрим на '2'. '2' меньше '6'. Значит, '2' не оптимальна. Вычеркиваем '2'. Число: 763198. (2 вычеркнуты)

3. Теперь смотрим на '6'. '6' больше '3'. Вычеркиваем '3'. Число: 76198. (3 вычеркнуты)

4. Теперь смотрим на '1'. '1' меньше '9'. Вычеркиваем '1'. Число: 7698. (4 вычеркнуты)

Итак, вычеркнули 4, 2, 3, 1. Получилось 7698.

Ответ: 7698