Основы алгоритмизации

Размещено на http://www.allbest.ru

Постановка задачи

В одномерном массиве, состоящем из n вещественных элементов, вычислить:

номер максимального отрицательного элемента;

преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в исходном массиве на нечётных позициях, во второй - элементы, стоявшие на чётных позициях. Предусмотреть случаи, когда n - четно и когда n - нечетно.

Дана целочисленная квадратная матрица размерностью NxN. Определить:

количество строк, среднее арифметическое элементов которых больше заданной пользователем величины;

сумму элементов, расположенных ниже побочной диагонали

С помощью генератора случайных чисел занести в массив Х(18) числа из диапазона от -15 до 20. Написать функцию для нахождения индекса минимального элемента массива. Ввод элементов массива и вызов созданной функции осуществлять в основной программе. Определить, в какой половине массива расположен минимум (1-ой или 2-ой).

Написать функцию, выводящую номера тех строк матрицы В(6,4), первый и последний элементы которых равны нулю, и подсчитывающую количество таких строк. Ввод элементов матрицы (с помощью генератора случайных чисел) и вызов созданной функции осуществлять в основной программе.

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

Описание глобальных переменных

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

Выполнение каждой подзадачи производится в отдельной функции, вызов которых производится из главного меню, расположенного в головной функции main(). Организация работы меню выполнена с использованием одной переменной - punkt. В эту переменную считывается значение, вводимое пользователем программного средства и соответствующее тому номеру пункта меню, которое пользователь выбирает для выполнения.

Блок-схема головной функции main().

Описание основных подпрограмм

В данном программном средстве разработчиком были составлены 2 основные функции Zadacha1() и Zadacha2() соответственно, реализующие одну из поставленных в условии задач. При этом каждая из этих функций содержит в себе обращение еще к ряду подпрограмм, отвечающих за реализацию отдельных типовых алгоритмов.

Описания функций программного средства:

Zadacha1() - функция содержит подменю, пункты которого соответствую подзадачам, изложенным в задании Задача 1 (см. «Постановка задачи»); входных параметров функция не имеет; возвращаемого значения функция не формирует.

Zadacha2() - функция содержит подменю, пункты которого соответствую подзадачам, изложенным в задании Задача 2 (см. «Постановка задачи»); входных параметров функция не имеет; возвращаемого значения функция не формирует

Zadacha3() - функция содержит подменю, пункты которого соответствую подзадачам, изложенным в задании Задача 3 (см. «Постановка задачи»); входных параметров функция не имеет; возвращаемого значения функция не формирует

Zadacha4() - функция содержит подменю, пункты которого соответствую подзадачам, изложенным в задании Задача 4 (см. «Постановка задачи»); входных параметров функция не имеет; возвращаемого значения функция не формирует

Fzad5() - функция содержит подменю, пункты которого соответствую подзадачам, изложенным в задании Задача 5 (см. «Постановка задачи»); входных параметров функция не имеет; возвращаемого значения функция не формирует

Блок-схема подпрограммы Zadacha1

Блок-схема подпрограммы Zadacha2

Блок-схема подпрограммы Zadacha3

Блок-схема подпрограммы Zadacha4

void PrintMass2 (unsigned int M, unsigned int N, int **p) - функция печатает элементы массива. Входные параметры: N, M - размерность массива, p -указатель на массив. Выходного значения нет.

Блок-схема подпрограммы PrintMass2

void PrintMass (unsigned int size, unsigned int N, int *p) - функция печатает элементы массива. Входные параметры: sz - размерность массива, p -указатель на массив. Выходного значения нет.

Блок-схема подпрограммы PrintMass

Функция void SortMass (unsigned int sz, int* p) - функция сортирует элементы массива между заданными индексами

Входные параметры:

sz - количество элементов в массиве

р - указатель на массив

Локальные переменные:

к1 - начальный индекс элемента массива

к2 - конечный индекс элемента массива

i, j - индексы текущего элемента массива

buf - дополнительная переменная для обмена значений двух элементов массива

В функции предусмотрено аварийное завершение работы с выводом соответствующего сообщения при не правильном вводе пользователем значений индексов элементов.

Блок-схема подпрограммы SortMass

блок схема матрица программа

