Некоммерческое  акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра  «Информационные  системы»

 

 

АЛГОРИТМЫ, СТРУКТУРЫ ДАННЫХ И ПРОГРАММИРОВАНИЕ

 

Методические указания к выполнению лабораторных работ

(для студентов специальности 5В070300 - Информационные системы)

 

 

Алматы 2013

Составитель: А.Г. Ни. Алгоритмы, структуры данных и программирование. Методические указания к выполнению лабораторных работ (для студентов специальности 5В070300 - «Информационные системы»)–Алматы: АУЭС, 2013– 47 с.

 

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

         Методические указания предназначены для студентов всех форм обучения  специальности 5В070300 - «Информационные системы».

         Ил.7, библиогр. – 14 назв.

 

         Рецензент: канд. техн. наук доцент М.В. Башкиров

 

         Печатается по плану издан НАО «Алматинский университет энергетики и связи»  на 2013 г.

 

© НАО «Алматинский университет энергетики и связи», 2013 г.

Сводный план 2013г. поз.194

 

Содержание
Введение		4
1	Общие указания к выполнению лабораторных работ	6
1.1	Методические рекомендации по выполнению лабораторных работ	6
1.2	Требования к оформлению отчета	7
1.3	Требования к защите	8
2	Варианты заданий к лабораторным работам	9
2.1	Тема1 Алгоритмы линейной структуры	9
2.2	Тема 2 Алгоритмы разветвляющейся структуры	15
2.3	Тема 3 Алгоритмы циклической структуры	21
2.4	Тема4 Алгоритмы обработки одномерных массивов	26
2.5	Тема 5 Алгоритмы обработки двумерных массивов	33
2.6	Тема 6 Алгоритмы поиска данных	41
2.7	Тема 7 Алгоритмы обработки динамических структур данных	47
Заключение		53
Приложение А Образец титульного листа		54
Список литературы		55

 

Введение

 

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

Предлагаемые методические указания к выполнению лабораторных работ по дисциплине “ Алгоритмы, структуры данных и программирование ” разработаны в помощь первокурсникам специальности 5B070300 - Информационные системы для приобретения практических навыков работы с базовыми структурами данных, разработки алгоритмов решения задач,  использующие базовые структуры данных, словесного, графического и программного описания данных алгоритмов.

Для программного описания алгоритмов решения задач,  использующие базовые структуры данных, студент  должен использовать язык программирования С, который называют “языком системного программирования”, поскольку на нем удобно писать компиляторы и операционные системы. Однако, он столь же удобен и для написания больших прикладных программ в самых разных областях применения. Язык C предлагает широкий ассортимент типов. Фундаментальные типы включают в себя символьный, а также целый и вещественный (с плавающей точкой) нескольких различных размеров. Кроме того, существует целая иерархия производных типов данных, создаваемых с помощью указателей, массивов, структур и объединений.

В языке С имеются все основные управляющие конструкции, необходимые для написания хорошо структурированной программы: группировка операторов в блоки, принятие решения по условию (if-else), выбор одного из нескольких возможных вариантов (switch), циклы с проверкой условия завершения в начале (while, for) и в конце (do), а также принудительный выход из цикла (break). Язык С  доказал свою высочайшую эффективность и выразительность для самого широкого круга приложений.

В настоящих методических указаниях, с учетом кредитной технологии обучения, разработаны лабораторные работы по семи темам:

1) алгоритмы линейной структуры;

2) алгоритмы разветвляющейся структуры;

3) алгоритмы циклической структуры;

4) алгоритмы обработки одномерных массивов;

5) алгоритмы обработки двухмерных массивов;

6) алгоритмы поиска данных;

7) алгоритмы обработки динамических структур данных.

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

Лабораторные работы включают в себя по два задания: А и В, отличающиеся по уровню сложности. При выборе первого задания студент при защите может получить максимальный балл, равный 80%, при защите второго задания – 100%. К  защите  второго задания студент допускается только при условии защиты  первого задания на максимальный балл. При выполнении лабораторных заданий студент должен также показать умение использовать знания, полученные при изучении дисциплин, входящих в комплекс пререквизитов:

-   информатика;

-   алгебра;

-   геометрия;

    - алгоритмы и структуры данных.

Задания к лабораторным работам разработаны таким образом, чтобы студенты могли бы использовать навыки, полученные при выполнении их, при изучении дисциплин, входящих в комплекс постреквизитов, в  частности, дисциплины «Объектно-ориентированное программирование».

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

 В настоящей работе также разработаны общие требования к выполнению  и защите лабораторной работы. 

 

1 Общие указания к выполнению лабораторных работ

 

1.1 Методические рекомендации по выполнению лабораторных работ

 

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

Каждая лабораторная работа состоит из 2-х задач и включает следующие виды работ:

- анализ условия задачи и выработка подхода к ее решению;

- пошаговая разработка алгоритма решения и его описание;

- обоснование алгоритма;

- словесное описание алгоритма;

- составление блок-схемы алгоритма;

- выбор и обоснование представления для входных, выходных и промежуточных данных;

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

- выбор набора тестов, на которых будет проверяться программа;

- отладка программы и демонстрация правильной ее работы на выбранном наборе тестов.

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

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

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

1) естественность внешнего представления исходных данных, их привычность для человеческого восприятия. То же самое касается и представления выходных данных. Польза от разработанной программы может быть сведена к минимуму, если для понимания напечатанного ответа от человека требуется дополнительная сложная работа, связанная с переводом данных ответа в понятия исходной формулировки задачи;

2)  возможность построения эффективного алгоритма решения задачи.

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

Рекомендуемый вид экрана во время выполнения программы:

- наименование лабораторной работы;

- тема лабораторной работы;

- номер варианта;

- приглашение к вводу исходных данных;

- ввод исходных данных;

- результаты работы программы;

- группа и ФИО автора программы.

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

Контрольный пример также должен быть просчитан с помощью Microsoft Excel. Результаты проведенного тестирования должны быть представлены в виде скриншота экрана с результатами решения контрольного примера.  

 

1.2 Требования к оформлению отчета

 

 Выполнив лабораторную работу, студент оформляет отчет, который состоит из следующих разделов:

1) №  лабораторной работы, тема;
2) цель работы  и условия задания;
3) схема алгоритма решения задачи;
4) математическая модель задачи;
5) блок схема алгоритма;
6) текст  программы;
7) результаты выполнения программы;
8) проверка правильности разработанной программы;
9) выводы.
В Приложении А приведен образец титульного листа. 

Отчет должен быть выполнен печатным способом с использованием компьютера и принтера на одной стороне листа белой бумаги формата А4 через один интервал. Шрифт - обычный, кегль 14. Текст отчета следует печатать, соблюдая следующие размеры полей: левое - 30 мм, верхнее - 20 мм, правое – 1,5 мм и нижнее - 25 мм. Выравнивание - по ширине страницы.

Заголовки структурных элементов следует печатать прописными (заглавными) буквами в середине строки без точки. «Содержание», «Введение», «Заключение», «Список использованной литературы», «Приложение» служат заголовками структурных элементов работы.

Заголовки разделов, подразделов и пунктов следует печатать с абзацного отступа (1,25 см.) с прописной буквы без точки в конце, не подчеркивая. Если заголовок состоит из двух предложений, их разделяют точкой. Переносы слов в заголовках не допускаются. Расстояние между текстом и заголовками структурных элементов располагают пустую строку. Расстояние между заголовками разделов и заголовками подразделов располагают пустую строку.

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

Таблицы должны иметь заголовки и нумероваться. Блок-схемы и схемы пользовательского интерфейса должны иметь подписи и нумероваться.

Иллюстрация обозначается словом «Рисунок». Если рисунок один, то он обозначается «Рисунок 1». Слово «Рисунок» и его наименование располагают посередине строки.

Нумерация иллюстраций сквозная (арабскими цифрами) в пределах отчета.

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

 

1.3 Требования к защите

 

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

Каждая лабораторная работа включает в себя два задания А и В, отличающиеся по уровню сложности. При выборе первого задания студент при защите может получить максимальный балл, равный 80%, при защите второго задания – 100%. К  защите  второго задания студент допускается только при условии защиты  первого задания на максимальный балл.

Для каждой лабораторной работы назначается день защиты согласно силлабусу дисциплины. За каждый просроченный день  отнимается 1% от общего балла, полученного студентом при  защите лабораторной работы.

2 Варианты заданий к лабораторным работам

 

2.1 Тема1.  Алгоритмы линейной структуры

 

Общие сведения.

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

Простейшая программа на языке  Си состоит из заголовка и тела основной функции main(). В заголовке указываются библиотечные файлы, содержащие функции, которые используются в программе. Основная часть программы на Си  начинается с оператора void main (), который указывает стартовую точку программы. Структура программы на языке  Си выглядит следующим образом:

 

# include  <stdio.h>

