x[j+1] = temp;

// вставка взятого элемента

}

}

Сортировка выбором

Выбираем (находим) в массиве элемент с минимальным значением от первого (0-го) элемента до последнего ( (n-1)-го) и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до последнего элемента и меняем его местами со вторым элементом. И так далее для всех элементов до

(n-1)-го.

#include <iomanip>

#include <stdlib.h>

void vybor (int x[], int n); int main()

{const int n =10; int x[n];

int i, j;

	for (i=0; i<n; i++)		//инициализация массива
	x[i] = rand();
	for (i=0; i<n; i++)		//вывод массива
	cout << setw(6) << x[i];
	cout<<endl<<endl;
	vybor (x, n);
	for (i=0;i<n;i++)
	cout<<setw(6) << x[i]; //вывод отсортированного массива
	cout<<endl;
	_getch();
}	return 0;
void vybor (int x[], int n)
{for (i=0; i<n-1; i++)		//выбор минимального элемента
	{int min = x[i];
	int i_min = i ;	// и запоминание его номера

// поиск минимального элемента в оставшейся части массива for (j=i+1; j< n; j++)

if (x[j] < min)

{min = x[j]; i_min = j;

}

x[i_min] = x[i]; //замена элементов x[i] = min;

}}

Примеры

Нахождение номера первого вхождения числа y в массив Х

Присвоить переменной k либо номер первого вхождения числа y в массив X, либо число n+1, если y не входит в Х:

#define N 10 int main ()

{int y, k, i, X[N];

cout << "input 10 X[i]\n"; for (i=0; i<N ; i++)

cin >> (X[i]);

Программирование – лекция 12 (лекции Стрикелевой Л.В.)

26

cout << "y?\n"; cin >> y;

k=0;

while ((k < N) && (y != X[k])) k= k+1;

cout << "index=" << k<< endl; _getch();

return 0;

}

Результаты: input 10 X[i]

1 2 3 4 5 6 7 8 9 0 y?

1

0

Поиск в массиве максимального элемента и его номера

#include <iomanip> #include <stdlib.h> #include <time.h>

int max1(int*		ar,int n,int& imax);		//первый способ
int max2(int*		ar,int n,int& imax);		//второй способ
int main()
{	const int n=20;
	static int	mas[n];
	int i, max,	imax=0;	//для получения разных случайных последвательностей
	srand (time(0));
	for (i=0; i<n; i++)		//заполнение массива случайными числами от 0 до 14
	mas[i] = rand()%15;
	for (i=0; i<n; i++)			//вывод значений элементов массива
	cout <<	setw(6)<< mas[i];

cout<<endl<< endl;

max = max1(mas, n, imax);

cout<<"max = "<< max <<" imax= "<< imax+1 <<endl;

max = max2(mas, n, imax);

cout<<"max = "<< max <<" imax= "<< imax+1 <<endl; _getch();

return 0;

}

int max1(int * ar, int n, int &imax)			//первый способ
{
int max=ar[0];imax=0;
for (int i=1; i<n; i++)			//максим.элемент и его номер
if (max < ar[i]) { max = ar[i]; imax=i;}
return max;
}
int max2(int * ar, int n, int &imax)			//второй способ
{
imax=0;
for (int i=1; i<n; i++)		//поиск номера максим.элемента
imax = ar[imax] < ar[i] ? i : imax;
return ar[imax];	//максим.элемент
}			27
Программирование – лекция 12 (лекции Стрикелевой Л.В.)

Проверка элементов массива на некоторую закономерность

Присвоить переменной t значение true, если в массиве X нет нулевых элементов, и при этом положительные элементы чередуются с отрицательными, иначе – значение false:

