Листинг 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