Подготовка к ЕГЭ по информатике
учебно-методический материал по информатике и икт (11 класс)

Слайд 1

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

Слайд 2

Битовый сдвиг N= 12 = 1100 -˃ 1100 00 =48 12*4 N= 11 = 1011 - 1011 10 = 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, которое может быть получено в результате работы этого алгоритма. В ответе это число запишите в десятичной системе . f or 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: s+=’0’ else: s+=’1 ’ r= int (s,2) - переводим число из 2-ой в 10-ую if r > 130 : проверяем условие из задачи print(r) – выводим числа, удовлетворяющие условию break 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 r>130: print (r)

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

Слайд 9

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "1", а справа - "11". В противном случае слева приписывается "11", а справа "00". Например, N = 5 10 = 101 2 => 110111 2 = 55 10 = 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 = 5 10 = 101 2 => 1010111 2 = 87 10 = R Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наименьшее число R, большее 1023, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления.

Слайд 12

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) Егэ - 23 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: Строится двоичная запись числа N . Далее эта запись обрабатывается по следующему правилу: а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры; б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа Полученная таким образом запись является двоичной записью искомого числа R . Результат переводится в десятичную систему и выводится на экран. Укажите максимальное число R , не превышающее 162, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в 10-ой системе счисления.

Слайд 13

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

Слайд 1

Циклические алгоритмы для исполнителя

Слайд 2

120 0 – треугольник 120*3=360 90 0 – квадрат 90*4=360 72 0 – пятиугольник 72*5=360 60 0 – шестиугольник 60*6=360 Р $: Если угол поворота делитель 360, то получим правильный многоугольник n 0 поворот = > 360/ n сторон

Слайд 3

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … Команда S ] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 100 [Вперёд 10 Направо 36 ]. Определите, из какого количества отрезков будет состоять фигура, заданная данным алгоритмом. Построить фигуру Работа с фигурой

Слайд 4

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепашки на n шагов в направлении движения; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 Команда3] означает, что последовательность команд в скобках повторится k раз. Черепашке был дан для исполнения следующий алгоритм: Повтори 5 [Вперёд 80 Направо 60] Какая фигура появится на экране? 1) правильный пятиугольник 2) правильный треугольник 3) правильный шестиугольник 4) незамкнутая ломаная линия

Слайд 5

Черепахе был дан для исполнения следующий алгоритм: Повтори 100 [Вперёд 10 Направо 36 ]. Определите, из какого количества отрезков будет состоять фигура, заданная данным алгоритмом.

Слайд 6

1. Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … Команда S ] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 100 [Вперёд 10 Направо 48 ]. Определите, периметр фигуры, которую построит Черепаха использовать Черепаха алг нач . опустить хвост . нц 100 раз . . вперед (10) . . вправо (48) . кц кон

Слайд 7

2. Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … Команда S ] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 36 [Направо 60 Вперёд 1 Направо 60 Вперёд 1 Направо 270 ]. Определите, сколько углов у фигуры, ограниченной линией, заданной данным алгоритмом использовать Черепаха алг нач . опустить хвост . нц 36 раз . . вправо (60) . . вперед (1) . . вправо (60) . . вперед (1) . . вправо (270) . кц кон

Слайд 8

использовать Черепаха алг нач . опустить хвост . нц 7 раз . . вправо (90) . . вперед (4) . . нц 2 раза . . . влево (90) . . . вперед (4) . . кц . кц кон Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … Команда S ] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 7 [Направо 90 Вперёд 4 Повтори 2 [ Налево 90 Вперёд 4 ] ]. Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

Слайд 9

from turtle import * - включает функцию Черепаха tracer(0) - выключает анимацию for i in range(7): - повтор 7 раз rt (90) fd (4*25) – вперед на 4 пикселя умноженное на масштаб for j in range(2): - повтор 2 раз lt (90) – поворот на 90 градусов fd (4*25) up() for x in range (-20, 20): for y in range (-20,20): goto (x*25, y*25) – перемещает Черепаху в указанную координату dot (3) – рисует точку размером в 3 пикселя update () – обновляет картинку Рисует фигуру Рисует сетку (точки)