Блок-схема подпрограммы MaxMass

Блок-схема подпрограммы SumAfterZerro

Блок-схема подпрограммы CreateMass2

Блок-схема подпрограммы PrintMass2

Блок-схема подпрограммы NonZerroRows

Блок-схема подпрограммы SwitchColumn

Листинг программного продукта на языке С++

//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

// Подключение библиотечных файлов C++:

#include<stdlib.h> // необходим для операций с генератором случайных чисел

#include<iostream.h> // необходим для операций потокового ввода-вывода

#include<conio.h> // необходим для работы с консолью

#include<stdio.h> // необходим для форматированного ввода-вывода

#include <iostream>

#include <windows.h>

#include <math.h>

// Прототипы функций

void Zadacha1 ();

void Zadacha2 ();

void Zadacha3 ();

void Zadacha4 ();

int* CreateMass (unsigned int &);

int** CreateMass2 (unsigned int &, unsigned int &);

void PrintMass (unsigned int, int*);

void PrintMass2 (unsigned int, unsigned int , int**);

void PrChetn (unsigned int, int*);

void NonMinusCols (unsigned int, unsigned int, int**);

void SumBetweenMinus (unsigned int sz, int* p);

void SwitchColumn (unsigned int M, unsigned int N, int** p);

void Fzad4 (unsigned int M, unsigned int N, int** p);

void Fzad3 (unsigned int sz, int* p);

#pragma argsused

//---------------------------------------------------------------------------

// Главная программа

void main ()

{

SetConsoleCP (1251); // регистры в C++ учитываются

SetConsoleOutputCP (1251);

char punkt;

do

{

clrscr();

cout << "\n СЕМЕСТРОВАЯ РАБОТА. ВАРИАНТ 26.\n";

cout << "\n ГЛАВНОЕ МЕНЮ\n\n";

cout << "1. ЗАДАЧА 1\n";

cout << "2. ЗАДАЧА 2\n";

cout << "3. ЗАДАЧА 3\n";

cout << "4. ЗАДАЧА 4\n";

cout << "5. ЗАДАЧА 5\n";

cout << "6. ВЫХОД\n";

punkt=getch();

switch (punkt)

{

case '1':

Zadacha1 ();

break;

case '2':

Zadacha2 ();

break;

case '3':

Zadacha3 ();

break;

case '4':

Zadacha4 ();

break;

}

}while (punkt!='6');

}

// ************************************************************************

// ******************************** ФУНКЦИИ ******************************

// ************************************************************************

void Zadacha1 ()

{

char punkt;

int *a=NULL; // указатель на создаваемый массив

unsigned int size; // размер массива

do

{

clrscr();

cout << "\n ЗАДАЧА 1. \n МЕНЮ\n\n";

cout << "1. Создать массив\n";

cout << "2. Распечатать массив\n";

cout << "3. Сумма элементов массива, расположенных между первым и вторым отрицательными элементами\n";

cout << "4. Произведение элементов массива с чётными номерами\n";

cout << "5. Вернуться в главное меню\n";

punkt=getch();

switch (punkt)

{

case '1':

if (a) delete[] a;

a=CreateMass(size);

break;

case '2':

PrintMass(size, a);

break;

case '3':

SumBetweenMinus(size,a);

break;

case '4':

PrChetn (size,a);

break;

}

}while (punkt!='5');

if (a) delete[] a; // освобождение памяти

return;

}

void Zadacha2 ()

{

unsigned int M,N; // Размер массива

int i,j;

char punkt;

int **a=NULL; // указатель на создаваемый массив

do{

clrscr();

cout << "\n ЗАДАЧА 2. \n МЕНЮ\n\n";

cout << "1. Создать двумерный массив\n";

cout << "2. Распечатать массив\n";

cout << "3. Подсчет суммы элементов в тех столбцах, которые не содержат отрицательных элементов\n";

cout << "4. Найти минимум среди сумм элементов диагоналей, параллельных побочной диагонали матрицыв\n";

cout << "5. Вернуться в главное меню\n";

punkt=getch();

switch (punkt)

{

case '1':

// Удаление массива из памяти

if (a)

{

for (i=0;i<M;i++) delete[] a[i];

delete [] a;

}

a=CreateMass2(M,N);

break;

case '2':

PrintMass2(M,N,a);

break;

case '3':

NonMinusCols (M,N,a);

break;

case '4':

SwitchColumn (M,N,a);

break;

}

}while (punkt!='5');

// Удаление массива из памяти

if (a)

{

for (i=0;i<M;i++) delete[] a[i];

delete [] a;

}

return;

}

