Элективный курс по информатике для 11 класса "Изучение языков программирования"

РАБОЧАЯ ПРОГРАММА ЭЛЕКТИВНОГО КУРСА

«Изучение программирования»

ПРОФИЛЬ: «Универсальный»

11 класс

СОСТАВИТЕЛЬ ШИШКИНА СВЕТЛАНА СЕРГЕЕВНА

Новосибирск 2025

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Место элективного курса в структуре образовательной программы

Элективный курс «Изучение программирования» выбирается учениками из возможных предоставляемых курсов, и он входит в часть, формируемую участниками образовательных отношений. К исходным требованиям, необходимым для изучения дисциплины «Изучение программирования», относятся знания, умения и виды деятельности, сформированные в процессе изучения информатики в средней общеобразовательной школе. В системе школьного образования дисциплина «Изучение программирования» занимает место в качестве элективного курса дополнительного образования являясь не только объектом изучения, но и средством обучения. Как средство познания действительности информатика обеспечивает развитие интеллектуальных и творческих способностей ребенка, развивает его абстрактное мышление, аналитическое мышление, память и воображение, формирует навыки самостоятельной учебной деятельности, самообразования и самореализации личности. Будучи формой хранения и усвоения различных знаний, информатика неразрывно связана со всеми школьными предметами и влияет на качество усвоения всех других школьных предметов, а в перспективе способствует овладению будущей профессией.

Цель реализации элективного курса:

Учебная программа курса составлена в условиях реализации ФГОС СОО, определяющим требования и содержащим рекомендации по обучению Информатике и ИКТ в старшей школе, основанном на использовании личностно-ориентированных методик, которые вносят существенный вклад в достижение личностных и метапредметных результатов, способствуют формированию профессиональных качеств обучающихся.

Основная цель курса – развитие практических навыков владения языка программирования и применять полученные знания на практике.

Задачи:

1. Обучающие – систематизировать и углубить знания в области информатики и программировании, полученные на ступени основного общего образования.

2. Развивающие – развитие умения применять теоретические знания на практике, знания и навыки работы с информационными технологиями, позволяющие использовать их при изучении других предметов.

3. Воспитывающие – воспитание стремления к самостоятельной работе по приобретению знаний и умений в различных областях жизни, интереса к предмету, заложить основу для дальнейшего профессионального обучения.

4. Практические – приобрести основы языков программирования, их основных аспектов использования и взаимодействия между собой.

ПЛАНИРУЕМЫЕ РЕЗУЛЬТАТЫ ОСВОЕНИЯ ЭЛЕКТИВНОГО КУРСА «Изучение программирования»

Личностными результатами освоения выпускниками средней школы курса являются:

бережное отношение к компьютерной технике как неотъемлемой части настоящего времени как основного помощника в быту;

потребность сохранять чистоту рабочего места и техники;

осознание применимости информационных технологий в народном хозяйстве и социально-экономической структуре;

осознание роли информационной технологии как главного атрибута XXI века;

сформированность мировоззрения, соответствующего современному уровню развития информационных технологий;

потребность саморазвития, в том числе логического мышления, понимание алгоритмов в информационных процессах;

готовность к самостоятельной творческой и ответственной

деятельности;

готовность и способность вести диалог с другими людьми; сформированность навыков сотрудничества;

эстетическое отношение к языкам программирования, осознание их

выразительных возможностей;

нравственное сознание и поведение на основе общечеловеческих ценностей.

Метапредметными результатами освоения выпускниками средней школы курса являются:

умениеэффективнообщатьсявпроцессесовместнойдеятельностисовсемиеё участниками, не допускать конфликтов;

владение навыками познавательной, учебно-исследовательской и проектной деятельности; использование различных методов познания; владение логическими операциям и анализа, синтеза, сравнения;

способность к самостоятельному поиску информации, в том числе умение пользоваться справками программ и интернет поиском;

умение критически оценивать и интерпретировать информацию, получаемую из различных источников;

владение всеми видами компьютерной деятельности: машинописью, чтением и редактированием;

умение правильно построить алгоритм и создавать программы разных типов и применимости с учётом языков программирования и их особенностей Turbo Pascal и Python;

свободное владение письменной формой записи программ, циклом и структурой;

умение определять цели деятельности и планировать её, контролировать и корректировать деятельность;

умение оценивать свою и чужую работу с эстетических и нравственных

позиций;

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

Предметные результаты

В результате изучения элективного курса «Информационные технологии» на уровне среднего общего образования:

Выпускник научится:

определять результат выполнения алгоритма при заданных исходных данных; узнавать изученные алгоритмы обработки чисел и числовых последовательностей; создавать на их основе несложные программы анализа данных; читать и понимать несложные программы, написанные на выбранном для изучения универсальном алгоритмическом языке высокого уровня;

выполнять пошагово (с использованием компьютера или вручную) несложные алгоритмыуправленияисполнителямиианализачисловыхитекстовыхданных;

создавать на алгоритмическом языке программы для решения типовых задач базового уровня из различных предметных областей с использованием основных алгоритмических конструкций;

использовать готовые прикладные компьютерные программы в соответствии с типом решаемых задачи по выбранной специализации;

использовать компьютерно-математические модели для анализа соответствующих объектов и процессов, в том числе оценивать числовые параметры моделируемых объектов и процессов, а также интерпретировать результаты, получаемые в ходе моделирования реальных процессов; представлять результаты математического моделирования в наглядном виде, готовить полученные данные для публикации; - правильно составлять текстовые документы в соответствии с эстетическими нормами и оптимальным количеством необходимого текста; -

работать с таблицами, обрабатывать большие массивы данных и проводить математические операции больших объемов;

разрабатывать программы, составляя этапы решения задач и проектирования их каркаса и подпрограмм;

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

Выпускник получит возможность научиться:

понимать важность дискретизации данных; использовать знания о постановках задач поиска и сортировки; их роли при решении задач анализа данных;

использовать навыки и опыт разработки программ в выбранной среде программирования, включая тестирование и отладку программ; использовать основные управляющие конструкции последовательного программирования и библиотеки прикладных программ; выполнять созданные программы;

разрабатывать и использовать компьютерно-математические модели; оценивать числовые параметры моделируемых объектов и процессов; интерпретировать результаты, получаемые в ходе моделирования реальных процессов; анализировать готовые модели на предмет соответствия реальному объекту или процессу;

применять базы данных и справочные системы при решении задач, возникающих в ходе учебной деятельности и вне ее; создавать учебные многотабличные базы данных;

критически оценивать информацию, полученную из сети Интернет.

Требования к уровню подготовки поступающего на обучение: иметь основные знания по информатики за курс средней школы (5-9 классы).

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Срок обучения: год.

Режим занятий: 2 часа в неделю.

Формы обучения: очная, с применением дистанционной формы обучения.

Общая трудоемкость: 68 часов.

Форма итогового контроля: проект.

ПЕРЕЧЕНЬ УЧЕБНО-МЕТОДИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования: учебник для сред. проф. образования. – М.: Издательский центр «Академия», 2010.

Васильев, А. Н. Python на примерах. Практический курс по программированию. – СПб. : Наука и Техника, 2016. – 432 с.Страуструп Б. Язык программирования Turbo Pascal (третье издание). – Спб., М.: "Невскийдиалект. Издательство "Бином", 2010.

Эпштейн М.С. Практикум по программированию: учебное пособие для сред. проф. образования. – М.: Издательский центр «Академия», 2009.

Лесневский А.С. Объектно-ориентированное программирование для начинающих. – М.: Бином. Лаборатория знаний, 2009. Интернет-ресурсы:

Компьютерные видео уроки. Форма доступа: http://compteacher.ru/programming/delphi

Книги по программированию. Форма доступа: http://delphiz.ru/books.html

Программирование на Visual Basic. Форма доступа: http://vbnet.ru/articles/showarticle.aspx?id=99

Самоучитель Visual Basic 6.0. Форма доступа: http://vbzero.narod.ru/

Visual Basic .NET – Мультимедийный Обучающий Курс. Форма доступа: http://gratisfile.com/publ/140-1-0-13

ДИДАКТИЧЕСКИЕ МАТЕРИАЛЫ (ФОС)

(практические задания для закрепления учебного материала, задания для итогового контроля)

Тема 1. Введение. Основные цели и задачи курса.

Задание: найти информацию о профессиях, связанные с программированием.

Тема 2. Основные понятия алгоритмизации.

Проведение занятия с помощью платформы ЯКласс.

Составление линейных алгоритмов

Сегодня мы попрактикуемся в составлении алгоритмов. Это очень важные навыки. Мы уже неоднократно отмечали, что составить алгоритм, то есть объяснить другому, как выполнять те или иные задачи так, чтобы это было понятно каждому, - очень тяжело. Наша задача – научиться составлять алгоритмы для различных примеров, чтобы впоследствии, когда вы столкнётесь с необходимостью составлять алгоритмы для написания различных программ, это не составляло для вас особого труда.

