Задача. Автомат обрабатывает натуральное число 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.
