Question

Дано число. В этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно обязательно изменить одну цифру, даже если исходное число уже делилось на 3. Программа получает на вход одно длинное натуральное число. Длина числа может достигать 100 цифр. Программа должна вывести другое натуральное число, удовлетворяющее условиям: 1. Новое число должно отличаться от данного ровно одной цифрой. 2. Новое число должно делиться на 3. 3. Новое число должно быть максимально возможным из всех таких чисел.

Answer 1

Почему-то мой ответ удалили, попробую еще раз.
1) Вводим число, как массив A[n] ; n - количество цифр в числе.
2) S = 0 ; S - сумма цифр. Если S делится на 3, то и число делится на 3.
3) Цикл по i от 1 до n
3.1) S = S + A[i]
3.2) Конец цикла по i
4) Ost = S Mod 3 ; находим остаток от деления S на 3.
4.1) Если Ost = 0, то прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
4.2) Если Ost = 1, то A[1] = A[1] + 2
4.2.1) Прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
4.3) Если Ost = 2, то A[1] = A[1] + 1
4.3.1) Прибавляем A[1] = A[1] + 3 до тех пор, пока A[1] <= 9
5) Выводим массив A[n]
6) Конец.

Модераторы, не удаляйте ответ, я его ниоткуда не списал, а сам
придумал! Если он один в один совпадает с алгоритмом на каком-то сайте, то я не виноват!

Answer 2

Для решения этой задачи можно использовать следующий алгоритм:

1. Преобразуйте входное число в массив цифр, чтобы можно было легко изменить одну из цифр. 2. Найдите первую цифру с конца, которую можно изменить так, чтобы новое число делилось на 3. 3. Измените эту цифру на максимально возможную, чтобы получить новое число. 4. Если новое число не делится на 3, повторите шаги 2-3, изменяя следующую цифру с конца.

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

1. Преобразуем число 376 в массив цифр [3, 7, 6]. 2. Начнем с последней цифры и уменьшим ее на 1, чтобы получить число 373, которое делится на 3. 3. Новое число 373 удовлетворяет всем условиям и является максимально возможным из всех чисел, удовлетворяющих этим условиям.

Таким образом, ответом на задачу будет число 373.