Проектная работа "Обработка одномерных массивов в среде КУМИР"

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ГИМНАЗИЯ № 1591»

Научно-исследовательская работа

 «Обработка одномерных массивов в среде КУМИР»

Выполнили:

Ученики 9 класса

Вуколов Егор,

 Куранов Данила

Руководитель работы:

Учитель информатики и ИКТ

О.В.  Яковлева

Москва 2017

Оглавление

1.      Введение. 3

2.      Глава 1. Знакомство с массивами. 4

1.1.       Одномерные и двумерные массивы. Определение. 4

1.2 Алгоритмы сортировки массивов по убыванию или по возрастанию.. 5

1.3 Алгоритм поиска элемента массива по условию.. 6

3. Глава 2.  Основы программирования на языке КУМИР. 8

2.1. Основные принципы построения программ в среде КУМИР. 8

2.2.       Описание переменных. 8

2.3. Основные операторы.. 9

2.4.   Основные алгоритмические структуры. 9

4. Глава 3 Программирование на языке КУМИР. 11

3.1 Примеры решение задач, содержащих массивы на языке. 11

3.2 Трассировка программы для отслеживания значения переменной. 12

5. Глава 4  Исследовательская деятельность. 13

4.1 Разработка рекомендаций по решению заданий содержащих массивы.. 13

4.2 Разбор заданий  № 9,10 ОГЭ, применяя наши рекомендации. 14

4.3  Опрос учеников, применявших наши рекомендации. 21

6.      Выводы.. 22

7.      Заключение. 22

8.      Список использованной литературы.. 23

1.    Введение

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

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

Гипотеза: Предположим, что наши исследования помогут успешно сдавать экзамены

Проблема: Требуется алгоритм решения экзаменационных задач, содержащих одномерные массивы данных

Объект  исследования:  Одномерный массив

Предмет исследования:  Способы обработки одномерных массивов

Цель исследования: разработать рекомендации для решений заданий ОГЭ и написания  программ в среде КУМИР, содержащих массивы.

 Задачи:

Задачи:

1.     Изучить теоретический материал по теме;

2.     Решить типовые задачи на массивы из материалов ОГЭ;

3.     Выработать рекомендации решения таких задач;

4.     Провести тестирование эффективности решения задач, используя наши рекомендации;

5.     Опросить  одноклассников о эффективности наших рекомендаций

Методы исследования:

1)    сбор информации;

2)    систематизация, обобщение;

3)    тестирование,  опрос, выводы.

 Актуальность выбранной темы

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

Практическая часть может использоваться на занятиях по подготовке к ОГЭ, на уроках темы  «Программирование»

2.    Глава 1. Знакомство с массивами.

1.1.       Одномерные и двумерные массивы. Определение.

Массив –совокупность переменных одного типа, объединенных общим именем и различаемых с помощью выражения порядкового типа, называемого индексом. Порядковый тип —тип, для каждого элемента которого однозначно определен следующий и предыдущий элементы. Так, например, для числа 3 однозначно определено следующее число: 4 и предыдущее: 2.

Каждая из этих переменных называется элементом массива. Индекс массива должен принимать столько различных значений, сколько в массиве элементов. Каждому элементу соответствует свое значение индекса.

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

Представим себе одномерные массивы (с одним индексом) как некий список значений, а двумерные массивы (с двумя индексами) как таблицу.

Одномерный массив

Двумерный массив

1.2 Алгоритмы сортировки массивов по убыванию или по возрастанию

Алгоритм "Сортировка выбором". 

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

Алгоритм:

1. Находим минимальный или максимальный элемент в массиве.

2. Меняем местами минимальный (или максимальный) и первый элемент местами.

3. Опять ищем минимальный (или максимальный) элемент в неотсортированной части массива

4. Меняем местами уже второй элемент массива и минимальный (или максимальный)  найденный, потому как первый элемент массива является отсортированной частью.

5. Ищем минимальные (или максимальные) значения и меняем местами элементы, пока массив не будет отсортирован до конца.

Сортировка по возрастанию элементов

1.3 Алгоритм поиска элемента массива по условию

Общий алгоритм поиска в массиве определенного элемента можно представить следующим образом:

 Блок-схема поиска требуемого элемента в массиве

3. Глава 2.  Основы программирования на языке КУМИР.

 2.1. Основные принципы построения программ в среде КУМИР.

Начинается программа с названия

 АЛГ <название  программы как на русском или английском языке>

Главное чтобы оно не начиналось с цифры, было не многословным, и вкратце отражала задачу.

НАЧ (НАЧАЛО)

КОН (КОНЕЦ)  < между ними пишется вся программа>

