Следующее число

[maksatktl]

Следующее число
(Время: 1 сек. Память: 16 Мб Сложность: 36%)
Задано натуральное число N.

Требуется написать программу, которая найдет следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число N (N ≤ 230).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать ответ на задачу.

Примеры

№ INPUT.TXT OUTPUT.TXT
1 1 2
2 2 4
3 3 5
pomogite 4em mojete
ssilka:http://acmp.ru/index.asp?main=task&id_task=318
HELP

[MBo]

http://e-maxx.ru/algo/generating_combinations

[хус++]

переводим N в двоичную систему счисления

Bin := '';
          while (N > 0)
          do
            begin
              Bin := Chr (N mod 2 + 48) + Bin;
              N := N div 2;
            end;

добавим в двоичное представление ведущие нули

for i := 1 to (35 - Length (Bin)) do
            Bin := '0' + Bin;

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

 for i := Length (Bin) downto 1 do
            if (Bin [i] = '1')
               and
               (Bin [i - 1] = '0')
              then
                begin
                  Bin [i - 1] := '1';
                  Bin [i] := '0';
                  t := i;

                  break;
                end;

потом сортируем оставшуются часть числа по неубыванию

 for i := t to (Length (Bin) - 1) do
            for j := t to (Length (Bin) - i) do
              if (Bin [j] > Bin [j + 1])
                then
                  begin
                    Bin [j] := '0';
                    Bin [j + 1] := '1';
                  end;

теперь переведем результат в десятичную систему счисления и прибавляем последнюю цифру двоичного разряда

 for i := 1 to (Length (Bin) - 1) do
            if (Bin [i] <> '0')
              then
                Inc (N, Pow (2, Length (Bin) - i));
Inc (N, Ord (Bin [Length (Bin)]) - 48);