# include  <math.h>

                   void main()

                   { объявления локальных переменных, констант;

                     выражения;

                     функции;

                    операторы;

                   }

 

Функция форматированного вывода  printf()

Синтаксис функции:

printf(<управляющая строка>, <список переменных>);

где <список переменных> - перечень идентификаторов переменных, значения которых необходимо вывести на экран.

<управляющая строка> - строка, которая представляет собой заключенный в двойные кавычки список спецификаторов: %i – для ввода целых чисел со знаком, %u – для ввода целых беззнаковых целых, %f – для ввода дробных чисел, %с – для ввода символа, %s – для ввода строки.

Функция форматированного ввода scanf()

Синтаксис:

scanf(<управляющая строка>, <список адресов переменных>);

где <управляющая строка> - строка, которая может содержать только спецификации формата, перечень допустимых значений спецификаций тот же самый, что и для функции  printf();

<список адресов переменных> – содержит перечисленные через запятую адреса переменных, вводимых функцией. Адрес переменной указывается символом & и далее идет идентификатор переменной, например, адрес переменной stud обозначается символами &stud.

В Си существует 5 базовых типов данных:

char - символьный тип;

int - целый тип;

float - тип данных с плавающей точкой;

double - тип данных с плавающей точкой удвоенной длины;

viod - пустой тип, не имеющий никакого значения.

 

Лабораторная работа №1. Словесная и графическая запись линейных алгоритмов

 

Цель работы: научиться разрабатывать алгоритмы линейной структуры, словесно и графически записывать линейные алгоритмы.

Варианты  задания А

1. Y=                 11. Y=

2. Y=                                   12. Y=

3. Y=                         13. Y=

4. Y=                                         14. Y=

5. Y=                          15. Y=)

6. Y=                              16.Y=

7. Y=                            17. Y=

8. Y=                      18. .        

9.                     19.

10.                     20.

21. Y=                           22. .        

23.                     24.

25.                      

Варианты  задания Б.

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

2. Дана треугольная пирамида, гранями которой являются равносторонние треугольники. Известна длина стороны основания а. Найти площадь основания и площадь боковых граней.

3. Дана пятиугольная пирамида, гранями которой являются равносторонние треугольники. Известна длина стороны основания а. Найти площадь основания и площадь боковых граней.

4. Даны два числа. Найти среднее арифметическое их квадратов и среднее арифметическое их модулей. 

5. Скорость лодки в стоячей воде V км/ч, скорость течения реки U км/ч (U < V). Время движения лодки по озеру T1 ч, а по реке (против течения) — T2 ч. Определить путь S, пройденный лодкой. 

6. Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили удаляются друг от друга. 

7. Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили первоначально движутся навстречу друг другу. 

8. Найти периметр и площадь прямоугольного треугольника, если даны длины его катетов a и b. 

9. Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба. 

10. Найти длину окружности и площадь круга заданного радиуса R. В качестве значения Pi использовать 3.14.

 11. Найти площадь кольца, внутренний радиус которого равен R1, а внешний радиус равен R2 (R1 < R2). В качестве значения Pi использовать 3.14. 

12. Дана сторона равностороннего треугольника. Найти площадь этого треугольника и радиусы вписанной и описанной окружностей. 

13. Дана длина окружности. Найти площадь круга, ограниченного этой окружностью. В качестве значения Pi использовать 3.14. 

14. Дана площадь круга. Найти длину окружности, ограничивающей этот круг. В качестве значения Pi использовать 3.14. 

15. Найти периметр и площадь равнобедренной трапеции с основаниями a и b (a > b) и углом alpha при большем основании (угол дан в радианах). 

16. Найти периметр и площадь прямоугольной трапеции с основаниями a и b (a > b) и острым углом alpha (угол дан в радианах).

 17. Найти расстояние между двумя точками с заданными координатами (x1, y1) и (x2, y2).

18. Дана длина ребра куба. Найти объем куба и площадь его боковой поверхности.

19. Три сопротивления R1, R2, R3 соединены параллельно. Найти сопротивление соединения.

20. Дано действительное число а. Не пользуясь никакими другими операциями, кроме умножения, получить: а) а¹⁰ за четыре операции;; б) а¹³ за пять операций; в) а⁶⁴ за шесть операций.

21. Студент начал решать задачи данного урока программирования, когда электронные часы показывали h1 часов и min1 минут, а закончил, когда было h2 часов и min2 минут. Составьте программу, позволяющую определить, сколько времени студент решал эти задачи. (Будем считать, что задачи решались не дольше суток.).

22. Дано действительное число а. Не пользуясь никакими другими операциями, кроме умножения, получить: а) а⁴ за две операции; б) а⁶ за три операции; в) а⁷ за четыре операции.

23. Даны два ненулевых числа. Найти их сумму, разность, произведение и частное. 

24. Дано трехзначное число. Найти сумму и произведение его цифр.

25. Даны два двухзначных числа А и В. Получить число С, первой цифрой которого является сумма первых цифр чисел А и В, второй цифрой- сумма вторых цифр чисел А и В.

Пример задания А.

Разработать алгоритм вычисления математического выражения

Задание: вычислить

 

 

Словесная запись:

1) присвоим значения переменным x,y; 

2) ;

3) ;

4)

5) ;

6) .

 

На рисунке 2.1 приведена графическое описание алгоритма решения задания А  в виде блок-схемы.

 

Рисунок 2.1 - Блок-схема задания А

 

Лабораторная работа №2. Программная  реализация  линейных алгоритмов

 

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

Варианты заданий даны в лабораторной работе №1.

Пример

Вычислить:   .

Программное описание алгоритма:

#include <stdio.h>

#include <math.h>

int main(void)

{ int x,y;

float dop,a,b,c, rezult,z;

 puts(" ЛАБОРАТОРНАЯ РАБОТА N1 - ЛИНЕЙНАЯ ПРОГРАММА ");

    puts("============================================");

printf ("введите x\nx=");

scanf("%d",&x);

printf ("введите y\ny=");

scanf("%d",&y);

printf ("введите z\nz=");

scanf("%d",&z);

        dop=fabs(y-x);

       a=pow(x,y+1)+exp(y-1);

       b=1+x*fabs(y-tan(z));

      c=0.5*pow(dop,2)-pow(dop,3)/3;

      rezult=a/b*(1+dop)+c;

    printf("\a\n ОТВЕТ:  rezult =%lf", rezult);

        printf (“Для завершения нажмите клавишу <Enter>”);

   getch( );  /* ЗАДЕРЖКА ДО НАЖАТИЯ ЛЮБОЙ КЛАВИШИ */

   return 0;

}

Результат выполнения программы:

 

ЛАБОРАТОРНАЯ РАБОТА N1 - ЛИНЕЙНАЯ ПРОГРАММА ============================================

введите x

x=2

введите y

y=3

введите z

z=1

ОТВЕТ:  rezult =6.849254

 

Контрольные вопросы.

1)     Для каких задач разрабатывается алгоритм линейной структуры?

2)     Как запустить программу на трансляцию и выполнение?

3)     Как записываются операторы начала и конца программы?

4)     Из каких разделов состоит программа на языке С?

5)     В какой последовательности должны быть записаны разделы программы на языке С?

6)     Как записываются операторы вывода на экран в С?

7)     Каково назначение <управляющая строка>?

8)      Перечислите базовые типы данных.

2.2 Тема 2.  Алгоритмы разветвляющейся структуры

 

Общие сведения.

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

В языке Си имеется возможность нелинейного хода программы, т.е. выполнения операторов не в том порядке, в котором они записаны. Такую возможность нам предоставляют разветвляющиеся алгоритмы. Они могут быть реализованы одним из трех способов:

1)     с использованием операторов перехода;

2)     условного оператора;

3)     оператора выбора.

Оператор перехода GOTO

Оператор перехода имеет вид

           GOTO <метка>;

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

Условный оператор

Условный оператор IF имеет два вида:

а) полная форма

         if (условие) оператор 1

              else оператор 2

б) сокращённая форма

         if (условие) оператор 1

где оператор 1, оператор 2 – любые операторы, включая условия и составные;  условие – в общем случае логическое выражение.

Если условие истинно, выполняется оператор 1, если ложно, то выполняется оператор 2.

Оператор выбора SWITCH CASE

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

Оператор выбора имеет следующий вид:

swich (выражение)

{

case константа 1:

        оператор 1;

        break;

…………………………    

case константа N:

        оператор N;

        break

        default: оператор

}

где выражение – целочисленная переменная или соотношение;

      константаN: - метка в виде константы или константного выражения;

      default – метка на оператор, которая выполняется в том случае, если выражение не совпадает ни с одной константной меткой;          

      break  - оператор выхода из переключателя.

 

Лабораторная работа №3 Словесная и графическая запись  разветвляющихся алгоритмов

 

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

Варианты  задания А

                           

 

                   

                     6.

 

7.         8.

 

 9.       10.

 

11.

 

 

12.    13.  

 

14.    15.   

 

16.        17.       

