Как найти минимальное значение в блок схемах

Принцип поиска максимального или
минимального элемента массива заключается
в следующем: в дополнительную переменную
заносится значение первого элемента
массива, которое принимается за максимум
(минимум); затем организовывается перебор
оставшихся элементов массива, каждый
из которых сравнивается с максимумом
(минимумом); если текущий элемент массива
оказывается больше (меньше), чем принятый
за максимум (минимум), то этот элемент
становится максимальным (минимальным).
Таким образом, после завершения перебора
элементов массива в дополнительной
переменной окажется максимальное
(минимальное) значение среди элементов
массива. Фрагмент блок-схемы алгоритма,
реализующий описанный метод приведен
на рисунке 5.2.1.

В блоке 1 дополнительным переменным maxиmin, в которых
будут храниться максимальное и минимальное
значения соответственно, присваивается
значение 1-го элемента массива. Кроме
этого введены еще две переменныеimaxиimin, которые будут
использоваться для хранения номеров
максимального и минимального элементов
массива. С помощью блока модификации
(блок 2) организовывается цикл по перебору
элементов массива Х (перебор начинается
со 2-го элемента, так как 1-й элемент уже
обработан в блоке 1). Если текущий элемент
массиваX_iбольше значения, которое хранится в
переменнойmax(блок 3), то за максимум принимается
значение этого элемента:max=X_i,
и запоминается его номер:imax=i(блок 4). Если текущий элемент массива
не больше максимума, то проверяется, не
меньше ли он минимума (блок 5). В случае
если текущий элементX_iокажется меньше минимального значения,
которое хранится в переменнойmin,
то за минимум принимается значение
этого элемента:min=X_i,
и запоминается его номер:imin=i(блок 6). После выхода из цикла будут
выведены значения максимального и
минимального элементов, а также их
номера в массиве (блок 7).

Приведенный
выше алгоритм имеет один недостаток –
в нем используется две лишние переменныеmaxиmin.
Зная индекс элемента массива всегда
можно получить его значение, поэтому
нет необходимости хранить максимальное
и минимальное значения в отдельных
переменных. Оптимальный алгоритм
приведен на рис. 5.2.2.

В блоке 1 дополнительным переменным
imaxиimin,
используемых для хранения номеров
максимального и минимального элемента,
присваивается значение 1. Таким образом,
за максимум и минимум принимается 1-й
элемент массива, само же значение этого
элемента нигде дополнительно не
сохраняется. Оставшиеся элементы массива
также перебираются, начиная со второго
(блок 2). При этом каждый элемент массиваX_i
сравнивается с
элементами, имеющими номер равныйimax(блок 3) иimin(блок
6), т.е. с элементами принятыми за максимум
(минимум). Если результат проверки
условий является истиной, то в переменныхimaxиiminсохраняются индексы новых максимального
(блок 4) и минимального (блок 6) элементов.
После выхода из цикла будут выведены
значения максимального и минимального
элементов, а также их номера в массиве
(блок 7).

Если в массиве имеется несколько
элементов равных по значению максимальному
(минимальному) элементу, то алгоритмы,
приведенные на рис 5.2.1 и 5.2.2, определят
позицию только первого такого элемента.
Например, чтобы найти количество
элементов массива равных максимальному
и позицию последнего такого элемента,
можно воспользоваться алгоритмом,
приведенным на рис. 5.2.3.

В начале алгоритма за максимум принимается
1-й элемент массива и вводится переменная
kдля подсчета
количества элементов равных максимальному
(блок 1). Затем организовывается цикл по
перебору оставшихся элементов массива
(блок 2). На каждом шаге цикла выполняется
следующая последовательность действий.

Вначале текущий элемент массива X_iсравнивается с максимальным (блок 3).
Если он оказывается больше элемента,
принятого за максимальный, то запоминается
номер этого элемента и переменнойkприсваивается 1 (блок 4). Это означает,
что встретился первый «новый» максимальный
элемент.