Слайд 10

from turtle import * - включает функцию Черепаха for x in range( а ): - повтор а раз Forward ( ) или fd ( ) – вперед ( ) Right ( ) или rt ( ) – поворот направо ( ) done( ) – задержка изображения

Слайд 11

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на ( a,b ) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами ( x+a , y+b ). Если числа a, b положительные, то значение соответствующей координаты увеличивается, если отрицательные — уменьшается. Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2,-3) переместит Чертёжника в точку (6,-1). Запись Повтори k раз Команда1 Команда2 Команда3, конец означает, что последовательность Команда1 Команда2 Команда3 повторится k раз. Чертёжнику был дан для исполнения следующий алгоритм: Повтори 5 раз Сместиться на ( 6 , 8 ) Сместиться на (-5 , 12 ) Сместиться на ( 6 , 0 ) Конец Определите длину линии, которая будет получена в результате выполнения данного алгоритма

Слайд 13

Чертёжнику был дан для исполнения следующий алгоритм: Повтори 10 раз Сместиться на (5, 7) Сместиться на (4 , -3) Сместиться на (-9, -4) Конец Перед началом алгоритма Чертёжник находится в начале координат. Определите, сколько точек с целочисленными координатами будут находиться внутри области. Ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

Слайд 14

from turtle import * tracer (0) for i in range(10): goto ( xcor ()+5*25, ycor ()+7*25) goto ( xcor ()+4*25, ycor ()-3*25) goto ( xcor ()-9*25, ycor ()-4*25) up() for x in range (-20,20): for y in range (-20,20): goto (x*25, y*25) dot (3) update()

Слайд 15

from turtle import * Screensize (10000,10000) tracer (0) for i in range(7): goto ( xcor ()+6*15, ycor ()-9*15) goto ( xcor ()-6*15, ycor ()+2*15) goto ( xcor ()+12*15, ycor ()+3*15) up() for x in range (-20,20): for y in range (-20,20): goto (x*15, y*15) dot (3) update()

Слайд 1

Кодирование графической и звуковой информации

Слайд 2

Графика Рассматривается только растровая Х рх У рх Х*У – количество пикселей i бит – информационный вес о дного пикселя, зависящий от к ол-ва используемых цветов N=2 i Размер изображения: А*В* i бит

Слайд 3

Какой минимальный объем памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 128 на 128 пикселов при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не надо. I= Х*У* i 256=2 i i = 8 бит 1 Кбайт = 1*8*1024 бит 2 3* 2 10 = 2 13 I = 128 * 128 * 8/2 13 = 16 Кбайт

Слайд 4

Камера делает фотоснимки размером 1600 × 1200 пикселей. На хранение одного кадра отводится 1 Мбайт. Найдите максимально возможное количество цветов в палитре изображения. 1600 × 1200 × i =1*2 23 i =1*2 23 /1600*1200 ≈ 4,36 бит i = 4 бит = > N = 2 4 = 16 цветов

Слайд 5

Автоматическая фотокамера каждые 6 с. Создаёт черно-белое растровое изображение, содержащее 256 оттенков. Размер изображения - 128×256 пикселей. Все полученные изображения и коды пикселей внутри одного изображения записываются подряд, никакая дополнительная информация не сохраняется, данные не сжимаются. Сколько Мбайтов нужно выделить для хранения всех изображений, полученных за сутки? 256=2 i => i =8 бит 1 изображение: 128×256×8бит Число снимков: 24*60*60/6с 128*256*8*24*60*60/6*2 23 = 450 Мбайт

Слайд 6

