И математическое моделирование

Вид материала

Методические указания

Содержание Лабораторная работа № 7 Лабораторная работа № 8 8. Методы сортировки и поиска 2. Методы сортировки Лабораторная работа № 9 9. Работа с файлами Режим работы Лабораторная работа № 10

Подобный материал:

• Математическое моделирование управляемого движения космических аппаратов, 213.72kb.
• Программа дисциплины имитационное моделирование в экономике для направления 080100., 228.47kb.
• Математическое моделирование многомерных квазистационарных электромагнитных полей, 380.28kb.
• Правительстве Российской Федерации» (Финансовый университет) Кафедра «Математическое, 246.23kb.
• Математическое моделирование термомеханических процессов в системах армированных стержней, 259.01kb.
• Вестник Брянского государственного технического университета. 2007. №4(16) математическое, 61.09kb.
• Программа вступительного испытания собеседования для магистерской программы «математическое, 67.11kb.
• Cols=2 gutter=66> Математическое моделирование и процесс создания математической модели, 130.19kb.
• Математическое моделирование процессов самоорганизации в широкополосных системах 05., 181.86kb.
• Программа дисциплины «Математическое моделирование в менеджменте», 242.16kb.

ЛАБОРАТОРНАЯ РАБОТА № 7

ОПИСАНИЕ ПОЛЬЗОВАТЕЛЬСКИХ ФУНКЦИЙ.

ОСНОВЫ РАБОТЫ СО СТРОКАМИ


Цель:

Изучение возможностей языка Си по описанию пользовательских функций и работы со строками

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

1. Что возвратит функция?
   

float a=1.5f,b=2.0f;

int summ()

{

return a+b;

}

2. Найдите ошибку в коде:
   

char a[5] = “abdcef”;

int b;

void main()

{

b = 0;

a[3] = b;

return b;

}

3. Какой максимальной длины может быть строка?
   
4. Строка определена как char str[10]. Можно ли в нее записать строку “1234567890”?
   

Задание:

Согласно вариантам реализовать программно решение задачи из индивидуального задания.


Индивидуальные задания:


1. Написать функцию подсчета длины строки s.

2. Написать функцию подсчета количества пробелов в строке s.

3. Написать функцию разбиения строки s пополам на две строки s1 и s2.

4. Написать функцию, которая в строке s заменяет все символы из диапазона 'a'-'z' на их аналоги из диапазона 'A'-'Z'.

5. Написать функцию разворота строки s в обратном порядке.

6. Написать функцию сравнения строк s1 и s2, которая возвращает 0 если строки равны, или 1 в противном случае.

7. Написать функцию, которая копирует содержимое строки s2 в строку s1.

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

9. Написать функцию, удаляющую N последних символов из строки s.

10. Написать функцию, удаляющую N первых символов из строки s.

11. Написать функцию, удаляющую все пробелы из строки s.

12. Написать функцию, записывающую в строку s2 все цифры из строки s1 в порядке их следования слева направо.

13. Написать функцию, которая выводит на экран через запятую все слова строки s, содержащей только пробелы и буквы английского алфавита, а также начинающейся и оканчивающейся пробелами (слово - последовательность символов между двумя пробелами).

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

15. Написать функцию перевода целого неотрицательного числа N в строку s (число записывать в десятичной системе счисления).


7. РЕКУРСИЯ


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

Например, вычисление факториала можно построить по рекурсивному принципу. Очевидно, N! = N*(N-1)! – это рекурсивная формула, на основе которой мы можем написать рекурсивную функцию вычисления факториала.


long int factorial( long int n )

{

return n*factorial( n-1 );

}

Нетрудно заметить, что данная функция будет работать некорректно: вызвав ее, программа зациклится и завершится сообщением об ошибке. Причина проста: внутри каждого вызова функции factorial происходит еще один вызов этой функции, внутри которого, очевидно, произойдет еще один вызов, внутри которого будет еще один вызов, и т.д. Подобная организация вычислений никогда не приведет к какому-нибудь результату. Поэтому золотым правилом при написании рекурсивных функций является определение условия завершения рекурсии – условие, при котором рекурсивная функция не вызовет в очередной раз саму себя, а вернет некоторое конкретное значение. В данном случае условием завершения рекурсии будет достижение некоторого краевого значения N, для которого значение факториала известно. Очевидно, таким значением будет 0, т.к. по определению 0! = 1, а факториал от отрицательных чисел не вычисляется. Данная часть рекурсивной функции, возвращающая конкретное значение и не вызывающая саму себя, называется базисом рекурсии. Вторая часть функции, вызывающая саму себя, называется рекурсивным переходом. Добавим в нашу функцию базис рекурсии.


long int factorial( long int n )

{

if ( n==0 ) return 1; // базис рекурсии

else return n*factorial( n-1); // рекурсивный переход

}


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


