4391

Некоторые простые алгоритмы в языке С++

Контрольная

Информатика, кибернетика и программирование

Некоторые простые алгоритмы в языке С++ Поиск максимального (или минимального) числа из выборки чисел Предположим, что мы имеем массив из n элементов. Необходимо найти элемент с максимальным (или минимальным) числовым значением. Задача поиска ...

Русский

2012-11-18

61.5 KB

7 чел.

Некоторые простые алгоритмы в языке С++

  1.  Поиск максимального (или минимального) числа из выборки чисел

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

Рис. 7.1. Алгоритм поиска максимального элемента массива

 Алгоритм поиска минимального элемента имеет ту же структуру. Только вместо условия: a[i]>Max – нужно записать условие: a[i]<Min. Программа поиска максимального и минимального элементов массива приведена в листинге 7.1.

Листинг 7.1. Поиск максимального и минимального элементов массива

# include <iostream>

int main(){

using namespace std;

int i, n;

float Min, Max;

float a[100];

cout<<"Input n: ";

cin>>n;

cout<<endl;

cout<<"Input array";

cout<<endl;

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

 cin>>a[i];

}

Min=a[0];

Max=a[0];

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

 if (a[i]<Min)

  Min=a[i];

 if (a[i]>Max)

  Max=a[i];

}

cout<<endl;

cout<<"Max: " << Max << endl;

cout<<"Min: " << Min << endl;

char Res;

cin>>Res;

return 0;

}

  1.  Пузырьковая сортировка (bubble sort)

С помощью операции сортировки можно расставить элементы числового массива в порядке их возрастания (или убывания). Существуют различные методы сортировки. Самым простым (но не самым быстрым) является пузырьковый метод. Он заключается в том, что два соседних элемента меняются местами, если они нарушают заданный порядок. При многократном повторении этой операции наименьший элемент «всплывает на поверхность как пузырек» – то есть попадает в начало выборки. Один из простых вариантов программы, реализующих данный метод, приведен в листинге 7.2.

Листинг 7.2. Пузырьковая сортировка элементов массива

# include <iostream>

void exch(double &a, double &b)

{ double t=a; a=b; b=t; }

void compexch(double &a, double &b)

{ if (a>b) exch(a, b); }

void bubble(double x[], int r)

{ for (int i=0; i<r-1; i++)

for (int j=0; j<r-1; j++)

 compexch(x[j], x[j+1]);

}

void main()

{

using namespace std;

int i, n;

double a[100];

cout<<"Input n: ";

cin>>n;

cout<<endl<<"Input array"<<endl;

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

 cin>>a[i];

}

cout<<endl;

bubble(a, n);

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

 cout<<a[i]<<endl;

 }

 char Res;

 cin>>Res;

}

В данной программе используется функция exch, которая меняет местами значения двух переменных («exchange» – на английском означает «обмен»). Функция может иметь несколько аргументов, но возвратить она способна максимум только одно значение. В данном случае функция exch вообще не возвращает ничего. Локальные переменные, которыми манипулирует функция, стираются из памяти сразу после ее выполнения.  Чтобы изменения сохранились, необходимо использовать ссылки.

Если задана переменная x, то оператор &x вернет нам адрес этой переменной в оперативной памяти компьютера. Ссылка (reference) – это псевдоним адресата. Все, что делается со ссылкой, происходит и с объектом, который находится по указанному адресу.

Ссылки используются также и в функции compexch, которая сравнивает значения двух переменных и, если они стоят не в том порядке, вызывает функцию exch.

В функции exch используется локальная переменная t для временного хранения первоначального значения переменной  a. Можно обойтись и без нее, если использовать следующий вариант функции exch.

void exch(double &a, double &b)

{ a=a+b; b=a-b; a=a-b; }

Эта программа использует меньше памяти, однако требуется комментарий, чтобы объяснить, для чего она предназначена.

  1.  Вычисление чисел Фибоначчи

Функция может вызывать сама себя – это свойство называется рекурсией. Рекурсию можно использовать для вычисления чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, … Эти числа определяются с помощью рекуррентной формулы

.     (7.1)

В листинге 7.3 приведена программа непосредственной рекурсивной реализации рекуррентного соотношения (7.1). Однако эта программа весьма неэффективна. В ней количество рекурсивных вызовов для вычисления  равно . Но теория чисел Фибоначчи утверждает, что  приближенно равно  при больших , где  – золотое сечение (для обозначения золотого сечения принято использовать букву  в честь известного афинского скульптора Фидия). Таким образом, для программы из листинга 7.3 время этого элементарного вычисления определяется экспоненциальной зависимостью.

Листинг 7.3. Числа Фибоначчи (рекурсивная реализация)

# include <iostream.h>

int F(int i) {

if (i<1) return 0;

if (i==1) return 1;

return F(i-1)+F(i-2);

}

void main() {

int k, fib;

cout<<"Input number:";

cin>>k;

fib=F(k);

cout<<"F="<<fib;

 char res;

cin>>res;

}

Можно легко вычислить первые  чисел Фибоначчи за время, пропорциональное значению , используя массив, как показано в листинге 7.4.

Листинг 7.4. Числа Фибоначчи (динамическое программирование)

# include <iostream.h>

int F(int i) {

static int knownF[46];

if (knownF[i]!=0) return knownF[i];

int t=1;

if (i<0) return 0;

if (i>1) t=F(i-1)+F(i-2);

return knownF[i]=t;

}

void main() {

int k, fib;

cout<<"Input number:";

cin>>k;

fib=F(k);

cout<<"F="<<fib;

 char res;

cin>>res;

}

