книги / Практикум по программированию на языке Си

В программе SIZE_ARRAY – препроцессорный идентификатор, который в тексте программы заменяется значением (константой) 100. Переменная size задает реальное количество элементов массива, используемых при выполнении программы. Если при вводе значения size выполнится условие size>SIZE_ARRAY, программа заканчивает выполнение с выдачей сообщения об ошибке.

ЗАДАЧА 06-05. Определите с помощью инициализации целочисленный массив. Введя целое число, проверьте его "принадлежность" массиву. (Найдите в массиве элемент с максимальным индексом, значение которого совпадает с введенным числом. Выведите значение индекса либо –1, если элемент отсутствует в массиве.)

/* 06_05.c - поиск в массиве. Размер задан инициализацией /

#include <stdio.h> int main ()

{

int i, number, count=-1; int size;

int ar[]={0,1,2,3,4,5,4,3,2,1,0}; printf("number="); scanf("%d",&number); size=sizeof(ar)/sizeof(ar[0]); for (i=0; i<size; i++)

if(number == ar[i]) count=i; printf("count=%d",count); return 0;

}

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

number=6<ENTER> count=-1

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

number=3<ENTER>

count=7

171

ЗАДАНИЕ. Модифицируйте программу, чтобы выполнялся поиск элемента с минимальным индексом (самый левый), значение которого совпадает с введенным числом.

Вариант решения предлагает программа 06_05_1.с.

ЗАДАЧА 06-06. Решите предыдущую задачу для массива с символьными элементами.

/* 06_06.c - поиск индекса символа в массиве. */ #include <stdio.h>

int main ()

{

int i, count=-1; char character;

char simb[]={'0','1','2','3','4','5','a'}; printf("character="); scanf("%c",&character);

for (i=0; i<sizeof(simb)/sizeof(simb[0]); i++) if(character == simb[i]) count=i;

printf("count=%d\n",count); return 0;

}

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

character=a<ENTER>

count=6

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

character=4<ENTER>

count=4

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

ЗАДАЧА 06-07. Введите количество n элементов последовательности вещественных чисел. Затем введите значения самих

элементов ai (i = 1, n) и вычислите средние значения отрицатель-

172

ных S– и положительных S+. Напечатайте значения элементов последовательности, удовлетворяющих условию S– < ai < S+.

/* 06_07.c - выбор элементов из массива с переменными размерами. */

#include <stdio.h> int main ()

{

int sizeArray; printf("sizeArray="); scanf("%d",&sizeArray);

{int i, j;

double a[sizeArray];

double sminus=0.0, splus=0.0; int nplus=0, nminus=0;

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

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

scanf("%le",&a[i]); if (a[i]<0.0) {

nminus++;

sminus+=a[i];

}

if (a[i]>0.0) { nplus++; splus+=a[i];

}

}

if(nplus > 0) splus/=nplus; if(nminus > 0) sminus/=nminus; printf("\nsminus=%e",sminus); printf("\nsplus=%e",splus); printf("\nsminus<a[i]<splus"); for (i=0; i < sizeArray; i++)

if (a[i]>sminus && a[i]<splus) printf("%ca[%d]=%e",j++%3?'\t':'\n',i,a[i]);

}

return 0;

}

Примечание. Еще раз обратите внимание, что для ввода значения типа double используется спецификация преобразования %le.

173

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

sizeArray=6<ENTER> a[0]=-3<ENTER> a[1]=7<ENTER> a[2]=-4<ENTER> a[3]=-5<ENTER> a[4]=9<ENTER> a[5]=2<ENTER>

sminus=-4.000000e+00 splus=6.000000e+00 sminus<a[i]<splus

a[0]=-3.000000e+00 a[5]=2.000000e+00

ЗАДАНИЕ. Дополните предыдущую задачу и измените программу так, чтобы она напечатала элементы последовательно-

сти (массива), разделив их на три группы: ai ≤ S–; S– < ak < S+; S+ ≤ aj.

ЗАДАНИЕ. Переделайте программу таким образом, чтобы в ней не использовался массив переменного размера. Предельный размер массива определите препроцессорной константой. Включите проверку вводимого пользователем значения количества элементов.

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

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

ЗАДАЧА 06-08. Введите размер массива (arraySize), затем значения его целочисленных элементов. Сформируйте новый массив и присвойте его элементам значения элементов исходного масси-

