Анализ алгоритмов для исполнителей

1.

Анализ алгоритмов для
исполнителей

2.

Битовый сдвиг
• N= 12 = 1100 -˃ 110000 =48
12*4
• N= 11 = 1011 - 101110 = 46
11*4 +2
• Старая запись числа сдвинулась на 2 знака вправо – битовый
сдвиг
• Сдвиг на 1 число, увеличивает первоначальное число в 2 раза
• Сдвиг на 2 числа, увеличивает первоначальное число в 4 раза
и т.д. в 8, 16 …
• Любое четное число в двоичной записи заканчивается на 0,
нечётное на 1

3.

• бит чётности – это дополнительный контрольный бит,
который добавляется к двоичному коду так, чтобы
количество единиц в полученном двоичном коде стало
чётным; если в исходном коде уже было чётное
количество единиц, дописывается 0, если нечётное –
дописывается 1.
• чтобы отбросить последнюю цифру в двоичной записи,
нужно разделить число на 2 нацело (остаток
отбрасывается)
• Перевод чисел в Python
• bin(67) – переводит десятичное число в двоичную систему
счисления
• Int(‘1101001’,2) – переводит число из двоичной системы
счисления в десятичную

4.

95) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему
новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N
было чётное число единиц, и 1, если нечётное.
3) К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи
исходного числа N) является двоичной записью искомого числа R. Укажите
минимальное число R, большее 130, которое может быть получено в результате
работы этого алгоритма. В ответе это число запишите в десятичной системе.
for n in range (1, 1000): перебор чисел от 1 до 1000
s=bin(n)[2:] – перевод чисел в 2-ую систему счисления
If s.count(‘1’)%2==0: подсчет единиц и определение четность их количества
s+=’0’ - при четном кол-ве «1», приписываем «0» справа
else:
s+=’1’ - при нечетном кол-ве «1», приписываем «1» справа
If s.count(‘1’)%2==0:
for i in range (1,100):
s+=’0’
b=bin(i) [2:]
else:
b+='0' if b.count('1')%2==0 else '1'
s+=’1’
b+='0' if b.count('1')%2==0 else '1'
r=int(s,2) - переводим число из 2-ой в 10-ую
r=int(b,2)
if r>130: проверяем условие из задачи
print(r) – выводим числа, удовлетворяющие условию if r>130:
print (r)
break

5.

147) На вход алгоритма подаётся натуральное число N. Алгоритм строит по
нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа дописывается 0, если в двоичном коде числа N чётное число
единиц, и 1, если нечётное.
4) К полученному результату дописывается ещё один бит чётности так, чтобы
количество единиц в двоичной записи полученного числа стало чётным.
Полученная таким образом запись (в ней на три разряда больше, чем в записи
исходного числа N) является двоичной записью искомого числа R. Укажите
минимальное число R, большее 105, которое могло получиться в результате
работы автомата. В ответе это число запишите в десятичной системе.
for i in range (1,100):
b=bin(i) [2:]
b=b+b[-1]
b+='0' if bin(i)[2:].count('1')%2==0 else '1'
b+='0' if b.count('1')%2==0 else '1'
r=int(b,2)
if r>105:
print (r)

6.

210) Автомат обрабатывает натуральное число N по следующему алгоритму:
1 Строится двоичная запись числа N.
2 Складываются все цифры полученной двоичной записи. В конец записи (справа)
дописывается остаток от деления полученной суммы на 2
3 Предыдущий пункт повторяется для записи с добавленной цифрой.
4 Результат переводится в десятичную систему и выводится на экран.
• Пример. Дано число N = 13 Алгоритм работает следующим образом:
• 1 Двоичная запись числа N: 1101
• 2 Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись
11011
• 3 Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись
110110
• 4 На экран выводится число 54
Сколько различных чисел, принадлежащих отрезку [210; 260], могут появиться на
экране в результате работы автомата?
k=0
for i in range (1,100):
b=bin(i) [2:]
b+='0' if b.count('1')%2==0 else '1'
b+='0' if b.count('1')%2==0 else '1'
r=int(b,2)
if 210<=r<=260:
k+=1
print (k)

7.

