Листинг 5.5

#include " stdafx.h"

#include < iostream>

#include " conio.h"

#include " math.h"

#include " windows.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, " Russian");

const int N = 1000;

int n, i, j, left, right, sp = 0, m = 1;

float *C = new float[N], middle, temp;

int *stackl = new int[N], *stackr = new int[N];

cout< < " \n\nЗадание: \n";

cout< < " \nСоставить программу с использованием динамических массивов\n";

cout< < " \nдля решения задачи на переупорядочивание элементов массива.\n";

cout< < " \nВ качестве алгоритма сортировки использовать метод быстрой сортировки массива.\n";

cout< < " \n\nЗадача: составить программу нахождения тех элементов массива С, \n";

cout< < " \nиндексы которых являются степенями двойки (1, 2, 4,...).\n";

cout< < " \n\nРабота программы: \n"

A:

cout< < " \nВведите количество элементов: ";

cin > > n;

if(n < = 0 || n > N)

{

cout< < " Неверный размер массива" < < " \n";

goto A;

}

cout< < " \nВведите элементы массива: \n\n";

for(i = 0; i < n; i++) cin > > C[i];

sp = 1;

stackl[1] = 0;

stackr[1] = n - 1;

while(sp > 0)

{

left = stackl[sp];

right = stackr[sp];

sp--;

while(left < right)

{

i = left;

j = right;

middle = C[(left + right)/2];

while(i < j)

{

while(C[i] < middle) i++;

while(middle < C[j]) j--;

if(i < = j)

{

temp = C[i];

C[i] = C[j];

C[j] = temp;

i++;

j--;

}

}

if(i < right)

{

sp++;

stackl[sp] = i;

stackr[sp] = right;

}

right = j;

}

}

cout< < " \nМассив после сортировки: \n\n";

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

{

cout < < C[i] < < " \n";

}

cout< < " \nМассив из элементов, индексы которых являются степенями двойки: \n\n" < < " \n";

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

{

while (m < n)

{

cout < < C[m] < < " \n";

m = m * 2;

}

}

delete[] C;

delete[] stackl;

delete[] stackr;

getch();

return 0;

}

Пример 5.4. В массиве {aj}, j = 1, 2, …10 есть положительные и отрицательные элементы. Вычислить произведение отрицательных элементов. UML-диаграмма этого алгоритма приведена на рисунке 5.2.

Рисунок 5.2 - UML-диаграмма деятельности для примера 5.4