Задание №5
ЕГЭ-2023. Задание 5
Тема: Формальное исполнение простого алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд, или умение восстанавливать исходные данные линейного алгоритма по результатам его работы. Время выполнения 4 минуты.
Разбор задания № 5 ЕГЭ-2023. Демо.
Эту задачу можно решить с помощью я.п.
Python:
q=4
t=True
while t:
n=bin(q)
n=str(n)
n=n.replace('0b','',1)
k=n.count('1')
if k%2==0:
n +='0'
n=n.replace(n[:2],'10',1)
else:
n +='1'
n=n.replace(n[:2],'11',1)
r = int(n,2)
if r>40:
print(q)
break
q +=1
Ответ: 16
Задание 5 ЕГЭ-2024 Демо
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное число R, большее 151, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение:
uses school;
begin
var mn:=10**10;
for var n:=4 to 1000 do
begin
var x:=bin(n);
if n mod 3 = 0 then
x +=x[x.Count-2:]
else
begin
var y:=bin((n mod 3)*3);
x +=y;
end;
var rez:=Dec(x,2);
if rez>151 then
mn:=min(mn,rez);
end;
print(mn);
end.
Ответ: 163
Задача 1.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается 01, в противном случае справа дописывается 10.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 81 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Решение.
Система программирования PascalABC.net постоянно модернизируется, поэтому ниже покажу решение этой задачи указанным я.п. При этом буду использовать модуль uses School (2018 - 2019 гг)
Сам алгоритм решения прост: перебираем числа от 82 до 100.
подсчитываем количество единиц в двоичной записи числа, которое на два разряда меньше искомого.
Проверяем: если количество единиц - нечетное число, то последние разряды двоичной записи числа должны быть '10', иначе - '01'.
И как только число отвечает поставленным требования - перебор останавливаем и выводим найденное значение.
uses School;
begin
for var i:=82 to 100 do
begin
var n:=i;
var nn:= n shr 2;
var k_ed:=bin(nn).Count(d->d='1') mod 2;
if k_ed=0 then begin
if((n and 1)=1) and ((n and 2)<>2) then begin
println(n);
break;
end
end
else begin
if((n and 1)<>1) and ((n and 2) = 2) then begin
println(n);
break
end;
end
end;
end.
Ответ: 86
Второй способ решения данной задачи (прямой):
uses school;
begin
for var n:=2 to 1000 do
begin
var x:=bin(n);
if n mod 2=0 then
x +='01'
else
x +='10';
var y:=dec(x,2);
if y>81 then begin
println(y);
break
end;
end;
end.
решение на я.п. C/C++ и Python
я.п. Python:
for i in range(82,100):
n = i
n = n >> 2
value = bin(n)
cnt = value.count('1')
nn = bin(i)
nn = nn[len(nn)-2:]
if cnt%2==0:
if nn=='01':
println(i)
break
else:
if nn=='10':
print(i)
break
2-ой вариант решения (Python):
for i in range(82,100):
n = i
n = n >> 2
value = bin(n)
cnt = value.count('1')%2
if cnt==0:
if (i & 1)==1 and (i & 2)==0:
println(i)
break
else:
if (i & 1)==0 and (i & 2)==2:
print(i)
break
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
int count_1(int x)
{
int k=0;
while (x)
{
if(x & 1)
k ++;
x = x>>1;
}
return k;
}
int main()
{
int n,nn,cnt;
for(int i=82;i<100;i++){
n = i;
nn = n >>2;
cnt = count_1(nn)%2;
if(cnt==0){
if((n & 1)==1 && (n &2)!=2){
cout<<i<<endl;
break;
}
}
else{
if((n & 1)!=1 && (n & 2)==2){
cout<<i<<endl;
break;
}
}
}
return 0;
}
Задача 2.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 92. В ответе это число запишите в десятичной системе.
Решение
Рассмотрим особенности решения задачи на примере ввода одного числа (N), например, 17.
Двоичная запись числа 17: 10001.
Количество единиц в числе: 2.
Остаток от деления суммы единиц (количество единиц): 0
Изменяем число, добавляя в конце еще один разряд: 0. И число получается: 100010.
Повторяя шаги 2 - 4, получим: 1000100.
Переводим 1000100 в десятичную систему и получаем число: 68.
Перебирая числа в диапазоне до 100, мы найдем первое (это и будет наименьшее) число, которое больше 92.
И это будет число 24, после преобразования по данному алгоритму даст число 96.
2 способ решения задачи - как при решении задачи 2.
Нахождение количества единиц в числе - смотри выше.
Прежде, чем определимся со способом решения задачи, давайте посмотрим один пример.
n = 17, двоичная запись которого - 10001.
n = 2*n + остаток от деления количества единиц на 2. Какой эффект: 1000100! (красный цвет - в этот разряд вписан остаток от деления количества единиц на 2). Следовательно, 2*n - увеличение разряда исходного числа или сдвиг числа на один разряд влево ! А всего число было увеличено на два разряда, так как алгоритм дважды повторяет это действие. Что означает "+ остаток..."? Это запись в последний разряд значения ("+" означает логическую операцию дизъюнкция).
Итак, на Питоне наша задача будет выглядеть так:
for i in range(1,50):
n = i
cnt = bin(n).count('1') % 2
n = 2*n + cnt
cnt = bin(n).count('1') % 2 #повторяем второй раз, как и написано в задаче
n = 2*n + cnt
if n > 92:
print(i)
break
Ответ: 24
решение я.п. PascalABC.net и C/C++
я.п. PascalABC.net:
uses School;
begin
for var i:=1 to 50 do
begin
var n:=i;
var cnt:=bin(n).Count(d->d='1') mod 2;
n:=2*n + cnt;
cnt:=bin(n).Count(d->d='1') mod 2;
n:=2*n + cnt;
if n>92 then begin
println(i);
break;
end;
end;
end.
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
int count_1(int x)
{
int k=0;
while (x)
{
if(x & 1) k ++;
x = x>>1;
}
return k;
}
int main()
{
int n,cnt;
for(int i=1;i<50;i++){
n = i;
cnt = count_1(n)%2;
n =2*n + cnt;
cnt = count_1(n)%2;
n =2*n + cnt;
if(n>92){
cout<<i<<endl;
break;
}
}
return 0;
}
Задача 3
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются ещё несколько разрядов по следующему правилу: если число чётное, то в конец числа (справа) дописывается 01, в противном случае - слева дописывается 1 и справа дописывается 10.
3) Результат переводится в десятичную систему счисления и выводится на экран.
Например, N = 13; после выполнения пункта 1 получим запись 1101. После выполнения пункта 2 получаем число 1110110. Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 214.
В ответе запишите это число в десятичной системе счисления.
Решение я.п. Python:
for i in range(1,50):
n = i
if i%2==0:
n = 2*n + 1
else:
n = ((n + 32) << 2) + 2
if n>214:
print(i)
break
Ответ: 23
решение я.п. С/С++ и PascalABC.net
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
int main()
{
for(int i=1;i<50;i++){
int n = i;
if(i%2==0){
n = 2*n + 1;
}
else
(n = (n + 32) << 2) + 2;
if(n>214){
cout<<i<<endl;
break;
}
}
return 0;
}
я.п. PascalABC.net:
uses School;
begin
for var i:=1 to 50 do
begin
var n:=i;
if i mod 2=0 then
n:=2*n + 1
else
n:=((n + 32)shl 2)+ 2;
if n>214 then
begin
println(i);
break;
end;
end;
end.
Задача 4
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная, запись числа N.
2. К этой записи дописываются справа ещё три разряда по следующему правилу:
а) если число чётное, то в конец числа (справа) дописывается 00, в противном случае дописывается 10;
б) если в полученном числе количество единиц чётное, то справа дописывается 0, в противном случае дописывается 1.
Например, N = 13. После выполнения пункта 1 получим запись 1101. После выполнения пункта 2а получаем число 110110. После выполнения пункта 2б получаем число 1101100.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите количество чисел R, которые принадлежат диапазону [130; 350] и могут являться результатом работы алгоритма.
Ответ: 27
проверь себя
Решение я.п. Python:
cnt = 0
for i in range(1,50):
n = i
if i%2==0: n = n << 2
else: n = (n << 2) + 2
value = bin(n)
k = value.count('1')%2
if k==0: n = n << 1
else: n = (n << 1) + 1
if n>=130 and n<=350:
cnt +=1
print(cnt)
Решение я.п. PascalABC.net:
uses School;
begin
var cnt:=0;
for var i:=1 to 50 do
begin
var n:=i;
if n mod 2=0 then
n:=n shl 2
else
n:=(n shl 2) + 2;
var val:=bin(n);
var k:=val.count(d->d='1') mod 2;
if k=0 then
n:= n shl 1
else
n:=(n shl 1) + 1;
if (n in 130..350) then
cnt +=1;
end;
println(cnt);
end.
Решение я.п. С/С++:
#include <bits/stdc++.h>
using namespace std;
int count_ed(int x)
{
int k = 0;
while(x){
k +=1;
x = x >> 1;
}
return k;
}
int main()
{
int cnt = 0;
for(int i=1;i<50;i++){
int n = i;
if (n%2==0)
n = n <<2;
else
n = (n << 2) + 2;
int value = count_ed(n)%2;
if (value==0)
n = n << 1;
else
n = (n << 1) + 1;
if(n>=130&&n<=350)
cnt +=1;
}
cout<<cnt<<endl;
return 0;
}
Задача 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи слева дописывается 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи слева дописывается 11;
в) инвертируем крайний правый разряд.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 120. В ответе запишите это число в десятичной системе счисления.
Решение:
uses school;
begin
for var n:=4 to 1000 do Begin
var x:=bin(n);
var k_ed:=x.Count(d -> d='1');
if k_ed mod 2=0 then
x :='10' + x
else
x := '11' + x;
var y:=1;
var r:=dec(x,2);
r:=r xor y;
if r>120 then begin
println(n);
break
end;
end;
end.
Результат: 26
Задача 6.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. строится четверичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R меньшее 261.
Решение я.п. PascalABC.net
Ответ: 61
uses school;
function ss_4(x: integer):string;
begin
var sl:='';
while x>0 do begin
var ost:=IntToStr(x mod 4);
sl := ost + sl;
x:=x div 4;
end;
ss_4:=sl;
end;
begin
var mx:=0;
for var n:=16 to 1000 do begin
var x:=ss_4(n);
var l:=x.Length;
if n mod 4 = 0 then
x +=x[l-1:]
else begin
var z:=ss_4(2*(n mod 4));
x +=z;
end;
var r:=dec(x,4);
if r<261 then
mx:=max(mx,n)
end;
println(mx);
end.
Решение я.п. Python
Ответ: 61
def ss_4(x):
sl=''
while x>0:
sl =str(x%4) +sl
x //=4
return sl
mx=0
for n in range(4,1000):
x = ss_4(n)
if n%4==0:
x +=x[-2:]
else:
y = ss_4(n%4*2)
x +=y
r = int(x,base=4)
if r<261:
mx=max(mx,n)
print(mx)
Задачи для самостоятельного решения
Задача 1с.
На вход алгоритма подаётся натуральное число N . Алгоритм строит по нему новое число R следующим образом .
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё три разряда по следующему правилу:
а) если число чётное, то в конец числа (справа) дописывается 00, в противном случае дописывается 10;
б) если в полученном числе количество единиц чётное, то справа дописывается 0 , в противном случае дописывается 1.
Например, N = 13. После выполнения пункта 1 получим запись 1101. После выполнения пункта 2а получаем число 110110. После выполнения пункта 26 получаем число 1101100.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N является двоичной записью искомого числа R.
Укажите количество чисел R, которые принадлежат диапазону [160; 630] и могут являться результатом работы алгоритма.
ответ
59
Задача 2с
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом .
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы.
Например, двоичная запись 1011 числа 11 будет преобразована в 101111.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R - результата работы данного алгоритма.
Укажите такое максимальное число N, для которого результат работы алгоритма будет меньше числа 102. В ответе это число запишите в десятичной системе счисления.
ответ
24
Задача 3с
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа 2N.
2. Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа).
3. Над полученной записью производится действие - справа дописывается остаток от деления суммы цифр на 2.
Например, двоичная запись 101 числа 5 будет преобразована в 101000.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое минимальное число N, для которого результат работы алгоритма будет больше числа 131. В ответе это число запишите в десятичной системе счисления.
ответ
17
Задания ЕГЭ прежних лет
