Конструкции цикла и передачи управления

Операторы цикла задают многократное исполнение операторов тела цикла. Определены три разных оператора цикла:

· цикл с предусловием

while (выражение_условие)

тело_цикла;

· цикл с постусловием

do

тело_цикла

while (выражение_условие)

· цикл for

for (инициализация_цикла; выражение_условие; список_выражений)

тело_цикла

Тело_цикла не может быть описанием, это либо один (может быть и пустой) оператор, который всегда завершается точкой с запятой, либо блок операторов, заключенных в скобки {}. Выражение_условие – это выражение, определяющее условие продолжения итераций. Операторы тела цикла выполняются, пока условие истинно (не равно нулю). Инициализация_цикла в цикле for - это последовательность определений и выражений, разделяемых запятыми. Даже если она пустая, точка с запятой должна присутствовать. Чаще всего здесь устанавливается начальные значения счетчиков и параметров цикла. Выражения из списка_выражений выполняются после выполнения операторов тела цикла и до следующей проверки выражения_условия.

Приведем примеры, иллюстрирующие разные решения задачи нахождения суммы s квадратов первых k членов натурального ряда.

for (int i=1,s=0;i<=k; i++) s+=i*i;

for (int i=0,s=0;i<=k; s+=++i*i);// тело цикла - пустой оператор;

for (int i=0,s=0;i<=k;) s+=++i*i; //отсутствует список выражений;

for (int i=0,s=0;i<=k;) {int j; j=++i; s+=j*j;}

Конструкцию for чаще применяют для организации детерминированных циклов, то есть циклов, число повторений которых заранее определено. А конструкции do и while чаще применяют для итерационных циклов, то есть циклов, число повторений которых зависит от выполнения условий, изменяющихся в теле цикла и заранее не определено. Хотя такое функциональное разделение довольно условно.

Каждый цикл может содержать вложенные циклы. Для принудительного выхода из цикла используется оператор break. Необходимость в его использовании возникает, когда условия продолжения итераций надо проверять не только в начале или конце итерации, но и в середине тела цикла. Например, если начальные значения переменных i,j таковы, что i<j, то следующий цикл определяет наименьшее целое, не меньшее их среднего арифметического.

while (i<j)

{ i++;

if (i==j) break;

j--;

}

Для i=0, j=3 результат i=j=2 достигается при выходе из цикла с помощью оператора break, а для i=0, j=2 результат i=j=1 достигается при естественном завершении цикла.

Циклические конструкции чаще всего применяют для ввода значений элементов массива. Массив – это именованная совокупность элементов одного типа, расположенных в памяти компьютера последовательно. Описание массива имеет два формата:

тип идентификатор[размерность];

или

тип идентификатор [размерность]={элемент1, элемент2,…};

Размерность – это константное выражение целого типа, обозначающее количество элементов в массиве. Если в первом случая описания размерность необходимо указывать, то во втором его указание не обязательно. Когда массив объявлен без указания размерности, но при этом инициализирован списком, его размерность вычисляется путем подсчета числа элементов этого списка. Явная инициализация массива разрешена только при его определении и возможна двумя способами: либо с указанием размера массива в квадратных скобках, либо без его явного указания, например,

int а[6]={1,2,3,4};//массив из 6 целых чисел с инициализацией

//первых четырех

char str[]={‘a’, ‘b’, ‘c’};// массив из 3 элементов типа char

Рекомендуется задавать размерность массива, не как числовую, а как именованную константу. Например, запись const int n=5; int a[n]; предпочтительнее записи int a[5];.

Одним из способов доступа к элементам массива является использование индексов. То есть, чтобы обратится к i- тому элементу массива а, используют запись а[i], при этом первый элемент массива имеет индекс 0. Например, ввод элементов массива с клавиатуры можно реализовать следующим образом:

const int n=10;

int a[n];

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

{ cout<< “\nЕnter a[”<<i<< “] ”;

cin >>a[i]

}

К элементам массива можно обращаться также с помощью указателей. Указатель – это переменная, значением которой является адрес участка памяти, выделенной для объекта конкретного типа. и являются специальными объектами в языке С++. В простейшем случае описание указателя-переменной на некоторый объект имеет вид:

тип *имя_указателя инициализатор;

Например,

int *T; // неинициализированный указатель на объект типа int,

