Основы компьютерного проектирования

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНВЕРСИТЕТ ИНФОРМАТИКИ  И РАДИОЭЛЕКТРОНИКИ 
 
 
 
 
 
 
 
 
 
 

Контрольная работа №1

     По  предмету «Основы компьютерного проектирования»

     Студентки ФЗВ и ДО БГУИР

     Специальность Информационные системы и технологии

     Группа 702301

     Соколовской Анны Валерьевны 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Минск 2007

 

Содержание 

1 Определение  алгоритма         3

2 Свойства алгоритма            3

3 Способы описания алгоритма        3

4 Базовые структуры блок-схем, линейные и разветвляющиеся структуры, циклические структуры, типы циклов       4

5 Структурированные блок-схемы        6

6 Предопределенные  процессы. Рекурсия.      7

Задача №1            8

Задача №2                    10 

 

        1 Определение алгоритма. 

       Алгоритм  – конечная последовательность команд предназначенная исполнителю и направленная на достижение определенной цели.

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

       2 Свойства алгоритмов 

       Алгоритм  имеет следующие свойства:

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

       2 Определенность (детерминированность) - каждое правило из системы однозначно, а данные однозначно связаны между собой, т.е. последовательность действий алгоритма строго и точно определена.

       3 Результативность (конечность) - алгоритм решает поставленную задачу за конечное число шагов.

       4 Массовость - алгоритм разрабатывается так, чтобы его можно было применить для целого класса задач, например, алгоритм вычисления определенных интегралов с заданной точностью. 

       3 Способы описания  алгоритма 

       Наиболее  распространенными способами описания алгоритмов являются словесное и графическое описания алгоритма.

       Словесное описание алгоритма рассмотрим на конкретном примере: необходимо найти корни квадратного уравнения a*x²+b*x+c=0

1. вычислить D = b²-4ac;
2. если D < 0, перейти к 4;

       3) вычислить корни уравнения x₁=(-b+ )/(2a); x₂=(-b- )/(2a);

       4) конец.

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

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

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

       4 Базовые структуры  блок-схем, линейные и разветвляющие структуры, циклические структуры, типы циклов. 

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

       1 Базовая структура «следование». Образуется последовательностью действий, следующих одно за другим: 

       

 

       2. Базовая структура "ветвление". Обеспечивает в зависимости от  результата проверки условия  (да или нет) выбор одного  из альтернативных путей работы  алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура «ветвление» существует в четырех основных вариантах:

• «если - то»

 

       

• «если –  то - иначе»;

 

• «выбор»;

 

• «выбор - иначе».

 

       3. Базовая структура "цикл". Обеспечивает  многократное выполнение некоторой  совокупности действий, которая  называется телом цикла. Основные разновидности циклов:

• Цикл типа «пока». Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.

 

 

       

• Цикл типа «для». Предписывает выполнять тело цикла для всех значений некоторой  переменной (параметра цикла) в заданном диапазоне.

 

 5 Структурированные  блок-схемы 

       Структурированные блок-схемы могут использоваться для показа межмодульных связей, для отображения структур данных, программ и систем обработки данных.  Существуют различные структурные диаграммы: диаграммы Насси-Шнейдермана, диаграммы Варнье, Джексона, МЭСИД и др.

 

      Рассмотрим  пример использования диаграмм МЭСИД.

           Задан одномерный массив из положительных и отрицательных чисел. Требуется определить частное от деления суммы положительных элементов на сумму отрицательных элементов этого массива.

 
 

6 Предопределенные  процессы. Рекурсия 

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

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

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

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

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

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

     Задача  № 1 

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

     

 
 
 

     

 

     Выполнение  программы по шагам 

     Начало

     Инициализация массива;

     a[5]={9,9,8,3,1}

     //находим номер первого четного элемента

     Цикл для i=n-1 пока i<1, i--

     Шаг 1:

     i=4

     a[4]\2==0?  //остаток от деления

     Нет

     Шаг 2

     i=3

     a[3]\2==0?  //остаток от деления

     Нет

     Шаг 3

     i=2

     a[2]\2==0?  //остаток от деления

     Да;

     index=3;

     Шаг 4

     i=1

     a[1]\2==0?  //остаток от деления

     Нет

     Шаг 5

     i=0

     a[0]\2==0?  //остаток от деления

     Нет

     //номер  первого четного элемента равен  2;

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

     Цикл для i=1 пока i<index-1, i++

     Шаг 6:

     a[1]>=max?

     Да;

     max=a[1];

     k=1;

     Вывод массива на экран

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

     к

конец

 

      Задача № 2 

     Проверить, все ли столбцы матицы содержат хотя бы один нулевой элемент. Если да, то заменить все нули в матрице на единицы. 

     

 

     

     

 

     Выполнение  программы по шагам. 

     Начало

     Введите количество строк и столбцов

     //количество  строк

     3

     //количество  столбцов

     3

     Заполнение  массива случайными числами

     //Рассмотрим  решение задачи на конкретном примере. Пусть есть у нас массив

Шаг 1: j=1  // рассматриваем первый столбец