На вход алгоритма подаётся натуральное число N. Алгоритм строит
по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по
следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления
суммы на 2 дописывается в конец числа (справа). Например,
запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа
дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше,
чем в записи исходного числа N) является двоичной записью
искомого числа R. Укажите такое наименьшее число N, для
которого результат работы алгоритма больше 125. В ответе это
число запишите в десятичной системе счисления.

8.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое чило R
следующим образом.
1) строится двоичная запись числа N.
2) к этой записи дописываются справа еще два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2
дописывается в конец числа (справа). Например, запись 11100 преобразуется в
запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от
деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного
числа N) является двоичной записью искомого числа R. Укажите такое наименьшее
число N, для которого результат работы данного алгоритма больше числа 154. В ответе
это число запишите в десятичной системе счисления.
For n in range (1, 1000):
s=bin(n)[2:]
b=b+'0' if b.count('1')%2==0 else '1':
If s.count(‘1’)%2==0:
s+=’0’
else:
s+=’1’
If s.count(‘1’)%2==0:
s+=’0’
else:
s+=’1’
if int(s, 2)>154:
print(n)

9.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему
новое число R следующим образом:
1) Строится двоичная запись числа N.
2) К этой записи дописывается ещё три или четыре разряда по следующему
правилу: если N нечётное, то слева к нему приписывается "1", а справа - "11". В
противном случае слева приписывается "11", а справа "00".
Например, N = 510 = 1012 => 1101112 = 5510 = R
Полученная таким образом запись (в ней на три или четыре разряда больше,
чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите наибольшее число R, меньшее 127, которое может быть получено с
помощью описанного алгоритма. В ответ запишите это число в десятичной
системе счисления.
for i in range (1,100):
b=bin(i) [2:]
if i%2!=0:
b='1'+b+'11'
else:
b='11'+b+'00'
r=int(b,2)
if r<127:
print (r)

10.

142) На вход алгоритма подаётся натуральное число N. Алгоритм
строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа дописывается бит чётности: 0, если в двоичном
коде полученного числа чётное
число единиц, и 1, если нечётное.
4) К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на три разряда больше,
чем в записи исходного числа N) является двоичной записью
искомого числа R. Укажите минимальное число N, после
обработки которого автомат получает число, большее 97 В ответе
это число запишите в десятичной системе.

11.

На вход алгоритма подаётся натуральное число N. Алгоритм строит
по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) К этой записи дописывается ещё три или четыре разряда по
следующему правилу: если N нечётное, то слева к нему
приписывается "10", а справа - "11". В противном случае слева
приписывается "1", а справа "00".
Например, N = 510 = 1012 => 10101112 = 8710 = R
Полученная таким образом запись (в ней на три или четыре
разряда больше, чем в записи исходного числа N) является
двоичной записью искомого числа R. Укажите наименьшее число
R, большее 1023, которое может быть получено с помощью
описанного алгоритма. В ответ запишите это число в десятичной
системе счисления.

12.

Егэ - 23
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое
число R следующим образом:
1) Строится двоичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются три последние двоичные
цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в
двоичную запись и дописывается в конец числа
Полученная таким образом запись является двоичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран. Укажите
максимальное число R, не превышающее 162, которое может быть получено с
помощью описанного алгоритма. В ответе запишите это число в 10-ой системе
счисления.
for n in range(1,1000):
b=bin(n) [2:]
if n%3==0:
b+=b[-3:]
else:
b+=bin(n%3*3) [2:]
r= int(b,2)
if r<=162:
print (r)

13.

Егэ -23
На вход алгоритма подается натуральное число N.
def f3(n):
Алгоритм строит по нему новое число R следующим
s=''
образом:
while n>0:
Строится троичная запись числа N
s=str(n%3)+s
1) Если N кратно 3, то в конце троичной записи
дописываются 3 последние цифры числа.
n=n//3
2) Иначе остаток от деления N на 3, умножается на 5,
return s
переводится в троичную запись и дописывается в
for n in range(7,100):
конец числа.
n3=f3(n)
Полученная таким образом запись является троичной
if n%3==0:
записью искомого числа R. Укажите минимальное число N,
n3+=n3[-3]
после обработки которого автоматом, получается число,
большее 150. в ответе это число запишите в десятичной
else:
системе счисления.
n3=f3(n%3*5)
r= int(n3,3)
if r>150:
print (n,r)