Если текущий элемент не больше максимума,
значит, он может быть равным или меньше
максимального элемента. Поэтому в блоке
5 текущий элемент массива X_i
проверяется на равенство
максимальному. Если он оказывается
равным максимуму, то опять запоминается
номер текущего элемента и значение
переменнойkувеличивается на 1 (блок 6). Это означает,
что встретился следующий элемент равный
максимальному элементу. В итоге после
выхода из цикла в переменнойimaxбудет храниться индекс последнего по
счету элемента равного максимальному,
а в переменнойkколичество элементов, равных максимуму.
Если же из блока 6 убрать операциюimax=i,
то в переменнойimax,
как и в предыдущих примерах будет
сохранен номер первого по счету элемента
равного максимальному.

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

Пример 5.2.В массиве Х [N]
найти минимальный положительный элемент.

Массив
Х может содержать как положительные,
так и отрицательные элементы. Поэтому
неизвестно какой элемент массива или
произвольное значение можно принять
за начальный минимум. Решение поставленной
задачи можно разбить на два этапа: поиск
положительных элементов в массиве с
определением первого такого элемента
и поиск среди положительных элементов
минимального по значению. Блок-схема
алгоритма приведена на рис. 5.2.4.

В нашем примере нумерация элементов
массива начинается с единицы, поэтому
в качестве начального значения для
переменной iminпринимается 0 (блок 1), т.е. значение
которое не могут принимать индексы
элементов массива Х. Таким образом
показывается, что при обработке массива
еще не встречался положительный элемент,
который можно принять за начальное
значение для минимума. Затем организовывается
цикл по перебору всех элементов массива
(блок 2). На каждом шаге цикла выполняется
следующая последовательность действий.

В блоке 3 проверяется, не является ли
текущий элемент массива X_iположительным. Если он отрицательный
или равен нулю, то такой элемент
пропускается и над ним не выполняется
никаких действий. ЕслиX_i> 0, то в блоке 4 проверяется, не является
ли этот элемент первым встретившимся
положительным элементом массива
(признаком чего служит значениеiminравное 0). В этом случае в блоке 5 переменнойiminбудет присвоено
текущее значениеi.
Таким образом, за начальное значение
для минимума будет принято значение
первого по счету положительного элемента
массива Х. Эта ситуация может возникнуть
только один раз, и при дальнейшей работе
цикла блок 5 больше выполняться не будет.
Остальные положительные элементы
массива в блоке 6 будут сравниваться с
элементом массива, принятым в текущий
момент за минимум. Если такой элемент
окажется меньше минимального, то в блоке
7 в переменнойiminбудет сохранен его номерi.

После выхода из цикла проверяется, не
равно ли значение iminнулю (блок 8), так как сразу же выводить
значение минимального элемента массиваX_imin
и его номерimin(блок 9) нельзя. Это объясняется тем что,
если в массиве Х не будет положительных
элементов, то значение переменнойiminостанется равным нулю, а обращение к
несуществующему элементу массиваХ₀не допустимо.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Дан массив X, состоящий из n элементов. Найти максимальный элемент массива и номер, под которым он хранится в массиве.

Алгоритм решения задачи следующий. Пусть в переменной с именем Max хранится значение максимального элемента массива, а в переменной с именем Nmax – его номер. Предположим, что нулевой элемент массива является максимальным, и запишем его в переменную Max, а в Nmax — его номер (то есть ноль). Затем все элементы, начиная с первого, сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax – текущее значение индекса i. Процесс определения максимального элемента в массиве приведён в табл. 5.3 и изображён при помощи блок-схемы на рис. 5.8. Соответствующий фрагмент программы имеет вид:

for (Max=X [ 0 ], Nmax= i =0; i<n; i++)
	if (Max<X [ i ] )
	{
		Max=X [ i ];
		Nmax= i;
	}
cout<<" Max = "<<Max<<" n ";
cout<<" Nmax = "<<Nmax<<" n ";

Таблица
5.3.
Определение максимального элемента и его номера в массиве

Номера элементов	0	1	2	3	4	5
Исходный массив	4	7	3	8	9	2
Значение переменной	4	7	7	8	9	9
Значение переменной	1	2	2	4	5	5