В информационной системе хранятся изображения размером 1600*1200 пикселей. При кодировании используется алгоритм сжатия изображений, позволяющий уменьшить размер памяти для хранения одного изображения в среднем в 5 раз по сравнению с независимым кодированием каждого пикселя. Каждое изображение дополняется служебной информацией, которая занимает 100 Кбайт. Для хранения 32 изображений выделено 10 Мбайт памяти. Какое максимальное количество цветов можно использовать в палитре каждого изображения? На 1 изображение: 10*2 10 /32 = 320Кбайт 320Кбайт – 100Кбайт = 220Кбайт 220 * 5 = 1100Кбайт 1600*1200* i = 1100 = > i =1100*2 13 /1600*1200 I ≈ 4,69 бит N=2 4 = 16 цветов

Слайд 7

Для хранения в информационной системе документы сканируются с разрешением 600 ppi и цветовой системой, содержащей 2 24 = 16 777 216 цветов. Методы сжатия изображений не используются . Средний размер отсканированного документа составляет 12 Мбайт. В целях экономии было решено перейти на разрешение 300 ppi и цветовую систему, содержащую 256 цветов . Сколько Мбайт будет составлять средний размер документа, отсканированного с изменёнными параметрами? Листок А*В дюймов 72А*72В 300А*300В До После 600А*600В*24 300А*300В*8 12Мбайт/12 = 1 Мбайт

Слайд 8

З вук ∂ - частота дискретизации (Гц) i – битовая глубина (разрешение) (бит) t – время звучания (сек) К – каналы I = ∂ * i *t*k бит – размер звука

Слайд 9

Производится одноканальная (моно) звукозапись с частотой дискретизации 22 кГц и глубиной кодирования 16 бит. Запись длится 2 минуты, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла , выраженному в мегабайтах? 1*22000*16*120=42240000 бит 4224/2 23 =5Мбайт

Слайд 10

Производилась двухканальная (стерео) звукозапись с частотой дискретизации 48 кГц и 24-битным разрешением . В результате был получен файл размером 5625 Мбайт, сжатие данных не производилось . Определите приблизительно, сколько времени (в минутах) производилась запись. В качестве ответа укажите ближайшее к времени записи целое число, кратное 5 2*48000*24* t =5625*2 23 t=5625* 2 23 / 2* 48000*24 t = 20480 c.= 340 мин.

Слайд 11

88 ) Производится двухканальная (стерео) звукозапись с частотой дискретизации 44 кГц. Запись длится 5 минут 25 секунд, её результаты записываются в файл без сжатия данных, причём каждый сигнал кодируется минимально возможным и одинаковым количеством бит. Информационный объём полученного файла без учета заголовка не превышает 82 Мбайт. Определите максимальную битовую глубину кодирования звука, которая могла быть использована в этой записи. В ответе запишите только число. 2*44000*325* i =82*2 23 i =82*2 23 /2*44000*325 i = 24 бит

Слайд 12

Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 15 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 3 раза выше и частотой дискретизации в 2 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. До После 1* ∂* i *t 2*3i * ∂ /2 – в 3 раза больше 15 Мбайт 15*3=45 Мбайта

Слайд 13

62 ) Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных . Получившийся файл был передан в город А по каналу связи за 120 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 3 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 4 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? Город А До После к* ∂* i *t k * ( ∂ /1,5) * 3i*t ( в 2 раза больше) 120 сек. = > 240 сек. в город Б – в 4 раза быстрее = > 240/4=60 сек.

Слайд 1

Кодирование данных, комбинаторика, системы счисления. 8 вопрос

Слайд 2

21. Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. Правило произведения: общее количество слов равно произведению количества комбинаций каждой отдельной буквы 2*4*4*4 = 128

Слайд 3

from itertools import product k=0 for x in product (‘ ЛТ‘ , ‘ ЛЕТО ‘ , ‘ ЛЕТО ‘ , ‘ ЛЕТО ‘ ) : c= ' '.join(x) k = k + 1 print (k) Итератор перебора значений декартово произведение (все возможные слова заданной длины, составленные из данного алфавита), « склеить» символы каждого кортежа в строки с помощью метода . join :

Слайд 4

26) Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. from itertools import product k=0 for x in product ('КУМА', repeat=5): c= ' '.join(x) if c[0] in 'КМ' and c[-1] in 'УА': k = k + 1 print (k)