Сразу после служебного слова НАЧ нужно описать переменные, которые будут использоваться в программе (например цел а).

 2.2.  Описание переменных

Величины, с которыми работает КуМир-программа, подразделяются на несколько типов. В языке КуМир предусмотрены следующие типы величин:

 • цел — принимает целые значения от -2147483647 до 2147483647

 • вещ — принимает вещественные значения между −21023 и 21023

 • лог — принимает значения да или нет (– да=1, нет=0)

• сим — значением может быть любой литеральный символ

• лит — значением может быть строка литеральных символов

 Типы цел и вещ называются числовыми;

 типы сим и лит — текстовыми.

В языке КУМИР используются простые и табличные величины (таблицы). Для таблиц кроме того определена размерность (бывают таблицы размерностей 1 и 2 т. д.). Для каждого измерения определены границы изменения индекса таблицы по этому измерению — два целых числа.

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

Пример: цел j, k, n

Для описания таблиц после описания типа нужно указать ключевое слово таб (слитно или раздельно с ключевым словом типа). Размерность таблицы и границы изменения индексов указываются после имени каждой величины.

 Примеры: цел таб k[-5:5]

Здесь k — линейная таблица, состоящая из 11 элементов целого типа. Индексы элементов принимают значения от -5 до 5.

вещтаб tab[1:4, 1:12]   

 Таблица tab — прямоугольная. В ней 48 элементов — 4 строки и 12 столбцов.

2.3. Основные операторы

Оператор присваивания

Знак := - это знак присваивания, т.е. в ячейку памяти с  определенным именем помещается определенное значение или результат вычисления выражения.

Команда  вывода  на экран текст или значение переменной.

вывод “ привет мир !”

вывод с

Команда вводит  с клавиатуры значение переменной и помещает в указанную ячейку  памяти

Ввод с

       2.4.   Основные алгоритмические структуры.

Линейный алгоритм – все команды выполняются друг за другом

Блок-схема линейной части алгоритма

Алг квадрат

нач

вещ к, х

ввод х

к := х*х

вывод к

кон

Разветвляющие алгоритмы – после проверки условия алгоритм расходится на две ветки

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

если <условие> то

 <действие 1>

  иначе <действие 2>

все

Базовые циклические алгоритмы.

Циклы –  алгоритмы, в которых некоторые команды повторяются неоднократно.

Блок-схема цикла со счетчиком (цикл с известным числом повторений).

цел I, N

нц для I от 0 до N

… тело цикла

кц

Цикл с предусловием  ПОКА

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

Блок-схема цикла ПОКА

нц пока <условие>

<тело цикла>

кц

4. Глава 3 Программирование на языке КУМИР.

3.1 Примеры решение задач, содержащих массивы на языке КУМИР.

Задача 1. Найти сумму всех элементов массива

алг сумма (арг цел n, вещ таб A[1;n], рез вещ S )

нач цел i

 нц для i от 2 до n

S:=S+A[i]

кц

вывод S

кон

Задача 2. Найти максимальное значение массива

алг сумма (арг цел n, вещ таб A[1;n], рез вещ макс )

нач цел i

макс:= A[i]

 нц для i от 2 до n

если A[i]>макс

то макс:= A[i]

все

кц

вывод макс

кон

Задача 3. Найти количество положительных элементов массива

алг сумма (арг цел n, вещ таб A[1;n], рез цел k )

нач цел i

k:=0

 нц для i от 1 до n

если A[i]>0

 то k:=k+1

все

кц

вывод k

кон

Задача 4. Найти сумму нечетных элементов

3.2 Трассировка программы для отслеживания значения переменной

Трассировка нужна для понимания чужой программы и для проверки правильности написания своей. Используют метод пошагового выполнения программы с отслеживанием значений всех переменных.

Трассировка программы к задаче сортировки массива методом выбора

5. Глава 4  Исследовательская деятельность

4.1 Разработка рекомендаций по решению заданий содержащих массивы

1.     Просмотрите программу и решите к какому типу алгоритмической структуры она относится:

v Ветвление;

v Циклы;

v Циклы, содержащие  условный алгоритм.

2.     Если программа содержит циклы используйте трассировку программы для нахождения результата

3.     Обратите внимание на условие в теле цикла (если есть)

4.     Проанализируйте действие в теле цикла

5.     Соедините условие с действием, сделайте вывод, какой смысл заложен в программе (выбор наибольшего элемента, подсчет элементом меньше заданного  и т.д.)

6.     Посчитайте количество повторений в цикле или проанализируйте условие продолжение цикла

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

4.2 Разбор заданий  № 9,10 ОГЭ, применяя наши рекомендации

Задание № 9