При поиске максимального элемента и его номера, можно найти только номер максимального элемента, а потом по номеру извлечь значение максимального элемента из массива.

Текст программы поиска номера максимального элемента:

#include <iostream>
using namespace std;
int main ( )
{
	float *X;
	int i,N, nom;
	cout<<"Введите размер массива "; cin>>N; //Ввод размерности динамического массива
	X=new float [N ]; //Выделение памяти для хранения динамического массива X.
	cout<<"Введите элементы массива X n "; //Ввод динамического массива X.
	for ( i =0; i<N; i++)
		cin>>X [ i ];
	//В переменной nom будем хранить номер максимального элемента.
	nom=0; //Предположим, что максимальным элементом является элемент с номером 0.
	for ( i =1; i<N; i++)
	//Если очередной элемент больше X[nom], значит nom не является номером максимального
	//элемента, элемент с номером i больше элемента X[nom], поэтому переписываем
	//число i в переменную nom.
		if (X [ i ]>X [ nom ] ) nom= i;
	cout << "Максимальный элемент= "<<X [ nom]<<", его номер= " << nom << endl;
	return 0;
}

Совет. Алгоритм поиска минимального элемента в массиве будет отличаться от приведённого выше лишь тем, что в условном блоке и, соответственно, в конструкции if текста программы знак поменяется с “<” на “>”.

Рассмотрим несколько задач.

Задача 5.3. Найти минимальное простое число в целочисленном массиве x[N].

Эта задача относится к классу задач поиска минимума (максимума) среди элементов, удовлетворяющих условию. Подобные задачи рассматривались в задачах на обработку последовательности чисел. Здесь поступим аналогично. Блок-схема приведена на рис. 5.9.

Необходимо первое простое число объявить минимумом, а все последующие простые элементы массива сравнивать с минимумом. Будем в цикле последовательно проверять, является ли элемент массива простым числом (функция prostoe). Если X[i] является простым числом, то количество простых чисел (k) увеличиваем на 1 (k++), далее, проверяем, если k равен 1 (if (k==1)), то этот элемент объявляем минимальным (min=x[i]; nom=i;), иначе сравниваем его с минимальным (if (x[i]<min) {min=x[i];nom=i;}).

Текст программы:

#include <iostream>
using namespace std;
bool prostoe ( int N)
{ int i; bool pr;
	if (N<2) pr=false;
	else
	for ( pr=true, i =2; i<=N/ 2; i++)
		if (N%i ==0)
		{
			pr=false;
			break;
		}
	return pr;
}
int main ( int argc, char **argv )
{
	int i, k, n, nom, min, *x;
	cout<<" n = "; cin>>n; //Ввод количества элементов в массиве.
	x=new int [ n ]; //Выделяем память для динамического массива x.
	cout<<"Введите элементы массива X "; //Ввод элементов массива.
	for ( i =0; i<n; i++)
		cin>>x [ i ];
	//С помощью цикла по переменной i, перебираем все элементы в массиве x,
	//k — количество простых чисел в массиве.
	for ( i=k=0; i<n; i++)
	//Проверяем, является ли очередной элемент массива простым числом.
		if ( prostoe ( x [ i ] ) ) //Если x[i] — простое число.
		{
				k++; //Увеличиваем счётчик количества простых чисел в массиве.
				//Если текущий элемент является первым простым числом в массиве,
				// объявляем его минимумом, а его номер сохраняем в перемнной nom.
				if ( k==1) {min=x [ i ]; nom= i; }
		else
			//Все последующие простые числа в массиве сравниваем с минимальным простым числом.
			//Если текущее число меньше min, перезаписываем его в переменную min,
			//а его номер — в переменную nom.
			if ( x [ i ]<min ) {min=x [ i ]; nom= i; }
		}
	//Если в массиве были простые числа, выводим значение и номер минимального простого числа.
	if ( k>0)
		cout<<" min = "<<min<<"  tnom = "<<nom<<endl;
	//Иначе выводим сообщение о том, что в массиве нет простых чисел.
	else cout<<"Нет простых чисел в массиве"<<endl;
	return 0;
}

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

