Составить из числа наименьшее число, которое делится на 3

[Promi]

Дано натуральное число, содержащее до 50 разрядов. Составить из этого числа наименьшее число, которое делится на 3. Если такое число составить невозможно, то выведите NO.

[Serge_Bliznykov]

для любого количества разрядов для десятичных чисел действует правило - если сумма цифр числа делится на 3, то и число делится, и верно обратное, если сумма цифр не делится на 3, то и само число не кратно трём.

Т.е. нужно сперва просуммировать все разряды. Проверить полученную сумму, если она не кратна трём - выход с NO
иначе отсортировать массив с числами по возрастанию.
Это и будет минимальное число, которое можно составить из исходного.
Всё, задача решена.

p.s. Написать решение в виде кода надо меньше времени, чем я это своё сообщение сочинял!

[Promi]

да, это мне было известно, но у меня не получается написать в виде кода(

[Serge_Bliznykov]

Сообщение от Promi

да, это мне было известно, но у меня не получается написать в виде кода(

А что получилось написать?
Переменные объявить получилось?
Осуществить ввод нужного 50-значного числа получилось?
Где ваш код?
я не вижу ваших попыток решить задачу.

[Аватар]

Здесь формирование наименьшего. Ввод/вывод и проверку делимости на 3 сам делай

  //в s строка с цифрами
  k:=0;
  for i:=1 to Length(s)-1 do begin
    for j:=i+1 to Length(s) do if s[j]<s[i] then begin c:=s[i]; s[i]:=s[j]; s[j]:=c; end;
    if (s[i]<>'0') and (k=0) then k:=i;
  end;
  if k=0 then k:=Length(s);
  if k>1 then begin s[1]:=s[k]; s[k]:='0'; end;
  //результат в s

[Smitt&Wesson]

Сообщение от Promi

Дано натуральное число, содержащее до 50 разрядов. Составить из этого числа наименьшее число, которое делится на 3. Если такое число составить невозможно, то выведите NO.

int n;// к-во разрядов
........
if(n > 15) {cout<<"NO"; return;}
// здесь делаем перестановки и проверку

Количество перестановок = n!
Для получения всех перестановок 50-и разрядов, компу не хватит ни времени ни ресурсов .

[Аватар]

А зачем их получать?

[Smitt&Wesson]

Сообщение от Аватар

А зачем их получать?

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

0000 = No
1111 = 1+1+1= 3
2222 = 2+2+2 = 6
3333 = 3
4444 = 4+4+4 = 12
5555 = 5+5+5 = 15
6666 = 6
7777 = 7+7+7 = 21
8888 = 8+8+8 = 24
9999 = 9

Ну и могут быть комбинации из разных цифр.
Возьмём другой пример:

1875 сумма = 21 - не делится
но минимальное число, составленное из этих цифр = 15 - делится.
1-а стоит в старшем разряде, а 5-а в младшем. Как компу "объяснить", что нужно считать наименьшую сумму? Только перестановками.
После N перестановок число примет вид 7815. Сумма двух последних и будет искомое наименьшее.

Если бы в задании было - определить, делится ли число на 3, тут и вопросов-бы небыло. Подсчитываем сумму всех цифр и делим на 3. Если в остатке 0 - делится, не ноль - не делится.

[Аватар]

Ну вот число 710052, оно делится на 3.
Наименьшее число из этих цифр 100257 без всяких перестановок и оно тоже делится на 3

[Smitt&Wesson]

Сообщение от Аватар

Ну вот число 710052, оно делится на 3.
Наименьшее число из этих цифр 100257 без всяких перестановок и оно тоже делится на 3

Не правда. Минимальная делящаяся на 3 сумма = 1 + 2 = 3
У тебя тоже числа переставлены. Как его получить без перестановок?
И у тебя оно не наименьшее. Наименьшим будет 001257.
Добиваемся простой сортировкой по возрастанию.