[28.03.2015]
ИНТЕРПРЕТИРУЮЩИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ПО КЛАССИЧЕСКОМУ ПРОГРАММИРОВАНИЮ: ОБРАБОТКА СТРОК В ФРАГМЕНТЕ АЛГОРИТМА Автор |
“Я не знаю, как решать задачи.
Я знаю только, что после того, как решишь их много, начинаешь делать это лучше, начинаешь лучше видеть возможные подходы к решению задач, начинаешь лучше их чувствовать”.
Леонид Волков и Никита Шамгунов
“Как стать чемпионом Урала по программированию”
Цель
Придумать технологию простого и наглядного способа решения задач уровня А 13.
Задачи
Преодоление затруднений у обучающихся при решении задач уровня А 13.
По предложенной технологии, каждый обучающийся решает индивидуальную задачу.
Домашнее задание: в текстовом редакторе Word, в табличном процессоре оформить решение задачи.
Придумать свою задачу.
Предложен интерпретирующий (пошаговый) метод решения задач по классическому программированию. Последовательное исполнение независимой компиляции каждого отдельного оператора (команды) исходной программы без применения среды программирования, в тетради. Построчное вычисление значения переменной для следующей строки. Рассмотрены понятия - свойства алгоритма. По таблице 1 проводится анализ и доказательство, что предложенный фрагмент алгоритма удовлетворяет требованиям, предъявляемым к алгоритму. Следовательно, обучающиеся могут придумать много задач данного уровня и выполнить задание творческого плана по композиции задач.
Задачи уровня А 13, представленные фрагментом алгоритма и записанные на учебном алгоритмическом языке вызывают неуверенность у обучающихся, из-за непонимания терминологии и условия. Для того, что бы обучающиеся поняли эту задачу без объяснения и сами сформировали свое знание по решению задач уровня А 13 предлагается интерпретирующий метод решения, который по операциям демонстрируется на интерактивной доске и все принимают участие в решении.
На примере двух задач А 13 с сайта К. Полякова продемонстрировать, что решение задач в информатике всегда связано с преобразованием информации, следовательно с исходными данными и результатом работы алгоритма должна быть информация:
ИСХОДНЫЕ (ВХОДНЫЕ) ДАННЫЕ → АЛГОРТМ → ВЫХОДНЫЕ ДАННЫЕ (РЕЗУЛЬТАТ)
Обучающиеся должны провести сопоставительный анализ и убедиться удовлетворяет - ли фрагмент данного алгоритма требованиям, предъявляемым к алгоритмам.
Действия обучающегося: заполнить таблицу 1:
СВОЙСТВА АЛГОРИТМА
№ | НАИМЕНОВАНИЕ | ОПИСАНИЕ | СООТВЕТСТВИЕ (+)/НЕТ ( - ) |
1 | ДИСКРЕТНОСТЬ (ПРЕРЫВНОСТЬ) | предоставить решение задачи последовательностью операций | |
2 | ОПРЕДЕЛЕННОСТЬ (ДЕТЕРМИНИРОВАННОСТЬ) | описать операцию однозначно и понятно для каждого случая и для исполнителя | |
3 | МАССОВОСТЬ | использовать переменные в качестве данных и получить решение для конкретного набора значений; для целого класса задач определяемого областью применимости алгоритма - диапазоном возможных исходных данных | |
4 | РЕЗУЛЬТАТИВНОСТЬ | получить конкретный результат или сообщение, что задача решения не имеет; рассмотреть все возможные ситуации | |
5 | КОНЕЧНОСТЬ | конечное количество операций | |
6 | ЭФФЕКТИВНОСТЬ | получить результат за приемлемое время |
Условие задачи А 13 - 1
В приведенном ниже фрагменте алгоритма на алгоритмическом языке, переменные а, b, c имеют тип «строка»
переменные i, k имеют тип «целое».
Используются следующие функции:
Длина (а) – возвращает количество символов в строке а. (Тип «целое»).
Извлечь (а, i) – возвращает i – тый (слева) символ в строке а. (Тип «строка»).
Склеить (а, b) возвращает строку, в которой записаны сначала все символы строки а, записывает все символы строки b. (Тип «строка»).
Значения строк записываются в одинарных кавычках (например, а:= ′ СОМ′.
Дан фрагмент алгоритма:
i:= Длина (а)
k:= 2
b:= ′А′
пока i > 0
нц
i:= Извлечь (а, i)
b:= Склеить (b, c)
i:= i – k
кц
b:= Склеить (b, ′ Т ′ )
Какое значение будет у переменной b, после выполнения фрагмента алгоритма, если значение переменной а было
′ПОЕЗД′?
Решение
Построим таблицу
Заполнение рекомендуем начать справа: отводим каждой переменной один столбец.
В столбце 1 пронумеруем:
- 0 строки данного алгоритма 1 первый вложенный цикл 2 второй вложенный цикл 3 третий вложенный цикл.
Тогда в столбце 1.1. запишем, какие строки тела цикла работают, на соответствующей строке - результат работы цикла и как меняют значение переменные.
В столбце 2 запишем на отдельной строке фрагмент алгоритма.
В столбце 3 будем проверять истинность условия. Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла. При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно.
В столбце 4 запишем строку а : = ′ПОЕЗД′.
В столбцах 5, 6, 7, 8 переменные.
ТАБЛИЦА РАБОТЫ ФРАГМЕНТА АЛГОРИТМА
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
Вложенный цикл | 0 | Алгоритм | Проверка условия пока i > 0 если истина 1, если ложь 0 | i: = Длина (а) | b | c | i | k |
3 | 2 | 1 | ||||||
3 цикл | 2 цикл | 1 цикл | ||||||
1 | 2 | 3 | 4 | 5 | ||||
0.1 | i:= Длина (а) | П | О | Е | З | Д ′ | ||
0.2 | k:= 2 | k:=2 | ||||||
0.3 | b:= ′А′ | b:= ′А′ | ||||||
3.4 | 2.4 | 1.4 | 4 | пока i > 0 | ||||
3.5 | 2.5 | 1.5 | 5 |
| ||||
3.6 | 2.6 | 1.6 | 6 | c:= Извлечь (а, i=5) | 5> 0 | 1 | c : = ′ Д′ | i:=5 |
c:= Извлечь (а, i=3) | 3>0 | 1 | c : = ′ E′ | i :=3 | ||||
c:= Извлечь (а, i=1) | 1>0 | 1 | c : = ′ П′ | i :=1 | ||||
3.7 | 2.7 | 1.7 | 7 | b:= Склеить (b, c=Д) | b:= ′А Д′ | |||
b:= Склеить (b, c=E) | b:= ′ АДЕ′ | |||||||
b:= Склеить (b, c=П) | b:= ′ АДЕП′ | |||||||
3.8 | 2.8 | 1.8 | 8 | i:= i – k | i:= 3 | |||
i:= 1 | ||||||||
3.9 | 2.9 | 1.9 | 9 | 1 кц | 2 кц | 3 кц | ||
- 1>0 | 0 | 0 | i := - 1 | |||||
0.10 | b:= Склеить (b, ′ Т ′ ) | b:= ′АДЕПТ ′ |
Домашняя самостоятельная работа студента группы 1С1 Мичурина Арсения
Решить задачу А13-2.
Имеется фрагмент алгоритма, записанный на алгоритмическом языке:
n := Длина (а) m := 7 пока i ≥ 7 b := Извлечь (а, m) с := Извлечь (а, m-4) b := Склеить (b, с) с := Извлечь (а, m+1) b := Склеить (b, с) нц для i от 10 до n с := Извлечь (а, i) b := Склеить (c, b ) кц |
Здесь переменные a, b и с - строкового типа; переменные n, m, k – целые.
В алгоритме используются следующие функции:
Длина (х) – возвращает количество символов в строке х. Имеет тип «целое».
Извлечь (х, i) – возвращает i - й символ слева в строке х. Имеет строковый тип.
Склеить (х, у) – возвращает строку, в которой записаны подряд сначала все символы строки х, а затем все символы строки у. Имеет строковый тип.
Значения строк записываются в кавычках (одинарных), например x = 'школа'.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма,
если переменная а имела значение 'КАРИКАТУРА'?
Решение
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||||||||||||||||
Цикл | Проверка логического условия пока i ≥ 7 | a | b | c | n | m | i | |||||||||||||||||
Вложенный цикл | 0 |
| ||||||||||||||||||||||
2 | 1 | |||||||||||||||||||||||
0.1 | n := Длина (а) | 10 | ||||||||||||||||||||||
0.2 | m := 7 | 7 | ||||||||||||||||||||||
1.3 | 3 | пока i ≥ 7 | 7≥ 7 | И | ||||||||||||||||||||
1.4 | 4 | b := Извлечь (а, m) | ′Т′ | 7 | ||||||||||||||||||||
1.5 | 5 | с := Извлечь (а, m+1) | 8≥7 | И | ′Р′ | 7+1=8 | ||||||||||||||||||
1.6 | 6 | b := Склеить (b, с) | ′ТР′ | |||||||||||||||||||||
2.3 | пока i ≥ 7 | 9≥7 | И | 8+1=9 | ||||||||||||||||||||
2.4 | с:=Извлечь (а, m+1) | ′У′ | ||||||||||||||||||||||
2.5 | b := Склеить (b, с) | ′ТРУ′ | ||||||||||||||||||||||
0.7 | кц | |||||||||||||||||||||||
0.8 | нц | |||||||||||||||||||||||
0.9 | для i = 10 | 10 | ||||||||||||||||||||||
0.10 | с := Извлечь (а, i) | ′А′ | ||||||||||||||||||||||
0.11 | b := Склеить (c, b) | ′АТРУ′ | ||||||||||||||||||||||
0.12 | кц |
Ответ: ′АТРУ ′ (футболист)
Заполним таблицу 1:
СВОЙСТВА АЛГОРИТМА
№ | НАИМЕНОВАНИЕ | ОПИСАНИЕ | СООТВЕТСТВИЕ (+)/НЕТ ( - ) |
1 | ДИСКРЕТНОСТЬ (ПРЕРЫВНОСТЬ) | предоставить решение задачи последовательностью операций | + |
2 | ОПРЕДЕЛЕННОСТЬ (ДЕТЕРМИНИРОВАННОСТЬ) | описать операцию однозначно и понятно для каждого случая и для исполнителя | + |
3 | МАССОВОСТЬ | использовать переменные в качестве данных и получить решение для конкретного набора значений; для целого класса задач определяемого областью применимости алгоритма - диапазоном возможных исходных данных | + |
4 | РЕЗУЛЬТАТИВНОСТЬ | получить конкретный результат или сообщение, что задача решения не имеет; рассмотреть все возможные ситуации | + |
5 | КОНЕЧНОСТЬ | конечное количество операций | + |
6 | ЭФФЕКТИВНОСТЬ | получить результат за приемлемое время | + |
ВЫВОД: фрагмент данного алгоритма удовлетворяет требованиям, предъявляемым к алгоритмам, выполним творческое задание по композиции и самостоятельно составим задачи уровня А 13.
Домашняя самостоятельная работа студента группы 1П1 Арбузникова Дениса
Творческое задание: придумать свою задачу по типу А13
А 13-3
Имеется фрагмент алгоритма, записанный на алгоритмическом языке:
n := Длина(а)
m := 1
b := Извлечь(а, m)
нц для i от 6 до n
с := Извлечь(а, i)
b := Склеить(b, с)
кц
Здесь переменные a, b и с - строкового типа; переменные n, m – целые. В алгоритме используются следующие функции:
Длина(х) – возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х, i) – возвращает i-й символ слева в строке х. Имеет строковый тип.
Склеить(х, у) – возвращает строку, в которой записаны подряд сначала все символы
строки х, а затем все символы строки у. Имеет строковый тип.
Значения строк записываются в кавычках (одинарных), например x='скула'.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма,
если переменная а имела значение 'ЭКОЛОГИЯ'?