Слайд 5

27) Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? from itertools import product k=0 for x in product ('КРОТ', repeat=6): c= ' '.join(x) if c.count ('О')==1: k = k + 1 print (k)

Слайд 6

Вася составляет 6-буквенные слова, в которых есть только буквы К, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? from itertools import product k=0 for x in product ('КАНТ', repeat=6): c=' '.join(x) if c.count ('К')==2: k = k + 1 print(k)

Слайд 7

Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? От противного: Найдем сколько всего возможных вариантов Найдем кол-во слов без буквы Е Найдем разность: 256 – 81 = 175

Слайд 8

from itertools import product k=0 for x in product ('ЛЕТО', repeat=4): c=' '.join(x) if c.count ('Е')>=1: k = k + 1 print(k)

Слайд 9

Петя составляет 7-ми буквенные слова перестановкой букв АССАСИН сколько всего различных слов может составить Петя? n ! – число перестановок из n элементов Так как перестановка одинаковых букв не даёт нового слова, каждая пара уменьшает количество уникальных слов в 2! раза; а 3 одинаковые буквы в 3! и т.д. В задаче перестановка 7 букв, в котором 2 буквы А и 3 буквы С. Общее количество слов получаемых в результате перестановки равно 7! = 5040 Т.к 2 буквы А, то число перестановок уменьшится в 2!=2 Т.к. 3 буквы С, то число перестановок еще уменьшится в 3!=6 => 5040:12= 420

Слайд 10

from itertools import permutations k=0 for x in set (permutations (' АССАСИН')): c=' '.join(x) k = k + 1 print(k) Перестановки Это множество, в котором хранятся только уникальные данные, используем, когда есть одинаковые элементы

Слайд 11

Демо 2023 Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых только одна цифра 6, при этом никакая нечётная цифра не стоит рядом с цифрой 6. Ответ: ___________________________. from itertools import * k=0 for x in product('01234567', repeat=5): s=''.join (x) if s.count ('6')==1 and s[0]!='0' and '16' not in s and '61' not in s and '36' not in s and '63' not in s and '56' not in s and '65' not in s and '76' not in s and '67' not in s: k=k+1 print (k)

Слайд 12

Вася составляет 5-буквенные коды из букв К, А, Л, И, Й. каждую букву нужно использовать ровно 1 раз при этом код не может начинаться с буквы Й и не может содержать сочетание ИА. Сколько разных кодов может составить Вася? from itertools import permutations k=0 for x in permutations ('КАЛИЙ'): c= ''.join(x) if c[0]!='Й' and 'ИА' not in c: k = k + 1 print (k)

Слайд 13

Сколько существует десятичных четырехзначных чисел, в которых все цифры различны и никакие две четные или две нечетные цифры не стоят рядом?

Слайд 14

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1 ААААА 2 ААААО 3 ААААУ 4 АААОА …… Запишите слово, которое стоит на 101-м месте от начала списка. Т.к. на первом месте стоит число 0, на втором – 1 и т.д . Тогда на 101 месте стоит слово с порядковым номером 101-1, записанное в троичной системе счисления. 100 = 10201 3 А – 0, О – 1, У – 2 Запишем соответствующие буквы в получившемся коде: 10201 3 ОАУАО from itertools import product k=0 for x in product ('АОУ', repeat=5): k = k + 1 c= ' '.join(x) if k==101: print (c)

Слайд 15

Демо - 22 Л – 1, Е – 0, М – 2, У – 4, Р – 3 пятеричная система счисления. Первое слово на Л: ЛЕЕЕ с кодом 1000 5 Переведём в 10-ую систему счисления 1000 5 = 125 – номер ЛЕЕЕ, находящееся на 125+1 = 126 месте from itertools import product k = 0 for x in product ('ЕЛМРУ', repeat=4): k=k+1 s=''.join(x) if s=='ЛЕЕЕ': print (k, s)

Слайд 1