void Zadacha3 ()

{

char punkt;

int *a=NULL; // указатель на создаваемый массив

unsigned int size; // размер массива

do

{

clrscr();

cout << "\n ЗАДАЧА 3. \n МЕНЮ\n\n";

cout << "1. Создать массив\n";

cout << "2. Распечатать массив\n";

cout << "3. Вызов функции\n";

cout << "4. Вернуться в главное меню\n";

punkt=getch();

switch (punkt)

{

case '1':

if (a) delete[] a;

a=CreateMass(size);

break;

case '2':

PrintMass(size, a);

break;

case '3':

Fzad3(size,a);

break;

}

}while (punkt!='4');

if (a) delete[] a; // освобождение памяти

return;

return;

}

void Zadacha4 ()

{

unsigned int M,N; // Размер массива

int i,j;

char punkt;

int **a=NULL; // указатель на создаваемый массив

do{

clrscr();

cout << "\n ЗАДАЧА 4. \n МЕНЮ\n\n";

cout << "1. Создать двумерный массив\n";

cout << "2. Распечатать массив\n";

cout << "3. Решение функции\n";

cout << "4. Вернуться в главное меню\n";

punkt=getch();

switch (punkt)

{

case '1':

// Удаление массива из памяти

if (a)

{

for (i=0;i<M;i++) delete[] a[i];

delete [] a;

}

a=CreateMass2(M,N);

break;

case '2':

PrintMass2(M,N,a);

break;

case '3':

Fzad4 (M,N,a);

break;

}

}while (punkt!='4');

// Удаление массива из памяти

if (a)

{

for (i=0;i<M;i++) delete[] a[i];

delete [] a;

}

return;

}

//----------------------------------------------------------------------

// Распечатка двумерного массива

//----------------------------------------------------------------------

void PrintMass2 (unsigned int M, unsigned int N, int **p)

{

int i,j;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

printf ("\n\nМассив a[%d][%d] имеет вид:\n",M,N);

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

{

for (j=0;j<N;j++) printf("%4d",p[i][j]);

printf("\n");

}

getch();

return;

}

//----------------------------------------------------------------------

// Выделение памяти под двумерный массив и заполнение его

//----------------------------------------------------------------------

int** CreateMass2 (unsigned int &M,unsigned int &N)

{

int i,j,r;

char punkt;

cout << "\n\nЗадайте размер для двумерного массива \n";

cout << "Строк в массиве M = "; cin >> M;

cout << "Cтолбцов в массиве N = "; cin >> N;

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

int **p=new int*[M]; // сначала массив из M указателей на int

// при этом переменная p является так назыв. указателем на указатель

for (i=0;i<M;i++) p[i]=new int[N]; // теперь каждый указатель укажет на массив N целых

if (!p)

{

cout << "\n\nОшибка! Невозможно создать массив! \nПопробуйте задать меньший размер.";

getch();

return NULL;

}

cout << "\n\nВвод значений в массив:";

cout << "\n1. Вручную";

cout << "\n2. Автоматически (случайные значения)\n";

punkt=getch();

switch (punkt)

{

case '1':

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

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

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

{

printf("a[%d][%d] = ",i,j); cin >> p[i][j];

}

break;

case '2':

cout << "\nВведите диапазон для случайных чисел (от 0 до r) r = ";

cin >> r;

randomize();

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

for (j=0;j<N;j++) p[i][j]=random(r);

}

cout << "\n\nМассив создан.";

getch();

return p;

}

//----------------------------------------------------------------------

// Выделение памяти под одномерный массив и заполнение его

//----------------------------------------------------------------------

int* CreateMass (unsigned int &sz)