//то есть в переменной T может храниться адрес объекта типа int;

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

char c1 = ‘a’;

char* p = &c1;// в p хранится адрес переменной c1

Переменная, на которую указывает p, это c1, а значение, которое хранится в c1, это символ ‘a’. Основная операция над указателем – разыменование, унарная операция ‘*’ (получение значения через указатель). Эта операция также называется косвенным обращением или обращением по адресу. Например, при выполнении оператора cout<<*p; на экран выведется значение того участка памяти, с которым связан указатель p, то есть символ ‘a’.

Имя массива является указателем-константой на его первый элемент. То есть, если описан массив int a [n], то для обращения к его i-ому элементу наряду с записью a[i], можно использовать запись *(a+i).

Например, пусть описан и инициализирован массив int a[n]. Выведем его элементы на экран столбиком, используя указатели, двумя способами:

а) int *p=a;

for (int i=1;i<=n;i++) сout<<*p++<<"\n";

b) for (int i=0; i<n; i++) cout<<*(a+i)<<"\n";

Чтобы связать указатель с новым участком памяти, еще не занятым никаким объектом программы, используют операцию new. Например,

char *p= new char; //выделили память для перемененной типа char

//и связали указатель p с эти участком памяти;

Объекты, созданные таким образом (динамические объекты), требуют явного уничтожения с помощью операции delete, например

delete p;

Операция new позволяет определять массив еще одним способом:

int k;

cin>>k;

int *a=new int [k];

Этот способ целесообразно использовать, если размерность массива не может быть описана как константа. Однако в данном случае необходимо удалить описанный динамический массив после использования с помощью операции delete [ ]а;, иначе память, выделенная под него останется занятой до перезагрузки операционной системы. Обращаться к элементам динамического массива можно всеми перечисленными выше способами.

Специальным образом в языке С++ обрабатываются массивы, называемые С-строками. С-строка - это массив символов, последний из которых символ ‘\0’. Дело в том, что в С++ нет специального типа данных для описания строк, но есть стандартный класс string (описанный в заголовочном файле cstring.h, см. задание 8.2), а также библиотека функций языка С для работы С-строками (описанная в заголовочном файле string.h, см. задание 6.3), которые обеспечивают различные операции для манипулирования строками. В этой главе мы рассмотрим работу, используя обычный принцип обработки символов как элементов массива.

При инициализации массив символов может задаваться как последовательность символов, заключенная в двойные кавычки: “...”. Компилятор располагает в конце каждой строки нулевой (пустой) байт \0 с тем, чтобы сканирующая строку программа могла найти ее конец. Например,

char str1[]= “abcd”; // действительная длина этой строки равна 5

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

char str2[]={‘a’, ‘b’, ‘c’, ‘d’, ‘\0’};

При такой инициализации списком, а также при посимвольном заполнении неинициализированного массива в цикле в конце символьного массива следует явным образом задать символ конца строки ‘\0’.. Только при этом массив получает свойства С-строки, которые можно использовать, например, в библиотечных функциях для работы со строками или при вводе и выводе строки. Например, С-строку str2 в отличии от любого несимвольного массива можно вывести на экран не в цикле, а с помощью с помощью одного оператора cout<<str2; А неинициализированный массив char str3[20], в отличии от любого несимвольного можно заполнить одним оператором cin>>str3; Однако, как отмечено в главе 2, при применении оператора cin>>str3; с клавиатуры считаются в массив str3 все символы только до первого пробела. Чтобы считать строку целиком, можно использовать функцию

gets (указатель_на_строку),

описанную в заголовочном файле stdio.h или функцию класса iostrem

getline(укзатель_на_строку,максимальное_число_считываемых_символов).

Например,

char s1[10]; gets(s1);

char * s2 =new char [m]; cin.getline(s2, m-3);

Строка s1 – это массив с константой размерностью 10, элементы которого считываются с клавиатуры с помощью функции gets. Строка s2 – это динамический массив из m элементов, в который считается только m-4 символов (m-3-ий элемент будет равен ‘\0’). Причем второй способ считывания строки предпочтительнее, чем первый, так как функция gets не накладывает ограничения на число считываемых с клавиатуры символов, а это значит, что массив s1 может переполниться.

Пример. Определить длину строки, введенной с клавиатуры, не использую библиотечных функций.

# include {iostream.h}