Числа возрастают экспоненциально, поэтому размер массива невелик. Например, =1836311903 – наибольшее число Фибоначчи, которое может быть представлено 32-разрядным целым, поэтому достаточно использовать массив из 46 элементов.

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

Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Любую такую функцию можно вычислить, вычисляя все значения функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Эта технология называется восходящим динамическим программированием (bottom-up dynamic programming). Она применима к любому рекурсивному вычислению при условии, что мы можем себе позволить хранить все ранее вычисленные значения.

Нисходящее динамическое программирование (top-down dynamic programming) – еще более простая технология, которая позволяет автоматически выполнять рекурсивные функции при том же (или меньшем) количестве итераций, что и восходящее динамическое программирование. При этом рекурсивная программа используется для сохранения каждого вычисленного ею значения и для проверки сохраненных значений во избежания повторного вычисления любого из них. Программа из листинга 7.4 – механически измененная программа из листинга 7.3, в которой за счет применения нисходящего динамического программирования достигается резкое снижение времени выполнения.


 
   i=0, n, 1

[i]>Max

   Max=a[i] 

Да

Нет

    Вводим

массив a[n] из n элементов

  Начало

     Задаем

    Max=a[0]

 Выводим на

экран значение

         Max

  Конец


 

А также другие работы, которые могут Вас заинтересовать

79264. Характерные признаки предприятий, образующих металлургическую отрасль 14.74 KB
  На территориальную организацию черной металлургии влияет ряд факторов. Например в черной металлургии ФРГ этот показатель равен всего 22. Так на 1 т готового проката у нас приходится 85 человекочасов что в 15 2 раза больше чем в странах с развитой черной металлургией Южной Корее Бразилии Китае Тайвань. Низкая производительность труда на предприятиях черной металлургии ведет к тому что конкурентоспособность отечественной металлопродукции может быть обеспечена только при сохранении самого низкого из существующих уровня заработной...
79265. Основы организации и управления производством коммерческого предприятия 15.88 KB
  Основы организации и управления производством коммерческого предприятия Финансы коммерческих предприятий представляют собой экономические отношения возникающие в процессе формирования производственных фондов производства и реализации продукции образования собственных ресурсов привлечения внешних источников финансирования их распределения и использование. Финансами коммерческих организаций и предприятий присущи те же функции что и общегосударственным финансам распределительная и контрольная. Положительный финансовый результат...
79266. Методы организации производства и их технико-экономическая характеристика 15.09 KB
  Различают три основных метода организации производства: индивидуальный единичный партионный и поточный. При индивидуальном единичном методе организации производства выпуск продукции осуществляется единичными экземплярами или очень мелкими партиями изделий широкой номенклатуры. Равномерная работа на всех участках производства при партионном методе достигается за счет определения оптимальных размеров партий заделов длительности цикла графиков запускавыпуска.
79267. Понятие и особенности производственного процесса. Основные принципы организации производственных процессов 14.73 KB
  По операциям ведется увязка объемов работ на участках: нормирование оперативное планирование и учет производства Основные операции операции технологического цикла состоящие из операционных циклов в результате которых изменяются форма размеры свойства и взаимное расположение деталей Технологический процесс совокупность основных операций Вспомогательные операции операции обеспечивающие бесперебойность производственного процесса связанные с перемещением предметов труда с одного рабочего места на другое снятием и установкой...
79268. Классификация производственных процессов 53.5 KB
  Ручные процессы – осуществляются рабочими без помощи механизмов. Машинно-ручные процессы – выполняются машинами или механизмами при непосредственном участии в них рабочих – вскрытие чугунной летки с помощью ВЧП
79269. Организационное проектирование системы управления персоналом 12.21 KB
  СУП является основой системы управления организацией т. Стратегический выбор руководства организации в отношении ее целей: Идеология управления; b Типы потребителей; c Типы рынков сбыта и территориальное размещение производства. В общем виде проект системы управления организации состоит
79270. Цели, функции, организационная структура системы управления персоналом 229.37 KB
  Традиционно в службы управления персоналом входят: отдел кадров отдел обучения отдел труда и заработной платы отдел социального развития и другие отделы социальной инфраструктуры отдел охраны труда и техники безопасности лаборатория социологии отдел охраны окружающей среды юридический отдел отдел организации труда производства и управления отдел научнотехнической информации патентнолицензионный отдел бюро рационализации и изобретательства. 1 Цели системы управления персоналом организации с точки зрения персонала Рис. 2 Цели...
79271. Анализ и описание работы и рабочего места 13.44 KB
  Анализ рабочего места представляет собой дифференцирование рабочего места с одной стороны через задачи деятельность которая на нем совершается а с другой через требования по отношению к образованию опыту и ответственности необходимым для успешного выполнения деятельности на этом месте. АРМ как правило состоит из двух частей: описание рабочего места перечисление видов деятельности задач трудовых условий средств оборудования и материалов которые используются на данном рабочем месте; спецификация рабочего места перечисление...
79272. Кадровое обеспечение системы управления персоналом 30.16 KB
  Под кадровым обеспечением системы управления персоналом понимается необходимый количественный и качественный состав работников кадровой службы организации. Работники службы управления персоналом должны: хорошо знать трудовое законодательство методические нормативные и другие материалы касающиеся работы с персоналом учета личного состава; основы педагогики социологии и психологии труда; передовой отечественный и зарубежный опыт в области управления персоналом; владеть современными методами оценки персонала профориентационной работы...