18.  19.     20.

 

21. 22.            23.

 

 24.       25.

Варианты  задания Б

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

2 Вводится число Т – порядковый день в году. Определить номер месяца М и дня недели D, соответствующих Т.(Например, если Т=365 . то М=12, а D=31).

3 Вводится номер месяца М и дня D. Определить порядковый номер дня в году Т соответсвующий этой дате.

4 Вводится номер месяца М и дня D. Определить день недели с датой М и D, считая, что год начинается с понедельника.

5  Даны четыре числа. Определить, сколько среди них отрицательных и сколько положительных.

6. Определить, какая из двух точек - M1(x1,y1) или M2(x2,y2) - расположена ближе к началу координат. Вывести на экран дисплея координаты этой точки.

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

8. Даны действительные числа a, b, c, x, y. Выяснить, пройдет ли кирпич с ребрами a,b,c в прямоугольное отверстие со сторонами x и y. Просовывать кирпич в отверстие разрешается только так, чтобы каждое из его ребер было параллельно или перпендикулярно каждой из сторон отверстия.

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

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

11. Напишите программу, определяющую период суток. Если до 12⁰⁰ – «утро», до 18⁰⁰ – «день»,  до 0⁰⁰ – «вечер», до 6⁰⁰ – «ночь», с выдачей соответствующих запросов и сообщений.

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

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

14. Сможет ли шар радиуса R пройти в ромбообразное отверстие со стороной P и острым углом Q?

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

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

-         среди цифр заданного трехзначного числа есть одинаковые.

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

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

18. Даны длины трех отрезков a, b, c. Если можно построить треугольник по этим трем отрезкам, то вычислить его периметр и площадь.

19. Определить, попадает ли точка M(x,y) в круг радиусом r с центром в точке (x0,y0).

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

21. Даны действительные положительные числа x, y, z. Выяснить, существует ли треугольник с длинами сторон x, y, z.

22. Даны действительные числа x, y. Если x, y отрицательны, то каждое значение заменить его модулем; если отрицательное только одно из них, то оба значения увеличить на 0.5; если оба значения не отрицательны и ни одно из них не принадлежит отрезку [0.5, 2.0], то оба значения уменьшить в 10 раз; в остальных случаях x, y оставить без изменения.

23. Определить и вывести на печать номер квадранта, в котором расположена точка М(x,y), x и y - заданные вещественные числа.

24. Из величин, определяемых выражениями a=sinx, b=cosx, c=ln|x| при заданном х, определить и вывести на экран дисплея минимальное значение.

25. Напишите программу, которая определяет сумму двух чисел, если сумма больше 100, то полученный результат умножается на 2, если условие не выполняется, то результат умножается на 3.

Пример

,

Словесная запись:

1) присвоим значения переменным n,S,e;

2) проверяем:  если, то вычисляем   , иначе переходим к п. 3;

3) проверяем:  если , то     вычисляем   , иначе переходим к п. 4;

4) вывод сообщения: задача не имеет решения.

На рисунке 2.1 приведена графическое описание алгоритма решения задания А  в виде блок-схемы

Рисунок 2.2 - Блок-схема задания А

 

Лабораторная работа №4 Программная  реализация   разветвляющихся алгоритмов

 

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

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

Варианты заданий даны в лабораторной работе №3

Пример

Задание: Составить программу, вычисляющую:

 

#include<stdio.h>

#include<conio.h>

#include<math.h>

void main()

{ int S,n;

float K;

printf("\n Введите данные");

printf("\n S=");

scanf("%d",&S);

printf("\n n=");

scanf("%d",&n);

if (fabs(n)<S && S<2*fabs(n))

K=sqrt(fabs(S*exp(2)-n*exp(-2))); else

if (S>=2*fabs(n))

K=sqrt(fabs(S*n)); else

printf("\n Нет решенния");

printf("\n Результат K=%f",K);

getch();

 

Результат выполнения программы:

 

Введите данные

S=7

n=1

Результат K=2.645751

 

Контрольные вопросы:

1)  Какие виды условного оператора вы знаете?

2)  Как выполняются оператор выбора?

3)  Какие операторы используются для программирования разветвлений?

4)  Как выполняются операторы перехода?

5)   Как записывается полная форма оператора перехода?

6)  Как записывается сокращённая форма оператора перехода?

7)  Для чего используется оператор break?

8)  Для чего используется метка default?

 

2.3 Тема 3 Алгоритмы циклической структуры

 

Лабораторная работа №5 Словесная и графическая запись циклических алгоритмов

 

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

Общие сведения

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

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

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

Циклы бывают:

1)     c предусловием;

2)     c постусловием;

3)     с параметрами.

Операторы циклов  в языке С

Оператор цикла  с предусловием:

while(условие)

    {

     //операторы тела цикла

    }

Операторные скобки можно не писать, если в цикле один оператор. Цикл c предусловием работает следующим образом: сначала проверяется логическое условие, если оно истинно, то выполняются операторы тела цикла, если условие ложно, то выполняются операторы после цикла.

Оператор цикла с постусловием:

do

{

     // операторы тела цикла

}while(условие);

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

Оператор цикла с параметром:

for(начало цикла; условие конца цикла; изменение шага цикла)

{

     //операторы тела цикла

}

Циклы с параметром работают следующим образом: пока управляющая переменная (счетчик цикла - j) меньше(больше) какого-то значения n, то выполняются операторы цикла, при этом с каждым витком цикла управляющая переменная меняет свое значение на какое-то определенное число, называемое шагом цикла.

Вложенные циклы.

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

Операторы управления циклом

Оператор break.  Как только компилятор встречает оператор break, он сразу же заканчивает выполнения циклов не зависимо от количества оставшихся операторов и витков цикла, и начинает выполнять операторы, которые стоят сразу после цикла.

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

Варианты  задания А.

Составить блок-схему и программу вычисления суммы:

       1.                               14.       

       2.                                    15.

3.                                         16.   

4.                                               17.    

                5.                                18.

 

6.                                     19.

7.                                        20.        

8.                                       21.

9.                                          22..

 

10.                                           23.

                11.                                          24.                        

               12.                                    25.            

               13..

 Варианты  задания Б.

1. Сколько можно купить быков, коров, телят, платя за быка 10 рублей, за корову 5 рублей, а за теленка 0,5 рублей, если на 100 рублей надо купить 100 голов скота (ответ: коров-9, бык-1,телят-90).

2. В компьютер вводятся по очереди координаты N точек. Определить, сколько из них попадет в круг радиусом R с центром в точке (а,в).

3. У гусей и кроликов вместе 24 лапы. Сколько может быть кроликов и гусей (указать все сочетания).

4. В компьютер вводятся по очереди данные о росте N учащихся группы. Определить средний рост учащихся группы.

5. Одноклеточная амеба каждые три часа делится на 2 клетки. Определить, сколько амеб будет через 3,6,9,12,…,24 часа (ответ: 256).

6. Составьте программу вычисления степени числа А с натуральным показателем N (записать варианты программы с 3 видами циклов: for, while, do…while).

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

8. С помощью оператора WHILE написать программу, которая ищет произведение 10 произвольно введенных чисел и выводит его на печать.

9. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый день он увеличивал норму на 10% нормы предыдущего дня. Какой суммарный путь пробежит спортсмен за 7 дней?

10. С помощью оператора WHILE напишите программу вывода всех четных чисел в диапазоне от 22 до 100 включительно.

11. Составить программу для вычисления значений функции F(x) на отрезке [a,b] с шагом h. Результат представить в виде таблицы, первый столбец которой - значения аргумента, второй – соответственно,  значение функции F(x)=cosx+ctgx.

12. С помощью оператора WHILE напишите программу, вычисляющую сумму квадратов чисел от 1 до введенного вами целого числа.

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

14. Составить программу поиска четырехзначных чисел, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.

15. С помощью оператора цикла с постусловием напишите программу-фильтр, которая вводит любые символы, но комментирует только буквы русского алфавита. Завершение работы - по нажатию буквы ‘Я’.

16. Найти все двузначные числа, сумма цифр которых не меняется при умножении числа на 2,3,4,5,6,7,8,9.

17. Найти все трехзначные числа, сумма цифр которых равна данному целому числу.

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

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

20. Найти все двузначные числа, сумма квадратов цифр которых делится на 17.

21. Начальный вклад в банк составляет а рублей. Через сколько лет он станет больше b рублей? Каждый год вклад увеличивается на 3%.

22. Ежегодный прирост рыбы в пруду составляет 15%.  Запасы рыбы оценены в А тонн. Ежегодный план отлова В тонн. Подсчитать, сколько лет можно выдерживать заданный план?

23. Каждая бактерия делится на две в течение одной минуты. В начальный момент имеется A бактерий. Сколько времени потребуется, чтобы количество бактерий превзошло X?

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

25. Найти все натуральные числа от 1 до N, представимые в  виде суммы кубов двух натуральных чисел.

