Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Максимальный и минимальный элементы массива.сортировка
|
|
Пример 1. Поменять местами максимальный и минимальный элементы массива
Алгоритм поиска сводится к определению переменной, в которой будет храниться значение максимума (минимума) и последующем сравнением ее величины со всеми элементами массива. В качестве начального значения можно использовать первый элемент массива.
Для решения задачи необходимо знать где находятся максимальный и минимальный элементы массива. Для этого вводятся две вспомогательные переменные, в которые заносятся индексы искомых элементов.
#include < iostream.h>
#include < iomanip.h>
#include < math.h>
main()
{ const int n=10;
int i, j, k, max, min, tmp, m[n]={6, 3, 1, 5, 9, -1, -9};
max=m[0];
min=m[0];
for(i=0; i< n; i++)
{ if(m[i]> max)
{ max=m[i]; j=i; }
if(m[i]< min)
{ min=m[i]; k=i; }
}
tmp=m[k];
m[k]=m[j];
m[j]=tmp;
cout< < min< < max;
}
Пример 2. Поиск максимального и минимального элементов в массиве в сочетании с условием отбора.
Поскольку необходим поиск min и max среди элементов массива, удовлетворяющих заданному условию, то величина первого такого элемента заранее неизвестна. Начальное значение переменной, в которой хранится min (max) должно быть заведомо большим (меньшим), чем любой из элементов массива, удовлетворяющих заданному условию. В качестве начального значения может служить максимально возможная величина, представимая в ЭВМ для типа данных элементов массива. Эти значения имеют именованные константы, определеные в библиотеках limits.h для целых типов и float.h для вещественных типов.
Программа, печатающая значения именованных констант
#include < iostream.h>
#include< iomanip.h>
#include< limits.h>
#include< float.h>
main()
{cout< < " LONG_MIN " < < LONG_MIN< < " LONG_MAX " < < LONG_MAX< < endl;
cout< < " FLT_MIN " < < FLT_MIN< < " FLT_MAX " < < FLT_MAX< < endl;
cout< < " DBL_MIN " < < DBL_MIN< < " DBL_MAX " < < DBL_MAX< < endl;
cout< < " LDBL_MIN " < < LDBL_MIN< < " LDBL_MAX " < < LDBL_MAX< < endl;
cout< < " FLT_DIG " < < FLT_DIG< < " FLT_EPSILON " < < FLT_EPSILON< < endl;
Программа поиска минимального положительного элемента в массиве
#include < iostream.h>
#include < iomanip.h>
#include < math.h>
#include < float.h>
main()
{ const int n=10;
double i, j, k, max, min, tmp, m[n]={6., 3., 1., 5., 9., -1., -9.};
min=DBL_MAX;
for(i=0; i< n; i++)
{ if(m[i]> 0 & & m[i]< min)
min=m[i];
}
cout< < min;
}
Пример 3. Сортировка массива методом “пузырька”
Вариант 1. Последовательным просмотром элементов массива m c индексом i от 0 до n-1 найдем наименьшее i, такое, что m[i]> m[i+1]. Поменяем местами m[i] и m[i+1] и возобновим просмотр с элемента m[i+1] и т. д. В результате самое большое число передвинется на последнее место. Следующие просмотры необходимо начинать с элемента с индексом 0, уменьшив на 1 количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали первый и второй элементы.
#include < iostream.h>
#include < iomanip.h>
#include < math.h>
main()
{int i, j, n, k, max, min, tmp, m[10]={6, 3, 1, 5, 9, -1, -9, 7, 2, 0};
n=10;
for(i=0; i< n-1; i++)
for(j=0; j< n-1-i; j++)
if(m[j]> m[j+1])
{ tmp=m[j];
m[j]=m[j+1];
m[j+1]=tmp; }
for(i=0; i< n; i++)
cout< < setw(3)< < m[i];
}
Вариант 2. Недостатком алгоритма первого варианта является независимость количества действий от степени упорядоченности элементов массива. Даже для полностью упорядоченного массива количество выполненных операций будет пропорционально n2. метод сортировки можно улучшить, использовав в качестве признака окончания сортировки значение вспомогательной переменной. Вспомогательная переменная будет иметь отличную от нуля величину, если в результате просмотра всего массива произошел обмен хотя бы одной пары элементов.
#include < iostream.h>
#include < iomanip.h>
#include < math.h>
main()
{ const int n=10;
int i, j, k, tmp, m[n]={6, 3, 1, 5, 9, -1, -9, 7, 2, 0};
i=1;
while(i> 0)
{ i=0;
for(j=0; j< n-1; j++)
if(m[j]> m[j+1])
{ tmp=m[j];
m[j]=m[j+1];
m[j+1]=tmp;
i=1;
}
}
for(i=0; i< n; i++)
cout< < setw(3)< < m[i];
}
Пример 4. Бинарный поиск в упорядоченном массиве
При бинарном поиске искомое значение х сначала сравнивается с элементом в середтне массива. Если х меньше, чем это значение, то областью поиска становится верхняя половина массива, в противном случае – нижняя. Процесс половинного деления продолжается до тех пор, пока либо будет найдено значение, совпадающее с х, либо диапазон поиска станет пустым. Поскольку на каждом шаге диапазон поиска уменьшается в два раза, то общее количество необходимых операций будет пропорционально log2n, где n – размерность массива.
#include< iostream.h>
#include< iomanip.h>
#include< conio.h>
void main()
{ clrscr();
const int n=9;
float m[n]={1, 2, 3, 4, 5, 6, 7, 8, 9};
float x;
int end=1;
cin> > x;
int i=0, j=n, k;
while (j> i & & end! =0)
{ k=(i+j)/2;
if(m[k]> x)
j=k;
else if(m[k]< x)
i=k;
else end=0;
}
if(end==0) cout< < k;
else cout< < " no" < < endl;
}
|
|