Начнём мы с самых простых алгоритмов – линейных. Их составление, обычно, не вызывает особого труда. Однако, навыки составления таких алгоритмов чрезвычайно важны.

Пример 1. Составить алгоритм запуска программы Paint.

Решение:

Данный алгоритм в виде блок-схемы имеет следующий вид:

 

Составление алгоритмов с ветвлениями

Рассмотрим пример на составление алгоритмов с ветвлениями.

 Пример 2. Составьте алгоритм для перехода дороги на светофоре.

Решение:

Возможны следующие ситуации: в тот момент, когда мы подошли к дороге горел красный или зелёный свет. Если горел зелёный свет, то можно переходить дорогу. Если же горел красный свет, то необходимо дождаться зелёного – и уже тогда переходить дорогу.

Таким образом, алгоритм имеет следующий вид:

Подойти к светофору.

Посмотреть на его свет.

Если горит зелёный, то перейти дорогу.

Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.

Блок-схема данного алгоритма имеет вид:

Составление циклических алгоритмов

Рассмотрим пример на составление циклического алгоритма. Мы уже несколько раз обсуждали перевод чисел из десятичной системы в двоичную. Теперь пришло время чётко сформулировать этот алгоритм.

Напомним, что его принцип состоит в делении числа на 2 и записей остатков, получающихся при делении.

Пример 3. Составить алгоритм перевода чисел из десятичной системы в двоичную.

Решение:

То есть, алгоритм будет выглядеть так:

Если число равно 0 или 1, то это и будет его двоичное представление.

Если число больше 1, то мы делим его на 2.

Полученный остаток от деления записываем в последний разряд двоичного представления числа.

Если полученное частное равно 1, то его дописываем в первый разряд двоичного представления числа и прекращаем вычисления.

Если же полученное частное больше 1, то мы заменяем исходное число на него и возвращаемся в пункт 2).

Блок-схема этого алгоритма выглядит следующим образом:

Примечание: подумайте, можно ли как-то упростить приведенную блок-схему.

«Чтение» алгоритмов

Пример 4. По заданной блок-схеме выполнить действия алгоритма для числа 23.

Решение:

a=23

23+5=28

28<35

28+5=33

33<35

33+5=38

38>35

76 – двузначное число

76-50=26.

Ответ: 26.

Индивидуальные задания к работе:

1. Найти результат работы алгоритма:

Входные данные по вариантам

При заданном Х условие выполнется? Написать результат вычисления и ответ попадаем в условие или нет.

Входные данные по вариантам

Написать результат выполнения алгоритма с указанными входными данными

Входные данные по вариантам

Написать результат выполнения алгоритма с указанными входными данными