{

int *p;

int i,r,t;

char punkt;

cout << "\n\nЗадайте размер массива ";

cin >> sz;

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

p=new int[sz];

if (!p)

{

cout << "\n\nОшибка! Невозможно создать массив! \nПопробуйте задать меньший размер.";

getch();

return NULL;

}

cout << "\n\nВвод значений в массив:";

cout << "\n1. Вручную";

cout << "\n2. Автоматически (случайные значения)\n";

punkt=getch();

switch (punkt)

{

case '1':

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

{

cout << "Ввод " << i <<"-го элемента: ";

cin >> p[i];

}

break;

case '2':

cout << "\nВведите минимум для случайных чисел: ";

cin >> t;

cout << "\nВведите максимум для случайных чисел: ";

cin >> r;

randomize(); // Настройка генератора случайных чисел

for (i=0;i<sz;i++) { p[i]=random(r)%(r-t+1)+t; }

}

cout << "\n\nМассив создан.";

getch();

return p;

}

//----------------------------------------------------------------------

// Распечатка одномерного массива

//----------------------------------------------------------------------

void PrintMass (unsigned int sz, int* p)

{

int i;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

cout << "\n\nМассив a[" << sz << "] содержит следующие значения:\n";

for (i=0;i<sz;i++) cout << p[i]<< " ";

getch();

return;

}

//-------------------------------------------------------------------

// Нахождение произведения элементов с четными номерами

//-------------------------------------------------------------------

void PrChetn (unsigned int sz, int* p)

{

int i;

int sum=1; // сумма элементов после нуля

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

// Находим четные индексы и затем считаем произведение

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

{

// Если номер элемента делится на 2 без остатка, то подсчет произведения

if (i%2) sum*=p[i];

}

if (sz==1) cout << "\n\n В массиве нет четных номеров элементов! Произведение не может быть найдена!";

else cout << "\n\n Произведение элементов с четными номерами равна " << sum;

getch();

return;

}

//-------------------------------------------------------------------

// Нахождение суммы элементов между отрицательными элементами

//-------------------------------------------------------------------

void SumBetweenMinus (unsigned int sz, int* p)

{

int i;

int otr1=-1; // индекс первого отрицательного элемента (если равен -1, отриц. значений массиве нет)

int otr2=-1; // индекс второго отрицательного элемента (если равен -1, отриц. значений в массиве нет)

int sum=0; // сумма элементов между 1м и 2м отрицательным элементом

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

// Находим первый отрицательный элемент

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

{

// Если индекс элемента найден, запомнить индекс

if (p[i]<0){ otr1=i;

break; }

}

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

{

// Если индекс элемента найден, запомнить индекс

if ((p[i]<0)&&(i>otr1)) {otr2=i;

break; }

}

for (i=otr1;i<=otr2;i++)

{

sum+=p[i];

}

if (otr1==-1) cout << "\n\n В массиве нет отрицательных значений! Сумма не может быть найдена!";

else cout << "\n\n Cумма между отрицательными элементами a["<<otr1<<"] и a["<<otr2<<"] равна " << sum;

getch();

return;

}

//-------------------------------------------------------------------

// Подсчет суммы элементов в тех столбцах, которые не содержат отрицательных элементов

//-------------------------------------------------------------------

void NonMinusCols (unsigned int M, unsigned int N, int** p)

{

unsigned int l,chk;

int i,j,sum;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

l=0;

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

{

sum=0;

chk=0; // Сначала предположим что i-я строка не содержит отрицательных элементов

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

{

// Если найден отрицательный элемент, то установить переменную проверки в 1

if (p[i][j]<0) chk=1;

}

// Если в ходе проверки отрицательных элементов не найдено в столбце то найти сумму столбца

if (chk==0)

{

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

{

sum +=p[i][j];

}

cout << "\n Сумма элеметов "<< j <<" -го столбза без отрицательных элементов равна "<<sum;

}

}

getch();

return;

}

//-------------------------------------------------------------------

// Минимум среди сумм элементов диагоналей, параллельных побочной диагонали матрицы

//-------------------------------------------------------------------

void SwitchColumn (unsigned int M, unsigned int N, int** p)