Задача 5.4. Найти минимальных чисел в вещественном массиве.

Перед решением этой довольно сложной задачи рассмотрим более простую задачу.

Найти два наименьших элемента в массиве. Фактически надо найти номера (nmin1, nmin2) двух наименьших элементов массива. На первом этапе надо найти номер минимального (nmin1) элемента массива. На втором этапе надо искать номер минимального элемента, при условии, что он не равен nmin1. Вторая часть очень похожа на предыдущую задачу (минимум среди элементов, удовлетворяющих условию, в этом случае условие имеет вид i!=nmin1).

Решение задачи с комментариями:

#include <iostream>
using namespace std;
int main ( int argc, char **argv )
{
	int kvo, i, n, nmin1, nmin2;
	double *X;
	cout<<" n = "; cin>>n;
	X=new double [ n ];
	cout<<"Введите элементы массива X n ";
	for ( i =0; i<n; i++)
		cin>>X [ i ];
	//Стандартный алгоритм поиска номера первого минимального элемента (nmin1).
	for ( nmin1=0, i =1; i<n; i++)
		if (X [ i ]<X [ nmin1 ] ) nmin1= i;
	//Второй этап — поиск номера минимального элемента среди элементов, номер
	//которых не совпадает nmin1. kvo — количество таких элементов.
	for ( kvo= i =0; i<n; i++)
		if ( i !=nmin1 ) //Если номер текущего элемента не совпадает с nmin1,
		{
			kvo++; //увеличиваем количество таких элементов на 1.
			//Номер первого элемента, индекс которого не равен nmin1,
			//объявляем номером второго минимального элемента.
			if ( kvo==1) nmin2= i;
			else
			//очередной элемент, индекс которого не равен nmin1, сравниваем с минимальным,
			//если он меньше, номер перезаписываем в переменную nmin2.
			if (X [ i ]<X [ nmin2 ] ) nmin2= i;
		}
	//Вывод двух минимальных элементов и их индексов.
	cout<<" nmin1 = "<<nmin1<<"  tmin1 = "<<X [ nmin1]<< endl;
	cout<<" nmin2 = "<<nmin2<<"  tmin2 = "<<X [ nmin2]<< endl;
	return 0;
}

По образу и подобию этой задачи можно написать задачу поиска трёх минимальных элементов в массиве. Первые два этапа (поиск номеров двух минимальных элементов в массиве) будут полным повторением кода, приведённого выше. На третьем этапе нужен цикл, в котором будем искать номер минимального элемента, при условии, что его номер не равен nmin1 и nmin2. Авторы настоятельно рекомендуют читателям самостоятельно написать подобную программу. Аналогично можно написать программу поиска четырёх минимальных элементов. Однако при этом усложняется и увеличивается код программы. К тому же, рассмотренный приём не позволит решить задачу в общем случае (найти k минимумов).

Для поиска минимумов в массиве можно поступить следующим образом. Будем формировать массив nmin, в котором будут храниться номера минимальных элементов массива x. Для его формирования организуем цикл по переменной от 0 до k-1. При каждом вхождении в цикл в массиве nmin элементов будет j-1 элементов,i и мы будем искать -й минимум (формировать -й элемент массива). Алгоритм формирования -го элемента состоит в следующем: необходимо найти номер минимального элемента в массиве x, исключая номера, которые уже хранятся в массиве nmin. Внутри цикла по необходимо выполнить такие действия. Для каждого элемента массива x (цикл по переменной ) проверить содержится ли номер в массиве nmin, если не содержится, то количество (переменная kvo) таких элементов увеличить на 1. Далее, если kvo равно 1, то это первый элемент, который не содержится в массиве nmin, его номер объявляем номером минимального элемента массива (nmin_temp=i;). Если kvo>1, сравниваем текущий элемент x[i] с минимальным (if (x[i]<X[nmin_temp]) nmin_temp=i;). Блок-схема алгоритма поиска минимальных элементов массива представлена на рис. 5.10^{2В блок-схеме отсутствует ввод данных и вывод результатов.}.Далее приведён текст программы с комментариями.