Кодирование данных, комбинаторика, системы счисления. 8 вопрос

Слайд 2

21. Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. Правило произведения: общее количество слов равно произведению количества комбинаций каждой отдельной буквы 2*4*4*4 = 128

Слайд 3

from itertools import product k=0 for x in product (‘ ЛТ‘ , ‘ ЛЕТО ‘ , ‘ ЛЕТО ‘ , ‘ ЛЕТО ‘ ) : c= ' '.join(x) k = k + 1 print (k) Итератор перебора значений декартово произведение (все возможные слова заданной длины, составленные из данного алфавита), « склеить» символы каждого кортежа в строки с помощью метода . join :

Слайд 4

26) Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. from itertools import product k=0 for x in product ('КУМА', repeat=5): c= ' '.join(x) if c[0] in 'КМ' and c[-1] in 'УА': k = k + 1 print (k)

Слайд 5

27) Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? from itertools import product k=0 for x in product ('КРОТ', repeat=6): c= ' '.join(x) if c.count ('О')==1: k = k + 1 print (k)

Слайд 6

Вася составляет 6-буквенные слова, в которых есть только буквы К, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? from itertools import product k=0 for x in product ('КАНТ', repeat=6): c=' '.join(x) if c.count ('К')==2: k = k + 1 print(k)

Слайд 7

Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася? От противного: Найдем сколько всего возможных вариантов Найдем кол-во слов без буквы Е Найдем разность: 256 – 81 = 175

Слайд 8

from itertools import product k=0 for x in product ('ЛЕТО', repeat=4): c=' '.join(x) if c.count ('Е')>=1: k = k + 1 print(k)

Слайд 9

Петя составляет 7-ми буквенные слова перестановкой букв АССАСИН сколько всего различных слов может составить Петя? n ! – число перестановок из n элементов Так как перестановка одинаковых букв не даёт нового слова, каждая пара уменьшает количество уникальных слов в 2! раза; а 3 одинаковые буквы в 3! и т.д. В задаче перестановка 7 букв, в котором 2 буквы А и 3 буквы С. Общее количество слов получаемых в результате перестановки равно 7! = 5040 Т.к 2 буквы А, то число перестановок уменьшится в 2!=2 Т.к. 3 буквы С, то число перестановок еще уменьшится в 3!=6 => 5040:12= 420

Слайд 10

from itertools import permutations k=0 for x in set (permutations (' АССАСИН')): c=' '.join(x) k = k + 1 print(k) Перестановки Это множество, в котором хранятся только уникальные данные, используем, когда есть одинаковые элементы

Слайд 11

Демо 2023 Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых только одна цифра 6, при этом никакая нечётная цифра не стоит рядом с цифрой 6. Ответ: ___________________________. from itertools import * k=0 for x in product('01234567', repeat=5): s=''.join (x) if s.count ('6')==1 and s[0]!='0' and '16' not in s and '61' not in s and '36' not in s and '63' not in s and '56' not in s and '65' not in s and '76' not in s and '67' not in s: k=k+1 print (k)

Слайд 12

Вася составляет 5-буквенные коды из букв К, А, Л, И, Й. каждую букву нужно использовать ровно 1 раз при этом код не может начинаться с буквы Й и не может содержать сочетание ИА. Сколько разных кодов может составить Вася? from itertools import permutations k=0 for x in permutations ('КАЛИЙ'): c= ''.join(x) if c[0]!='Й' and 'ИА' not in c: k = k + 1 print (k)

Слайд 13

Сколько существует десятичных четырехзначных чисел, в которых все цифры различны и никакие две четные или две нечетные цифры не стоят рядом?

Слайд 14

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1 ААААА 2 ААААО 3 ААААУ 4 АААОА …… Запишите слово, которое стоит на 101-м месте от начала списка. Т.к. на первом месте стоит число 0, на втором – 1 и т.д . Тогда на 101 месте стоит слово с порядковым номером 101-1, записанное в троичной системе счисления. 100 = 10201 3 А – 0, О – 1, У – 2 Запишем соответствующие буквы в получившемся коде: 10201 3 ОАУАО from itertools import product k=0 for x in product ('АОУ', repeat=5): k = k + 1 c= ' '.join(x) if k==101: print (c)