Пример: разработать алгоритм вычисления суммы:

 

Словесная запись:

1) присвоим значение переменным  х, n;

2) обнулим переменную S=0;

3) присвоим первоначальное значение переменной k=1;

4) начало цикла пока k<n делаем:

 -;

 - k=k+1;

5) конец цикла.

На рисунке 2.3 приведена графическое описание алгоритма решения задания А  в виде блок-схемы.

Рисунок 2.3 - Блок-схема задания А

 

Лабораторная работа №6 Программная  реализация  циклических алгоритмов

 

Цель работы: научиться  составлять программы. реализующих циклические алгоритмы, изучить циклические операторы for, while, do – while.

Варианты заданий даны в лабораторной работе №5.

 Пример.

Задание: составить программу вычисляющую:

,

 

Текст  программы может иметь следующий вид:

 

#include <stdio.h>

#include <math.h>

int main()

{int n, x;

float S;

printf ("\n Введите значение  n\n n=");

scanf ("%d", &n);

printf ("\n Введите значение  x\n x=");

scanf ("%d", &x);

S=0;

k=1;

while (k<n)

{  S=S+(cos(k*x)/k);

  k=k+1;

}

printf ("\n Сумма S=%f", S);

getch();

return 0;

}

Результат выполнения программы:

 

Введите значение  n

 n=4

Введите значение  x

 x=1

Сумма S=0.002231

 

Контрольные вопросы:

1)     Как записывается и как работает оператор FOR?

2)     Для организации каких циклов применим оператор FOR?

3)     В чем отличие оператора WHILE от оператора  DO WHILE?

4)     Как программируются циклические алгоритмы с явно заданным числом повторений цикла?

5)     Как программируются циклические алгоритмы с заранее неизвестным числом повторений цикла?

6)     Напишите оператор цикла, который не выполняется ни разу.

7)     В каких случаях используются операторные скобки?

8)     Как работают операторы управления циклом

2.4 Тема 4.  Алгоритмы обработки одномерных массивов 

 

Общие сведения.

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

При описании массива необходимо указать:

- тип элементов;

- имя массива;

- размерность массива.

Общая форма описания массива имеет вид:

тип  имя_масссива [размер1][размер 2]….;

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

float   A[5],   B[25];

При описании можно инициализировать элементы массива заданными значениями.

   Например:

int   D[5]={23, 45, 32, 12, 88};

В языке Си элементы в массиве нумеруются, начиная с нуля, т.е. индекс первого элемента равен 0, а индекс последнего элемента – на единицу меньше размера массива.

Связь между указателями и массивами. В языке Си массивы и указатели тесно связаны.

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

Указатель объявляется следующим образом:

                            тип *<имя переменной>;

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

Унарная операция &, примененная к некоторой переменной, показывает, что нам нужен адрес этой переменной, а не ее текущее значение. Если переменная uk объявлена как указатель, то оператор присваивания uk=&x означает: "взять адрес переменной x и присвоить его значение переменной-указателю uk".

  Унарная операция *. примененная к указателю, обеспечивает доступ к содержимому ячейки памяти, на которую ссылается указатель. Например, *uk можно описать словами как "то, что содержится по адресу, на который указывает uk".

Доступ к любому элементу массива может быть выполнен с помощью указателей. Если uk -указатель на целое, описанный как int *uk, то uk после выполнения операции uk=&a[0] содержит адрес a[0], а uk+i  указывает на i -й элемент массива. Таким образом, uk+i является адресом a[i]. Так как имя массива в программе отождествляется с адресом его первого элемента, то выражение uk=&a[0] эквивалентно такому: uk=a. Поэтому значение a[i] можно записать как *(a+i). Применив к этим двум элементам операцию взятия адреса, получим, что &a[i] и a+i идентичны.

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

#include <stdio.h>
main()
{
char *uk1,*uk2;
uk1=uk2=”Алгоритмы, структуры данных и программирование”

  putchar(*uk2++);
putchar('\n');
while(--uk2 >= uk1)
putchar(*uk2);
putchar('\n');
}

В самом начале указателям uk1 и uk2 присваивается начальный адрес строки " Алгоритмы, структуры данных и программирование ". Затем строка посимвольно печатается и одновременно указатель uk2 смещается вдоль строки. В конце вывода uk2 указывает на последний символ исходной строки. Во втором цикле while все тот же указатель uk2 начинает изменяться в обратном направлении, уменьшаясь до тех пор, пока он не будет указывать на нулевой элемент массива, обеспечивая выдачу строки в обратном порядке.

 

Лабораторная работа №7 Словесная и графическая запись алгоритмов обработки одномерных массивов 

 

Цель работы: научиться словесно и  графически описывать алгоритмы обработки одномерных массивов.

Варианты  задания.

1.    Дан массив А(10). Найти сумму и количество положительных элементов, предшествующих первому нулевому элементу.

2.    Дан массив А(20). Найти минимальный и максимальный элементы массива и их порядковые номера.

3.    Дан массив А(15). Найти минимальный элемент среди элементов, расположенных на нечетных позициях массива, а также определить количество и произведение ненулевых элементов, следующих за первым минимальным элементом.

4.    Дан массив А(30). Найти сумму и количество положительных элементов, расположенных между минимальным и максимальным элементами массива.

5.    Если у массива А(30) есть элемент, равный В, то переменной Х присвоить значение, равное сумме всех положительных четных элементов, предшествующих первому по порядку такому элементу, иначе переменной Х присвоить 0.

6. Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам первый элемент. Первый элемент массива не изменять. 

 7. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам последний  элемент. Последний элемент массива не изменять. 

8. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам среднеарифметическое значение первого и последнего элементов.

 9. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам первый  элемент. Первый элемент массива не изменять. 

 10. Поменять местами минимальный и максимальный элементы массива размера 10. 

 11. Дан массив A[N]. Все положительные  элементы уменьшить на значение  минимального элемента. 

12. Дан массив A[N]. Все отрицательные элементы увеличить на значение максимального элемента. 

 13. Дан массив размера 10. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами. 

 14. Дан массив размера N. Найти произведение количества  положительных и отрицательных элементов. 

15. Дан массив размера N. Найти разницу между количеством  положительных и отрицательных элементов. 

16. Дан массив A[N]. Найти целую часть среднего арифметического значения положительных элементов массива A[N].

17. Дан массив A[N]. Найти целую часть среднего арифметического значения отрицательных элементов массива A[N].

18. Дан массив A[N]. Найти целую часть среднего арифметического значения четных элементов массива A[N].

19. Дан массив A[N]. Найти целую часть среднего арифметического значения нечетных элементов массива A[N].

20. Дан массив A[N]. Все отрицательные  элементы уменьшить на значение  минимального элемента. 

21. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N] следующим образом: вначале заполнить  элементами с четными индексами, а затем — с нечетными. 

 22. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N] следующим образом: вначале заполнить  элементами с |нечетными индексами, а затем —с четными. 

 23. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству: A[1] < A[i] < A[10]. Незаполненные элементы массива В[N] заполнить оставшимися элементами массива A[N].

24. Дан массив A[N]. Заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству: A[1] < A[i] или A[i]  < A[10]. Незаполненные элементы массива В[N] заполнить оставшимися элементами массива A[N].

25. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам первый элемент. Первый элементы массива не изменять. 

Варианты  задания Б.

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

1. Дан массив A[N]. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов

2. Дан массив A[N]. Осуществить сдвиг вправо на k позиций, где k – число отрицательных элементов

3. Дан массив A[N]. Осуществить сдвиг влево на k позиций, где k – число нулевых элементов массива A[N].

4. Дан массив A[N]. Осуществить сдвиг вправо на k позиций, где k – число ненулевых элементов массива A[N].

5. Дан целочисленный массив размера N. Осуществить сдвиг вправо на k позиций, где k – число четных элементов

6. Дан целочисленный массив размера N. Осуществить сдвиг вправо на k позиций, где k – число нечетных элементов

7. Дан целочисленный массив размера N. Осуществить сдвиг влево на k позиций, где k – сумма нечетных элементов

8. Дан целочисленный массив размера N. Осуществить сдвиг влево на k позиций, где k – среднеарифметическое значение первого и последнего элементов.

9. Дан целочисленный массив размера N. Осуществить сдвиг вправо на k позиций, где k – сумма четных элементов

10. Дан целочисленный массив размера N. Осуществить сдвиг вправо на k позиций, где k – число элементов, расположенных между его минимальным и максимальным элементами. 

11. Дан массив A[N]. Все положительные  элементы уменьшить на значение  минимального элемента. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов

12. Дан массив A[N]. Все отрицательные элементы увеличить на значение максимального элемента. Осуществить сдвиг влево на k позиций, где k – число отрицательных элементов

13. Дан массив размера 10. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – k – число элементов, расположенных между его минимальным и максимальным элементами

14. Дан массив размера N. Осуществить циклический сдвиг элементов массива влево на k позиций, где k – индекс минимального элемента. 

15. Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента. 

16. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения положительных элементов массива A[N].

17. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения отрицательных элементов массива A[N].

18. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения четных элементов массива A[N].

19. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения нечетных элементов массива A[N].

20. Дан массив A[N]. Все отрицательные  элементы уменьшить на значение  минимального элемента. Осуществить сдвиг вправо на k позиций, где k – число положительных элементов

21. Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – количество максимальных элементов. 

22. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – остаток среднего арифметического значения положительных элементов массива A[N].

23. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – остаток среднего арифметического значения отрицательных элементов массива A[N].

24. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – остаток среднего арифметического значения четных элементов массива A[N].

25. Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – остаток среднего арифметического значения нечетных элементов массива A[N].

Пример 1. Дан массив А[n].Заполнить массив B[n] элементами массива А[n] , начиная с последнего. Найти число положительных элементов массива B[n].

Словесная запись:

1) начало алгоритма;

2) задать размерность массива, то есть константе  n присвоить заданное значение;

3) заполнить массив А[n] случайными числами;

4) обнулить переменную pol и j=n;

5) организовать цикл с заданными параметрами от i=1; n;1.   Внутри цикла:

   -  элементу массива B[n] присвоить элемент массива А[n], то есть B[j]= А[i];

   -  j= j-1;

   - проверить: если B[j]>=0, то  число положительных элементов увеличить на 1, т.е.   pol= pol+1,  иначе перейти к следующему циклу;

6) вывести число положительных элементов массива B[n];

7) вывести элементы массива B[n];

8) конец алгоритма.

На рисунке 2.4 приведена графическое описание алгоритма решения задания А  в виде блок-схемы.

Рисунок 2.4 - Блок-схема задания А

 

 

Пример 2. Дан массив А[n].Осуществить сдвиг вправо на К позиций.

Словесная запись:

1) начало алгоритма;

2) задать размерность массива, то есть константе  n присвоить заданное значение;

3) заполнить массив a[n] случайными числами;

4) задать количество сдвигов k;

5) организовать цикл с заданными параметрами от i=1; k;1.    Внутри цикла:

        - запомнить последний элемент buf=a[n];

        - организовать цикл с заданными параметрами от j = n; 1;-1.   Внутри цикла:  

        - последующему элементу присвоить предыдущий,  то   есть

a[j]=a[j-1];

                - по окончании цикла по j первому элементу присвоить значение последнего, то   есть a[1]= a[n];

6) по окончании цикла по i вывести элементы массива a[n];

7) конец алгоритма.

На рисунке 2.6 приведена графическое описание алгоритма решения задания Б  в виде блок-схемы.

Рисунок 2.5 - Блок-схема задания Б

Лабораторная работа №8 Программная  реализация алгоритмов обработки одномерных массивов 

 

Цель работы: приобретение навыков программирования при решении задач с использованием структур данных типа массив. Перед выполнением работы необходимо изучить правила описания и использования переменных типа массив.

Варианты заданий даны в лабораторной работе №7.

Пример 1. Дан массив А[n].Заполнить массив B[n] элементами массива А[n] , начиная с последнего. Найти число положительных элементов массива B[n].

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

#include <stdlib.h>

# include <conio.h>

# include <stdio.h>

#define n 10

int main ()

{  int buf,j,pol,i,b[n], a[n];

       for (i = 0; i < n; i++)

         a[i]=rand()%10-5;

 pol=0;

   printf ("\n \n Сгенерированный массив a[n] \n");

  for (i=0;i< n;i++)

   printf ("%d ",a[i]);

   j=n-1;

  for (i=0;i< n;i++)

    {b[i]=a[n-1];

      n=n-1;

       if (b[i]>=0)pol++;    }

printf ("\n Число положительных элементов \n pol=%d",pol);

printf ("\n \n вывод массива b[n] \n");

for (i=0;i< n;i++)

   printf ("%d ",b[i]);

     for (i=0;i<pol;i++)

return 0;}

 

Результат выполнения программы:

 

Сгенерированный массив a[n]

1  2  3 -4 -5 -1 -2 -3 -7 9

Число положительных элементов

 pol=4

вывод массива b[n]

9 -7 -3 -2 -1 -5 -4 3 2 1

Пример 2. Дан массив А[n].Осуществить сдвиг вправо на К позиций.

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

#include <stdlib.h>

# include <conio.h>

# include <stdio.h>

#define n 10

int main ()

{  int buf,j, K,i, a[n];

       for (i = 0; i < n; i++)

         a[i]=rand()%10-5;

    K=4;

                      printf ("\n \n Сгенерированный массив a[n]\n");

 for (i=0;i<n;i++)

   printf ("%d ",a[i]);

     for (i=0;i<K;i++)

   { buf=a[n-1];

      for(j=n-1;j>0;j--)

      a[j]=a[j-1];

      a[0]=buf;    }

           printf ("\n \n Сдвиг элементов массива a[n]на %d позиций \n", K);

    for (i=0;i<n;i++)

      printf ("%d ",a[i]);

    printf ("\n");

  system("PAUSE");

  return 0;}

 

Результат выполнения программы:

 

Сгенерированный массив a[n]

9 -7 -3 -2 -1 -5 -4 3 2 1

Сдвиг элементов массива a[n]на 4 позиций

-4 3 2 1 9 -7 -3 -2 -1 -5

 

Контрольные вопросы:

1)    Каким образом определяются переменные типа массив?

2)    Какие операторы языка Си  используются при обработке элементов массива?

3)    Как осуществляется доступ к отдельному элементу одномерного массива с помощью указателя?

4)    Каким образом выводятся элементы массива на экран? 

5)    Какой результат унарной операции &?

6)    Какой результат унарной операции *?

7)    Выражение uk=&a[0] эквивалентно  uk=a?

8)    Выражения &a[i] и a+i идентичны?

 

2.5 Тема 5 Алгоритмы обработки двумерных массивов 

 

Общие сведения.

Массивы - это последовательная группа ячеек памяти, имеющих одинаковое имя. Доступ к отдельным элементам массивов организуется посредством указания имени массива и порядкового номера (индекса) необходимого элемента. Индекс определяет положение элемента относительно начала массива. Поскольку элементом массива может быть массив, можно определить и многомерные массивы, простейшей формой  которых является двумерный массив. Двумерные массивы называют также матрицами. При описании массива первый размер  определяет количество строк, а второй - количество столбцов. Двумерный массив int a[2][4]

а[0][0] a[0][l] a[0][2] a[0][3]

а[1][0] a[1][l] a[1][2] a[1][3]

Первый индекс - номер строки, второй индекс - номер столбца.

Рассмотрим пример программы, которая заполняет элементы матрицы случайными числами a[n][n] и осуществляет вывод данных в виде матрицы.

#include<stdio.h>

#include<stdlib.h>

#define n 10

void main()

{  int a[n][n],i,j,k,*pa,s1;

    pa=&a[0][0];

    for(i=0;i<n;i++)       

   {for(j=0;j<n;j++)

      {*pa=rand()%9; 

         printf("%d  ",*pa);   pa++;  }

  printf("\n");}

     getch();

}

 

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

 

Цель работы: научиться словесно и  графически описывать алгоритмы обработки двумерных массивов.

Варианты  задания А.

1.   Дан массив A[5,5]. Найти минимальный элемент среди элементов, расположенных в нечетных строках массива.

2.   Дан массив A[6,6]. Если среди элементов массива есть элемент, равный В, то переменной Х присвоить значение, равное сумме положительных элементов, расположенных слева от этого элемента, иначе переменной Х присвоить 0.

3.   Дан массив A[5,5]. Построить массив В(5) по следующему правилу: В(J) присвоить максимальный элемент J - го столбца массива А.

4.   Дан массив A[7,7]. Найти произведение и количество четных положительных элементов, расположенных выше главной диагонали.

5.   Дан массив A[6,6]. Найти суммы положительных элементов строк и присвоить их элементам побочной диагонали соответствующих строк.

6.   Дан массив A[5,5]. Построить массив В(5) по следующему правилу: В(I) присвоить 1, если в I-той строке массива есть хотя бы один отрицательный элемент, в противном случае В(I) присвоить 0.

7.   Дан массив A[6,6]. Построить массив В(6) по следующему правилу: В(J) присвоить 1, если в J-ом столбце массива А количество ненулевых элементов больше количества нулевых элементов, в противном случае В(J) присвоить 0.

8.   Дан массив A[8,8]. Найти максимальный элемент среди элементов, расположенных выше побочной диагонали. Поменять местами элементы строки и столбца, на пересечении которых находится максимальный элемент.

9.   Дан массив A[7,7]. Построить массив В(7) по следующему правилу: В(I) присвоить 1, если в I-той строке массива представляют возрастающую последовательность, в противном случае В(I) присвоить 0.

