8 Предопределенные процессы. Рекурсия.
Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной
Пример прямой рекурсии:
int a() {.....a().....}
Пример косвенной рекурсии:
a(){.....b().....}b(){.....c().....}c(){.....a().....} .
Предопределенный процесс — это символ, который отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле). Изображается следующим образом:
Задача № 1
Найти значение максимального элемента среди элементов, кратных k и расположенных до первого отрицательного элемента.
Решение задачи на языке программирования C:
#include <stdio.h>
#include <stdlib.h>
main(){
int i,j,k,maxi=0,z=0,a[50],maxx=0;
printf("Введите значение kратности k=");scanf("%d",&k);
for (i=0;i<50;i=i+1){
a[i]=(rand()%100+1)-20;
printf("a[%d]=%d\n",i,a[i]);}
printf("\nЭлементы кратные k=%d\n",k);
for (i=k;i<50;i=i+k){
printf("a[%d]=%d\n",i,a[i]);
if (a[i]<0){
if (i==k){
printf("Положительные элементы отсутствовали!!!\n");
maxi=i;
maxx=a[i];}
printf("Максимальный элемент является a[%d]=%d\n",maxi,maxx);
z=z+1;break;}
if (maxx<a[i]){
maxi=i;maxx=a[i];}}
if (z==0){
printf("Отрицательный элемент отсутствовал!!!\n");
printf("Максимальный элемент является a[%d]=%d\n",maxi,maxx);}}
Блок-схема решения задачи:
Выполнение программы:
Начало
Инициализация переменных
int i,j,k,maxi=0,z=0,a[50],maxx=0;
Ввод значения кратности
printf("Введите значение kратности k=");scanf("%d",&k);
Заполняем массив случайными числами по средством цикла
for (i=0;i<50;i=i+1)
{a[i]=(rand()%100+1)-20;
Вывод заполненного элемента на экран
printf("a[%d]=%d\n",i,a[i]);}
Вывод сообщения “Элементы кратные k=” и самого значения k
printf("\nЭлементы кратные k=%d\n",k);
Вывод элементов массива кратного k
for (i=k;i<50;i=i+k){
printf("a[%d]=%d\n",i,a[i]);
Проверка элемента кратного k. Является ли он отрицательным числом.
if (a[i]<0){
если элемент кратный k является отрицательным числом, то идет проверка является ли этот элемент первым(единственным) проверяемым элементом.
if (i==k){
Если элемент является первым, то выводиться сообщение и максимальному элементу присваивается данное значение и порядковый номер элемента в массиве.
printf("Положительные элементы отсутствовали!!!\n");
maxi=i;maxx=a[i];}
Продолжается выполнение первого условия с отрицательностью элемента. Выводиться сообщение о максимальном элементе. Z увеличивается на единицу. Прерывается выполнение цикла.
printf("Максимальный элемент является a[%d]=%d\n",maxi,maxx);
z=z+1;
break;}
Идет проверка элемента. Является ли текущий элемент больше максимального. Если да, то идет присвоение нового значения. Если нет, то ничего не происходит
if (maxx<a[i]){
maxi=i;maxx=a[i];} }
Идет проверка. Выполнялось ли хоть раз условие отрицательного элемента. Если встречался отрицательный элемент в искомой нами области, то ничего не происходит, если же нет, то выводиться соответствующее сообщение и выводиться максимальный элемент.
if (z==0){
printf("Отрицательный элемент отсутствовал!!!\n");
printf("Максимальный элемент является a[%d]=%d\n",maxi,maxx);}}
Конец
Задача № 2
Найти в матрице первый столбец, все элементы которого упорядочены по убыванию. Заменить значения отрицательных элементов этого столбца на их модулями.
Решение задачи на языке программирования C:
#include <stdio.h>
#include <stdlib.h>
main(){
int z,i,j,a[4][10],k;z=0;
for (i=0;i<4;i++){
for (j=0;j<10;j++){
a[i][j]=(rand() % 58+1)-50;printf("a[%d][%d]=%d ",i,j,a[i][j]);}
printf("\n");}printf("\n");printf("Ответ:\n");k=0;
for (j=0;j<10;j++){
for (i=1;i<4;i++){
if (a[i][j]<a[i-1][j]){
z=z+1;
if (z==3){
printf("Столбец %d\n",j);k++;
for (i=0;i<4;i++){
if (a[i][j]<0){
a[i][j]=abs(a[i][j]);}}}}}z=0;}
if (k==0){
printf("Нет таких столбцов!!\n");}
for (i=0;i<4;i++){
for (j=0;j<10;j++){
printf("a[%d][%d]=%d ",i,j,a[i][j]);}
printf("\n");} printf("\n");}
Блок-схема решения задачи:
Выполнение программы:
Начало
Инициализация переменных
int z,i,j,a[4][10],k;z=0;
Заполнение двухмерного массива случайным набором чисел от -50 до 8. Вывод полученного массива на экран. Вывод сообщения "Ответ:".
for (i=0;i<4;i++){
for (j=0;j<10;j++){
a[i][j]=(rand() % 58+1)-50;printf("a[%d][%d]=%d ",i,j,a[i][j]);}
printf("\n");}printf("\n");printf("Ответ:\n");
Поиск столбцов с упорядоченными элементами по убыванию. Проверяем является ли текущий элемент меньше прошлого. Если да, то z=z+1 для того чтобы проверить. Все ли следующие элементы были меньше предыдущих.
k=0;
for (j=0;j<10;j++){
for (i=1;i<4;i++){
if (a[i][j]<a[i-1][j]){
z=z+1;
Все ли следующие элементы были меньше предыдущих. Если да, то выводим наш столбец. Если нет,
if (z==3){
printf("Столбец %d\n",j);k++;
Заменяем элементы на положительные с помощью цикла, если элементы отрицательный.
for (i=0;i<4;i++){
if (a[i][j]<0){
a[i][j]=abs(a[i][j]);}}}}}
Проверяем был ли хоть один такой столбец. Если да, то выводим сообщение.
if (k==0){
printf("Нет таких столбцов!!\n");}
Выводим массив с положительными элементами в искомых столбцах, если такие были.
for (i=0;i<4;i++){
for (j=0;j<10;j++){
printf("a[%d][%d]=%d ",i,j,a[i][j]);}
printf("\n");} printf("\n");}
Конец.
Список используемых источников
1 Мытник Н.П. «Основы конструирования программ» / Мытник Н.П. Минск: БГУИР, 2010.
2 Крупник А. Б. «Изучаем Cи» / Крупник А. Б. Минск, 2001 — 233 с.