Информатика. Часть 2
Занятие 2. Основы алгоритмизации Необходимо ознакомиться с примерами выполнения заданий по алгоритмизации. Затем решить свой вариант заданий, представленный ниже в п. 2. Задания для выполнения. Решение записывается в Документ Гугл или в текстовый файл Word, который должен быть потом загружен на Облако Гугл. Убедитесь, что к файлу открыт совместный доступ с преподавателем (аккаунт преподавателя itcamptomsk@gmail.com).
Блок-схемы и диаграммы лучше создавать в документе Word, а затем загружать на Облако.
Вариант заданий выбирается по номеру студента в списке группы.
Для дополнительных баллов студенту предлагается ответить на контрольные вопросы в конце данного документа. Пример решения задания для самостоятельного выполнения
Записать следующие алгоритмы:
дана матрица A[n x m], найти максимальные элементы всех столбцов матрицы. Для записи алгоритма использовать систему кодирования псевдокод;
дана произвольная строка символов S. Найти количество слов строки. Словом считается последовательность символов, ограниченная пробелами и не имеющая пробелов внутри себя. Для записи алгоритма использовать блок-диаграмму;
сформировать массив X из n элементов по следующему правилу — X[i+1]=X[i]+2; i изменяется от 1 до n – 1; X[1] = 15. Для записи алгоритма использовать диаграмму Насси-Шнайдермана.
Диаграммы Насси-Шнайдермана
Основные конструкции структурного программирования в диаграмме Насси-Шнайдермана обозначаются следующим образом:
Пример 6. Дано число натуральное число n <10. Вывести на экран грамматически верную фразу (n лет — 1 год, 2 года, 10 лет и т.д.).
Решение.
Схема решения первой задачи будет следующей: зафиксируем номер столбца j=1, положим за максимальный элемент A[1][j] — т.е. элемент, лежащий в первой строке столбца j. Далее начнем просматривать элементы столбца j, начиная со второго элемента. Если в процессе поиска найдено значение матрицы, превышающее значение максимума, то заменим текущий максимум на найденное значение. После того, как весь столбец j будет просмотрен, вернем в качестве результата найденное значение максимума. Таким образом, будет найден максимальный элемент в столбце 1. Повторим описанный алгоритм для j:=2,3,…,m . Запишем решение на псевдокоде: Задать — количество строк, — количество столбцов.
Задать элементы матрицы
ЦИКЛ ()
;
ЦИКЛ()
ЕСЛИ ТО
КОНЕЦ ЦИКЛА
Вернуть «В столбце» «максимальное значение» ;
КОНЕЦ ЦИКЛА
Для второй задачи можно предложить следующую схему решения: так как не оговорено, что между словами строки ровно один пробел, то между словами может быть и группа пробелов. Для подсчета слов используем переменную-счетчик k. Начнем просматривать строку с первого символа, если первый символ не пробел, то в строке уже найдено первое слово, увеличим значение переменной k на единицу. Далее циклически просматриваем строку и ищем сочетания: i-тый символ равен пробелу, а i+1-ый символ не равен пробелу, фиксируем начало каждого слова строки и увеличиваем в этом случае счетчик слов k на единицу. Просмотр заканчивается при достижении переменной i значения n – 1, где n — длина строки. Блок-диаграмма описанного алгоритма представлена на рисунке 1.
Рисунок 1 – Блок-диаграмма Решим третью задачу следующим образом: зададим первый элемент массива и переменную i определим равной единице. Все следующие элементы массива будем определять по формуле, данной в условии. Для этого организуем цикл, где переменную i будем изменять от 1 до n – 1, где n — размерность массива. Шаг изменения переменной i равен единице. На рисунке ниже представлена диаграмма Насси-Шнайдермана описанного алгоритма. Обратите внимание на то, каким образом выполнен возврат полученного результата: на каждом шаге цикла возвращается предыдущее значение элемента массива, а после выполнения цикла возвращается последнее полученное значение. Задать
Задать
Задать
Вернуть
Вернуть
Задания на выполнение
Вариант 1
а) Записать на псевдокоде алгоритм: в квадратной матрице найти минимальный элемент, заменить его значение на 100. Если минимальных элементов несколько, то выполнить замену для всех найденных минимальных элементов. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: заполнить массив , состоящий из элементов, по следующему правилу —
, . в) Записать блок-схему для решения следующей задачи: проверить, является ли заданная строка палиндромом. Палиндром — последовательность, читающаяся справа налево и слева направо одинаково. Вариант 2
а) Записать на псевдокоде алгоритм: заполнить квадратную матрицу по следующему правилу:
б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: в массиве из элементов найти сумму элементов с нечетными индексами. в) Записать блок-схему для решения следующей задачи: «перевернуть» заданную строку S, — поменять 0-й символ с -м символом, 1-й с n — 2-м символом и т.д. Вариант 3
а) Записать на псевдокоде алгоритм: в матрице найти сумму всех элементов, лежащих выше главной диагонали. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: в массиве из элементов найти количество элементов с нечетными значениями. в) Записать блок-схему для решения следующей задачи: в заданной строке S удвоить (повторить) все гласные буквы. Например: «Москва» — «Мооскваа». Вариант 4
а) Записать на псевдокоде алгоритм: заполнить квадратную матрицу по следующему правилу:
. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: в массиве из элементов найти произведение минимального и максимального элементов. в) Записать блок-схему для решения следующей задачи: в заданной строке S удалить все символы, не являющиеся буквами. Вариант 5
а) Записать на псевдокоде алгоритм: в матрице найти минимальный элемент, лежащий ниже главной диагонали. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: заполнить массив по следующему правилу — . в) Записать блок-схему для решения следующей задачи: найти минимальный элемент из четырех заданных . Вариант 6
а) Записать на псевдокоде алгоритм: заполнить квадратную матрицу по следующему правилу:
б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: в массиве из элементов найти сумму элементов с четными индексами. в) Записать блок-схему для решения следующей задачи: даны 4 числа . Если среди этих чисел встречаются одинаковые, то переменной присвоить значение 1, если нет, то 0.
Вариант 7
а) Записать на псевдокоде алгоритм: в квадратной матрице найти сумму элементов, лежащих на главной и побочной диагоналях. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: просмотреть массив и если пара элементов удовлетворяет условию , то поменять элементы местами. в) Записать блок-схему для решения следующей задачи: даны 4 целых числа , значения которых лежат от 0 и до 1000. Если среди этих чисел есть полные квадраты (1, 4, 9, …), то переменной присвоить значение 1, если нет, то 0. Вариант 8
а) Записать на псевдокоде алгоритм: в квадратной матрице поменять местами элементы -го столбца и -той строки. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: просмотреть массив и найти количество ненулевых элементов. в) Записать блок-схему для решения следующей задачи: даны 4 целых числа , проверить, есть ли среди них отрицательные числа, если есть, то в переменной сохранить количество этих чисел, если нет, то присвоить значение 0.
Вариант 9
а) Записать на псевдокоде алгоритм: в квадратной матрице заменить элементы -го столбца на их абсолютные значения. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: просмотреть массив и найти сумму отрицательных элементов. в) Записать блок-схему для решения следующей задачи: даны 4 целых числа , найти минимальное и максимальное значение среди заданных. Вариант 10
а) Записать на псевдокоде алгоритм: в квадратной матрице найти минимальный элемент, лежащий на побочной диагонали. б) Записать диаграмму Насси-Шнайдермана для решения следующей задачи: задать элементы массива по следующему правилу: . в) Записать блок-схему для решения следующей задачи: в заданной строке найти количество символов, являющихся буквами.
Контрольные вопросы и упражнения
Дайте определение алгоритма.
Перечислите основные конструкции структурного программирования.
Приведите пример алгоритма, который использует конструкцию следования.
Приведите пример алгоритма, который использует конструкцию развилки.
Приведите пример алгоритма, в котором используется циклическая конструкция.
Для чего может быть использована флаговая переменная?
Запишите алгоритм поиска максимального элемента в заданном массиве. Используйте любую систему кодирования.
Запишите алгоритм поиска индекса минимального значения в заданном массиве.
Запишите словесную постановку задачи, которая может быть решена следующим алгоритмом:
Задать ;
ЕСЛИ
ТО Вернуть «Все числа одинаковы»
ИНАЧЕ ЕСЛИ ТО
ИНАЧЕ
КОНЕЦ ЕСЛИ
ЕСЛИ ТО
КОНЕЦ ЕСЛИ
Вернуть .
Какие значения примут переменные x,y,z после выполнения следующего алгоритма:
Задать ;
ЕСЛИ И
ТО
ИНАЧЕ
Перечислите системы кодирования алгоритмов.
Запишите алгоритм вычисления значений функции, заданной следующим образом:
Запишите алгоритм решения произвольного квадратного уравнения . Какие конструкции структурного программирования использовались в алгоритме?
Запишите алгоритм, подсчитывающий количество слов заданной строки, начинающихся с заданного символа.
|