10.   Дан массив A[6,6]. Построить массив В(6) по следующему правилу: В(1) присвоить  количество нулевых элементов главной диагонали, В(2) присвоить  количество нулевых элементов диагонали, расположенной выше и параллельно главной диагонали и т.д.

11.   Дан массив A[5,5]. Найти минимальную сумму положительных элементов диагоналей, параллельных побочной диагонали.

12.   Дан массив A[6,6]. В каждой строке найти максимальный элемент, в каждом столбце найти минимальный элемент. Найденные элементы соответствующей строки и столбца поменять местами.

13.   Дан массив A[7,7]. Упорядочить элементы массива построчно.

14.   Дан массив A[6,6]. Найти мах среди элементов, повторившихся более одного раза.

15.   Дан массив A[8,8]. Найти количество локальных максимумов массива.

16.   Дан массив A[7,7]. Найти количество столбцов, составленных из попарно различных элементов.

17.   Дан массив A[8,8]. Найти минимальный элемент среди элементов строк, упорядоченных либо по возрастанию, либо по убыванию.

18.   Дан массив A[7,7]. Вывести строки массива по убыванию максимальных элементов строк массива.

19.   Дан массив A[8,8]. Найти максимальное произведение ненулевых элементов диагоналей, параллельных главной диагонали.

20.   Дана матрица A[7,7]. Найти наибольший элемент среди стоящих на главной и побочной диагоналях и поменять его местами с элементом, стоящим на пересечении этих диагоналей.

21.   Дан двумерный массив целых чисел. Поменять местами строку, содержащую максимум массива, со строкой, содержащей его минимум.

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

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

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

25.   В двумерном массиве, состоящем из целочисленных элементов, поменять местами в каждом столбце первый принадлежащий отрезку [a, b] и первый отрицательный элементы;

Варианты  задания Б.

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

 2. Дана целочисленная прямоугольная матрица.

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

 3. Дана целочисленная прямоугольная матрица. Определить номер строки, в которой находится самая длинная серия одинаковых элементов.

4. Дана целочисленная квадратная матрица. Определить  максимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

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

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

Примечание:

Матрица А имеет седловую точку А_ij, если A_ij является минимальным элементом в i-й строке и максимальным в j-м столбце.

 7. Для заданной матрицы размером 8 на 8 найти сумму элементов в тех строках, которые содержат хотя бы один отрица­тельный элемент.

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

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

10. Дана действительная квадратная матрица порядка n. Найти сумму модулей элементов, расположенных выше главной диагонали.

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

 12. Дана действительная квадратная матрица порядка n. Найти номер первой из строк, содержащих хотя бы один положительный элемент.

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

14. Дана действительная квадратная матрица порядка n. Найти сумму положительных элементов нечетных строк.

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

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

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

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

19. Дана целочисленная квадратная матрица. Определить минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

20. .Соседями элемента Аij в матрице назовем элементы А_i-1,j-1. А_i-1,j, А_i-1,j+1, А_i,j-1, А_i,j+1, А_i+1,j-1. А_i+1,j, А_i+1,j+1. Операция сглаживания матрицы дает новую матрицу того же размера, каждый элемент которой получается как среднее арифметическое имеющихся соседей соответствующего элемента исходной матрицы В сглаженной матрице найти сумму модулей элементов, расположенных ниже главной диагонали.

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

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

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

24. Дана действительная квадратная матрица порядка n. Найти сумму положительных элементов четных строк.

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

Пример 1.  Дана целочисленная матрица размером 8 на 8. Найти такие k, что k-я строка  матрицы совпадает с k-м столбцом. Номера таких строк вывести

 

Словесная запись:

1) начало алгоритма;

2) задать размерность массива, то есть константе  n и m присвоить значение 8;

3) заполнить массив a[n][m];

4) организовать внешний цикл по k =1; n;1.  Внутри  цикла по k:

-  признаку совпадения p присвоить значение 1, т.е. p =1

-  организовать внутренний цикл по j =1; m;1.  Внутри цикла по j:

                  -  проверить на совпадение элементов k-ой строки с элементами

k-ого столбца. Если элементы не совпадают , т.е. a [k][j] не равно a [j][ k], то:

         - признаку совпадения p присвоить значение p =0;

         - прервать внутренний цикл по j;

         -  перейти на внешний цикл  по k, в противном случае продолжить внутренний цикл;

                 - по окончании внутреннего цикла проверить: если p =1, то вывести номер k -ой строки;

              - по окончании внешнего цикла перейти к п. 5;

        5. конец алгоритма.

На рисунке 2.6 приведена графическое описание алгоритма решения задания А  в виде блок-схемы.

Рисунок 2.6 - Блок-схема задания А

Пример 2.  Дана целочисленная матрица размером 8 на 8. Найти сумму элементов в тех строках, которые  содержат хотя бы один отрицательный элемент.

Словесная запись:

1) начало алгоритма;

2) задать размерность массива, то есть константе  n и m присвоить значение 8;

3) заполнить массив a[n][m];

4) организовать внешний цикл по i =1; n;1.  Внутри  цикла по i:

- признаку наличия отрицательного элемента P1 присвоить значение 0, т.е. P1 =0 и обнулить переменную s;

- организовать внутренний цикл по j =1; m;1. Внутри цикла по j:

          - проверить на совпадение элементов k-ой строки с элементами k-ого столбца.  Если элементы не совпадают , т.е. a [k][j] не равно a [j][ k], то:

         - признаку совпадения p присвоить значение p =0;

         - прервать внутренний цикл по j;

         -  перейти на внешний цикл  по k,  в противном случае  

продолжить внутренний цикл;

        - по окончании внутреннего цикла проверить: если p =1, то вывести номер k -ой строки; по окончании внешнего цикла перейти к п. 6;

5)  конец алгоритма.

На рисунке 2.7 приведена графическое описание алгоритма решения.

 

Рисунок 2.7 - Блок-схема задания Б

 Лабораторная работа №10. Программная  реализация алгоритмов обработки двумерных массивов

 

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

Задание.

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

Варианты задания даны в лабораторной  работе №9.

Пример 1.  Дана целочисленная матрица размером 8 на 8. Найти такие k, что k-я строка  матрицы совпадает с k-м столбцом. Номера таких строк вывести      

#include <stdio.h>

#include <stdlib.h>

#define m 8

#define n 8

int main()

{  int     a[n][m];    /* Объявляем матрицу nхm */

   int     k, j, p;  /* Счетчик и признак совпадения */ 

/* генератором случайных чисел заполняем матрицу */

    for (k = 0; k < m; k ++)

    for (j = 0; j < n; j++)

     a[k][j]=rand()%10-1;

printf("\n \t\t\t  СГЕНЕРИРОВАННАЯ МАТРИЦА ИМЕЕТ ВИД:\n ");

 /* вывод матрицы */

for (k = 0; k < m; k ++)

   { for (j = 0; j < n; j++)

      printf(“%d  “,a[k][j]);

      printf("\n ");

    }

        printf("\n \t\t\tРЕЗУЛЬТАТ РЕШЕНИЯ:");

     for (k = 0; k < m; k ++)

      { p=1; 

         for (j = 0; j < n; j++)

       { if (a [k][j] != a [j][k])

            { p=0; 

                break;

            }

        }

    /* В случае p=1 выводим на экран  номер соответствующей строки */

        if (p==1) printf("\n номер совпавших строки и столбца = %d ", k);

    }

    if (p==0) printf("\n нет одинаковых строк и столбцов ");

getchar();

}

Результат выполнения программы:

                        СГЕНЕРИРОВАННАЯ МАТРИЦА ИМЕЕТ ВИД:

2 7 2 7 1 4 0 3

1 0 7 6 0 -8 3 5

2 7 1 8 1 4 9 3

9 2 8 5 2 0 0 6

7 1 1 3 9 3 9 1

8 2 4 9 1 -6 4 9

0 3 9 0 9 4 8 8

1 8 3 2 8 2 8 0

                        РЕЗУЛЬТАТ РЕШЕНИЯ:

номер совпавших строки и столбца = 2

номер совпавших строки и столбца = 6

 

Пример 2.  Дана целочисленная матрица размером 8 на 8. Найти сумму элементов в тех строках, которые  содержат хотя бы один отрицательный элемент.

#include <stdio.h>

#include <stdlib.h>

#define m 8

#define n 8

int main()