#include <iostream>
using namespace std;
int main ( int argc, char **argv )
{
	int p, j, i, n, *nmin, k, kvo, nmin_temp;
	bool pr;
	double *x;
	cout<<" n = "; cin>>n;
	x=new double [ n ];
	cout<<"Введите элементы массива Хn ";
	for ( i =0; i<n; i++)
		cin>>x [ i ];
	cout<<"Введите количество минимумовn "; cin>>k;
	nmin=new int [ k ];
	for ( j =0; j<k; j++) //Цикл по переменной j для поиска номера j + 1 минимального элемента
		{
		kvo=0;
		for ( i =0; i<n; i++) //Перебираем все элементы массива.
		{
			//Цикл по переменной p проверяет, содержится ли номер i в массиве nmin.
			pr=false;
			for ( p=0;p<j; p++)
				if ( i==nmin [ p ] ) pr=true;
			if ( ! pr ) //Если не содержится, то количество элементов увеличить на 1.
			{
				kvo++;
				//Если kvo=1, то найден первый элемент, который не содержится в массиве
				//nmin, его номер объявляем номером минимального элемента массива
				if ( kvo==1) nmin_temp= i;
				else
					//Если kvo>1, сравниваем текущий элемент x[i] с минимальным.
					if ( x [ i ]<x [ nmin_temp ] ) nmin_temp= i;
			}
		}
	nmin [ j ]=nmin_temp; //Номер очередного минимального элемента записываем в массив.
	}
	for ( j =0; j<k; j++) //Вывод номеров и значений k минимальных элементов массива.
		cout<<" nmin1 = "<<nmin [ j ]<<"  tmin1 = "<<x [ nmin [ j ]]<< endl;
	return 0;
}

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

#include <iostream>
using namespace std;
//Функция проверяет, содержится ли число i в массиве x из n элементов.
//Функция возвращает true, если содержится, и false, если не содержится.
bool proverka ( int i, int *x, int n )
{
	bool pr;
	int p;
	pr=false;
	for ( p=0;p<n; p++)
	if ( i==x [ p ] ) pr=true;
	return pr;
}
int main ( int argc, char **argv )
{
	int j, i, n, *nmin, k, kvo, nmin_temp;
	double *x;
	cout<<" n = "; cin>>n;
	x=new double [ n ];
	cout<<"Введите элементы массива Хn ";
	for ( i =0; i<n; i++)
		cin>>x [ i ];
	cout<<"Введите количество минимумовn "; cin>>k;
	nmin=new int [ k ];
	for ( j =0; j<k; j++) //Цикл по переменной j для поиска номера j + 1 минимального элемента
	{
		kvo=0;
		for ( i =0; i<n; i++) //Перебираем все элементы массива.
		{
			//Вызов функции proverka, определяем, содержится ли число i в массиве nmin из j элементов
			if ( ! proverka ( i, nmin, j ) )
			{
				kvo++;
				if ( kvo==1) nmin_temp= i;
				else
					if ( x [ i ]<x [ nmin_temp ] ) nmin_temp= i;
			}
		}
		nmin [ j ]=nmin_temp;
	}
	for ( j =0; j<k; j++) //Вывод номеров и значений k минимальных элементов массива.
		cout<<" nmin1 = "<<nmin [ j ]<<"  tmin1 = "<<x [ nmin [ j ]]<< endl;
	return 0;
}

Авторы настоятельно рекомендуют читателю разобрать все версии решения задачи 5.4.

Задача 5.5. Поменять местами максимальный и минимальный элементы в массиве X.

Алгоритм решения задачи можно разбить на следующие этапы.

1. Ввод массива.
2. Поиск номеров максимального (nmax) и минимального (nmin) элементов массива.
3. Обмен элементов местами. Не получится записать “в лоб” (X[nmax]=X [nmin]; X[nmin]=X[nmax];). При таком присваивании мы сразу же теряем максимальный элемент. Поэтому нам понадобится временная (буферная) переменная temp. Обмен элементов местами должен быть таким: temp=X[nmax]; X[nmax]=X[nmin]; X[nmin]=temp;