Слайд 15

Демо - 22 Л – 1, Е – 0, М – 2, У – 4, Р – 3 пятеричная система счисления. Первое слово на Л: ЛЕЕЕ с кодом 1000 5 Переведём в 10-ую систему счисления 1000 5 = 125 – номер ЛЕЕЕ, находящееся на 125+1 = 126 месте from itertools import product k = 0 for x in product ('ЕЛМРУ', repeat=4): k=k+1 s=''.join(x) if s=='ЛЕЕЕ': print (k, s)

Слайд 1

Выполнение алгоритмов для исполнителя

Слайд 2

Что проверяется: Умение анализировать результат исполнения алгоритма. Что нужно знать : правила выполнения линейных, разветвляющихся и циклических алгоритмов основные операции с символьными строками (определение длины, выделение подстроки , удаление и вставка символов, «сцепка» двух строк в одну ) исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – « конец цикла »; все команды между нц и кц – это тело цикла, они выполняются несколько раз запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1

Слайд 3

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w ) - заменяется первое вхождение v на w нашлось (v) Дана программа для исполнителя Редактор: НАЧАЛО while ‘333’ in S or ‘555’ in S ПОКА нашлось (333) ИЛИ нашлось (555) ЕСЛИ нашлось (555 ) - if '555' in s: ТО заменить (555, 3 ) - S= S.replace (‘555’, ‘3’) – замена на строку, где все ИНАЧЕ заменить (333, 5 ) вхождения 555 заменяются на 3 КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 62 идущих подряд цифр 5? В ответе запишите полученную строку . S=‘5’*62 else: s= s.replace ('333', '5', 1)

Слайд 4

s='5'*62 while '333' in s or '555' in s: if '555' in s: s= s.replace ('555', '3', 1) else: s= s.replace ('333', '5', 1) print (s ) 5355

Слайд 5

167) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) нашлось (v) Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (63) ИЛИ нашлось (664) ИЛИ нашлось (6665) ЕСЛИ нашлось (63) ТО заменить (63, 4) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (664) ТО заменить (664, 5) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (6665) ТО заменить (6665, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой выше программы к строке, в которой первая и последняя цифры – 3, а между ними стоит 120 цифр 6? В ответе запишите полученную строку.

Слайд 6

s='3'+'6'*120+'3' while '63' in s or '664' in s or '6665' in s: if '63' in s: s= s.replace ('63', '4', 1) if '664' in s: s= s.replace ('664', '5', 1) if '6665' in s: s= s.replace ('6665', '3', 1) print (s ) 33

Слайд 7

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) нашлось (v) Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось ( 555 ) ИЛИ нашлось ( 333 ) ЕСЛИ нашлось ( 555 ) ТО заменить ( 555 , 3 ) ИНАЧЕ заменить (333, 5 ) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Дана строка, состоящая из 200 цифр 5. чему равна сумма цифр строки , полученной после обработки по этой программе? s='5'*200 while '555' in s or '333' in s: if '555' in s: s= s.replace ('555', '3', 1) else: s= s.replace ('333', '5', 1) print (sum ([ int ( n )for n in s]))

Слайд 8

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) нашлось (v) Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось ( >1 ) ИЛИ нашлось ( >2 ) ИЛИ нашлось ( >3 ) ЕСЛИ нашлось ( >1 ) ТО заменить ( >1 , 22> ) КОНЕЦ ЕСЛИ ЕСЛИ нашлось ( >2 ) ТО заменить ( >2. 2>1 ) КОНЕЦ ЕСЛИ ЕСЛИ нашлось ( >3 ) ТО заменить ( > 3 . 1>2 ) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход приведенной ниже программе поступает строка, начинающаяся с символа « > », а затем содержащая 20 цифр 1, 15 цифр 2 и 40 цифр 3, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы. s='>'+20*'1'+ 15*'2' + 40* '3' while '>1' in s or '>2' in s or '>3' in s: if '>1' in s: s= s.replace ('>1', '22>', 1) if '>2' in s: s= s.replace ('>2', '2>1', 1) if '>3' in s: s= s.replace ('>3', '1>2', 1) print (sum ([ int (n)for n in s if n!='>']))