{

int i,j;

unsigned int k1,k2;

int sum,minsum;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

// Идем до диагонали

for (i=0;i<N-1;i++) //N-1 - саму диагональ пропускаем

{

sum=0;

for (j=0;j<i+1;j++) sum+=p[j][(i-1)-j+1];

if (sum<minsum) minsum=sum;

}

//идем после диагонали:

for (i=1; i<N; i++) //саму побочную диагональ пропускаем

{

sum=0;

for (j=i; j<N;j++) sum+=p[j][(N-1)-j+i];

if (sum<minsum) minsum=sum;

}

cout << "\n \n Минимальная из сумм элементов в побочных диагоналях матрицы равна "<<minsum;

getch();

return;

}

//-------------------------------------------------------------------

// Выполнение задания 3

//-------------------------------------------------------------------

void Fzad3 (unsigned int sz, int* p)

{

int i,ind;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

// Ищем первый отрицательный элемент

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

if (p[i]<0)

{

ind=i; // Запоминаем его номер

p[i]=1;

}

}

// Заполняем массив согласно заданию

for (i = 0; i < ind; i++) p[i]=0;

for (i = ind+1; i < sz; i++) p[i]= abs(p[i]);

cout <<"\n Массив новый ";

for (i = 0; i < sz; i++) cout << p[i];

getch();

return;

}

//-------------------------------------------------------------------

// Минимум среди сумм элементов диагоналей, параллельных побочной диагонали матрицы

//-------------------------------------------------------------------

void Fzad4 (unsigned int M, unsigned int N, int** p)

{

int i,j,kol;

if (!p)

{

cout << "\n\nОшибка! Массив еще не создан.";

getch();

return;

}

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

kol=0;

for (j = 1; j < N-1; j++)

if ((p[i][j-1]<p[i][j])&(p[i][j]<p[i][j+1])) kol++;

cout << "\n \n Количество элементов удовлетворяющих условиям в "<<i<<"-й строке равно "<<kol;

}

getch();

return;

}

void Fzad5()

{

char text[]="In a year instead of the promised Morrowind the company Bethesda released Battlespiare, a primitive 3D-action based on Daggerfall engine.";

int i,kol,max=0,x=0,m;

int n=sizeof(text)/sizeof(char);

clrscr();

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

{

if (text[i] == ' ' || text[i] == ',' || text[i] == '.')

{

if (x >= max)

{

if(x > max)

{

kol=1;

m=i-x;

}

else

kol++;

max=x;

}

x=0;

}

else

x++;

}

if (x > max)

{

max = x;

kol++;

}

printf("Lenth = %d; Kol = %d;\n",max,kol);

for (i=m;i<max+m;i++)

printf ("%c",text[i]);

getch();

}

Результаты тестового прогона программы

Задача 1

Задача 2

]

Задача 3

Задача 4

Задача 5

Текст «error lnk2001 unresolved external, symbol main»

Заключение

Программа была разработана в рамках семестрового задания, и обладает рядом достоинств и недостатков. Представляемый программный продукт отвечает все требованиям, предъявленным заказчиком (см. пункт «Постановка задачи»).

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

Все задачи варианта объединены одним общим интерфейсом. Выполнение каждой задачи осуществляется как последовательный вызов всех необходимых подпрограмм, для этого был составлен уникальный алгоритм. Предусмотрена возможность повтора выполнения каждой задачи через пункты главного меню. Результаты печатаются с максимально возможными комментариями. Размерность массивов задается пользователем программного средства.

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

Программа была разработана в процессе изучения разработчиком курса «Программирование и основы алгоритмизации», и поэтому обладает также и рядом недостатков. Были использованы не всегда оптимальные по времени исполнения алгоритмы для решения некоторых подзадач. Некоторые участки кода могут быть, по мнению автора, реорганизованы в более читабельный вид или реализованы более оптимально. Но, не смотря на эти недочеты, данная программная разработка, по твердому убеждению автора, полностью удовлетворяет заданным требованиям, и даже в некоторых моментах выходит за рамки задания, что является ее неоспоримым достоинством.

Использованная литература

1. Б.И.Березин, С.Б.Березин "Начальный курс С и С++" -M.: ДИАЛОГ-МИФИ, 1996 г.

2. В.А.Скляров "Язык С++ и объектно-ориентированное программирование" - Мн.: Выш. шк., 1997 г.

3. С.Поттс, Т.С.Монк "BORLAND C++ в примерах" - Мн.: ООО "Попурри", 1996 г.

Размещено на Allbest.ru