Основы алгоритмизации
Постановка задачи
В одномерном массиве, состоящем из 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>
// Прототипы функцийZadacha1
();Zadacha2 ();Zadacha3 ();Zadacha4 ();* CreateMass (unsigned int &);**
CreateMass2 (unsigned int &, unsigned int &);PrintMass (unsigned int,
int*);PrintMass2 (unsigned int, unsigned int , int**);PrChetn (unsigned int,
int*);NonMinusCols (unsigned int, unsigned int, int**);SumBetweenMinus
(unsigned int sz, int* p);SwitchColumn (unsigned int M, unsigned int N, int**
p);Fzad4 (unsigned int M, unsigned int N, int** p);Fzad3 (unsigned int sz, int*
p);
#pragma argsused
//---------------------------------------------------------------------------
// Главная программаmain ()
{(1251); // регистры в C++
учитываются(1251);punkt;
{();<< "\n СЕМЕСТРОВАЯ
РАБОТА. ВАРИАНТ
26.\n";
cout <<
"\n ГЛАВНОЕ МЕНЮ\n\n";
cout <<
"1. ЗАДАЧА 1\n";
cout <<
"2. ЗАДАЧА 2\n";
cout <<
"3. ЗАДАЧА 3\n";
cout <<
"5. ЗАДАЧА 5\n";
cout <<
"6. ВЫХОД\n";
punkt=getch();(punkt)
{'1':();;'2':();;'3':();;'4':();;
}
}while (punkt!='6');
}
//
************************************************************************
// ********************************
ФУНКЦИИ ******************************
//
************************************************************************Zadacha1
()
{punkt;
*a=NULL;
// указатель на создаваемый массив
unsigned int size; // размер массива
{();<< "\n ЗАДАЧА 1. \n
МЕНЮ\n\n"; << "1. Создать массив\n";
cout <<
"2. Распечатать массив\n";
cout <<
"3. Сумма элементов массива, расположенных между первым и вторым
отрицательными элементами\n";
cout <<
"4. Произведение элементов массива с чётными номерами\n";
cout <<
"5. Вернуться в главное меню\n";
punkt=getch();(punkt)
{'1':(a) delete[]
a;=CreateMass(size);;'2':(size, a);;'3':(size,a);;'4':(size,a);;
}
}while (punkt!='5');(a) delete[] a;
// освобождение памяти;
}Zadacha2 ()
{int M,N; // Размер
массиваi,j;punkt; **a=NULL;
// указатель на создаваемый массив
do{();<< "\n ЗАДАЧА 2. \n
МЕНЮ\n\n";<< "1. Создать двумерный
массив\n";
cout <<
"2. Распечатать массив\n";
cout <<
"3. Подсчет суммы элементов в тех столбцах, которые не содержат
отрицательных элементов\n";
cout <<
"4. Найти минимум среди сумм элементов диагоналей, параллельных побочной
диагонали матрицыв\n";
cout <<
"5. Вернуться в главное меню\n";
punkt=getch();(punkt)
{'1':
// Удаление массива из памяти
if (a)
{(i=0;i<M;i++) delete[] a[i];[]
a;
}=CreateMass2(M,N);;'2':(M,N,a);;'3':(M,N,a);;'4':(M,N,a);;
}
}while
(punkt!='5');
// Удаление массива из памяти
if (a)
{(i=0;i<M;i++) delete[] a[i];[]
a;
};
}Zadacha3 ()
{
char
punkt;
int *a=NULL;
// указатель на создаваемый массив
unsigned int size; // размер массива
{();<< "\n ЗАДАЧА 3. \n
МЕНЮ\n\n"; << "1. Создать массив\n";
cout <<
"2. Распечатать массив\n";
cout <<
"3. Вызов функции\n";
cout <<
"4. Вернуться в главное меню\n";
punkt=getch();(punkt)
{'1':(a) delete[]
a;=CreateMass(size);;'2':(size, a);;'3':(size,a);;
}
}while (punkt!='4');(a) delete[] a;
// освобождение памяти;;
}Zadacha4 ()
{int M,N; // Размер
массиваi,j;punkt; **a=NULL;
// указатель на создаваемый массив
do{();<< "\n ЗАДАЧА 4. \n
МЕНЮ\n\n";<< "1. Создать двумерный
массив\n";
cout <<
"2. Распечатать массив\n";
cout <<
"3. Решение функции\n";
cout <<
"4. Вернуться в главное меню\n";
punkt=getch();(punkt)
{'1':
// Удаление массива из памяти
if (a)
{(i=0;i<M;i++) delete[] a[i];[]
a;
}=CreateMass2(M,N);;'2':(M,N,a);;'3':(M,N,a);;
}
}while
(punkt!='4');
// Удаление массива из памяти
if (a)
{(i=0;i<M;i++) delete[] a[i];
[] a;
return;
}
//----------------------------------------------------------------------
// Распечатка двумерного массива
//----------------------------------------------------------------------PrintMass2
(unsigned int M, unsigned int N, int **p)
{i,j;(!p)
{<< "\n\nОшибка! Массив
еще не создан.";
getch();
return;
}("\n\nМассив a[%d][%d] имеет
вид:\n",M,N);(i=0;i<M;i++)
{(j=0;j<N;j++)
printf("%4d",p[i][j]);("\n");
}
getch();
return;
}
//----------------------------------------------------------------------
// Выделение памяти под двумерный массив и
заполнение его
//----------------------------------------------------------------------**
CreateMass2 (unsigned int &M,unsigned int &N)
{i,j,r;punkt;
<< "\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)
{<< "\n\nОшибка! Невозможно
создать массив! \nПопробуйте
задать меньший размер.";
getch();
return
NULL;
}
cout <<
"\n\nВвод
значений в массив:";
cout << "\n1.
Вручную";<< "\n2. Автоматически
(случайные значения)\n";
punkt=getch();
switch (punkt)
{
case '1':
cout <<
"\nВвoдите
числo в каждый элемент
массива:\n";
for (i=0;i<M;i++)(j=0;j<N;j++)
{("a[%d][%d] = ",i,j); cin
>> p[i][j];
}
break;
case '2':
cout <<
"\nВведите диапазон
для случайных чисел (от 0 до r)
r = ";
cin >> r;();(i=0;i<M;i++)(j=0;j<N;j++)
p[i][j]=random(r);
}
cout <<
"\n\nМассив
создан.";
getch();
return
p;
}
//----------------------------------------------------------------------
// Выделение памяти под одномерный массив и
заполнение его
//----------------------------------------------------------------------*
CreateMass (unsigned int &sz)
{*p;i,r,t;punkt;<<
"\n\nЗадайте размер массива "; >> sz;
// Динамическое выделение памяти под массив
p=new int[sz];(!p)
{
cout <<
"\n\nОшибка!
Невозможно создать массив! \nПопробуйте
задать меньший размер.";
getch();
return
NULL;
}
cout <<
"\n\nВвод
значений в массив:";
cout << "\n1.
Вручную";<< "\n2. Автоматически
(случайные значения)\n";
punkt=getch();
switch (punkt)
{'1':(i=0;i<sz;i++)
{
cout <<
"Ввод " << i
<<"-го элемента: ";
cin >> p[i];
};'2': <<
"\nВведите минимум для
случайных чисел: ";
cin >> t;
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)
{i;(!p)
{<< "\n\nОшибка! Массив
еще не создан.";
getch();
return;
}
cout <<
"\n\nМассив
a[" << sz
<< "] содержит следующие значения:\n";
for (i=0;i<sz;i++) cout <<
p[i]<< " ";();
return;
}
//-------------------------------------------------------------------
// Нахождение произведения элементов с четными
номерами
//-------------------------------------------------------------------PrChetn
(unsigned int sz, int* p)
{
int
i;
int
sum=1; // сумма
элементов после нуля
if (!p)
{<< "\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;
}
//-------------------------------------------------------------------
// Нахождение суммы элементов между
отрицательными элементами
//-------------------------------------------------------------------SumBetweenMinus
(unsigned int sz, int* p)
{
int
i;
int
otr1=-1; // индекс
первого отрицательного элемента (если равен -1, отриц. значений массиве нет)
int
otr2=-1; // индекс
второго отрицательного элемента (если равен -1, отриц. значений в массиве нет)
int
sum=0; // сумма
элементов между 1м и 2м отрицательным элементом
if (!p)
{<< "\n\nОшибка! Массив
еще не создан.";
getch();
return;
}
// Находим первый отрицательный элемент
for (i=0;i<sz;i++)
{
// Если индекс элемента найден, запомнить индекс
if (p[i]<0){ otr1=i;; }
}
for (i=0;i<sz;i++)
{
// Если индекс элемента найден, запомнить индекс
if
((p[i]<0)&&(i>otr1)) {otr2=i;; }
}(i=otr1;i<=otr2;i++)
{
sum+=p[i];
}
else
cout << "\n\n
Cумма между
отрицательными элементами a["<<otr1<<"]
и a["<<otr2<<"]
равна " << sum;
getch();
return;
}
//-------------------------------------------------------------------
// Подсчет суммы элементов в тех столбцах,
которые не содержат отрицательных элементов
//-------------------------------------------------------------------NonMinusCols
(unsigned int M, unsigned int N, int** p)
{int l,chk;i,j,sum;(!p)
{<< "\n\nОшибка! Массив
еще не создан.";
getch();
return;
}=0;(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)
{(i = 0; i < N; i++)
{
sum +=p[i][j];
}
cout <<
"\n Сумма элеметов
"<< j
<<" -го столбза без отрицательных элементов равна "<<sum;
}
}
getch();
return;
}
//-------------------------------------------------------------------
// Минимум среди сумм элементов диагоналей,
параллельных побочной диагонали матрицы
//-------------------------------------------------------------------SwitchColumn
(unsigned int M, unsigned int N, int** p)
{i,j;int k1,k2;sum,minsum;(!p)
{
cout <<
"\n\nОшибка!
Массив еще не создан.";
getch();
return;
}
// Идем до диагонали
for (i=0;i<N-1;i++)
//N-1 - саму диагональ
пропускаем
{=0;(j=0;j<i+1;j++)
sum+=p[j][(i-1)-j+1];(sum<minsum) minsum=sum;
}
//идем после диагонали:
for (i=1;
i<N;
i++) //саму побочную
диагональ пропускаем
{=0;(j=i; j<N;j++)
sum+=p[j][(N-1)-j+i];(sum<minsum) minsum=sum;
}
cout <<
"\n \n
Минимальная из сумм элементов в побочных диагоналях матрицы равна
"<<minsum;
getch();;
}
//-------------------------------------------------------------------
// Выполнение задания 3
//-------------------------------------------------------------------Fzad3
(unsigned int sz, int* p)
{i,ind;(!p)
{
cout <<
"\n\nОшибка!
Массив еще не создан.";
getch();
return;
}
// Ищем первый отрицательный элемент
for (i = 0; i < sz; i++)
{(p[i]<0)
{
ind=i;
// Запоминаем его номер
p[i]=1;
}
}
// Заполняем массив согласно заданию
for (i
= 0; i < ind;
i++) p[i]=0;
return;
}
//-------------------------------------------------------------------
// Минимум среди сумм элементов диагоналей,
параллельных побочной диагонали матрицы
//-------------------------------------------------------------------Fzad4
(unsigned int M, unsigned int N, int** p)
{i,j,kol;(!p)
{
cout <<
"\n\nОшибка!
Массив еще не создан.";
getch();;
}(i = 0; i <M ; i++) {=0;(j = 1;
j < N-1; j++)((p[i][j-1]<p[i][j])&(p[i][j]<p[i][j+1])) kol++;
<< "\n \n
Количество элементов удовлетворяющих условиям в "<<i<<"-й
строке равно "<<kol;
}();;
}Fzad5()
{text[]="In a year instead of
the promised Morrowind the company Bethesda released Battlespiare, a primitive
3D-action based on Daggerfall
engine.";i,kol,max=0,x=0,m;n=sizeof(text)/sizeof(char);
();(i=0,m=0;i<n;i++)
{(text[i] == ' ' || text[i] == ','
|| text[i] == '.')
{(x >= max)
{(x > max)
{=1;=i-x;
}++;=x;
}=0;
}++;
}(x > max)
{= x;++;
}("Lenth = %d; Kol =
%d;\n",max,kol);(i=m;i<max+m;i++)("%c",text[i]);();
}
Результаты тестового прогона программы
Задача 1
Задача 2
]
Задача 3
Задача 4
Задача 5
Текст «error lnk2001 unresolved
external, symbol main»
Заключение
Программа была разработана в рамках семестрового
задания, и обладает рядом достоинств и недостатков. Представляемый программный
продукт отвечает все требованиям, предъявленным заказчиком (см. пункт
«Постановка задачи»).
Разработка программного средства проводилась в
полном соответствии с современными тенденциями в технологии программирования, а
именно, с использованием принципов модульного и структурного проектирования
программных средств. Для решения каждой из подзадач были разработаны отдельные
функции, которые могут быть настроены на различные массивы с помощью изменения
значений входных параметров. Данный подход существенно сократил программный код
и, соответственно, память компьютера, необходимую для размещения и успешной
работы программного средства, а так же увеличил быстродействие и эффективность
работы программы.
Все задачи варианта объединены одним общим
интерфейсом. Выполнение каждой задачи осуществляется как последовательный вызов
всех необходимых подпрограмм, для этого был составлен уникальный алгоритм.
Предусмотрена возможность повтора выполнения каждой задачи через пункты
главного меню. Результаты печатаются с максимально возможными комментариями.
Размерность массивов задается пользователем программного средства.
В случае необходимости программа сообщает об
ошибках, возникающих по вине пользователя или при сбоях в самой программе.
Например, при реализации решения подзадачи сортировки для определенной части
массива, подпрограмма выполняет дополнительную проверку данных, вводимых
пользователем, на корректность, что, соответственно, повышает эффективность
всего программного продукта в целом.
Программа была разработана в процессе изучения
разработчиком курса «Программирование и основы алгоритмизации», и поэтому
обладает также и рядом недостатков. Были использованы не всегда оптимальные по
времени исполнения алгоритмы для решения некоторых подзадач. Некоторые участки
кода могут быть, по мнению автора, реорганизованы в более читабельный вид или
реализованы более оптимально. Но, не смотря на эти недочеты, данная программная
разработка, по твердому убеждению автора, полностью удовлетворяет заданным
требованиям, и даже в некоторых моментах выходит за рамки задания, что является
ее неоспоримым достоинством.
Использованная литература
1.
Б.И.Березин, С.Б.Березин "Начальный курс С и С++" -M.:
ДИАЛОГ-МИФИ, 1996 г.
.
В.А.Скляров "Язык С++ и объектно-ориентированное программирование" -
Мн.: Выш. шк., 1997 г.
.
С.Поттс, Т.С.Монк "BORLAND
C++ в примерах"
- Мн.: ООО "Попурри", 1996 г.