ЛАБОРАТОРНАЯ РАБОТА № 8

РЕКУРСИЯ


Цель:

Изучение особенностей организации рекурсивных функций на языке Си.

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

1. Что такое рекурсия и для чего она используется?
   
2. Напишите функцию, рекурсивно находящую: а) сумму элементов массива; б) максимальный \ минимальный элементы массива; а также рекурсивные функции, реализующие ввод \ вывод элементов массива.
   

Задание:

Согласно вариантам реализовать программно решение задачи из индивидуального задания.


Индивидуальные задания:


1. Реализовать рекурсивно подсчет суммы элементов линейного массива.

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

3. Реализовать рекурсивно нахождение НОД числа по алгоритму Евклида.

4. Даны два целых положительных числа n и m, представляющие собой дробь n/m. Реализовать рекурсивно сокращение этой дроби.

5. Реализовать рекурсивно вывод на печать всех цифр строки s.

6. Реализовать рекурсивно нахождение числа Фибоначчи с номером N.

7. Реализовать рекурсивно подсчет суммы первых N членов ряда 1+1/2+1/3+1/4+... .

8. Реализовать рекурсивно удаление N первых символов из строки s.

9. Реализовать рекурсивно вывод заданного числа N в восьмеричной системе счисления.

10. Реализовать рекурсивно реверс заданной строки s.

11. Реализовать рекурсивно нахождение остатка от деления заданных положительных целых чисел N и M без использования операций / и %.

12. Реализовать рекурсивно нахождение целой части от деления заданных положительных целых чисел N и M без использования операций / и %.

13. Реализовать рекурсивно функцию возведения в степень.

14. Реализовать рекурсивно функцию циклического сдвига строки s вправо на заданное число символов N.

15. Реализовать рекурсивно удаление N последних символов из строки s.


8. МЕТОДЫ СОРТИРОВКИ И ПОИСКА


1. Методы поиска


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

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

Ниже приведен фрагмент кода, реализующий линейный поиск:


// На входе имеем линейный массив a,

// состоящий из n элементов, и x - искомый элемент.


int i = 0;

while( (i < n) && (a[i] != x) ) i++;

if (i == n)

printf( "Искомый элемент не найден!\n" );

else

printf( "Искомый элемент находится в поизиции %d.\n", i );


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

1. Изначально рассматриваемой областью является весь массив.
   
2. Если в рассматриваемой области только один элемент, то переход к шагу 5.
   
3. Выбираем средний элемент рассматриваемой области и сравниваем с искомым. Если искомый элемент меньше, чем средний, то новой рассматриваемой областью становится левая половина текущей, иначе –правая половина.
   
4. Переход к шагу 2.
   
5. Если найденный элемент не равен искомому, значит искомый элемент в массиве отсутствует, иначе найденный элемент является искомым.
   

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


// На входе имеем линейный массив a, состоящий из n элементов,

// отсортированных по неубыванию, и x - искомый элемент.


int l = 0; // левая граница

int r = n; // правая граница


while( (r-l)>1 )