{  int     matrix[n][m];    /* Объявляем матрицу nхm */

   int     i, j, p;  /* Счетчик и признак совпадения */ 

int  p1, iSumm; /* признак нахождение отрицательного элемента и переменная для    хранения суммы */

/* генератором случайных чисел заполняем матрицу */

    for (i = 0; i < m; i++)

    for (j = 0; j < n; j++)

      matrix[i][j]=rand()%10-1;

printf("\n \t\t\t  СГЕНЕРИРОВАННАЯ МАТРИЦА ИМЕЕТ ВИД:\n ");

 /* вывод матрицы */

for (i = 0; i < m; i++)

   { for (j = 0; j < n; j++)

      printf(“%d  “,matrix[i][j]);

      printf("\n ");

    }

printf("\n \t\t\tРЕЗУЛЬТАТ ВТОРОЙ ЧАСТИ ЗАДАНИЯ:");

    printf("\n\n");

    for (i = 0; i < m; i++)

    {

        /* Присваеваем переменным исходные значения */

        iSumm = 0;

        p1=0;

        for (j = 0; j < n; j++)

        {   /* Суммируем значения элементов i-й строки */

                iSumm += matrix [i][j];

/* При нахождение хотя бы одного отрицательного элемента присваиваем p1=1, обозначающее необходимость вывода Суммы на экран */

           if (matrix [i][j] < 0) p1=1;             

        }

        /* В случае нахождения в строке хотя бы одного отрицательного элемента выводим на экран сумму элементов i-й строки */

    if (p1==1) printf("Сумма элементов строки  #%d = %d\n", i+1, iSumm);

    }

system("PAUSE");/* задержка экрана*/   

      return 0;

}

 

Результат выполнения программы:

                         СГЕНЕРИРОВАННАЯ МАТРИЦА ИМЕЕТ ВИД:

2 7 2 7 1 4 0 3

1 0 7 6 0 -8 3 5

2 7 1 8 1 4 9 3

9 2 8 5 2 0 0 6

7 1 1 3 9 3 9 1

8 2 4 9 1 -6 4 9

0 3 9 0 9 4 8 8

1 8 3 2 8 2 8 0

                       

          РЕЗУЛЬТАТ ВТОРОЙ ЧАСТИ ЗАДАНИЯ:

сумма элементов строки #1 = 14

сумма элементов строки #5 = 31

 

Контрольные вопросы:

1)  Каким образом определяются переменные типа массив?

2)  Какие операторы языка Си  используются при обработке элементов массива?

3)  Как осуществляется доступ к отдельному элементу матрицы с помощью указателя?

4)    Каким образом выводятся элементы матрицы на экран?  

5)    Какой результат унарной операции &?

6)    Какой результат унарной операции *?

7)    Выражение uk=&a[0][0]  эквивалентно  uk=a?

8)    Выражения &a[i][j]  и a+i+j идентичны?

2.6 Тема 6 Алгоритмы поиска данных

 

Общие сведения.

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

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

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

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

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

 

Лабораторная работа №11. Словесное и графическое и описание алгоритмов поиска элементов массива 

 

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

Задание А. Словесно и графически описать алгоритм последовательного поиска элемента равного среднему значению суммы первого и последнего элементов массива, полученного при выполнении задания А в лабораторных работах № 7-8.

Варианты задания А: задания соответствуют вариантам задания А, данных в  лабораторных работах № 7-8.

Задание Б. Словесно и графически описать алгоритм бинарного поиска элемента равного числу k, полученного при выполнении задания Б в лабораторных работах № 7-8.

Варианты  задания Б: задания соответствуют вариантам задания Б, данных в  лабораторных работах № 7-8.

Лабораторная работа №12. Программная запись алгоритмов поиска элементов массива 

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

Задание А: программно описать алгоритм последовательного поиска элемента равного среднему значению суммы первого и последнего элементов массива, полученного при выполнении задания А в лабораторных работах № 7-8

Варианты задания А: задания соответствуют вариантам задания А, данных в  лабораторных работах № 7-8.

Задание Б: программно описать алгоритм бинарного поиска элемента равного числу k, полученного при выполнении задания Б в лабораторных работах № 7-8.

Варианты  задания Б: задания соответствуют вариантам задания Б, данных в  лабораторных работах № 7-8.

 

Контрольные вопросы:

1)  Чем можно объяснить многообразие алгоритмов поиска в линейных структурах?

2)  В чем преимущества поиска с барьером по сравнению с последовательным поиском?

3)  Нахождение какого по порядку элемента в линейном множестве (первого, последнего) гарантирует алгоритм прямого поиска? Как в этом случае должен быть выполнен просмотр?

4)  Нахождение какого по порядку элемента в линейном множестве (первого, последнего) гарантирует алгоритм бинарного поиска? Ответ обоснуйте.

5)  Как трудоемкость алгоритма бинарного поиска на дискретном множестве зависит от мощности множества?

6)  Почему время выполнения алгоритма бинарного поиска на вещественном множестве не зависит от количества элементов

7)  В чем суть алгоритма бинарного поиска?

8)  В чем суть алгоритма последовательного поиска?

 

2.7 Тема 7 Алгоритмы обработки динамических структур данных 

 

Общие сведения.

Статическая структура данных характеризуется тем, что:

- она имеет имя, которое используется для обращения к ней;

- ей выделяется память в процессе трансляции программы;

- количество элементов сложной структуры (размерность) фиксировано при ее описании;

- размерность структуры не может быть изменена во время выполнения

программы.

Динамическая структура данных характеризуется тем, что:

- она не имеет имени;

- ей выделяется память в процессе выполнения программы;

- количество элементов структуры может не фиксироваться;

- размерность структуры может меняться в процессе выполнения программы;

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

Каждой динамической структуре данных сопоставляется статическая переменная типа «указатель» (ее значение - адрес этого объекта), посредством которой осуществляется доступ к динамической структуре. Для создания динамического объекта используется унарная операция new:

new имя_типа

или

new имя_типа инициализатор

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

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

Указатель объявляется следующим образом:

                            тип *<имя переменной>;

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

Унарная операция &, примененная к некоторой переменной, показывает, что нам нужен адрес этой переменной, а не ее текущее значение. Если переменная uk объявлена как указатель, то оператор присваивания uk=&x означает: "взять адрес переменной x и присвоить его значение переменной-указателю uk".

  Унарная операция  *,  примененная к указателю, обеспечивает доступ к содержимому ячейки памяти, на которую ссылается указатель. Например, *uk можно описать словами как "то, что содержится по адресу, на который указывает uk".

Продолжительность существования динамического объекта – от точки его создания операцией new до конца программы или до явного его уничтожения.

Уничтожение динамического объекта (освобождение памяти, выделенной под динамическую переменную) осуществляется операцией delete:

delete имя_указателя;

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

Для освобождения памяти, выделенной для массива, используется следующая модификация этой операции:

delete [ ] имя_указателя;

.

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

struct list

{ int n;

type elem [ k ]; }

Здесь элемент с именем n определяет фактическое количество данных (элементов) в списке, если n равно 0, то список пуст, если n равно k, то список полон; элемент с именем elem (в данном случае массив) определяет само множество элементов списка, type – тип элемента списка.

Динамический список – это множество данных, связанных между собой указателями.

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

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

Основными операциями обработки списка являются:

1) поиск заданного элемента по его значению или порядковому номеру. Операция заканчивается, когда элемент найден или просмотрен весь список (если элемента нет). Результат операции должен определять, есть ли элемент в списке или нет и, если есть, то возможно его адрес или значение;

2) включение ( вставка ) в список нового элемента перед или после заданного элемента ( в том числе перед первым элементом или после последнего ). Включению, как правило, предшествует поиск элемента, после и/или перед которым происходит включение. При включении элемента перед первым в список без заглавного звена меняется заголовок списка. При включении после некоторого элемента меняется ссылочное поле у элемента, после которого происходит включение, поэтому надо определять ссылку на элемент после которого происходит включение;

3) исключение ( удаление ) заданного элемента из списка ( в том числе удаление первого элемента или последнего ). Исключению, как правило, предшествует поиск, исключаемого элемента.  Результатом поиска должна быть ссылка на элемент предшествующий исключаемому, так как при удалении элемента из списка меняется ссылочное поле у элемента, предшествующего удаляемому. При удалении первого элемента в списке без заглавного звена меняется заголовок списка;

4) определение числа звеньев списка;

5) упорядочение элементов списка по значению информационного поля.

 

Лабораторная работа №13 Словесная и графическая запись алгоритмов обработки динамических структур данных.  Линейные однонаправленные списки

 

Цель работы: изучить тип указатель; получить навыки в организации и обработке однонаправленных списков.

Варианты задания

1. Даны действительные числа x1, x2, . . . , xn ( n >= 2 и заранее неизвестно). Получить последовательность ( x1 – xn ) , ( x2 – xn ) , . . . , ( xn-1 – xn ).

2. Дана последовательность действительных чисел a1, a2, . . . , an ( n >= 2 и заранее неизвестно). Если последовательность упорядочена по неубыванию, то оставить ее без изменения, иначе получить последовательность an , an-1 , . . . , a1 .

3. Даны действительные числа x₁, ..., x_n, p₁, ..., p_n. ( n >= 2 и заранее неизвестно). Последовательности x₁, ..., x_n и p₁, ..., p_n определяют систему n материальных точек на прямой: x_i -координата, р_i  - вес i-й точки (i = 1, ..., n). Указать номер точки, наиболее близко расположенной к центру тяжести системы. Если таких точек несколько, то взять любую из них.