Далее приведён текст программы с комментариями.

#include <iostream>
using namespace std;
int main ( int argc, char **argv )
{
	int i,N, nmax, nmin;
	float temp;
	cout<<" N = "; cin>>N;
	float X [N ];
	cout<<"Введите элементы массива Хn ";
	for ( i =0; i<N; i++)
		cin>>X [ i ];
	//Поиск номеров максимального и минимального элементов массива.
	for (nmax=nmin=0, i =1; i<N; i++)
	{
		if (X [ i ]<X [ nmin ] ) nmin= i;
		if (X [ i ]>X [ nmax ] ) nmax= i;
	}
	//Обмен максимального и минимального элементов местами.
	temp=X [ nmax ]; X [ nmax]=X [ nmin ]; X [ nmin ]=temp;
	cout<<"Преобразованный массив Хn "; //Вывод преобразованного массива.
	for ( i =0; i<N; i++)
		cout<<X [ i ]<<" ";
	cout<<endl;
	return 0;
}

Задача 5.6. Найти среднее геометрическое среди простых чисел, расположенных между максимальным и минимальным элементами массива.

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

Алгоритм решения задачи состоит из следующих этапов:

1. Ввод массива.
2. Поиск номеров максимального (nmax) и минимального (nmin) элементов массива.
3. В цикле перебираем все элементы массива, расположенные между максимальным и минимальным элементами. Если текущий элемент является простым числом, то необходимо увеличить количество простых чисел на 1, и умножить на значение элемента массива.
4. Вычислить .

При решении этой задачи следует учитывать, что неизвестно, какой элемент расположен раньше — максимальный или минимальный.

Текст программы с комментариями приведён ниже.

#include <iostream>
#include <math.h>
using namespace std;
bool prostoe ( int N)
{
	int i;
	bool pr;
	if (N<2) pr=false;
	else
	for ( pr=true, i =2; i<=N/ 2; i++)
	if (N%i ==0)
	{
		pr=false;
		break;
	}
	return pr;
}
int main ( int argc, char **argv )
{
	int i, k, n, nmax, nmin, p, *x;
	cout<<" n = "; cin>>n; //Ввод количества элементов в массиве.
	x=new int [ n ]; //Выделяем память для динамического массива x.
	cout<<"Введите элементы массива X"; //Ввод элементов массива.
	for ( i =0; i<n; i++)
		cin>>x [ i ];
	//Поиск номеров максимального и минимального элементов в массиве.
	for (nmax=nmin= i =0; i<n; i++)
	{
		if ( x [ i ]<x [ nmin ] ) nmin= i;
		if ( x [ i ]>x [ nmax ] ) nmax= i;
	}
	if ( nmin<nmax )
		for ( p=1,k=0, i=nmin+1; i<nmax; i++)
		//Обратите особое внимание на использование в следующей строке фигурной скобки
		//(составного оператора). В цикле всего один оператор!!! При этом, при отсутствии
		//составного оператора, программа начинает считать с ошибками!!!
		{
			//Проверяем, является ли очередной элемент массива простым числом.
			if ( prostoe ( x [ i ] ) ) //Если x[i] — простое число.
			{
			//Домножаем y[i] на p, а также увеличиваем счётчик количества простых чисел в массиве.
			k++;p*=x [ i ];
			}
		}
	else
			for ( p=1,k=0, i=nmax+1; i<nmin; i++)
			//Проверяем, является ли очередной элемент массива простым числом.
			if ( prostoe ( x [ i ] ) ) //Если x[i] — простое число.
			{//Домножаем y[i] на p, а также увеличиваем счётчик количества простых чисел в массиве.
			k++;p*=x [ i ];
			}
		//Если в массиве были простые числа, выводим среднее геометрическое этих чисел на экран
		if ( k>0)
			cout<<" SG "<<pow ( p, 1./ k )<<endl;
		//Иначе выводим сообщение о том, что в массиве нет простых чисел.
		else cout<<"Нет простых чисел в массиве"<<endl;
	return 0;
}