1. За­пи­ши­те зна­че­ние пе­ре­мен­ной s, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел s, k s := 0 нц для k от 3 до 7 s := s + 6 кц вывод s кон					Трассировка  k      s 3       0+6=6 4       6+6=12 5       12+6=18 6        18+6=24 7         24+6=30 Повторений цикла: 5 Каждое повторение в теле цикла прибавляется  6 Заменим сложение умножением. 5×6=30 Ответ 30

2. За­пи­ши­те зна­че­ние пе­ре­мен­ной s, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел s, k s := 0 нц для k от 4 до 8 s := s + 7 кц вывод s кон

Решение: Число  Повторений: 5 5×7=35 Ответ 35

3. За­пи­ши­те зна­че­ние пе­ре­мен­ной s, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел s, k s := 0 нц для k от 1 до 7 s := s + 8 кц вывод s кон  Решение: Число повторений : 7 7×8=56  Ответ: 56

4. За­пи­ши­те зна­че­ние пе­ре­мен­ной s, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы

алг нач цел s, k s := 0 нц для k от 2 до 8 s := s + 9 кц вывод s кон Решение: Число повторений : 7 7×9=63  Ответ: 63

5. За­пи­ши­те зна­че­ние пе­ре­мен­ной s, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы. Текст про­грам­мы при­ведён на трёх язы­ках про­грам­ми­ро­ва­ния.

алг нач цел s, k s := 0 нц для k от 5 до 9 s := s + 7 кц вывод s кон Решение: Число повторений : 5 5×7=35  Ответ: 35

Задание № 10

1. В таб­ли­це Dat хра­нят­ся дан­ные из­ме­ре­ний сред­не­су­точ­ной тем­пе­ра­ту­ры за 10 дней в гра­ду­сах (Dat[1] — дан­ные за пер­вый день, Dat[2] — за вто­рой и т. д.). Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел­таб Dat[1:10] цел к, m Dat[1] := 12 Dat[2] := 15 Dat[3] := 17 Dat[4] := 15 Dat[5] := 14 Dat[6] := 12 Dat[7] := 10 Dat[8] := 13 Dat[9] := 14 Dat[10] := 15 m := 0 нц для к от 1 до 10 если Dat[к]=15 то m : = m+1 все КЦ вывод m КОН Решение: Трассировка программы k   Dat[к]  проверка условия           m 1     12        Ложь                               0 2      15       Истина                            0+1 3       17      Ложь                                1 4       15      Истина                             2 5       14      Ложь                                2  6       12      Ложь                                 2 7       10      Ложь                                 2 8        13     Ложь                                 2 9        14     Ложь                                 2 10       15    Истина                              3 Ответ 3  Программа считает количество  Dat[к]  Равных 15

2. В таб­ли­це Dat хра­нят­ся дан­ные из­ме­ре­ний сред­не­су­точ­ной тем­пе­ра­ту­ры за 10 дней в гра­ду­сах (Dat[1] — дан­ные за пер­вый день, Dat[2] — за вто­рой и т. д.). Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы. 

алг нач цел­таб Dat[1:10] цел к, m Dat[1] := 12 Dat[2] := 15 Dat[3] := 17 Dat[4] := 15 Dat[5] := 14 Dat[6] := 12 Dat[7] := 10 Dat[8] := 13 Dat[9] := 14 Dat[10] := 15 m := 0 нц для к от 1 до 10 если Dat[к] > m то m : = Dat[к] все КЦ вывод m КОН Решение: Трассировка программы k   Dat[к]  проверка условия           m (кладем значение Dat[к] ) 1     12           Истина                         12 2      15       Истина                            15 3       17      Истина                            17 4       15      Ложь                                17 5       14      Ложь                                17  6       12      Ложь                                 17 7       10      Ложь                                17 8        13     Ложь                                 17 9        14     Ложь                                17 10       15    Ложь                                  17 Ответ 17  Программа находит максимальный элемент среди  Dat[к]  сравнивая их

3. В таб­ли­це Dat пред­став­ле­ны дан­ные о ко­ли­че­стве го­ло­сов, по­дан­ных за 10 ис­пол­ни­те­лей на­род­ных песен (Dat[1] — ко­ли­че­ство го­ло­сов, по­дан­ных за пер­во­го ис­пол­ни­те­ля, Dat[2] — за вто­ро­го и т. д.). Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел­таб Dat[1:10] цел к, m Dat[1] := 56 Dat[2] := 70 Dat[3] := 20 Dat[4] := 41 Dat[5] := 14 Dat[6] := 22 Dat[7] := 30 Dat[8] := 12 Dat[9] := 65 Dat[10] := 35 m := 0 нц для к от 1 до 10 если Dat[к] > 25 то m : = m+1 все КЦ вывод m КОН Решение: Трассировка программы k   Dat[к]  проверка условия           m 1     56        Истина                              0+1 2      70       Истина                            1+1=2 3       20      Ложь                                2 4       41      Истина                             2+1=3 5       14      Ложь                                3  6       22     Ложь                                 3 7       30      Истина                                3+1=4 8        12     Ложь                                 4 9        65     Истина                                4+1=5 10       35    Истина                              5+1=6 Ответ 6 Программа считает количество  Dat[к]  Больше 25