#include <math.h>
const int n=10;
int main ()
{	X[n], i;
int
bool t;
printf ("input X[i]\n");
for (i=0; i<n; i++)			//ввод массива
	scanf ("%d", &X[i]);
for (i=0; i<n; i++)			//вывод массива
	printf ("%6d", X[i]);
if (X[0] && X[1])			//не равны 0
t =(X[0]/abs(X[0]) == - X[1]/abs(X[1]));
else
{printf ("\nX[i]==0\n"); return 1;}
for (i=1; i<n-1; i++)
{if (X[i+1])		//не равно 0
	t=t && ((X[i] / abs(X[i])) == - (X[i+1] / abs(X[i+1])));
else{printf("\nX[i]==0\n"); return 1;}
if (!t) { printf ("\nnot\n");
}	break;	//досрочный выход из цикла
else printf ("\nyes %d \n", t);
}
_getch();
return 0;
}
или:
#include <math.h>
const int n=10;
int main ()
{	X[n];
int
bool t;
printf ("input X[i]\n");			//ввод массива
for (int i=0; i<n; i++)
	scanf ("%d", &X[i]);		//вывод массива
for (int i=0; i<n; i++)
	printf ("%6d", X[i]);
if (X[0] && X[1])			//не равны 0
t=(X[0] * X[1] <0);
else	{printf ("\nX[i]==0\n");
}	return 1;
for (int i=1; i<n-1; i++)			//не равно 0
	if (X[i+1])
		t=t && (X[i] * X[i+1] <0);
	else {printf("\nX[i]==0\n");
	}	return 1;
		%d \n", t);
printf ("\n yes
_getch();			28
Программирование – лекция 12 (лекции Стрикелевой Л.В.)

return 0;

}

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

По заданному массиву символов С получить массив В логических значений по правилу: элементу B[i] присвоить true, если C[i] – цифра, и false – в противном случае:

const int n=10; int main ()

{

char C[n], i; bool B[n];

cout << "input X[i]\n"; for (i=0; i<n; i++)

cin >> C[i]; //ввод массива for (i=0; i<n; i++)

cout << C[i] << " "; //вывод массива cout << endl;

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

{B[i] = (C[i] >'0') && (C[i] < '9'); cout << B[i];}

cout << endl; _getch(); return 0;

}

Нахождение количества положительных элементов между максимальным и минимальным элементами целочисленного массива

Рассмотрим нахождение количества положительных элементов между максимальным и минимальным элементами целочисленного массива из 10 элементов:

Запишем алгоритм в самом общем виде:

1.Определить, где в массиве расположены максимальный и минимальный элементы, т.е. найти их индексы.

2.Просмотреть все элементы, расположенные между ними. Если элемент

массива положительный, увеличить счетчик элементов на 1. Составим, кроме того, тестовый пример:

6

-8

15

9

-1

3

5

-10 12

2

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

1.Определить, где в массиве расположены максимальный и минимальный элементы, т.е. найти их индексы.

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

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

Программирование – лекция 12 (лекции Стрикелевой Л.В.)

29

2.Определить границы просмотра массива для поиска положительных элементов, находящихся между его максимальным и минимальным элементами:

a.Если максимум расположен в массиве раньше, чем минимум, принять левую границу просмотра равной индексу максимума, иначе – индексу минимума.

b.Если максимум расположен в массиве раньше, чем минимум, принять правую границу просмотра равной индексу минимума, иначе – индексу максимума.

3.Обнулить счетчик положительных элементов. Просмотреть все элементы массива, расположенные в указанном диапазоне.. Если очередной элемент массива положительный, увеличить счетчик элементов на 1.

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

int main()
{
const int n = 10;	-5, 1, -2, 1, -1, 3, 8, 4};
int a[n] = {1, 3,
int i, imax, imin, count;
for (i = imax = imin =0; i<n; i++) {
	if (a[i] > a[imax]) imax = i;
}	if (a[i] < a[imin]) imin = i;
		//для отладки
cout << "\nmax = " << a[imax] << "\tmin = " << a[imin];
int ibeg = imax <	imin ? imax : imin;
int iend = imax <	imin ? imin : imax;	// для отладки
cout << "\nibeg =	" << ibeg << "\tiend = " << iend;
for (count=0, i =	ibeg+1; i<iend; i++)
if (a[i] >0) count++;
cout << "\n >0: "	<< count << endl;
_getch();
return 0;
}

Массив можно всегда просматривать от максимума к минимуму, а индекс при просмотре увеличивать или уменьшать в зависимости от их взаимного расположения. В приведенной ниже программе направление просмотра, то есть приращение индекса, хранится в переменной d. Если массив просматривается слева направо, она равна 1, иначе

– -1:

int main()
{
const int n = 10;
int a[n];
int i, imax, imin, kol;
cout << "input " << n << "a[i]" << endl;	//ввод массива
for (i = 0; i<n; i++) cin >> a[i];
for (i = 0; i<n; i++) cout << a[i] << " ";	//вывод массива
for (i = imax = imin =0; i<n; i++)
{if (a[i] > a[imax]) imax = i;	//поиск индексов максимального и
if (a[i] < a[imin]) imin = i;
}	// минимального элементов
int d = 0;
if (imax < imin) d = 1;
else if (imax > imin) d = -1;
for (kol=0, i = imax+d; i!=imin; i +=d)
if (a[i] >0) kol++;
cout << "\n >0: " << kol << endl;
_getch();	30
Программирование – лекция 12 (лекции Стрикелевой Л.В.)