Построить блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Построить блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Построить блок схему к задаче(по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Построить блок схему к задаче (по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Построить блок схему к задаче (по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Построить блок схему к задаче (по вариантам). Указать тип алгоритма, что дано и что нужно найти.

Тестовое задание через платформу OnlainTest Pad.

Тестирование учащихся:

Тема 3. Обзор языков программирования

Тема 4. Программирование на алгоритмическом языке Паскаль.

Паскаль – язык, который изучается преимущественно в школьной программе. Он позволяет ознакомиться с алгоритмами, а также разобраться с основами разработки ПО. Здесь выделяют несколько алгоритм-типов:

линейный алгоритм;

разветвленный;

циклический.

Каждый вариант подразумевает свои собственные особенности. Далее они будут рассмотрены более подробно. Предложенные концепции подходят не только для Паскаль, но и для других языков разработки.

Линейный

Это инструкции, в которых команды будут выполняться последовательно друг за другом. Самые простые. На них базируются не только элементарные программы, но и сложные проекты. Линейные последовательности с легкостью осваиваются новичками.

Вот пример в Паскаль, который помогает разобраться в принципах реализации рассматриваемого метода. В нем нужно найти объем куба и площадь его поверхности, если длина ребра равна a:

А вот – пример программы, которая вычисляет сумму двух чисел. После расчетов она выведет получившийся результат непосредственно на экран устройства:

Это – база, без которой не получится разобраться с остальными видами «последовательностей» при формировании кода приложения.

Разветвленный

В них ход решения зависит непосредственно от выполнения или невыполнения заданного условия. В приложении реализация сводится к принципу выбора действия в зависимости от ответа «да» или «нет».

Выше – пример блок-схемы, наглядно демонстрирующий соответствующий вариант. Разобраться с соответствующей последовательностью тоже не составляет особого труда.

Циклический

Алгоритм программы в Паскале или другом ЯП, в котором определенная часть вычислений производится многократно. Простыми словами – цикл. В нем имеется итоговое количество повторений.

Факториал

Отдельно стоит изучить несколько «базовых» алгоритмов, которые используются в Pascal, но не относятся к ранее перечисленным типам. Первый вариант – факториал натурального числа. Его можно назвать линейным. Связано это с определением самого факториала – произведение натуральных чисел от 1 до самого заданного числа.

Наглядный пример реализации в программном коде Pascal. Его можно использовать в качестве шаблона для решения характерных задач.

Работа на сайте Российская Электронная школа (РЭШ).

Выполнение тестовых работ на сайте РЭШ.

Выполнение творческих заданий.

Решение типовых задач.

Задание. Составить презентацию в группах по одному из вопроса:

Суть объектно-ориентированного программирования

Принципы ООП

Структура объектно-ориентированного программирования

Плюсы и минусы объектно-ориентированного программирования

Языки в ООП

Задание 2. Выполнение практических работ.

Решение задач:

Задача:(Ветвление)

Даны координаты центров двух окружностей (х1,у1) и (х2,у2), а также их радиусы R1 и R2 (R1>R2). Определить взаимное расположение окружностей.

расстояние от точки до точки

Program fffff;

var x1,x2,y1,y2,r1,r2,d:real;

begin

readln(x1,x2,y1,y2,r1,r2);

d:=sqrt(sqr(x1-x2)+sqr(y1-y2));

if d=r1+r2 then write('касаются') else

if d>r1+r2 then write('не касаются') else write('пересекаются');

readln;

end.

Задача: (Символьные величины)

Составить программу, которая определяет количество букв «а» в заданном тексте

program fff;

var a,b:string;

i,n,k:integer;

begin

readln(a);

n:=length(a);

for i:=1 to n do

begin

if a[i]='а' then k:=k+1;

end;

writeln('в слове ',a,' буква А встречается ',k,' раз');

readln;

end.

Задача: (Символьные величины)

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

program fff;

var a,b:string;

i,n,k:integer;

begin

readln(a);

n:=length(a);

for i:=1 to n do

begin

if a[i]=' ' then k:=k+1;

end;

writeln('в тексте: ',a,', количество слов= ',k);

readln;

end.

Задача: ( Массив)

Дан массив А(6). Нужно расположить в порядке возрастания элементы массива.

program aaa;

var a: array[1..6] of real;

k,i,j,:integer;

min:real;

begin

writeln('введи шесть элементов массива');

for k:=1 to 6 do readln(a[k]);

writeln('элементы массива по возрастанию');

for k:=1 to 6 do

begin

i:=k;

for j:=k+1 to 6 do if a[j]<a[i] then i:=j;

min:=a[k];

a[k]:=a[i]; a[i]:=min; write(a[k]:5:0);

end;

readln;

end.

Задача: ( Массив)

С клавиатуры вводятся N числа. Составьте программу, которая определяет количество положительных, отрицательных чисел и нулей среди введённых чисел. Значение N вводится с клавиатуры.

Program aaa;

var i,n: integer;

s,c,k: real;

M:array[1..n1] of real;

begin

writeln('введи число элементов<= 100');

readln(n);

writeln('введи элементы');

for i:=1 to n do read(M[i]);

s:=0; c:=0; k:=0;

for i:=1 to n do

begin

if M[i]<0 then s:=s+1 else

if M[i]>0 then c:=c+1 else k:=k+1;

end;

writeln('колличество положительных чисел = ',c:2:0);

writeln('колличество отрицательных чисел = ',s:2:0);

writeln('колличество нулей = ',k:2:0);

readln;

readln;

end.

Задача: (Массив с символьными переменными)

Составить массив из пяти фамилий, и вывести на экран столбиком, начиная с последней.

program fff;

var v:array[1..5] of string;

i:integer;

begin

writeln('введи пять фамилий');

for i:=1 to 5 do readln(v[i]);

writeln(' фамилии наоборот:');

for i:=5 downto 1 do writeln(v[i]);

readln;

end.

Задача: ( Массив с символьными переменными)

Составить массив из пяти фамилий, и вывести на экран те из них, которые начинаются с определённой буквы, которая вводиться с клавиатуры.

Длину строки можно указать в разделе описания переменных:

<имя переменной, …>:string[n]

program fff;

var v:array[1..5] of string;

k:string[1];

i:integer;

begin

writeln('введи букву, с которой будет начинаться фамилия');

readln(k);

writeln('введи пять фамилий');

for i:=1 to 5 do readln(v[i]);

writeln('интересующие Вас фамилии:');

for i:=1 to 5 do

if (v[i])[1]=k then writeln(v[i]);

readln;

end.

Задача: ( Массив с символьными переменными)

Из вводимого с клавиатуры слова вырезать каждую третью букву.

program aa;

var a:string;

k,x: integer;

begin

readln(a);

k:=length(a);

x:=3;

while x<=k do

begin

a[x]:=' ';

x:=x+3;

end;

writeln(a);

readln;

end.

Задача: ( Массив с символьными переменными)

В вводимом слове с клавиатуры заменить все буквы «а» на букву «о».

program aa;

var a:string;

k,x: integer;

begin

readln(a);

k:=length(a);

for x:=1 to k do

if a[x]='а' then a[x]:='о';

writeln(a);

readln;

end.

Задача: ( Массив с символьными переменными)

Заданны фамилия, имя, отчество учащегося, разделённые пробелами. Напишите программу, печатающую фамилии ученика и его инициалы.

program aaa;

uses crt;

var d,r:string;

k,i:integer;

begin

clrscr;

writeln('введи Ф.И.О.');

readln(d);

k:=length(d);

for i:=1 to k do

begin

if d[i]=' ' then d:=copy(d,1,i)+d[i+1]+'.';

end;

writeln(d);

readln;

end.

Задача: ( Цикл)

Найти сумму чисел от 100 до 200 кратные 17 и вывести их.

PROGRAM Ret2;

VAR i: integer; s:real;

Begin

s:=0;

For i:=100 to 200 do

Begin

If i mod 17=0 then

begin

Writeln(i);

s:=s+i;

End;

End;

Writeln('сумма чисел=',s:5:0);

readln;

End.

Задача: ( Массив)

Ввести с клавиатуры 10 чисел. Если квадрат чисел меньше 100, напечатать порядковый номер, число и его квадрат.

program Svetlana;

var A: array [1..10] of real;

i: integer;

begin

for i:=1 to 10 do readln (A[i]);

writeln ('число и его квадрат');

for i:=1 to 10 do

begin

if A[i]*A[i]<100 then

begin

writeln ('A[',i,']=', A[i]:2:1);

writeln (A[i]*A[i]:5:1);

end;

end;

readln;

end.

З адачи для школьной олимпиады среднего звена

Заданы два целых числа А и В. Найдите сумму чётных чисел от А до В.

Определить, является ли строка палиндромом.

3) Даётся последовательность из N чисел. Найдите количество различных чисел.

Тема 5. Программирование на языке Python.

Введение в алгоритмы и структуры данных

Алгоритмы и структуры данных являются основополагающими концепциями в программировании. Они позволяют эффективно решать задачи, управлять данными и оптимизировать производительность программ. В этой статье мы рассмотрим основные структуры данных и алгоритмы, используемые в Python, и приведем примеры их реализации.

Алгоритмы — это пошаговые инструкции для выполнения задач. Они могут быть простыми, как сортировка списка чисел, или сложными, как алгоритмы машинного обучения. Структуры данных, с другой стороны, представляют собой способы организации и хранения данных, чтобы они могли быть эффективно использованы. Понимание этих концепций критически важно для написания эффективного и оптимизированного кода.

Основные структуры данных в Python

Списки

Списки в Python — это упорядоченные коллекции элементов, которые могут содержать данные любого типа. Они аналогичны массивам в других языках программирования, но обладают большей гибкостью. Списки позволяют добавлять, удалять и изменять элементы, что делает их очень удобными для работы с динамическими данными.

Python

# Пример создания списка

my_list = [1, 2, 3, 4, 5]

print(my_list)

# Добавление элемента в список

my_list.append(6)

print(my_list)

# Удаление элемента из списка

my_list.remove(3)

print(my_list)

# Доступ к элементу по индексу

print(my_list[2])

Словари

Словари — это неупорядоченные коллекции пар "ключ-значение". Они позволяют быстро находить значение по ключу. Словари особенно полезны, когда нужно хранить данные, связанные с уникальными ключами, такими как имена пользователей и их данные.

Python

# Пример создания словаря

my_dict = {'name': 'Alice', 'age': 25, 'city': 'New York'}

print(my_dict)

# Добавление новой пары ключ-значение

my_dict['email'] = 'alice@example.com'

print(my_dict)

# Удаление пары ключ-значение

del my_dict['age']

print(my_dict)

# Доступ к значению по ключу

print(my_dict['name'])

Множества

Множества — это неупорядоченные коллекции уникальных элементов. Они полезны для выполнения операций над множествами, таких как объединение, пересечение и разность. Множества автоматически удаляют дублирующиеся элементы, что делает их идеальными для задач, связанных с уникальными значениями.

Python

# Пример создания множества

my_set = {1, 2, 3, 4, 5}

print(my_set)

# Добавление элемента в множество

my_set.add(6)

print(my_set)

# Удаление элемента из множества

my_set.remove(3)

print(my_set)

# Проверка наличия элемента в множестве

print(4 in my_set)

Кортежи

Кортежи — это упорядоченные коллекции элементов, которые, в отличие от списков, являются неизменяемыми. Они полезны для хранения данных, которые не должны изменяться в ходе выполнения программы. Кортежи могут быть использованы в качестве ключей в словарях, что невозможно для списков.

Python

# Пример создания кортежа

my_tuple = (1, 2, 3, 4, 5)

print(my_tuple)

# Доступ к элементу по индексу

print(my_tuple[2])

# Попытка изменить элемент (вызовет ошибку)

# my_tuple[2] = 10

Базовые алгоритмы и их реализация

Сортировка пузырьком

Сортировка пузырьком — это простой алгоритм сортировки, который многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Этот алгоритм не является самым эффективным, но он прост в реализации и понимании.

Python

def bubble_sort(arr):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

return arr

# Пример использования

my_list = [64, 34, 25, 12, 22, 11, 90]

sorted_list = bubble_sort(my_list)

print(sorted_list)

Бинарный поиск

Бинарный поиск — это эффективный алгоритм поиска, который работает только с отсортированными списками. Он делит список пополам и сравнивает средний элемент с искомым значением. Если средний элемент не является искомым, алгоритм повторяет процесс с одной из половин списка.

Python

def binary_search(arr, x):

low = 0

high = len(arr) – 1

mid = 0

while low <= high:

mid = (high + low) // 2

if arr[mid] < x:

low = mid + 1

elif arr[mid] > x:

high = mid – 1

else:

return mid

return -1

# Пример использования

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]

result = binary_search(my_list, 4)

print(f'Элемент найден на индексе {result}')

Программирование линейных алгоритмов

Практические примеры и задачи

Задача 1: Поиск максимального элемента в списке

Поиск максимального элемента в списке — это базовая задача, которая часто встречается в программировании. Она может быть решена с помощью простого перебора всех элементов списка и сравнения их значений.

Python

def find_max(arr):

max_element = arr[0]

for num in arr:

if num > max_element:

max_element = num

return max_element

# Пример использования

my_list = [10, 20, 4, 45, 99]

max_value = find_max(my_list)

print(f'Максимальный элемент: {max_value}')

Задача 2: Проверка на палиндром

Палиндром — это слово или фраза, которые читаются одинаково слева направо и справа налево. Проверка на палиндром может быть выполнена с помощью сравнения строки с её перевёрнутой версией.

Python

def is_palindrome(s):

return s == s[::-1]

# Пример использования

word = "radar"

print(f'Слово "{word}" палиндром? {is_palindrome(word)}')

Задача 3: Реверс строки

Реверс строки — это задача, в которой необходимо изменить порядок символов в строке на обратный. Это может быть полезно в различных приложениях, таких как криптография и обработка текста.

Python

def reverse_string(s):

return s[::-1]

# Пример использования

original_string = "hello"

reversed_string = reverse_string(original_string)

print(f'Оригинальная строка: {original_string}')

print(f'Реверс строки: {reversed_string}')

Задача 4: Сумма элементов списка

Сумма элементов списка — это простая задача, которая часто используется для проверки базовых навыков программирования. Она может быть решена с помощью цикла, который проходит по всем элементам списка и складывает их значения.

Python

def sum_list(arr):

total = 0

for num in arr:

total += num

return total

# Пример использования

my_list = [1, 2, 3, 4, 5]

total_sum = sum_list(my_list)

print(f'Сумма элементов списка: {total_sum}')

Выполнение практической работы:

Прохождение тестов на сайте OnlineTestPad - https://onlinetestpad.com/ru/test/1144997-python-dlya-11-klassa

ИНФОРМАТИКА

Фамилия, имя________________________________________________

Класс _______________ Дата ________________

ЯЗЫКИ ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ КОНСТРУКЦИИ ЯЗЫКА ПРОГРАММИРОВАНИЯ. ТИПЫ ДАННЫХ

Задание 1. Выбери правильный ответ. Язык программирования это:

1) это программный математический язык, предназначенный для записи придуманных программ и их работы