4. В таб­ли­це Dat хра­нят­ся дан­ные о ко­ли­че­стве уче­ни­ков в клас­сах (Dat[1] — ко­ли­че­ство уче­ни­ков в пер­вом клас­се, Dat[2] — во вто­ром и т. д.). Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы.

алг нач цел­таб Dat[1:11] цел к, m Dat[1] := 20 Dat[2] := 25 Dat[3] := 19 Dat[4] := 25 Dat[5] := 26 Dat[6] := 22 Dat[7] := 24 Dat[8] := 28 Dat[9] := 26 Dat[10] := 21 Dat[11] := 27 m := 0 нц для к от 1 до 11 если Dat[к] > 22 то m : = m+1 все КЦ вывод m КОН Решение: Трассировка программы k   Dat[к]  условие         m 1     20        Ложь              0 2      25       Истина       +1 3       19      Ложь             1 4       25     Истина            2 5       26     истина             3 6       22     Ложь                3 7       24      истина           4 8        28    истина              5 9        26     истина             6 10       21    ложь               6 11       27     истина          7 Ответ 7  Программа считает количество  Dat[к]  Больше 22

5. В таб­ли­це Dat хра­нят­ся оцен­ки (по де­ся­ти­балль­ной шкале) сту­ден­та по про­грам­ми­ро­ва­нию за 8 про­шед­ших с на­ча­ла учёбы се­мест­ров (Dat[1] — оцен­ка за пер­вый се­местр, Dat[2] — за вто­рой и т. д.). Опре­де­ли­те, что будет на­пе­ча­та­но в ре­зуль­та­те вы­пол­не­ния сле­ду­ю­ще­го ал­го­рит­ма

алг нач цел­таб Dat[1:10] цел к, m, term Dat[1] := 7 Dat[2] := 7 Dat[3] := 6 Dat[4] := 8 Dat[5] := 4 Dat[6] := 5 Dat[7] := 4 Dat[8] := 7 term:=1 m := Dat[1] нц для к от 2 до 8 если Dat[к] < m то m:= Dat[k] term := k все КЦ вывод term КОН

Решение:

Трассировка программы

k   Dat[к]  проверка условия           m (кладем значение Dat[к] ) term( кладем к)

2      7      ложь  7<7                          7                                                 1

3       6     Истина   6< 7                        6                                              3

4       8     Ложь                                6                                                   3

5       4   Истина                                4                                                  5

6       5     Ложь                                 4                                                   5 

7       4     Ложь                                4                                                    5

8        7    Ложь                                 4                                                   5

Ответ 5  Программа находит минимальный элемент среди  Dat[к]  сравнивая их

И выводит его порядковый номер

4.3  Опрос учеников, применявших наши рекомендации

Ученикам 9-х классов был представлен разбор заданий № 9, 10 ОГЭ. Были  розданы для самостоятельной работы, разработанные нами рекомендации для решения этих заданий и других задач по теме «Программирование».  После этого предлагалась опросный лист с вопросом:

Помогли ли тебе наши рекомендации?

Ответы:

 Помогли, я стал(а) разбираться в программах на массивы………………………………………..63%

Скорее да, чем нет………………………….12%

Я разбирался(лась)…………………………..1%

Нет, не помогли……………………………….18%

Не понял(а), что написано…………..………6%

6.    Выводы

Для понимания работы программы, необходимо:

1.      Применять трассировку программы

2.      Обратить внимание на условие в теле цикла

3.      Проанализировать действие в теле цикла

4.      Соединить условие с действием, сделайте вывод, какой смысл заложен в программе

5.      Посчитать количество повторений в цикле или проанализируйте условие продолжение цикла

 

7.    Заключение

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

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

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

8.    Список использованной литературы

1.     Информатика 7-9 кл.: Учеб. Для общеобразоват. Учреждений/ А.Г. Кушниренко, Г.В. Лебедев, Я.Н. Зейдельман._М.:Дрофа,2003.-336 с.

2.     Азы программирования: Факультативный курс 5-9 кл./ А.А.Дуванов. СПб.:БХВ-Петербург, 2005.-496 с.

3.     Паскаль для школьников/ Д. М. Ушаков, Т. А. Юркова.-СПб.: Питер, 2010,- 256 с.