книги / Практикум по программированию на языке Си
..pdf
printf("\nResulting array:\n"); for (i=0; i<sizeArray; i++)
printf("%c[%d]=%d",i%5?'\t':'\n',i,integer[i]); return 0;
}
Результаты выполнения программы:
Source array:
[0]=5 |
[1]=6 |
[2]=2 |
[3]=4 |
[4]=9 |
[5]=2 |
[6]=1 |
[7]=3 |
[8]=8 |
[9]=6 |
Resulting array: |
|
|
|
|
[0]=5 |
[1]=6 |
[2]=2 |
[3]=4 |
[4]=0 |
[5]=2 |
[6]=0 |
[7]=3 |
[8]=8 |
[9]=6 |
В функции minMaxIndex() параметры-указатели int *iMin и int *iMax при разыменовании обеспечивают доступ к внешним по отношению к функции переменным, адреса которых использованы в качестве аргументов. Именно этим внешним переменным kMin, kMax присваиваются индексы искомых элементов массива. Далее выражения integer[kMin], integer[kMax] позволяют получить доступ к соответствующим элементам массива-аргумента integer[].
Рассмотрим особенности передачи адресов элементов массивапараметра через другие параметры функции.
ЗАДАЧА 08-16. Определите функцию, которая возвращает через параметры адреса максимального и минимального элементов массива, заданного в качестве параметра. В основной программе определите одномерный массив и, используя функцию, замените найденные элементы нулевыми.
Чтобы при выполнении операторов тела функции изменялся внешний по отношению к функции объект-указатель, аргументом функции должен быть адрес указателя. При этом соответствующий параметр необходимо специфицировать как указатель на указатель
301
на объект нужного типа. Таким образом, для функции нужен такой прототип:
void minAndMax(int mir[], int n, int **pMin, int **pMax);
где mir – имя массива, n – его размер (количество обрабатываемых элементов), pMin – указатель (адрес) на объект, предназначенный для хранения адреса объекта типа int. Чтобы "достать" значение указателя (адреса), нужна операция разыменования, чтобы оперировать с тем значением, которое он адресует, нужно использовать еще одну операцию разыменования.
Задачу решает следующая программа:
/* 08_16.c - адреса максимального и минимального элементов массива-параметра */
#include <stdio.h>
void minAndMax(int mir[], int n, int ** pMin, int ** pMax)
{
int j;
* pMin = * pMax = &mir[0]; for(j=1; j<n; j++)
{if (** pMin > mir[j]) *pMin = &mir[j]; if (** pMax < mir[j]) *pMax = &mir[j];
}
}
int main()
{
int integer[]={2,4,9,2,1,3,8,6,3,5};
int sizeArray=sizeof(integer)/sizeof(integer[0]); int i, * kMin, * kMax;
printf("Source array:\n"); for (i=0; i<sizeArray; i++)
printf("[%d]=%d%c",
i,integer[i],(i+1)%5?'\t':'\n'); minAndMax(integer, sizeArray, &kMin, &kMax); * kMin = * kMax = 0;
printf("\nResulting array:\n"); for (i=0; i<sizeArray; i++)
printf("[%d]=%d%c",
i,integer[i],(i+1)%5?'\t':'\n');
return 0;
}
302
Результаты выполнения программы:
Source array: |
[2]=9 |
[3]=2 |
[4]=1 |
|
[0]=2 |
[1]=4 |
|||
[5]=3 |
[6]=8 |
[7]=6 |
[8]=3 |
[9]=5 |
Resulting array: |
[2]=0 |
[3]=2 |
[4]=0 |
|
[0]=2 |
[1]=4 |
|||
[5]=3 |
[6]=8 |
[7]=6 |
[8]=3 |
[9]=5 |
Обратите внимание на определенные в основной программе пе- ременные-указатели kMin, kMax. При обращении к функции minAndMax() в качестве аргументов используются их адреса (&kMin, &kMax). Разыменования *kMin, *kMax обеспечивают доступ к значениям искомых элементов массива-аргумента.
ЗАДАЧА 08-17. Определите функцию с двумя параметрамимассивами. Функция возвращает указатель на массив-аргумент, среднее значение элементов которого максимально (больше, чем у второго массива-аргумента). В основной программе определить два массива, используя функцию, выбрать из двух массивов один и присвоить его "среднему" (центральному) элементу нулевое значение. В случае если в массиве четное количество элементов, то "обнулить" элемент с меньшим индексом.
Будем решать задачу для массивов с вещественными элементами (типа double). В программе удобно использовать вспомогательную функцию для вычисления среднего значения элементов массивапараметра. Прототип ее может быть таким:
double average(double array[], int size);
Функция для "выбора" массива-аргумента должна возвращать указатель на его начало. В основной программе целесообразно определить вспомогательный указатель и присвоить ему результат, возвращаемый функцией. Далее, сравнивая значение этого указателя с именами массивов, определим, какой из них выбран, изменим его центральный элемент и напечатаем.
303
К сожалению, только так можно определить размеры выбранного функцией массива. Возвращаемое значение – это адрес, а не "настоящее" имя массива, и поэтому с помощью sizeof нельзя вычислить число его элементов.
Задачу решает следующая программа:
/* 08_17.c - функция с двумя параметрами-массивами*/ #include <stdio.h>
#include <stdlib.h> /* для exit() */ double average(double array[], int size)
{int i;
double a=0.0; if (size <= 0)
{printf("\nParameter error!"); exit(1);
}
for (i=0; i < size; i++) a += array[i];
return a/size;
}
double * maxArray(double ar1[], int n1, double ar2[], int n2)
{
double mean1=0.0, mean2=0.0; mean1 = average(ar1,n1); mean2 = average(ar2,n2);
return mean1 > mean2 ? ar1 : ar2;
}
int main()
{
double real[] = {2,4,9,2,1,3,8,6,3,5};
int sizeReal = sizeof(real)/sizeof(real[0]); double agent[] = {3.0,4.9,5.6,7.1,3.5};
int sizeAgent = sizeof(agent)/sizeof(agent[0]); double * pResult;
int j, size;
pResult = maxArray(real,sizeReal,agent,sizeAgent); if (pResult == real)
{ printf("Real array:\n"); size = sizeReal;
}
if (pResult == agent)
304
{printf("Agent array:\n"); size = sizeAgent;
}
pResult[size/2] =0.0; for (j=0; j < size; j++)
printf("[%d]=%5.2f%c",
j,pResult[j],(j+1)%5?'\t':'\n');
return 0;
}
Результаты выполнения программы:
Agent array:
[0]= 3.00 [1]= 4.90 [2]= 0.00 [3]= 7.10 [4]= 3.50
ЗАДАНИЕ. Для знакомства с особенностями, опасностями и ограничениями применения вызова функции, возвращающей адрес некоторого объекта, замените в программе 08_17.с во всех выражениях функции main() указатель pResult на вызов: maxArray(real, sizeReal, agent, sizeAgent).
Трансляция и исполнение соответствующей заданию программы 08_17_1.с пройдут вполне успешно, но результат будет таким:
Agent array: |
[2]=9.00 |
3]=2.00 |
[4]=1.00 |
|
[0]=2.00 |
[1]=4.00 |
|||
Как и в программе 08_17.с с указателем pResult, правильно выбрано название массива, но напечатаны первые 5 элементов другого массива. Объяснение: после оператора
maxArray(real,sizeReal,agent,sizeAgent)[size/2]=0.0;
(заменившего pResult[size/2]=0.0;) изменился третий (с индексом 2) элемент массива agent и при последующих сравнениях массивов выбирается указатель на массив real. Поэтому аргумент функции printf()
maxArray(real, sizeReal, agent, sizeAgent)[j]
(заменивший выражение pResult[j]) будет "доставать" элемент real[j].
305
8.4. Рекурсивные функции
При разработке рекурсивных алгоритмов (а в случае языка Си – рекурсивных функций) должны соблюдаться два правила:
1. В последовательности рекурсивных обращений должен быть явный разрыв, т.е. необходима проверка условия, по которому следует завершить исполнение.
2.При "самовызовах" функции должны происходить изменения параметров, и эти изменения после конечного числа вызовов должны привести к выполнению условия из пункта 1.
ЗАДАЧА 08-18. Напишите рекурсивную функцию для возведения в целую степень вещественного основания. (Аналогом служит библиотечная функция pow().) В основной программе вводите разные значения основания и степени. Если оба введенных значения равны 0, завершите выполнение программы.
В рекурсивной функции необходимо предусмотреть соблюдение двух сформулированных выше правил. Чтобы вычислить степень k некоторого основания x, необходимо умножить значение x на xk-1 при k>0 или разделить на x значение xk-1 при k<0. Отсюда следуют правила изменения параметра, определяющего значение степени при рекурсивном обращении к функции из ее тела. Прекращение вызовов должно происходить при нулевом значении параметра k. В этом случае возвращается значение 1.0, так как для любого x (не равного нулю) x0 равно 1. Второе условие прекращения выполнения функции – равенство нулю основания. В этом случае функция возвращает нулевое значение. Третье условие, прерывающее выполнение функции – равенство нулю и основания и степени. В этом случае результат не определен. Указанным соглашениям соответствует функция expo() из следующей программы:
/* 08_18.c - рекурсивная функция для возведения в степень */
#include <stdio.h>
#include <stdlib.h> /* для exit()*/ double expo(double x, int k)
{
if (k == 0 && x == 0.0)
{printf("\nError arguments of expo()!"); exit(1);
306
}
if (k == 0) return 1.0; if (x == 0.0) return 0.0;
if (k > 0) return x*expo(x,k-1); if (k < 0) return expo(x,k+1)/x;
}
int main()
{
int power; double base; while (1)
{
printf("base="); scanf("%le",&base); printf("power="); scanf("%d",&power); printf("expo()=%f\n",expo(base, power));
}
return 0;
}
Результаты выполнения программы:
base=2<ENTER> power=-3<ENTER> expo()=0.125000 base=5<ENTER> power=2<ENTER> expo()=25.000000 base=0<ENTER> power=4<ENTER> expo()=0.000000 base=3<ENTER> power=0<ENTER> expo()=1.000000 base=0<ENTER> power=0<ENTER>
Error arguments of expo()!
В функции main() бесконечный цикл, в котором пользователь вводит пары: значение основания (base) и значение показателя степени (power). Обращение к функции expo() выполняется в аргументе функции printf(). При вводе нулевых значений base и power
307
в функции expo() вызывается библиотечная функция exit(), завершающая исполнение программы. (Тем самым заканчивается "бесконечный" цикл в функции main().)
ЗАДАНИЕ. В текст функции expo() вставьте печать значений параметров и проследите, как они изменяются при выполнении функции.
Рекурсия применима (но не всегда рекомендуется) при программировании итерационных алгоритмов, применяемых в вычислительной математике. В учебных целях для освоения особенностей построения рекурсивных алгоритмов и соответствующих им рекурсивных функций нужно научиться преобразовывать итерационные алгоритмы в рекурсивные и обратно. Напомним, что основной конструкцией для реализации итерационного алгоритма является цикл, а для рекурсивного – самовызов функции.
ЗАДАНИЕ. В предыдущей задаче замените рекурсивный алгоритм циклом, т.е. напишите новую функцию возведения в целую степень вещественного основания. Основную программу 08_18_1.с не изменяйте (за исключением смены имени вызываемой функции).
Функция без рекурсии может быть, например, такой:
double expoCycle(double x, int k)
{
int i;
double temp = 1.0;
if (k == 0 && x == 0.0)
{printf("\nError arguments of expo()!"); exit(1);
}
if (k == 0) return 1.0; if (x == 0.0) return 0.0;
for (i = 0; i < abs(k); i++) temp *= x;
if (k < 0)
temp = 1.0/temp;
308
return temp;
}
Задачу в целом решает программа 08_18_1.с.
ЗАДАЧА 08-19. Напишите рекурсивную функцию для сортировки методом отбора элементов одномерного массива с вещественными элементами. Сортировку (т.е. упорядочение) следует выполнять по возрастанию значений элементов массива. В основной программе определите и инициализируйте массив, затем, используя функцию, упорядочите его.
Напомним, что метод отбора состоит в следующем. Среди элементов массива выберем элемент с наименьшим значением и "переставим" его на место нулевого элемента (с нулевым индексом). Затем выберем наименьший из элементов, начиная с первого, и поставим его на место элемента индексом 1 и т.д.
Рекурсивную процедуру метода отбора можно представить таким псевдокодом:
Если в массиве 1 элемент Завершить процедуру
Иначе Найти в массиве минимальный элемент и переставить его
в начало массива Увеличить на 1 указатель, адресующий начало массива
Вызвать рекурсивную процедуру сортировки
Следующая программа решает задачу:
/* 08_19.c – метод отбора в рекурсивной функции сортировки */
#include <stdio.h>
/* поменять местами значения v[i] и v[j] */ void swap(double v[], int i, int j)
{
double temp; temp = v[i]; v[i] = v[j]; v[j] = temp;
309
}
/* Сортирует массив-параметр по возрастанию */ void arraySort(double v[], int n)
{
int i, new=0; if (n <= 1)
return;
for (i = 1; i < n; i++)
if (v[i] < v[new]) new = i; if (new != 0) swap(v, 0, new); arraySort(v+1, n-1);
}
int main()
{
int i;
double array[] = {2,4,9,2,1,3,8,6,3,5};
int sizeArray = sizeof(array)/sizeof(array[0]); arraySort(array, sizeArray);
printf("Sort Array:\n"); for (i=0; i<sizeArray; i++)
printf("[%d]=%4.2f%c",
i,array[i],(i+1)%4?'\t':'\n');
return 0;
}
Результаты выполнения программы:
Sort Array:
[0]=1.00 [1]=2.00 [2]=2.00 [3]=3.00 [4]=3.00 [5]=4.00 [6]=5.00 [7]=6.00 [8]=8.00 [9]=9.00
В программе использована функция swap(), обменивающая значения элементов массива-параметра. Индексы этих элементов определяют параметры функции.
У рекурсивной функции arraySort() два параметра: первый адресует начало сортируемого массива, второй задает количество его элементов. В соответствии с псевдокодом проверяется количество элементов массива, если n<=1, то исполнение завершается. В противном случае в цикле определяется индекс (переменная new) минимального элемента. Если минимальный элемент не в начале массива
310