174

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

// 06_08.c - формирование отсортированного массива

#include <stdio.h> #include <math.h> int main ()

{

int arraySize; printf("arraySize="); scanf("%d",&arraySize);

{int i, k;

int series[arraySize]; int result[arraySize];

for (i=0; i<arraySize; i++) { printf("series[%d]=",i);

scanf("%d",&series[i]);

}

k=0;

for (i=0; i<arraySize; i++) if (series[i]%2 == 0)

result[k++]=series[i]; for (i=0; i<arraySize; i++)

if (series[i]%3 == 0 && series[i]%2 != 0) result[k++]=series[i];

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

if (series[i]%2 != 0 && series[i]%3 != 0) result[k++]=series[i];

for (i=0; i<arraySize; i++) printf

("%cresult[%d]=%d",i%3?'\t':'\n',i,result[i]);

}

return 0;

}

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

arraySize=9<ENTER>

series[0]=5<ENTER>

series[1]=2<ENTER>

series[2]=3<ENTER>

series[3]=9<ENTER>

175

series[4]=11<ENTER>

series[5]=46<ENTER>

series[6]=5<ENTER>

series[7]=7<ENTER>

series[8]=6<ENTER>

result[0]=2 result[1]=46 result[2]=6 result[3]=3 result[4]=9 result[5]=5 result[6]=11 result[7]=5 result[8]=7

Алгоритм очевиден – трижды в трех циклах "просматривается" исходный массив series[] и по разным правилам анализируются значения его элементов. Переменная k служит счетчиком выбранных из исходного массива элементов и одновременно индексом элементов массива результатов: result[k++]. При каждом присваивании значение переменной k "автоматически" увеличивается на 1.

ЗАДАНИЕ. Переделайте программу таким образом, чтобы в ней не использовался массив переменного размера. (См. задание к предыдущей задаче.)

6.2. Вложенные циклы и сортировка массивов

ЗАДАЧА 06-09. Введя размер (количество элементов) одномерного целочисленного массива, определите массив и присвойте его элементам значение выражения 12 * sin((5 * i + 2) / 3), где i – индекс элемента. Переставьте элементы массива так, чтобы вначале разместились элементы с четными, а затем с нечетными значениями. Напечатайте массив до и после сортировки. Не используйте вспомогательные массивы.

Внешне задача не кажется сложной, но ее программная реализация и выбор алгоритма потребуют некоторых знаний и усилий. Вопервых, в программе нужно использовать библиотечную функцию sin(), аргумент которой должен иметь тип double. Приведенное выражение (5*i+1)/3 нельзя непосредственно использовать, так как при целочисленном индексе i будет выполняться целочисленное деление с округлением до целых значений. Во-вторых, применение

176

библиотечной функции sin() потребует включения заголовочного файла math.h. В третьих, функция sin() возвращает вещественное значение (типа double), а формируемый массив должен иметь целочисленное значение (типа int). Четвертая особенность – алгоритмическая: нужно достаточно экономно реализовать алгоритм сортировки. Рассмотрим крайние ситуации. Если все элементы массива четные или все нечетные, – задача решена. Если в начале массива все элементы подряд четные, а в конце – нечетные, – задача решена. В противном случае остается наиболее общий вариант, требующий перестановок значений элементов. Будем менять значения самого левого нечетного элемента с самым правым четным. Для этого используем два вложенных цикла (рис. 6.1). Внешний цикл с параметром (индексом) j, возрастающим от 0 до предельного значения jmax. Внутренний цикл с уменьшающимся параметром (индексом) k от kmax до j+1. Предельное значение jmax для параметра j должно быть переменным. До начала проверки значений элементов массива jmax равно sizeArray-1, т.е. проверять предполагается все элементы массива. Если в процессе проверки (в цикле по j) обнаружен нечетный элемент, т.е. aj%2!=0, выполняется вложенный цикл с параметром k. Вначале kmax устанавливается равным sizeArray-1, т.е. перебор элементов массива выполняется от его конца. Если обнаружен четный элемент, т.е. ak%2==0, значения aj и ak меняются местами, kmax устанавливается равным (k-1), jmax присваивается значение (k-1).

Рис. 6.1. Обмен значений при сортировке в задаче 06-09

Программная реализация:

/* 06_09.c - сортировка целочисленного массива. */ #include <stdio.h>

177

#include <math.h> int main ()

{

int sizeArray; printf("sizeArray="); scanf("%d",&sizeArray);

{int i, j, jmax, k, kmax;

int series[sizeArray], temp; for (i=0; i<sizeArray; i++)

series[i]=12*sin((5*i+2)/3.0); for (i=0; i<sizeArray; i++)

printf ("%cseries[%d]=%d",i%4?'\t':'\n',i,series[i]);

jmax=sizeArray-1; kmax=sizeArray-1;

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

{ if (series[j]%2 == 0) continue; for (k=kmax; k > j ; k--)

if (series[k]%2 == 0)

{temp =series[j]; series[j]=series[k]; series[k]= temp; kmax=jmax=k-1;

break; /* выход из цикла с параметром k */

}

}

printf("\nResult:");

for (i=0; i<sizeArray; i++) printf

("%cseries[%d]=%d",i%4?'\t':'\n',i,series[i]);

}

return 0;

}

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

sizeArray=8<ENTER>

series[0]=7 series[1]=8 series[2]=-9 series[3]=-6 series[4]=10 series[5]=4 series[6]=-11 series[7]=-2 Result:

series[0]=-2 series[1]=8 series[2]=4 series[3]=-6 series[4]=10 series[5]=-9 series[6]=-11 series[7]=7

178

Обратите внимание на использование в циклах операторов continue и break.

ЭКСПЕРИМЕНТ. В обращении к функции sin() замените вещественную константу 3.0 на целое число 3. Объясните результаты.

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

ЗАДАНИЕ. Переделайте программу, избавившись от массива переменных размеров (исключите неконстантное выражение в определении массива).

ЗАДАНИЕ. Модифицируйте программу таким образом, чтобы сортировка элементов массива выполнялась по другому правилу, например:

1) разместите в начале массива все положительные элементы;

2)разместите в начале массива элементы, значения которых кратны трем, и элементы, значения которых кратны пяти.

Задачи сортировки многочисленны и обычно не просты. Основная их особенность – необходимость экономии памяти и повышения быстродействия программ (сокращение количества операций). Если в алгоритме не предусматривается создания вспомогательных массивов, то требуемая память обычно определяется размером исходного (сортируемого) массива. Быстродействие оценивается тремя факторами: сколько раз просматривается исходный массив, какое количество обменов выполняется и сколько сравнений используется в процессе сортировки. Классической работой по алгоритмам сортировки является [12]. Д. Кнут выделяет и рассматривает отдельно внешнюю сортировку и внутреннюю сортировку. Внешняя сортировка предусматривает использование внешних запоминающих устройств (файловая система) для хранения исходных данных, а также промежуточных и окончательных результатов. При внутренней сортировке число элементов, подлежащих сортировке, относительно мало и весь процесс можно провести "в оперативной памяти ЭВМ". Именно к внут-

179

ренней сортировке относятся задачи упорядочения элементов массивов.

ЗАДАЧА 06-10. Введя размер n массива, вычислите значения его элементов по следующей формуле:

		i			i	2
	a =		−	sin			, i = 0, n − 1.
	i	i + 2			i +	2

Упорядочите значения элементов по возрастанию.

Среди многочисленных алгоритмов сортировки (см. [12]) выберем простейший, реализующий прямой перебор. Нам понадобятся два вложенных цикла. Во внешнем цикле (с параметром – индексом j) последовательно перебираются элементы, и каждый из них во вложенном цикле с параметром – индексом i сравнивается со всеми последующими. Когда aj<ai, выполняется обмен значений ai и aj.

/* 06_10.c - сортировка по возрастанию элементов массива */

#include <stdio.h> #include <math.h> int main ()

{

int size; printf("size="); scanf("%d",&size);

{int i, j;

double row[size], temp; for (i=0; i<size; i++)

row[i]=i/(2.0+i)-sin(i*i/(2.0+i)); for (i=0; i<size; i++)

printf ("%crow[%d]=%9.2e",i%3?'\t':'\n',i,row[i]);

for (j=0; j < size-1; j++) for (i=j+1; i < size; i++)

if (row[j]>row[i])

{temp=row[j];

row[j]=row[i];

row[i]=temp;

}

printf("\nResult:"); for (i=0; i<size; i++)

180