Язык Паскаль. Автомат обрабатывает натуральное число N > 1. Для скольких значений N в результате работы алгоритма получится число, принадлежащее отрезку [150; 200]?

 Задача. Автомат обрабатывает натуральное число N > 1 по следующему алгоритму:

1. Строится двоичная запись числа N.

2. В конец записи (справа) дописывается вторая справа цифра двоичной записи.

3. В конец записи (справа) дописывается вторая слева цифра двоичной записи.

4. Результат переводится в десятичную систему.

Пример. Дано число N = 11. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1011.

2. Вторая справа цифра 1, новая запись 10111.

3. Вторая слева цифра 0, новая запись 101110.

4. Результат работы алгоритма R = 46.

Для скольких значений N в результате работы алгоритма получится число, принадлежащее отрезку [150; 200]?

Как будем решать задачу?

Будем искать число N, для которого результат работы алгоритма будет принадлежать отрезку [150; 200].

Обнулим искомый счетчик чисел r:=0.

Запустим цикл по подбираемым числам (по условию задачи это числа, больше 1, правую границу возьмем за 100, эту границу можно подбирать): 

for k:=2 to 100 do

За число N возьмем значение k.

Выполним перевод числа N в двоичную систему счисления: для этого пока число не равно 0, вычислим остаток от деления на 2 (это двоичная цифра), число уменьшим нацело в 2 раза. Чтобы получить двоичный код, превратим цифру n mod 2 в строку d процедурой str(n mod 2, d), и накопим строку s - это и будет двоичный код числа N, причем будем к вновь полученной цифре добавлять строку, тогда цифры двоичного кода будут получены в правильном порядке:

s:=d + s;

Далее по алгоритму, описанному в условии задачи, добавим к полученному коду предпоследний символ и второй символ, это и есть результат работы алгоритма:

s:=s+s[length(s)-1]+s[2];

Далее проверим, принадлежит ли полученный двоичный код результата диапазону чисел [150, 200].

Мы знаем, что числа из данного промежутка имеют длину 8 в двоичной коде, поэтому сравним принадлежность отрезку условием:

(length(s)=8) and (s>='10010110') and (s<='11001000')

Двоичный код числа 150 - это 10010110, а двоичный код числа 200 - это 11001000.

Если условие ИСТИНА, накопим искомый счетчик чисел r, также можно вывести само подходящее число N (это значение счетчика k, значение самой переменной N равно 0 из-за выполненного перевода).

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

Программа решения на языке Паскаль

var s,d:string; n,k,r:integer;

  begin

    r:=0;

    for k:=2 to 100 do

    begin

      n:=k; s:='';

      while n<>0 do

      begin

        str(n mod 2,d);

        s:=d+s;

        n:=n div 2;

      end;

      s:=s+s[length(s)-1]+s[2];

      if (length(s)=8)and(s>='10010110')and(s<='11001000')

          then begin print(k); r:=r+1; end;

    end;

    println('Количество чисел:',r);

  end.

Результат запуска программы

Ответ к задаче: 12 чисел

Способ 2 (используем модуль School и функции bin и dec)

Будем использовать функцию bin из модуля School для перевода числа в двоичную систему счисления, результатом будет строка двоичных цифр.

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

Программа решения задачи на языке Паскаль

uses School;

var N,R,Kol:integer; B:string; 

  begin

    for N:=2 to 100 do

    begin

      B:=bin(N);

      B:=B+B[length(B)-1]+B[2];

      R:=dec(B,2);

      if R in [150..200] then Kol+=1;

    end;

    println(Kol);

  end.