Слайд 9

213) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. К исходной строке, содержащей более 80 единиц и не содержащей других символов, применили приведённую ниже программу. НАЧАЛО ПОКА нашлось (111) заменить (111, 2) заменить (222, 1) КОНЕЦ ПОКА КОНЕЦ В результате получилась строка 21 Какое наименьшее количество единиц могло быть в исходной строке ?

Слайд 10

for i in range (81,100 ): - содержащей более 80 единиц s='1'* i while '111' in s: s= s.replace ('111', '2', 1) s= s.replace ('222', '1',1) if s=='21 ': - Проверяем наличие результата ’ 21 ’ print ( i ) – выводим номер i , при котором результат = ’ 21 ’ Находим минимальное значение 84 C одержащей не более 100 единиц и не содержащей других символов : for i in range ( 1 ,101): В результате получилась строка 321 Сколько различных значений количества единиц может быть в исходной строке?

Слайд 11

231) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для Редактора: НАЧАЛО ПОКА нашлось (32) заменить (32, 6) КОНЕЦ ПОКА КОНЕЦ Исходная строка содержит 8 двоек и некоторое количество троек , других цифр нет, точный порядок расположения двоек и троек неизвестен. После выполнения программы получилась строка с суммой цифр 93 Какое наименьшее количество троек могло быть в исходной строке?

Слайд 12

s= '3333333333333333232323232323232‘ - анализируем строчку, чтобы выполнялось условие (мин. ч исло 3) while '32' in s: s= s.replace ('32', '6', 1) print (sum( int (c) for c in s )) – находит сумму цифр последовательности ИЛИ print (3* s.count ('3')+2* s.count ('2')+6* s.count ('6'))

Слайд 13

(№ 6113) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (91) ИЛИ нашлось (92) ЕСЛИ нашлось (91) ТО заменить (91, 39) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (92) ТО заменить (92, 59) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход приведённой выше программе поступает строка, начинающаяся с цифры «9», а затем содержащая n цифр «1» и n цифр «2», расположенных в произвольном порядке. Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым трехзначным числом.

Слайд 14

def pr (x): for d in range (2, round (x**0.5) + 1): if x%d ==0: return False return True for n in range (1, 100): s='9'+n*'1'+ n*'2' while '91' in s or '92' in s: if '91' in s: s= s.replace ('91', '39', 1) if '92' in s: s= s.replace ('92', '59', 1) summa = (sum ([ int (n)for n in s])) if pr (summa) and summa in range (100, 1000): print (n) Создаем функцию, проверяющую является ли число простым Проверяем, что сумма трехзначное число

Слайд 15

( № 6414) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА НЕ нашлось (00) заменить (02, 101) заменить (11, 2) заменить (012, 30) заменить (010, 00) КОНЕЦ ПОКА КОНЕЦ Известно, что исходная строка содержала ровно два нуля – на первом и на последнем месте, 100 единиц, больше 50 двоек и не содержала других цифр. После выполнения программы получилась строка, сумма цифр которой оказалась простым числом. Какое наименьшее количество двоек могло быть в исходной строке? О твет: 56

Слайд 16

(№ 6236) (PRO100 ЕГЭ) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0) ЕСЛИ нашлось (>1) ТО заменить (>1, 22>) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (>2) ТО заменить (>2, 2>) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (>0) ТО заменить (>0, 1>) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход приведённой выше программы поступает строка, начинающаяся с символа «>», а затем содержащая 12 цифр «0», n цифр «1» и 8 цифр «2», расположенных в произвольном порядке. Определите значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, равна 68. Ответ: 10