void main()

{

const int n=255;

char stroka [n];

cin.getline(stroka,n);//считали строку

int len = 0; // будем использовать переменную len

//как индекс массива

while (stroka[len]) len++; // условие окончание цикла

//stroka[len]= ‘\0’

cout<<len;

}

Многомерные массивы описываются как массивы массивов, например,

int a2[3][2] // массив из 3 массивов, содержащих по 2 целых элемента.

Для обращения к элементу двумерного массива используется два индекса, например, a2[i][j]. Рассмотрим, как используется конструкция вложенных циклов для работы с двумерными массивами и как возможен выход из вложенных циклов.

Для принудительного выхода из вложенных циклов используют оператор безусловного перехода goto, который имеет формат:

goto идентификатор;

где идентификатор – имя метки оператора, расположенного в той же функции, где используется оператор безусловного перехода. Метка – это обычный идентификатор, после которого ставится двоеточие и следует некоторый оператор. Использование оператора goto принято считать плохим стилем, однако в некоторых случаях его использование может быть действительно обосновано. Например, при решении задачи поиска в матрице размерности (n,m) поиска в матрице хотя бы одного элемента с заданным значением x.

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

for (int j=0; j<m;j++)

if (a[i][j]==x) goto success;

…

…

success:

cout << “Элемент найден. Строка i= ”<<i;

cout<< “Столбец j=” <<j;

Также в циклах применяется оператор continue. С его помощь завершается текущая итерация и начинается проверка условий дальнейшего продолжения цикла. Типичный пример использования continue - подсчитать среднее значение только положительных элементов одномерного массива.

for (s=0,k=0,i=0;i<n;i++)

{

if (x[i]<=0) continue;

k++;

s+=x[i];

}

if (k>0) s=s/k;

Каждому студенту рекомендуется выполнить одно из упражнений 1-12 каждого задания 1-6 и все упражнения задания 7.

Задание 1. Детерминированные циклы. Простейшие задачи

Пример. Даны натуральные числа N, x. Вычислить .

# include <iostream.h>

void main()

{

int x,N,S ed=1, fact=1, stepX=1;

cout << “Enter x,N ”;

cin >>x>> N;

for (int k=1; k<=N; k++)

{

ed=-ed; // меняем знак единицы при каждой итерации

stepX=*x; // вычисляем

fact*=k+1; // вычисляем (k+1)!

S+=ed*stepX/fact;

}

cout<< “S= ”<< S;

}

1. Дано натуральное число N. Вычислить * .

2. Дано натуральное число N. Вычислить , где

3. Даны натуральные числа N и M (N > M). Вычислить .

4. Дано натуральное число N. Вычислить .

5. Дано натуральное число N и вещественное число x. Вычислить , . Функцию pow() не использовать.

6. Дано натуральное число N и вещественное число x. Вычислить , . Функцию pow() не использовать.

7. Дано натуральное число N и вещественное число x. Вычислить, . Функцию pow() не использовать.

8. Дано натуральное число N >2. Вычислить .

9. Дано натуральное число N и вещественное число x. Вычислить .

10. Дано натуральное число N. Вычислить , где

11. Дано натуральное число N. Вычислить .

12. Дано натуральное число N. Вычислить .

Задание 2. Итерационные циклы. Простейшие задачи

Пример. Дано натуральное число N. Определить его первую и последнюю цифры.

# include <iostream.h>

void main()

{

long n,m;

int last;

cout << “Enter n”;

cin >> n;

m=n; // Сохранили значение исходного числа

last=m%10;

while (m>9) m/=10;

cout << “\n In number ”<<n<< “first digit ” << m;

cout<< “, last digit ”<< last;

}

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

2. Дано натуральное число n. Подсчитать сумму цифр этого числа, находящихся на нечетных позициях (нумерация позиций идет слева направо).

3. Дано натуральное число n. Найти сумму цифр числа, находящихся на четных позициях (старшая цифра числа находится на первой позиции).

4. Даны натуральные числа n и k. Определить k-ю слева цифру числа n.

5. Дано натуральные числа n и k. Вычислить сумму k старших разрядов (находящихся слева) цифр числа.

6. Дано натуральные числа n и k. Вычислить произведение k старших разрядов (находящихся слева) цифр числа.

7. Дано натуральное число n. Вычислить сумму его цифр.

