Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Практическая часть. Пример 12.4. Напишите программу сортировки по возрастанию заданного массива случайных чисел, равномерно распределенных в интервале [–6;6]
|
|
Пример 12.4. Напишите программу сортировки по возрастанию заданного массива случайных чисел, равномерно распределенных в интервале [–6; 6], с помощью вспомогательной функции.
Программный код решения примера:
#include < stdio.h> #include < conio.h> #include < stdlib.h> #include < time.h> #define MAX 10 // Прототип функции с формальными параметрамиvoid sort(double arr[], int n); int main (void) { double M[MAX]; int i, size = MAX; long int L; unsigned int some; L = (long) time(NULL); srand((unsigned)L); for (i = 0; i < MAX; ++i) M[i] = 12.0*rand()/RAND_MAX - 6.0; printf(" \n\t The original array: \n"); for (i = 0; i < MAX; ++i) printf(" \t%8.4f\n", M[i]); // Обращение к функции с фактическими параметрами sort(M, size); // Распечатка отсортированного массива printf(" \n\t After sorting: \n"); for (i = 0; i < MAX; ++i) printf(" \t%8.4f\n", M[i]); printf(" \n Press any key: "); _getch(); return 0; }// Вспомогательная функция сортировки void sort(double Array[], int m) {int i, j; double tmp; for (i = 0; i < m-1; ++i) for (j = 0; j < m-i-1; ++j)if (Array[j+1] < Array[j]) {tmp = Array[j]; Array[j] = Array[j+1]; Array[j+1] = tmp; }}Следует обратить внимание на имена формальных параметров в самой функции sort() и в ее прототипе: они имеют разные имена, но одинаковые типы. Фактические параметры или аргументы функции sort() в вызывающей программе (в теле функции main()) имеют свои имена, не связанные с именами формальных параметров.
Заполнение массива случайными числами производится с помощью библиотечной функции rand() и макроопределения RAND_MAX. Для рандомизации массива случайных чисел при каждом новом запуске программы используется библиотечная функция srand(), аргументом которой является системное время, формируемое библиотечной функцией time().
Возможный результат выполнения программы показан на рис. 12.3.
Рис. 12.3. Пример сортировки числового массива
Пример 12.5. Напишите программу поиска максимального элемента среди минимальных элементов строк двухмерного целочисленного массива.
Условие примера соответствует поиску максимина в двухмерном массиве, т.е.
где 
– элементы матрицы 
.
Алгоритм поиска максмина заключается в следующем. Сначала предполагаем, что максимальным элементом является начальный элемент первой строки A[0][0], затем заменяем его минимальным элементом этой же строки, т.е. теперь минимальный элемент первой строки принимается за искомый максимум. Последовательно просматривая остальные строки, находим в каждой из них минимальный элемент. Если окажется, что минимальный элемент текущей строки больше текущего максимума, то он принимается за максимальный. Результатом поиска являются значение максимального элемента и его индексы (номер строки и номер столбца).
Программный код решения примера:
#include < stdio.h> #include < conio.h> #include < stdlib.h> #include < time.h> #define n 6#define m 7const int N = 100; int main (void) {//Прототип функцииint MaxMin(int A[][m], int nn, int mm, int *imax, int *jmax); int i, j, A[n][m], max, imax, jmax; long int L; L = (long) time(NULL); srand((unsigned)L); //Заполнение матрицы целыми случайными числами for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) A[i][j] = 2*N*rand()/RAND_MAX - N; // Распечатка матрицыprintf(" \n\t The original matrix A(%d*%d): \n\n", n, m); for (i = 0; i < n; ++i){ printf(" \t"); for (j = 0; j < m; ++j) printf(" %4d", A[i][j]); printf(" \n"); } max = MaxMin(A, n, m, & imax, & jmax); printf(" \n\t Result: MaxMin = A[%d][%d] = %d\n", imax+1, jmax+1, max); printf(" \n Press any key: "); _getch(); return 0; } // Функция поиска максминаint MaxMin(int A[][m], int nn, int mm, int *imax, int *jmax){ int i, j, min, max, imin, jmin; max = A[0][0]; *imax = 0; *jmax = 0; for (j = 1; j < mm; ++j) if (A[0][j] < max) {max = A[0][j]; *imax = 0; *jmax = j; } for (i = 1; i < nn; ++i) { min = A[i][0]; imin = i; jmin = 0; for (j = 1; j < mm; ++j) if (A[i][j] < min) {min = A[i][j]; imin = i; jmin = j; } if (max < min) {max = min; *imax = imin; *jmax = jmin; } } return max; }В программе поиск максмина выполняется на основе обычной индексации двухмерного массива. В объявлении функции MaxMin() для матрицы явно указывается только второй размер – количество столбцов. Указатели *imax, *jmax используются для передачи в вызывающую функцию индексов найденного максимина. Возвращение самого максимина осуществляется по значению с помощью оператора return, т.е. return max. Вывод значений индексов максмина сделан традиционно в соответствии с принятой обычной математической индексацией.
Возможный результат выполнения программы показан на рис. 12.4.
Рис. 12.4. Максмин двухмерного массива
Пример 12.6. Напишите программу выделения слов из символьной строки, когда слова в ней разделены пробелами, и поместите каждое слово в отдельной строке свободного (вспомогательного массива).
Программный код решения примера:
#define _CRT_SECURE_NO_WARNINGS#include < stdio.h> #include < conio.h> #include < stdlib.h> #include < string.h> #define N 123#define M 40 int wordstr(char *c, char **FA) {int Ln, n = 0, i = 0; char *wr; char *tempstr; Ln = strlen(c); tempstr = (char *)calloc(Ln + 1, sizeof(char)); strcpy(tempstr, c); wr = strtok(tempstr, " "); Ln = strlen(wr); FA[i] = (char *)calloc(Ln + 1, sizeof(char)); strcpy(FA[i++], wr); n++; while (wr = strtok(NULL, " ")) {Ln = strlen(wr); FA[i] = (char *) calloc(Ln + 1, sizeof(char)); strcpy(FA[i++], wr); n++; }free(tempstr); return n; } int main (void) { int i, n; char *Farr[M]; char str[N]; printf(" \n\t Enter the string of characters: \n > > "); gets_s(str, N-1); printf(" \n\t The original string of characters: \n"); printf(" %s\n", str); //Обращение к функции обработки строки n = wordstr(str, Farr); //Распечатка слов, помещенных в свободный массив printf(" \n\t The characters in a free array: "); for (i = 0; i < n; ++i) printf(" \n\t %s", Farr[i]); //Освобождение памяти, занятую выделенными словами for (i = 0; i < n; ++i) {free(Farr[i]); Farr[i] = NULL; } printf(" \n\n Press any key: "); _getch(); return 0; }В программе использована библиотечная функция strtok(), которая выделяет слова из строки. При этом для каждого выделенного слова получаем динамическую память с помощью функции calloc(). Адрес выделенной памяти помещаем в соответствующий указатель массива свободных строк FA[].
Обратите внимание, что в функции calloc() вводится число на единицу больше, чем длина строки. Это сделано для учета символа завершения строки (или одного слова), т.е. для символа " \0"
Для исключения предупреждений о безопасной работе с функциями strcpy(), strtok() в MS Visual Studio в программе используется директива #define _CRT_SECURE_NO_WARNINGS.
Результат выполнения программы показан на рис. 12.5.
Рис. 12.5. Пример выделения слов из строки
Пример 12.7. Написать программу расчета суммы и среднего арифметического произвольного количества данных. В качестве ключевых слов для выбора варианта расчета принять mean (среднее) и sum (сумма).
В данном примере необходимо использовать функцию с переменным числом аргументов. Формула расчета среднего арифметического (m):
где 
– количество числовых данных, 
– текущее число.
Программный код решения примера
#include < conio.h> #include < string.h> #include < stdarg.h> #include < float.h> /* Прототип функции с переменным числом аргументов*/double varfun(char str[], double v1,...); int main(void){ double v1 = 10.0, v2 = 2.5, control; char str[121]; printf(" \n Enter one of the key words 'mean' or 'sum': "); gets_s(str, 120); control = varfun(str, v1, v2, 7.5, 0.0); if (control < DBL_MAX) printf(" \n Result: %lf\n", control); else printf(" \n Invalid input keyword.\n"); printf(" \n\n... Press any key: "); _getch(); return 0; } /* Определение функции с переменным числом аргументов */double varfun(char str[], double v1,...) {/* Указатель на переменные списка аргументов */ va_list parg; double sum = v1; double value = 0.0; /* значение аргумента */ int count = 1; /* начальное количество аргументов */ int k, p; char *ch = " mean"; char *ch2 = " sum"; // Лексиграфическое сравнение строк k = strcmp(str, ch); if (! k) // k == 0 p = 1; else if (k) // k! = 0 { k = strcmp(str, ch2); if (! k) p = 2; else p = 0; } if (p == 1) { va_start(parg, v1); /* инициализация указателя parg */ /* Просмотр списка аргументов*/ while((value = va_arg(parg, double))! = 0.0) { // Суммирование числовых аргументов функции varfun() sum += value; count++; } /* Завершение процесса счтывания аргументов */ va_end(parg); return sum/count; } if (p == 2) { va_start(parg, v1); while((value = va_arg(parg, double))! = 0.0) { sum += value; count++; } va_end(parg); return sum; } return DBL_MAX; }Возможный вариант выполнения программы показан на рис. 12.6.
Рис. 12.6. Пример выполнения программы
Пример 12.8. Напишите программу с функцией пузырьковой сортировки, использующей вызов по ссылке.
В условии примера " вызов по ссылке" означает, что в качестве фактических параметров функций будут использоваться адреса переменных. И в этом случае прототип таких функций будет содержать указатели на соответствующие типы.
Программный код решения примера:
#include < stdio.h> #include < conio.h> // Прототип функцииvoid bsort (int* const, const int); int main (void) { int A[] = {56, 34, 2, 0, 1, -21, 6, 8, 7}; int i, n; //Размерность массива n = sizeof(A)/sizeof(A[0]); puts(" \n Data items in original order: "); for (i = 0; i < n; i++) printf(" %3d", A[i]); // Вызов функции сортировки - bsort() bsort (A, n); puts(" \n\n Data items in ascending order: "); for (i = 0; i < n; i++) printf(" %3d", A[i]); printf(" \n\n... Press any key: "); _getch(); return 0; } // Определение функцииvoid swap(int *pa, int *pb){int temp; temp = *pa; *pa = *pb; *pb = temp; } void bsort (int *const arr, const int size){int pass, //счетчик проходов j; // счетчик сравнений// Прототип функции обмена - swap()void swap (int*, int*); // Цикл для контроля проходовfor (pass = 0; pass < size - 1; pass++) { // цикл для контроля сравнений на данном проходе for (j = 0; j < size - 1; j++) { // обмен значений при нарушении порядка возрастания if (arr[j] > arr[j + 1]) { swap(& arr[j], & arr[j+1]); } }} }В программе функция сортировки bsort() в качестве формального параметра используется константный указатель, который указывает на первый элемент заданного массива. Второй формальный параметр также константный, чтобы подчеркнуть неизменность этого параметра в теле функции bsort(). Передача функции размера массива в качестве параметра имеет два преимущества – это хороший стиль программирования и, кроме того, такую функцию можно использовать многократно.
Прототип функции swap() включен в тело функции bsort(), потому что это единственная функция, которая вызывает функцию обмена swap().
Пример выполнения программы показан на рис. 12.7.
Рис. 12.7. Пример сортировки массива методом пузырька
Пример 12.9. Напишите программу, в которой используется функция по расчету среднего значения (среднего арифметического) одномерного числового массива, его исправленной выборочной дисперсии и среднего квадратичного отклонения (стандартного отклонения). Эти значения должны быть выведены на консоль в главной функции программы main()
Приведем формулы, по которым рассчитываются среднее значение выборки, исправленная выборочная дисперсия и среднеквадратичное отклонение.
Среднее выборочное значение одномерного массива размерностью N
где – элементы массива.
Исправленная выборочная дисперсия одномерного массива размерностью N
где mean – среднее значение данного массива
Исправленное среднеквадратичное отклонение S
где D – дисперсия данного массива.
Программный код решения примера:
#include < stdio.h> #include < conio.h> #include < stdlib.h> #include < math.h> // Прототип функцииdouble *mean_D_S(int arr[], int n); int main(void){ int mass[] = {2, -3, 5, 6, 7, 8, 9, -1}; int i, n; double *R; n = sizeof(mass)/sizeof(mass[0]); puts(" \n\t Initial array: "); for (i = 0; i < n; i++) printf(" %3d", mass[i]); // Вызов функции R = mean_D_S(mass, n); // Вывод расчтных характеристик массиваprintf(" \n\n The average value of an array: %g\n", R[0]); printf(" The dispersion of the array: %g\n", R[1]); printf(" The standard deviation of the array: %g\n", R[2]); // Освобождение памяти free(R); printf(" \n... Press any key: "); _getch(); return 0; } // Определение функцииdouble *mean_D_S(int arr[], int N){int j; double *PTR3 = (double *)calloc(N, sizeof(double)); double mean, D, S; mean = 0.0; for (j = 0; j < N; j++)mean += arr[j]; mean /= N; D = 0.0; for (j = 0; j < N; j++)D += (arr[j] - mean)*(arr[j] - mean); D /= (N-1); S = sqrt(D); PTR3[0] = mean; PTR3[1] = D; PTR3[2] = S; return PTR3; }В программе используется функция динамического распределения памяти calloc(), которая выделенные ячейки памяти обнуляет. Расчетные характеристики одномерного массива размещаются последовательно друг за другом в выделенной памяти для указателя *PTR3. Сформированный указатель функция возвращает в точку вызова функции mean_D_S().
Результат выполнения программы показан на рис. 12.8.
Рис. 12.8. Расчет статистических характеристик числового массива
Пример 12.10 Напишите программу с указателем на функции, которые рассчитывают следующие статистические характеристики одномерного числового массива: среднее арифметическое значение, медиану и модус (моду).
Среднее арифметическое рассчитывалось в предыдущем примере.
Приведем определения медианы и моды.
Медиана – это серединное значение в наборе данных – т. е. такое, что ровно половина значений располагается выше, и ровно половина ниже его.
Мода – это значение, наиболее часто встречающееся в наборе данных.
Программный код решения примера:
#include < stdio.h> #include < conio.h> double mean(int*, int); double median(int*, int); double mode(int*, int); int main(void) { int mass[] = {5, 6, 5, 5, 3, 6, 5, 3, 1, 4, 5, 3, 1, 6, 5, 2, 5, 2, 3, 4}; int *ptr = mass; int temp, i, j, k, n; // Указатель на функции double (*fun[3])(int*, int) = {mean, median, mode}; n = sizeof(mass)/sizeof(mass[0]); puts(" \n The original array: "); j = 0; for (i = 0; i < n; i++) { j++; if (j%6) printf(" %2d", mass[i]); else {puts(" "); printf(" %2d", mass[i]); j = 1; } } // Сортировка методом выбораfor (i = 0; i < (n - 1); ++i) { temp = ptr[i]; k = i; for (j = i + 1; j < n; ++j)if (ptr[j] < temp) { k = j; temp = ptr[k]; }ptr[k] = ptr[i]; ptr[i] = temp; } puts(" \n\n Results - mean, mediana, modus: "); for (i = 0; i < 3; i++)printf(" %6g\n", (*fun[i])(ptr, n)); printf(" \n\n... Press any key: "); _getch(); return 0; } // Определения функцийdouble mean(int* arr, int N){int i; double aver = 0.0; for (i = 0; i < N; i++)aver += arr[i]; return (aver/N); } double median(int* arr, int N){int i; double med = 0.0; for (i = 0; (i < N/2); i++)med = arr[i]; if (N % 2)med = arr[i]; elsemed = (med + arr[i])/2; return med; } double mode(int* arr, int N){int instances = 0, tempinst = 1, i = 1; double tempmode, mode_return = 1.0; tempmode = (double)arr[0]; while (i < N) { while ((double)arr[i] == tempmode) { i++; tempinst++; } if (tempinst > instances) { mode_return = tempmode; instances = tempinst; } tempinst = 1; tempmode = (double)arr[i]; i++; } return (mode_return); }В программе указатель на функции (*fun) – это массив указателей на функции, на три функции. В случае, когда возвращаемые значения функций имеют различный тип, то можно определить несколько указателей на функции.
Для понимания работы функции по расчету моды алгоритм вычислений рекомендуется формулировать следующим образом: " Разбить сортированный список значений на ряд меньших списков, каждый из которых содержит одинаковые значения. Пересчитать число элементов в этих списках, и список с наибольшим числом элементов будет соответствовать моде данных".
Результат выполнения программы показан на рис. 12.49.
Рис. 12.9. Значения среднего, медианы и модуса
Пример 12.11 Напишите программу сортировки массива строк с использованием указателей на функции.
Программный код решения примера:
#include < stdio.h> #include < conio.h> #include < string.h> // Прототипы функцийvoid bsort (char **arr, int size, int (*comp) (const char *s1, const char *s2)); int less (const char *s1, const char *s2); int greater (const char *s1, const char *s2); int main (void){ char *Lines[] = { " asd", " aza", " baza", " qwerty", " hello", " world", " aza" }; int n = sizeof (Lines) / sizeof (Lines[0]); int i; // Вызов функции сортировки по возрастанию в алфавитном порядке puts(" \n The sorting in ascending order: "); bsort (Lines, n, less); for (i = 0; i < n; ++i) printf(" \t %s\n", Lines[i]); // Вызов функции сортировки по убыванию в алфавитном порядке puts(" \n The sorting in descending order: "); bsort (Lines, n, greater); for (i = 0; i < n; ++i) printf(" \t %s\n", Lines[i]); printf(" \n\n... Press any key: "); _getch(); return 0; } // Определение функции сортировки строкvoid bsort (char **arr, int size, int (*comp) (const char *s1, const char *s2)){ int i, j; for (i = 0; i < size - 1; ++i) for (j = 0; j < size - 1; ++j) if (comp (arr[j], arr[j + 1]) > 0) { char *s = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = s; }} // Определение функции сравнения строк по возрастаниюint less (const char *s1, const char *s2){ return strcmp (s1, s2); } // Определение функции сравнения строк по убываниюint greater (const char *s1, const char *s2){ return -strcmp (s1, s2); }В программе используются указатель на функцию для вызова двух функций – less() и greater() в процессе сортировки для определения порядка расположения элементов (слов).
Результат выполнения программы показан на рис. 12.10.
Рис. 12.10. Пример сортировки строк
Пример 12.12 Напишите программу построения на экране дисплея графика следующей функции:
Предусмотрите возможность записи в текстовый файл графика данной функции.
Для решения примера используем средства вывода на печать форматированных данных без применения специальных графических библиотек.
Программный код решения примера:
/ Заголовочные файлы#include < stdio.h> #include < conio.h> #include < stdlib.h> #include < math.h> // Размеры диаграммы по ширине и высоте экрана#define SCREENW 79#define SCREENH 25 // Функция построения графика заданной функцииvoid plot (FILE *fout, double a, double b, double (*f) (double)){// Формальные параметры функции plot// FILE *fout – указатель на поток вывода // double a – левая граница оси абсцисс// double b – правая граница оси абсцисс// double (*f) (double) – указатель на функцию char screen[SCREENW][SCREENH]; double x, y[SCREENW]; double ymin = 0, ymax = 0; double hx, hy; int i, j; int xz, yz; // hx – шаг по оси абсцисс hx = (b - a) / (SCREENW - 1); for (i = 0, x = a; i < SCREENW; ++i, x += hx) { // вычисляем значение функции y[i] = f (x); // запоминаем минимальное и максимальное значения if (y[i] < ymin) ymin = y[i]; if (y[i] > ymax) ymax = y[i]; } hy = (ymax - ymin) / (SCREENH - 1); yz = (int)floor (ymax / hy + 0.5); xz = (int)floor (-a / hx + 0.5); // рисование осей координат for (j = 0; j < SCREENH; ++j) { for (i = 0; i < SCREENW; ++i) { if (j == yz & & i == xz) screen[i][j] = '+'; // '.', '? ', '+' else if (j == yz) screen[i][j] = '-'; else if (i == xz) screen[i][j] = '|'; else screen[i][j] = ' '; } } // рисование графика функции for (i = 0; i < SCREENW; ++i) { j = (int)floor ((ymax - y[i]) / hy + 0.5); screen[i][j] = '.'; // символ начертания графика } // вывод результата в файл или в стандартный поток stdout for (j = 0; j < SCREENH; ++j) { for (i = 0; i < SCREENW; ++i) fputc (screen[i][j], fout); fprintf (fout, " \n"); } } // Заданная функцияdouble f (double x){ return sin (3.0*x) * exp (-x / 3.0); //return x * x - 3; } int main (void) { // Вывод графика в стандартный поток (консоль) plot (stdout, 0.0, 10.0, f); printf(" \n\n … Press any key: "); _getch(); return 0; }В программе используется указатель на файл, который может быть стандартным потоком, т. е. экран дисплея. В главной функции main() происходит обращение к функции рисования графика plot(), в которую вводят фактические параметры, в частности файл – это stdout, т. е. стандартный поток, 0.0 – это левая граница оси абсцисс, 10.0 – правая граница оси абсцисс, f – имя функции с описанием зависимости y = f(x).
Пример выполнения программы показан на рис. 12.11.
Рис. 12.11. Пример построения графика функции на консоли
|
|