{

int i = (l+r)/2;

if(x
else

if(x>a[i]) l = i+1; // меняем левую границу

else l = r = i; // искомый элемент найден

}

if (a[i] != x)

printf( "Искомый элемент не найден !\n" );

else

printf( "Искомый элемент находится в позиции %d.\n", i );


2. Методы сортировки


Рассмотрим два наиболее простых метода сортировки – сортировку методом прямого включения и сортировку методом обмена («пузырёк»).

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

1. Изначально отсортированным считается лишь один первый элемент массива.
   
2. Выбирается первый элемент массива из не отсортированной части.
   
3. Начиная с первого элемента отсортированной части, методом линейного поиска ищется первый элемент, больший выбранного.
   
4. Выбранный элемент вставляется перед найденным элементом, сдвигая его и все последующие элементы массива вправо.
   
5. Шаги 2-4 повторяются до тех пор, пока количество элементов не отсортированной части не достигнет нуля.
   

Пример кода сортировки методом прямого включения:


// На входе имеем линейный массив a,

// состоящий из n вещественных чисел.


int k = 1; //Длина отсортированной части

while( k < n )

{

float x = a[k];

int i = 0;


// Поиск места включения.

while( (i

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

// включение нового элемента.

for(int j=k;j>i;j--) a[j] = a[j-1];

a[i] = x; k++;

}


Существует также метод бинарного включения. В основе его лежит применение для поиска в отсортированной части массива метода бинарного поиска вместо линейного поиска.

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


// На входе имеем линейный массив a,

// состоящий из n вещественных чисел.


for(int i=1;i
for(int j=n-1;j>=i;j--)

if(a[j-1]>a[j]) // Если не выполняется условие сортировки,

// то поменять элементы местами

{

float t = a[j-1];

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

a[j] = t;

}


ЛАБОРАТОРНАЯ РАБОТА № 9

МЕТОДЫ СОРТИРОВКИ И ПОИСКА


Цель:

Ознакомиться с простейшими методами сортировки и поиска.

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

1. Опишите достоинства и недостатки известных вам методов сортировки.
   
2. Опишите достоинства и недостатки известных вам методов поиска.
   
3. Какие ограничения накладываются на метод бинарного поиска элемента в массиве?
   

Задание:

Необходимо реализовать три программы.

Первая выполняет ввод с клавиатуры массива из 25 элементов, либо случайными числами (использовать функцию random(num) библиотеки stdlib.h) и сортирует его в порядке не убывания методом прямого включения и методом «пузырька». Исходный и отсортированный массивы вывести на экран.

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

Третья программа осуществляет поиск подстроки в строке. Строка и подстрока вводятся пользователем с клавиатуры.


9. РАБОТА С ФАЙЛАМИ


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

Основные функции для работы со структурой FILE реализуют операции: открытия файла, закрытия файла, записи в файл и чтения из него.

После объявления указателя на структуру FILE, её необходимо инициализировать. Для этого вызывается функция fopen, осуществляющая открытие файла. Эта функция имеет два параметра: имя открываемого файла и режим работы с файлом.

Режим работы – это символьная строка, в которой специальным образом кодируется набор операций, разрешенных над файлом, таких как: чтение/запись данных и их формат. Рассмотрим два наиболее часто применяемых режима работы с файлами.

Режим чтения текста – этот режим задается указанием "rt" в качестве второго параметра функции fopen. В этом режиме с файлом можно аналогично вводу с клавиатуры при помощи все той же функции scanf, только в этом случае применяется ее функция-близнец fscanf. В отличие от функции scanf в вызове данной функции используется ещё один параметр – указатель на структуру FILE файла, из которого производится чтение. Данный параметр указывается первым (перед форматной строкой).

Режим записи текста – задается указанием "wt" в качестве второго параметра функции fopen. Аналогично режиму чтения текста, вывод в файл производится с помощью близнеца функции printf - функции fprintf, при вызове которой в качестве первого параметра задается указатель на структуру FILE файла, используемого для записи.

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

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

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


#include


void main()

{

FILE * f = fopen( "input.txt", "rt" ); // открытие файла

long int sum = 0;


while( !feof(f) ) // пока не достигнут конец файла

{

int a;

fscanf( f, "%d", &a ); // считываем число

sum += a;

}

fclose(f); // закрываем файл

printf( "Сумма чисел из файла равна %ld\n", sum );

}


Во втором примере программа считывает из файла input.txt линейный массив из 100 чисел, затем сортирует его методом "пузырька" и выводит в файл output.txt:


#include

void main()

{

FILE * f1 = fopen( "input.txt", "rt" );

FILE * f2 = fopen( "output.txt", "wt" );

int a[100];

int i,j,t;

for(i=0;i<100;i++)fscanf( f1, "%d", &a[i] );

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

if(a[j-1]>a[j])

{

t = a[j-1];

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

a[j] = t;

}


for(i=0;i<100;i++) fprintf( f2, "%d ", a[i] );

fclose(f2); fclose(f1);

}


ЛАБОРАТОРНАЯ РАБОТА № 10

ОСНОВЫ РАБОТЫ С ФАЙЛАМИ


Цель:

Получить навыки работы с файлами на языке Си.

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

1. Что такое файл с точки зрения программы на Си?
   
2. Какие вам известны операции над файлами?
   
3. Можно ли в файлах хранить значения разных типов?
   

Задание:

Согласно вариантам реализовать программно решение задачи из индивидуального задания.


Индивидуальные задания:


1. Осуществить копирование заданного текстового файла в новый файл.

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

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

4. Дан текстовый файл с набором целых чисел. Вывести в новый текстовый файл модули этих чисел в порядке следования.

5. Дан текстовый файл с набором целых чисел. Вывести в новый файл эти числа в порядке их не возрастания по модулю.

6. Дан текстовый файл с набором слов, разделенных пробелами. Определить количество слов в файле.

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

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

9. Дано два текстовых файла с набором неповторяющихся целых чисел в диапазоне от 1 до 100. Вывести в новый файл те из них, которые есть в обоих файлах.

10. Дано два текстовых файла с набором слов, разделенных пробелами. Вывести в новый файл те из них, которые есть в первом файле, но нет во втором.

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

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

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

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

15. Дан текстовый файл с набором вещественных чисел. Найти среди них два таких, сумма которых максимальна по модулю.

1 В ряде компиляторов может быть зарезервировано другое имя (в частности, для ряда компиляторов под платформу MS Windows вместо имени main зарезервировано имя winmain), однако подобеные договорённости обговариваются производителями компиляторов.

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