8. Дано натуральное число n. Вычислить произведение его цифр.

9. Дано натуральное число n. Найти разность между первой цифрой этого числа и суммой всех остальных.

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

11. Целое положительное десятичное число m записать в восьмеричной системе счисления и распечатать число, состоящие из разрядов этой записи, выписанных в обратном порядке. Например, m =477, результат n =537.

12. Целое положительное число m записать в двоичной системе счисления и распечатать число, состоящие из разрядов этой записи, выписанных в обратном порядке. Например, m =37, результат n =101001.

Задание 3. Одномерные массивы

Пример. Сформировать массив целых чисел X(N), элементами которого являются случайные числа в диапазоне [-20..20]. Найти максимальный элемент и его номер.

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void main ()

{

int a[100],n,max,imax;

cout<<"\nEnter n ";

cin >>n;

cout<<"\n";

randomize();// инициализация счетчика случайных чисел

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

{

a[i]= random(41)-20; // генерируем массив случайных чисел

//в диапазоне [-20..20]

cout<<"a["<<i<<"]="<<a[i]<<"\n";

}

max=a[0];

for(int i=1;i<n;i++)

if (a[i]>max) {max=a[i]; imax=i;}

cout<< "\nmax = a["<<imax<<"]= "<<max;

}

1. В целочисленном массиве X (N), сгенерированном случайным образом, нечетные элементы увеличить в два раза, а у элементов с четными номерами заменить знаки на противоположные.

2. В целочисленном массиве, сгенерированном случайным образом, определить количество перемен знака.

3. В целочисленном массиве, сгенерированном случайным образом, найти наименьший из положительных элементов.

4. Дан вещественный массив X (N). Найти элемент массива, значение которого наиболее близко к какому-нибудь целому числу.

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

6. Проведено измерение роста 70 студентов. Данные записаны в массиве ROST. Разместить в массиве N R номера тех студентов, чей рост меньше 180 см и подсчитать число таких студентов.

7. Результаты сдачи экзамена группой из N студентов находятся в массиве REZ. Подсчитать количество студентов, сдавших экзамен на «хорошо» и «отлично».

8. Из целочисленного массива X (N), сгенерированного случайным образом, переписать в массив Y элементы массива X c нечетными номерами, а в массив Z – элементы массива X, значения которых кратны 5.

9. Сформировать случайным образом массив X (N), элементами которого могут быть только 0 и 1. Проверить, существует ли строгое чередование 0 и 1.

10. Сформировать целочисленный массив X (N), элементами которого являются случайные числа из диапазона [-3..3]. Определить, сколько раз в нем встретилось два подряд идущих нулевых элемента.

11. Сформировать целочисленный массив X (N), элементами которого являются случайные числа из диапазона [-20..10]. Найти величину наибольшего среди отрицательных чисел этого массива.

12. Сформировать вещественный массив X 1(N), элементами которого являются случайные числа из диапазона [0..50]. Переслать из него в массив X 2 все элементы, значения которых больше 24 и меньше 34.

13. Сформировать целочисленный массив X (N), элементами которого являются случайные числа из диапазона [-40..40]. Подсчитать сумму элементов этого массива, значения которых кратны 8.

Задание 4. Вложенные циклы

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

#include <iostream.h>

#include <stdlib.h>

void main ()

{

const int n=100;

int a[n];

int m,d,sum1,sum2,i,k;

cout<<"\nEnter day and month ";

cin >>d>>m;

sum1=d%10+d/10+m%10+m/10;// считаем сумму цифр месяца и

//дня рождения

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

{ a[i]=random(1001); //генерируем элемент массива

sum2=0;

k=a[i];//сохраняем значения a[i]

while (k>0)// ищем сумму цифр числа a[i]

{ sum2+=k%10;

k/=10;

}

if (sum1==sum2)//нашли счастливое число

{ cout << "\nHappy number a["<<i<<"]="<<a[i];

break;//прекратили генерировать следующие элементы

//массива (выход из цикла)

}

}

if (i==n) cout<<"\n No number";

}

1. Найти все натуральные числа в диапазоне между m и n (m < n), делящиеся на каждую из своих цифр.

2. Найти все натуральные числа, в диапазоне между m и n (m < n), десятичная запись которых есть строго возрастающая последовательность цифр. Подсчитать количество таких чисел.