2) это формализованный математический язык, предназначенный для работы программ

3) это формализованный искусственный язык, предназначенный для записи программ

Задание 2. Распредели верно виды языков программирования по признакам:

Задание 3. Подчеркни основные конструкции языка программирования:

ПЕРЕМЕННЫЕ ЦИКЛЫ ЧИСЛА ОПЕРАТОРЫ ДИАГРАММЫ

Задание 4. Восстанови очередность работы переменных для хранения данных:

Задание 5. Выбери ответ верно: собой целые числа без дробной части, например, 5, 100, -25 это:

1) строки (string)

2) числа с плавающей запятой (float)

3) целые числа (int)

Задание 6. Напиши примеры типы данных:

Задание 1. Выбери правильный ответ. Язык программирования это:

3) это формализованный искусственный язык, предназначенный для записи программ

Задание 2. Распредели верно виды языков программирования по признакам:

Задание 3. Подчеркни основные конструкции языка программирования:

ПЕРЕМЕННЫЕ ЦИКЛЫ ОПЕРАТОРЫ

Задание 4. Восстанови очередность работы переменных для хранения данных:

Задание 5. Выбери ответ верно: собой целые числа без дробной части, например, 5, 100, -25 это:

3) целые числа (int)

Задание 6. Напиши примеры типы данных:

Тема 7. Подготовка и сдача проекта.

Решение олимпиадных задач с помощью пройденных языков программирования: Turbo Pascal и Python.

Задача 1: Газон

Перед коттеджем Ивана Ивановича есть газон – его можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы. Однажды владелец купил новую газонокосилку, и в качестве тест-драйва подстриг прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). При этом пучки травы, находящиеся на границе этого прямоугольника, также были подстрижены. После стрижки владелец установил на газоне поливальную установку. Она находится в точке с координатами (x3, y3) и имеет радиус действия r. Таким образом, установка начала поливать все пучки, расстояние, от которых до точки (x3, y3) не превышает r. Напишите программу, которая поможет Ивану Ивановичу определить, сколько пучков травы оказалось и подстрижено, и полито.

Рисунок 1. Пересечение – подстриженные и политые пучки травы

Формат входных данных

В первой строке содержатся четыре целых числа x1, x2, y1, y2 (−100000 ≤ х1 < х2 ≤ 100000, −100000 ≤ y1 < y2 ≤ 100000).

Вторая строка содержит три целых числа x3, y3, r (−100000 ≤ x3, y3 ≤ 100000, 1 ≤ r ≤ 100000.

Формат выходных данных

Целое число (количество подстриженных и политых пучков травы).

Пример ввода:

Решение

Сначала прямые, на которых расположены пучки травы, нужно разделить на группы в зависимости от их положения относительно осей абсцисс и ординат. Затем для каждой группы находим пересечение этих прямых с окружностью − областью, которую орошает поливальная установка. Если такие точки пересечения существуют, подсчитать количество постриженных и политых пучков травы для них можно с помощью простой операции − нахождения целой части числа. После этого все полученные числа складываются, и полученный результат будет ответом на задачу.

Время работы такого решения равно O(r), то есть оно пропорционально радиусу окружности (области полива) и не зависит от количества пучков травы или прямых.

Задача 2: Оптимальная стратегия

Два пирата придумали новую игру: выложили на стол в ряд все пиастры, и договорились, что во время очередного хода игрок может взять 1 монету либо справа, либо слева. Игра заканчивается, когда все монеты разобраны.

Оба пирата стремятся выиграть, и поэтому они будут брать монеты в соответствии с оптимальной стратегией. Разница между жадным алгоритмом и оптимальной стратегией выглядит так:

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

Примеры ввода и вывода:

Решение

Эту задачу можно решить двумя способами.

Способ 1 – рекурсия с мемоизацией

Во время хода у каждого игрока есть две опции:

1. Взять монету Ci слева – тогда оппонент выберет монету Ci+1 или Cj. При этом каждый игрок стремится сделать выбор, который оставить противника с минимальной прибылью, то есть игрок может забрать монету Ci + min(function(i+2, j), function(i+1, j-1) ) где [i+2,j] – диапазон монет, доступных игроку, если противник выберет монету Ci+1, a[i+1,j-1] – монеты, доступные игроку в том случае, если оппонент возьмет монету справа, Cj.

2. Взять монету Cj справа – в этом случае противник выберет либо Ci слева, либо Cj-1 справа. Чтобы оставить противника с минимальной прибылью, игрок возьмет монету, соответствующую условию Cj + min(function(i+1, j-1), function(i, j-2) ), где [i,j-2] – монеты, доступные пользователю, если противник выберет монету справа, а [i+1,j-1] – монеты, доступные при выборе Ci.

Код решения с рекурсией:

def winner_is(coins, n):

memo_dict = {}

def options(i, j):

if i > j or i >= n or j < 0:

return 0

k = (i, j)

if k in memo_dict:

return memo_dict[k]

opt1 = coins[i] + min(options(i + 2, j), options(i + 1, j - 1))

opt2 = coins[j] + min(options(i + 1, j - 1), options(i, j - 2))

memo_dict[k] = max(opt1, opt2)

return memo_dict[k]

return options(0, n - 1)

n = int(input())

coins = list(map(int, input().split()))

result = winner_is(coins, n)

if result > (sum(coins) - result):

print(f'Победил 1-й игрок, сумма выигрыша: {result}')

elif result < (sum(coins) - result):

print(f'Победил 2-й игрок, сумма выигрыша: {result}')

else:

print(f'Ничья: игроки выиграли по {result}')

Способ 2 – динамическое программирование

Алгоритм решения:

Нужно создать матрицу размера n x n.

В цикле рассматриваются элементы i и j на всех возможных позициях. Элементы разделены определенным количеством других элементов – дистанцией. В зависимости от результатов сравнения присваиваем значения переменным x, y, z:

если i+2 <=j, то x равно matrix[i+2][j], в противном случае x = 0;

если i+1 <=j-1, то y = matrix[i+1][j-1] , в противном случае y = 0;

если i <= j-2, то z = matrix[i][j-2] , в противном случае z = 0.

Присваиваем matrix[i][j] максимальное значение из двух выражений – coins[i] + min(x, y) и coins[j] + min(y, z).

Ответ – в matrix[0][n – 1].

Код решения с динамическим программированием:

def winner_is(coins, n):

matrix = [[0 for i in range(n)] for i in range(n)]

for distance in range(n):

for j in range(distance, n):

i = j - distance

x = 0

if i + 2 <= j:

x = matrix[i + 2][j]

y = 0

if i + 1 <= j - 1:

y = matrix[i + 1][j - 1]

z = 0

if i <= j - 2:

z = matrix[i][j - 2]

matrix[i][j] = max(coins[i] + min(x, y), coins[j] + min(y, z))

return matrix[0][n - 1]

n = int(input())

coins = list(map(int, input().split()))

result = winner_is(coins, n)

if result > (sum(coins) - result):

print(f'Победил 1-й игрок, сумма выигрыша: {result}')

elif result < (sum(coins) - result):

print(f'Победил 2-й игрок, сумма выигрыша: {result}')

else:

print(f'Ничья: игроки выиграли по {result}')

Задача 3. Эскалатор

Станция метрополитена оснащена эскалатором. Пусть N человек бегут вниз по эскалатору, причем i-й пробегает одну ступеньку за ti секунд. Техника безопасности на эскалаторе запрещает «обгоны», то есть если человек A в процессе бега догнал человека B, который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B. Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно.

Напишите программу, которая поможет работникам станции рассчитать, когда закончит свой бег по эскалатору каждый бегущий человек.

Формат входных данных

В первой строке программа получает число N (1 ≤ N ≤ 105). В последующих строках перечислены пары чисел ti, wi(1 ≤ ti, wi ≤ 106) – время пробега одной ступени и количество ступеней до конца эскалатора для i-того человека.

Формат выходных данных

Время в секундах, через которое i-й человек сойдет с эскалатора.

Решение

Создаем массив order из индексов [0..n-1] для хранения порядка отсортированных людей.

Вызываем быструю сортировку qs, которая сортирует людей по скорости, записывая индексы отсортированных людей в массив order.

После сортировки для каждого человека вычисляем максимум из его собственного времени выхода и времени выхода предыдущего человека (учитывая, что обгонять нельзя).

В итоге мы получаем время для каждого человека с учетом правил эскалатора:

import random

n = int(input())

times = []

speeds = []

for i in range(n):

a, b = map(int, input().split())

times.append(a)

speeds.append(b)

order = list(range(n))

res = [a * b for a, b in zip(times, speeds)]

def qs(l, r):

if l >= r:

return

i = l

j = r

x = speeds[order[random.randint(l, r-1)]]

while i <= j:

while speeds[order[i]] < x:

i += 1

while speeds[order[j]] > x:

j -= 1

if i <= j:

order[i], order[j] = order[j], order[i]

i += 1

j -= 1

qs(l, j)

qs(i, r)

qs(0, n-1)

for i in range(1, n):

res[order[i]] = max(res[order[i]], res[order[i-1]])

for x in res:

print(x)