4. Дана последовательность символов s1, s2, . . . , sn ( n >= 2 и заранее

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

5. Дана последовательность символов s1, s2, . . . , sn ( n >= 2 и заранее

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

6. Дана последовательность символов s1, s2, . . . . Известно, что s1 отличен от точки и , что среди s2, s3, . . . имеется хотя бы одна точка. Пусть s1, s2, . . . , sn - символы, предшествующие первой точке. Получить последовательность s1, s3 , . . . , sn , если n нечетно и последовательность s2, s4, . . . , sn , если n четно.

7. Дана последовательность действительных чисел a₁, ..., a_n. ( n >= 2 и заранее неизвестно. Если последовательность a₁, ..., a_n упорядочена по неубыванию (т. е. если a₁ ³ a₂ ³ … ³ a_n ), то оставить ее без изменения. Иначе получить последователь­ность a_n, ..., a₁.

8. Даны действительные числа x₁, ..., x_n ( n >= 2 и заранее неизвестно). Вычислить:

x₁x_n + x₂x_n-1 + … + x_nx₁.                

9. Даны действительные числа x₁, ..., x_n ( n >= 2 и заранее неизвестно). Вычислить:

                    (x₁ + x_n)(x₂ + x_n-1) … (x_n + x₁).

10. Даны действительные числа x₁, ..., x_n ( n >= 2 и заранее неизвестно). Вычислить:

     (x₁ + x₂ + 2x_n)(x₂ + x₃ + 2x_n-1) … (x_n-1 + x_n + 2x₂).

11. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно). Получить:

 (a₁ - a_2n)(a₃ - a_2n-2)(a₅ - a_2n-4) … (a_2n-1 - a₂).

12. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно). Получить:

 a₁a_2n + a₂a_2n-1 + … + a_na_n+1.

13. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно). Получить:

min(a₁ + a_n+1, a₂ + a_n+2, …, a_n + a_2n).

 14. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно). Получить:

max (min(a₁, a_2n), min(a₂, a_2n-1), …, min(a_n, a_n+1)).

15. Даны действительные числа a₁, ..., a_n. ( n >= 2 и заранее неизвестно). Выяснить, имеются ли среди чисел a₁, ..., a_n совпадающие.

16. Даны действительные числа r₁, ..., r_n. ( n >= 2 и заранее неизвестно). Получить последовательность:   

r₁, ..., r_n, r₁, ..., r_n.

17. Даны действительные числа r₁, ..., r_n. ( n >= 2 и заранее неизвестно). Получить последовательность:   

r₁, ..., r_n, r_n, ..., r₁;.

 18. Даны действительные числа r₁, ..., r_n. ( n >= 2 и заранее неизвестно). Получить последовательность:   

r_n, ..., r₁, r₁, ..., r_n.

19. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно). Требуется получить последовательность x₁, y₁, x₂, y₂, …, x_k, y_k, где x₁, ..., x_m — взятые в порядке следования четные члены последовательности a₁, ..., a_n, а y₁, ..., y_l — нечетные члены, k = min(m, l).

20. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно).. Выяснить, верно ли, что для i = l, ..., n выполнено:  а) a_i = a_n+i;  б) a_i = 2a_n-i + 2a_2n-i+1;  в) a_i + a_2n-i+1 > 17;  г) a_2n-i+1 < a_i < a_2n-i.

21. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно).. Выяснить, верно ли, что для i = l, ..., n выполнено: 

 a_i = a_n+i.

22. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно).. Выяснить, верно ли, что для i = l, ..., n выполнено: 

a_i = 2a_n-i + 2a_2n-i+1. 

23. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно).. Выяснить, верно ли, что для i = l, ..., n выполнено:

 a_i + a_2n-i+1 > 17.

24. Даны действительные числа a₁, ..., a_2n ( n >= 2 и заранее неизвестно).. Выяснить, верно ли, что для i = l, ..., n выполнено: 

a_2n-i+1 < a_i < a_2n-i.

25. Для заданных полиномов Pn( x ) и Qn( x ) найти полином R – сумму

полиномов P и Q. Каждый полином представить в виде списка. Причем в список а) включать, б) не включать и коэффициенты равные нулю. Считать, что входные данные не содержат равных нулю коэффициентов.

 

Лабораторная работа №14 Программная реализация алгоритмов обработки динамических структур данных.  Линейные однонаправленные списки

 

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

Пример. Даны действительные числа a₁, ..., a_n. ( n >= 2 и заранее неизвестно).Если последовательность a₁, ..., a_n упорядочена по не убыванию (т. е. если a₁ ³ a₂ ³ … ³ a_n ), то оставить ее без изменения. Иначе получить последователь­ность a_n, ..., a₁.

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

struct st

        {struct st *pc1;

        int c;

        struct st *pc;

        };

 int main()

{ struct st *str;

  struct st *beg=NULL;

  struct st *end=NULL;

   struct st *end1=NULL;

   struct st *buf=NULL;

  int min,P=0;

  char pr[4];

  printf("vvedite dannie structuri");

   /*cikl vvoda i formirovanie spiska*/

   do

    {   str= new st;//(struct stud*)malloc(sizeof(struct stud));

        printf("\n vvedi c=");

        scanf("%d",&str->c);

            /*vcluchit zveno v spisok*/

         if(beg==NULL && end==NULL)

            {beg=str;str->pc1=NULL;buf=str;}

          else

          { end1=str;end->pc=str;

            end1->pc1=buf;

          }

          end=str;

          end->pc=NULL;buf=str;

            printf("\n vvesti sled. znachenie?");

      scanf("%s",pr);

      if (strcmp(pr,"no")==0)

          break;

       

     }while(1);

     printf("\n soderjimoe spiska:");

      str=beg;min=str->c;

       while(str!=NULL)

          { if(str->c<min){P=1;break;}

           str=str->pc;

           } printf("\n spisok\n ");

       

        if(P==0)

        {str=beg;

           while(str!=NULL)

            { printf("  %d ",str->c);

            str=str->pc;

           }

       }

         else

         {str=buf;

           while(str!=NULL)

            {

              printf(" %d ",str->c);

            str=str->pc1;

           }

         }

          free(str);

          system("PAUSE");       

  return 0;

  }

 

Результат выполнения программы

vvedite dannie structuri

 vvedi c=7

 vvesti sled. znachenie?y

 vvedi c=8

 vvesti sled. znachenie?y

 vvedi c=6

 vvesti sled. znachenie?y

 vvedi c=4

 vvesti sled. znachenie?y

 vvedi c=5

 vvesti sled. znachenie?no

 

 soderjimoe spiska:

 spisok

 5 4 6 8 7              

 

Контрольные вопросы:

1) понятие типа указатель;

2) задание переменных типа указатель. Операции над указателями;

3) понятие статического и динамического объекта;

4) создание и уничтожение динамического объекта. Операции над динамическим объектом;

5)  понятие списка;

6) понятие линейного односвязного списка;

7) операции над односвязным списком;

8) задание односвязного списка;

 

Заключение

 

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

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

 

Список литературы

 

1.  Эпштейн М.С. Программирование на языке С. - М.: «Академия», 2011.

2. Эпштейн М.С. Практикум по программированию на языке С. - М.: «Академия», 2007.

3. Уэйт М и др. Язые Си. Руководство для начинающих. - М.: «Мир», 1988.

4. Керниган Б. Язык программировния Си. - М.: «Финансы и статистика», 1992.

5. Вирт Н. Алгоритмы и структуры данных. - М.: «Мир», 1989.

6. Березин Б.И. Начальный курс С и С++. - М.: «Диалог-Мифи», 2004.

7. Архангельский А.Я. Язык С++ в С++ BUILDER. - М., 2008.

8. Ишкова Э.А. С++ начала программирования. - М.: «Бином», 2011.

9. Коплиен Дж. Программирование на С++. - СПб., 2005.

10 Либерти Дж. Освой самостоятельно С++ за 21 день. - М., 2007.

11. Павловская Т.А. С/С++. Структурное  программирование. - СПб.: «Питер», 2010.

12. Подбельский В.В. Программирование на языке Си. – М., 2000.

13. Полубенцева М. С/С++ процедурное программирование. - СПб., 2008.

14. Культин Н. С/С++ в задачах и примервх.-СПб.: «БХВ-Петербург» , 2011.

 

Приложение А

 

Образец титульного листа  отчета

 

Некоммерческое акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Факультет «Информационные технологии»

Кафедра «Информационные системы»

                                                                           

ОТЧЕТ

по лабораторным работам №1, №2

по дисциплине «Алгоритмы, структуры данных и программирование»

тема: «Алгоритмы линейной структуры»

вариант № 1

 

                                                                      Выполнил ст.гр. БИС-12-2

                                                                               Петров И.И.

        Проверил к.т.н., доцент  

  _______________Ни А.Г.

“______”__________2013

 

 

 

 

 

 

 

 

 

Алматы 2013