3. Найти все натуральные числа в диапазоне между m и n (m < n), в записи которых нет двух одинаковых цифр. Подсчитать количество таких чисел.

4. Натуральное число из m цифр называется числом Амстронга, если сумма его цифр, возведенная в степень m, равна самому числу. Распечатать все числа Амстронга, не превосходящие заданного n, и подсчитать количество таких чисел.

5. Дано натуральное число n. Подсчитать количество различных цифр, встречающихся в k старших разрядах его записи.

6. Распечатать все различные тройки последовательных элементов одномерного массива цифр. Например, в массиве 318731873 различные тройки - это 318, 187, 873, 731.

7. Сколько чисел между n и m (n < m) состоит только из нечетных цифр. Выведите на экран эти числа.

8. Заданное натуральное число представить в виде суммы квадратов двух натуральных чисел или выдать сообщение, что это невозможно.

9. Указать индексы и напечатать те элементы целочисленного массива X, сумма цифр которых равна заданному числу M (если такие элементы есть).

10. Для натуральных a и b определим операцию a Ä b = a - b + a % b. Найти все пары a, b, не превосходящие заданного n, для которых a Ä b = b Äа.

11. Определить, сколько чисел между n и m (n < m) состоит только из четных цифр. Выведите на экран эти числа.

12. Найти максимальное из чисел, встречающихся в заданном целочисленном массиве более одного раза.

Задание 5. Двумерные массивы

Пример. Сформировать матрицу A (10,10) следующего вида

# include <iostream.h>

void main ()

{ const int N=10;

static int a[N][N]; //статический массив инициализируется

//нулями

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

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

if (i>=j) a[i][j]=i-j+1 //условие попадания под главную

// диагональ

for (i=0; i<N; i++) // печать матрицы

{

for (j=0; j<N; j++) cout << a[i][j];

cout << “\n”;

}

}

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

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

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

a[i][j]=i-j+1

1. Сгенерировать случайным образом квадратную матрицу размерности K<20. Найти сумму ее элементов, находящихся на диагонали, «ортогональной» главной.

2. Дана прямоугольная матрица A (N, M) (N M, M 15). Найти произведение элементов каждой строки матрицы. Сформировать массив B из найденных произведений.

3. Дана прямоугольная матрица A (N, M) (N M, M 15). Найти максимальный элемент в каждой строке. Сформировать массив B из найденных элементов.

4. Дана прямоугольная матрица A (N, M) (N M, M 15). Преобразовать матрицу таким образом, чтобы на месте первой строки находилась вторая, на месте второй – третья, и т.д., а на месте последней - первая.

5. Дана прямоугольная матрица A (N, M) (N M, M 15) и искомое число k. Найти все имеющиеся в матрице числа k и их позиции. Если таких элементов нет, то выдать соответствующее сообщение.

6. Сформировать и распечатать квадратную матрицу А (10,10) следующего вида:

7. Сформировать и распечатать прямоугольную матрицу A (10,20) следующего вида:

8. Сформировать и распечатать квадратную матрицу A (12,12) следующего вида:

9. Сформировать и распечатать квадратную матрицу A (15,15) следующего вида:

10. Сформировать и распечатать квадратную матрицу A (15,15) следующего вида:

11. Сформировать и распечатать квадратную матрицу размерности M <20 следующего вида:

12. Сформировать и распечатать квадратную матрицу A (15,15) следующего вида:

Задание 6. Посимвольная обработка строк

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

# include <iostream.h>

void main()

{

const int n=255;

char str1[n];

cout<<"Enter string ";

cin.getline(str1,n);

int len = 0; // вычислим длину строки str1 - len

while (str1[len]) len++;

char *str2=new char [len+1]; //определили указатель

//на второй массив символов

//и выделил участок памяти для него

int j=0; //определили индекс для массива str2

for (int i=2;i<=len;i+=3)// цикл пересылки каждого

//третьего символа

str2[j++]=str1[i];

str2[j]='\0'; // в новую строку на последнее место внесли

// символ конца строки

cout<<"str1= "<<str1;

cout<<"\nstr2= "<<str2;

}

1. Сформировать строку, в которой все прописные буквы заданной заменить строчными, а все строчные буквы – прописными.

2. Сформировать строку, состоящую из всех строчных букв, входящих в заданную строку, без повторов.

3. Дано слово. Определить, упорядочены ли его буквы по алфавиту. Выделить первую упорядоченную последовательность в новую строку.

4. Из заданной текстовой строки выбрать все строчные и прописные буквы в разные подстроки, пробелы и небуквенные символы повторять в обеих подстроках.

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

6. Из заданной текстовой строки выбрать все символы главных букв в одну строку, а все прочие в другую.

7. Дана строка. Сформировать строку, содержащую символы данной в обратном порядке, причем каждый четвертый символ (считая с конца данной строки) выкинуть.

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

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

10. Дана строка. Сформировать строку, содержащую все символы данной, но точки заменены на многоточие.

11. Дана строка. Сформировать строку, содержащую все символы, которые входят в данную только один раз, в том порядке, в котором они расположены в исходной строке.

12. Дана строка. Сформировать строку, содержащую все символы данной, кроме символов, заключенных в скобки ‘(‘, ‘)’. Сами скобки нужно включить в новую строку. (Считается, что скобки расставлены корректно, и не могут быть вложенными).

Задание 7. Сортировка массива

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

Пример. Реализовать пузырьковую сортировку случайным образом генерируемого массива. Пузырьковая сортировка: массив просматривается от начала до конца. Сравниваются i -тое и (i +1)-ое числа. Если i -тое число больше (сортировка по возрастанию), то они меняются местами. Массив просматривается до тех пор, пока от начала до конца массива не сделано ни одной перестановки соседних чисел.

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void main ()

{

int a[100],n,b;

bool f;

cout<<"Enter n<100 ";

cin >>n;

cout<<"\nArray:\n";

randomize();

for (int i=0;i<n;i++) //Генерируем массив случайных чисел в

//диапазоне [0..50] и выводим на экран

{

a[i]= random(51);

cout <<a[i]<<" ";

}

cout<<"\nSotr:\n";

do

{

f=false;

for(int i=0;i<n-1;i++)// Просматриваем весь массив

if (a[i]>a[i+1])

{

b=a[i];

a[i]=a[i+1];

a[i+1]=b;

f=true; //Был обмен

}

}

while (f); // Проверяем, был ли хоть один обмен

for (int i=0;i<n;i++) // Выводим на экран отсортированный

//массив

cout<<a[i]<<" ";

}

Отсортировать случайным образом генерируемый массив, используя следующие алгоритмы.

1. Усовершенствованная пузырьковая сортировка. Используется принцип пузырьковой сортировки, но массив просматривается не от начала до конца, а от начала до последнего перемещенного элемента (после которого все элементы уже упорядочены). Вначале этим «последним» элементом выбирается последний элемент массива.

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

3. Простые вставки. Так обычно сортируют карты: из веера карт берут одну, стоящую не по старшинству и помещают между двумя уже упорядоченными картами. Массив просматривают с начала до конца. Рассматривается i-тый элемент массива и вставляется на нужную позицию в ряду первых (i -1) уже упорядоченных элементов. (Первоначально “упорядочен” только первый элемент массива). Если i -тый элемент перемещается в j -тую позицию, то все элементы с j -того по (i -1)-ый элемент должны быть сдвинуты на одну позицию вправо.

4. Метод подсчета. Если для какого-то элемента массива известно, что если он больше, чем i других элементов этого массива, то он должен стоять на (i +1)-ом месте после упорядочивания. Для каждого i-го элемента массивасчитают, сколько чисел меньше его, и результат заносят в массив индексов с [ i ]. Это делается следующим образом. Сравнивают попарно все элементы массива: i -тый и j -тый. (Одна пара чисел может сравниваться только один раз.) Если i -тый больше, то с[ i ] увеличивают на единицу, иначе c[ j ] увеличивают на единицу. После формирования массива индексов с, формируют результирующий массив.

5. Метод распределяющего подсчета. Используется, если в массиве много одинаковых элементов. Создается массив индексов d [ i ]. Размерность массива – число различных между собой элементов исходного массива. Затем в элемент массива d [ i ] заносят количество элементов массива, равных i, и в результирующий массив записывают по d [ i ] элементов i -того типа. Например, исходный массив 0010101031; d [0]=5, d [1]=4, d[2]=0, d[3]=1. Результирующий массив 0000011113.

Дата добавления: 2014-12-27