Информатика (группы АВТ-х12, АВТ-х13, АВТ-х14) — Методические указания по выполнению всех видов работ

Оглавление / Contents

Тема №1 Операторы описания. Условный оператор. Тернарная операция.
Тема №2 (Лабораторная работа) Операторы цикла. Операторы передачи управления.
Тема №3 Оператор переключатель. Перечислимые типы.
Тема №4 Массивы целых чисел.
Тема №5 Многомерные массивы - матрицы.
Тема №6 (Лабораторная работа) Символьные массивы - строки.
Тема №7 Указатели
Тема №8 (Лабораторная работа) Массивы указателей
Тема №9 (Лабораторная работа) Рекурсивные алгоритмы

Ознакомиться с заданием (частная задача).
Дать формулировку полной (общей) задачи. Определить основные абстрактные операции, присущие задаче.
Сформировать тестовые данные (ТД).
Проверить соответствие ТД предъявляемым требованиям (см. УП «Разработка программного продукта» стр. 23). Исправить ТД при необходимости!
Построить блок-схему(ы) алгоритма (ов).
Проверить соответствие блок-схем (ы) предъявляемым требованиям (см. чек-лист №1 в ЭУМК «Информатика» раздел «Требования к учебному программному продукту»). Исправить при необходимости!
Проверить правильность алгоритма по всем наборам ТД. Исправить при необходимости!
Закодировать алгоритм(ы) и оформить интерфейс пользователя (ИП).
Проверить соответствие кода предъявляемым требованиям (см. чек-лист №2 в ЭУМК «Информатика» раздел «Требования к учебному программному продукту»). Исправить при необходимости!
Проверить соответствие ИП предъявляемым требованиям (см. чек-лист №3 в ЭУМК «Информатика» раздел «Требования к учебному программному продукту»). Исправить при необходимости!
Оформить отчетную документацию.
Проверить правильность оформления отчета.
Отправить отчет на проверку.

Облачная платформа НГТУ

https://cloud.nstu.ru/wiki/%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B5%D1%80%D0%B2%D0%B5%D1%80%D0%B0

Цели работы.

Знать:

основные типы данных языка С/С++;
основные операции языка - арифметические, логические, отношения, тернарная операция;
приоритеты выполнения операций;
операторы описания, выбора if, if / else.

Уметь:

использовать простые операторы передачи управления;
использовать операторы ввода-вывода;
создавать программы, содержащие вызов функции.

Варианты заданий.

Выполните задание, используя:

а) условный оператор;

б) замените условный оператор на тернарную операцию (где это возможно).

Значения переменных a, b и c поменять местами так, чтобы оказалось a ≥ b ≥ c.
В декартовой системе координат задана окружность радиуса R₁ с центром в начале координат и две точки A(A_x, A_y) и B(B_x, B_y). Определить, лежат ли точки А и B внутри окружности, лежат на ней, находятся вне её.
Даны три различных числа. Найти два таких числа, чтобы модуль разности между ними был максимален.
Определить, что из трёх целых чисел a, b и c только два равны между собой.
Даны три различных числа. Вывести их в порядке возрастания.
Известно, что из четырех чисел а₁, а₂, а₃, а₄ одно отлично от трех других, равных между собой; определить номер этого числа.
Определить номер четверти плоскости, в которой находится точка с координатами х и у (х*у ≠ 0).
Даны произвольные числа a, b и c. Если нельзя построить треугольник с такими длинами сторон, то напечатать 0, иначе напечатать 3, 2 или 1 в зависимости от того, равносторонний это треугольник, равнобедренный или какой-либо иной.
Даны три различных числа. Вывести их в порядке убывания.
Даны три различных числа. Найти два таких числа, чтобы модуль разности между ними был минимален.

Примеры программ.

Пример 1. Напишите программу, которая вводит натуральное число и определяет, чётное оно или нечётное.

Файлы включения: stdio.h

// проверка чётности натурального числа

int Chetnoe_1 (int number)

{

if ((number % 2) == 0)

{

printf("Число чётное");

return 1;

}

else

{

printf("Число нечётное");

return 0;

}

void Chetnoe_2 (int number)
{
((number%2)==0) ? printf("Число чётное") : printf("Число нечётное"); // использование тернарной операции
}

int main()
{
int my_number; // оператор описания
printf("Проверка натурального числа на чётность. \nВведите число: ");
scanf("%d", &my_number);
Chetnoe_1 (my_number);
}

Пример 2. Определить, равна ли сумма первых двух цифр заданного четырехзначного числа сумме двух его последних цифр.

void Rav_Sum()
{
int number, l, r, t; // оператор описания

printf("Enter number (1000-9999): ");
scanf("%d", &number);

if ((number > 999) && (number / 1000)< 10 ) // условный оператор
{
t = number%100;
r = (t/10) + (t%10);
t = number/100;
l = (t/10) + (t%10);
(l== r) ? printf(" %d = %d", l, r) : printf(" %d != %d", l, r); // использование тернарной операции
}

else printf("Error number!");
}

int main()
{
printf("Proverka ravenstva summ.");
Rav_Sum();
getch();
}

Пример 3. Напишите программу, которая вводит два натуральных числа, сравнивает их и печатает большее число после слова «больше». Если числа равны, выводится сообщение «Эти числа равны».

void Ravny(int a, int b)
{
if(a==b) printf("Chisla ravny"); // условный оператор
else
{
printf("\n Bolshe ");
(a > b) ? printf ("%d", a) : printf ("%d", b); // использование тернарной операции
}
}

int main()
{
int a,b; // оператор описания
printf("Proverka ravenstva chisel. Enter numbers: ");
scanf("%d %d", &a,&b);
Ravny (a, b);
getch();
}

Теоретические положения.

Обратимся к оператору if, который фигурировал при рассмотрении первых примеров.

Оператор if имеет следующий основной формат:

if (значение) оператор1;

else оператор2;

где "значение" является любым выражением, которое приводится или может быть приведено к целочисленному значению.

Если "значение" отлично от нуля ("истина"), то выполняется "оператор1", в противном случае выполняется "оператор2".

Дадим пояснение относительно двух важных моментов по использованию оператора if-else. Во-первых, часть "else оператор2" является необязательной частью оператора if; другими словами, правомерно употребление следующей формы оператора if:

if (значение) оператор1;

В этой конструкции "оператор1" выполняется тогда и только тогда, когда "значение" отлично от нуля.

Если "значение" равно нулю, "оператор1" пропускается и программа продолжает выполняться дальше. Во-вторых, что делать, если вы хотите выполнить более одного оператора в зависимости от того ложно или истинно выражение, указанное в операторе if? Ответ: используйте составной оператор.

Составной оператор состоит из:

- левой или открывающей фигурной скобки ({)

- последовательности операторов, разделенных точкой с запятой (;)

- правой или закрывающей фигурной скобки (})

В приведенном ниже примере в предложении if используется один оператор

if (b == 0.0) printf("Отношение не определено \n");

а в предложении else - составной оператор

else { ratio = a / b; printf( "Значение отношения равно %f \n", ratio); }

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

Язык С / С++ имеет еще условную операцию (?:), которая близка к структуре управления if / else.

Это единственная трехчленная операция (тернарная), имеющая три операнда. Эти опранды вместе с условной операцией формируют условное выражение.

операнд_1 ? операнд_2 : операнд_3 ;

Первый операнд является условием, второй операнд содержит значение условного выражения в случае, если условие истинно, третий операнд равен значению условного выражения, если условие ложно.

Вопросы и упражнения.

Какие три характеристики определяет тип переменной?
Оператор if позволяет программе принимать решения при выполнении определенного условия. Запишите примеры оператора в сокращенном и полном видах.
Если поставить точку с запятой после правой круглой скобки оператора if, что будет происходить в программе?
Структура выбора if / else используется для выполнения одного действия, если условие истинно, и другого, если условие ложно.Если возможных состояний больше чем два, как быть? Запишите примеры.
В чем отличие между описанием и объявлением переменной?
Приведите примеры инициализации переменных в операторах описания (в качестве инициализирующих выражений используйте: константу, переменную, арифметическое выражение).
Запишите формулу для вычисления максимально допустимого значения целой переменной в зависимости от типа данных.
Условный оператор: if ( a > b) ? max = a; else max - b; запишите в виде тернарной операции.
Напишите примеры условных операторов, которые не будут выполняться никогда.
Перечислите арифметические операции одного уровня приоритета.
Запишите пример арифметического выражения, в котором круглые скобки меняют последовательность выполнения одноприоритетных операций.
Определите сумму кодов символов, образующих слова: "HELLO", "today", "Good-bye".
Приведите пример использования составного оператора при истинности условия оператора if, if / else.
Запишите в виде мантиссы и порядка (внутренне представление) значения вещественных переменных: float x = 352.78901; double y = - 42913.175;.
В каких случаях при вводе значения переменной необходимо проверять её равенство нулю?
Как правильно проверить равенство двух вещественных переменных а и с, напишите пример оператора.
Для каких переменных следует одновременно с их объявлением задать нулевые начальные значения, запишаите примеры.
Приведите примеры унарных операций с постфиксной и префиксной формой записи.
Объясните, почему в условных операторах, содержащих комбинированные условия: при использовании операции (&&) самым левым должно быть простое условие, которое наиболее вероятно окажется ложным, а при использовании операции (||) самым левым должно быть простое условие, которое наиболее вероятно окажется истинным. Запишите примеры.
На какие три логически завершеных этапа можно разделить процесс решения задачи? Приведите примеры.
Какое представление алгоритма (блок-схема или псевдокод) наиболее близко к программной реализации? Объясните почему.

Цели работы.

Знать:

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

Уметь:

строить алгоритмы по принципу нисходящего проектирования с пошаговой детализацией;
использовать структуры повторений while, do / while, for;
использовать операторы передачи управления break, continue, return;
использовать библиотечные функции;
создавать новые функции.

Варианты заданий.

Задание №1. При решении задачи использовать три типа циклов (три реализации функции).

Написать функцию, которая считывает целое k, за которым следует k целых чисел. Функция должна считывать только по одному значению в операторе ввода.

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

Задание №2.

Написать функцию, которая выводит все цифры последовательности до k – ой. Использовать функцию, определяющую количество цифр в числе Count_Pos (number) (см пример дальше по тексту).

Последовательность 123456789101112131415…, в которой выписаны подряд все натуральные числа.
Последовательность 14916253649…, в которой выписаны подряд квадраты всех натуральных чисел.
Последовательность 18645124096…, в которой выписаны подряд все степени 8.
Последовательность 11235813213455…, в которой выписаны подряд все числа Фибоначчи.
Последовательность 10111213…9899, в которой выписаны подряд все двузначные числа. Значение k задается от 1 до 180.
Последовательность 110100100010000…, в которой выписаны подряд все степени 10.
Последовательность 1001111112211331…98899999, в которой выписаны подряд все двузначные числа и числа наоборот. Значение k задается от 1 до 360.
Последовательность 1248163264128256…, в которой выписаны подряд все степени 2.
Последовательность 182764125216343…, в которой выписаны подряд кубы всех натуральных чисел.
Последовательность 116256409665536…, в которой выписаны подряд все степени 16.

Примеры программ.

Пример 1. Напишите программу, которая вычисляет квадрат и куб для чисел от 1 до n, и, используя табуляцию, выводит таблицу (число квадрат куб).

Файлы включения: stdio.h, conio.h

void Kvadrat_Kub (int n)
{
int i;
printf("chislo Kvadrat Kub ");
for ( i = 1; i <= n; i++) // цикл с параметром
printf("\n %2d \t %3d \t %4d", i, i * i, i * i * i);

}

int main()
{
int n;
printf("Vichislenie kvadrata, kuba chisel ot 1 do n. Vvedi n:");
scanf("%d", &n);
Kvadrat_Kub (n);
getch();
}

Пример 2. Определить количество разрядов в числе.

Файлы включения: stdio.h, conio.h, math.h

int Count_Pos (int number)
{
int p = 1;
while ((number / (int) pow (10, p)) > 0) p++; // цикл с предусловием
return p;
}

int main()
{
int num;
printf ("Enter number: ");
scanf ("%d", &num);
printf ("kol-vo razraydov = %d", Count_Pos(num));
getch();
}

Пример 3. Напечатать каждую цифру в числе отдельно.

Файлы включения: stdio.h, conio.h, math.h

int Count_Pos(int number)
{
int p = 1;
while ((number / (int) pow (10, p)) > 0) p++; // цикл с предусловием
return p;
}
void Print_zifra (int num)
{
int k = Count_Pos(num) - 1, z;
for ( ; k >= 0; k--) // цикл с параметром
{
z = num / (long)pow(10, k);
printf("%d\t", z);
num = num % (long)pow(10, k);
}
}

int main()
{
int my_number;
int x, k = 9;
printf("Pecat po zifram. Enter number: ");
scanf("%d", &my_number);
printf("Result:\n");
Print_zifra (my_number);
getch();
}

Пример 4. Определить, сколько различных цифр входит в число (см пример блок-схемы).

Файлы включения: stdio.h, conio.h

int Count_Zifri (int n)
{
int a,b,i,j,l,k,p,m;
k = Count_Pos(n);
l = p = k;
for(i = 1; i <= p - 1; i++) // вложенность циклов
{
   a = n % 10;
   m = n / 10;
   l = l-1;
   for ( j = 1; j <= l; j++)
   {
    b = m % 10;
    m = m / 10;
    if (a == b)
    {
     k = k - 1;
     break;
    }
   }
   n = n / 10;
}
return k;
}

int main()
{
int my_number;
printf("\nKolichestvo razlichn zifr. Enter number: ");
scanf("%d",&my_number);
printf("\nRazlichn zifr: %d", Count_Zifri (my_number));
getch();
}

Теоретические положения.

Наряду с операторами (или группами операторов), которые могут выполняться в зависимости от каких-либо условий, существуют еще и операторы, которые могут выполняться несколько раз в одной и той же последовательности. Такой вид конструкции в программе известен как цикл.

Есть три основных типа циклов (хотя два из них можно рассматривать как разновидность одного).

Это цикл while ("пока"), цикл for ("для") и цикл do...while ("делать ... пока").

Цикл while

Цикл while является наиболее общим и может использоваться вместо двух других типов циклических конструкций. В принципе можно сказать, что по-настоящему для программирования необходим только цикл while, а другие типы циклических конструкций служат лишь для удобства написания программ.

int len;

len=0;

puts("Наберите предложение, затем нажмите <Ввод>");

while ( getchar() != '\n') len++;

printf("\nВаше предложение имеет длину %d символов\n",len);

Этот фрагмент программы позволяет ввести предложение с клавиатуры и подсчитать при этом, сколько раз вы нажали на клавиши клавиатуры до тех пор, пока не нажали на клавишу <Ввод> (соответствует специальному символу конца строки - '\n'). Затем программа сообщит вам, сколько символов (символ '\n' не подсчитывается) вы ввели.

Оператор while имеет следующий формат:

while (выражение)

оператор

где "выражение" принимает нулевое или отличное от нуля значение, а "оператор" может представлять собой как один оператор, так и составной оператор.

В процессе выполнения цикла while вычисляется значение "выражения". Если оно истинно, то "оператор", следующий за ключевым словом while, выполняется и "выражение" вычисляется снова. Если "выражение" ложно, то цикл while завершается и программа продолжает выполняться дальше.

Обратите внимание на другой пример цикла while.

char *msg = "Здравствуй, мир";

int index = 1;

while (index <= 10 )

{

printf("Время # %2d: %s\n", index, msg);

index ++;

}

После выполнения этой программы на экране будут отображены строки со следующей информацией:

Время # 1 : Здравствуй, мир

Время # 2 : Здравствуй, мир

Время # 3 : Здравствуй, мир

........................

Время # 9 : Здравствуй, мир

Время # 10 : Здравствуй, мир

Очевидно, что оператор printf() был выполнен ровно десять раз. При этом значение параметра цикла index изменилось от 1 до 10. Немного подумав, вы сможете переписать этот цикл несколько компактнее:

index = 0 ;

while (index ++ < 10 )

printf("Время #%2d: %s\n", index, msg);

Цикл for

Цикл for является одним из основных видов циклов, которые имеются во всех универсальных языках программирования, включая Си. Однако, версия цикла for, используемая в С/С++, как вы увидите, обладает большей мощностью и гибкостью.

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

char *msg = "Здравствуй, мир";

int index;

for (indx = 0; index < 10; index++ )

printf("Время #%2d: %s\n", index, msg);

Выполните эту программу, и вы убедитесь, что она делает те же действия, что и программа с циклом while, которую мы уже разобрали, и является точным эквивалентом первого ее варианта. Теперь приведем основной формат цикла for:

for (выр1; выр2; выр3) оператор

Так же, как и в цикле while, "оператор" в теле цикла for обычно является одним из операторов программы, но может использоваться и составной оператор, заключенный в фигурные скобки ({...}).

Заметим, что параметры цикла for, заключенные в скобки, должны разделяться точкой с запятой (позиционный параметр), которая делит в свою очередь пространство внутри скобок на три сектора. Каждый параметр, занимающий определенную позицию, означает следующее:

- выр1 - обычно задает начальное значение индексной переменной;

- выр2 - условие продолжения цикла;

- выр3 - обычно задает некоторую модификацию (приращение) индексной переменной за каждое выполнение цикла.

Основной вариант цикла for эквивалентен следующей конструкции, выраженной с помощью цикла while:

выр1;

while (выр2)

{

оператор; выр3;

}

Вы можете опускать одно, несколько или даже все выражения в операторе for, однако о необходимости наличия точек с запятой вы должны помнить всегда. Если вы опустите "выр2", то это будет равносильно тому, что значение выражения "выр2" всегда будет иметь значение 1 (истина) и цикл никогда не завершится (такие циклы известны еще как бесконечные).

Во многих случаях вам поможет использование оператора запятая (,), который позволяет вводить составные выражения в оператор цикла for. Вот, например, еще одна правильная модификация с использованием составного выражения в операторе for:

char *msg = "Здравствуй, мир";

int up, down ;

for (up = 1, down = 9; up <= 10; up++, down--)

printf("%s: %2d растет, %2d уменьшается \n", msg, up, down);

Заметьте, что и первое и последнее выражение в этом цикле for состоит из двух выражений, инициализирующих и модифицирующих переменные up и down. Вы можете сделать эти выражения сколь угодно сложными.

Цикл do...while

Последним видом цикла является цикл do...while.

float a, b, ratio;

do {

printf("\n Введите два числа: ");

scanf("%f %f", &a, &b);

if (b == 0.0) printf("\n Деление на ноль!");

else

{

ratio = a/b;

printf("\n Результат деления двух чисел: %f", ratio);

}

printf("\n Нажми 'q' для выхода или любую клавишу для продолжения");

} while ( getch() != 'q');

Эта программа вычисляет результат деления одного числа на другое. Затем просит вас нажать любую клавишу. Если вы нажмете клавишу 'q', то выражение в операторе цикла while в конце программы примет значение "ложь" и цикл (а значит и программа) завершится. Если вы введете какой-либо другой символ, отличный от 'q', то выражение будет иметь значение "истина" и цикл повторится.

Формат цикла do...while можно представить в виде:

do оператор while (выр);

Основное отличие между циклом while и циклом do...while в том, что операторы внутри do...while всегда выполняются хотя бы один раз (т.к. проверка условия выполнения цикла осуществляется после выполнения последовательности операторов, составляющих тело цикла). Это похоже на цикл repeat...until в Паскале с одним, однако, различием: цикл repeat выполняется до тех пор, пока его условие не станет истинным; а цикл do...while выполняется пока истина.

Принудительный выход из конструкций for, while, do while можно выполнить оператором break. После чего осуществляется переход к следующему оператору программы.

Оператор continue вызывает пропуск оставшейся части итерации во всех указанных циклах и осуществляет переход к началу следующей итерации не завершая цикла.

Вопросы и упражнения.

Каким образом можно реализовать бесконечные циклы? Напишите три варианта.
Напишите функцию вычисления факториала числа К используя три различных цикла.
Запишите цикл для ввода К значений переменной Х без использования дополнительной переменной-счетчика.
Напишите функцию вычисления Х в степени У (Х и У - натуральные числа) используя три различных цикла.
Запишите вычисление суммы из К первых нечетные натуральных чисел используя только заголовок цикла for (в теле цикла не должно быть операторов).
Запишите пример обоснованного использования оператора continue в структурах цикла for, while, do / while.
Запишите пример из двух вложенных циклов, в котором из каждого цикла необходимо выходить с помощью оператора break.
Напишите три функции, первая их которых возвращает в качестве своего значения константу целого типа, вторая - значение переменной целого типа, третья - целочисленное выражение.
Запишите пример цикла, в котором совместно используются операторы continue и break (приведите конкретный пример необходимости использования такой конструкции цикла).
Напишите логическую функцию, которая определяет, кратно ли число А числу В.
Перечислите какую информацию содержит заголовок функции.
Чем отличается определение функции от объявления функции?
Из чего состоит оператор вызова функции?
Запишите пример, когда необходимо явное преобразование типа значения, возвращаемого функцией.
Назовите три вида параметров, которые могут передаваться в функцию.
Какая последовательность дейсвий осуществляется при передаче управления в функцию?
Каким требованиям должны соответствовать списки формальных и фактических параметров функции?
Могут ли переменные, используемым в разных функциях, иметь одинаковые идентификаторы?
Когда и зачем используется директива препроцессора #include?
Существуют два вида блоков в программе на языке С / С++: определение функции и составной оператор. Перечислите особенности первого и второго, запишите примеры.

Цели работы.

Знать:

основные проблемы технологии принятия решений;

необходимость и возможность использования оператора множественного выбора;

потребность в создании перечислимых типов данных.

Уметь:

создавать алгоритмы по методологии нисходящей разработки с пошаговой детализацией;

использовать структуру выбора switch для выбора альтернативного варианта действий;

создавать перечислимые типы и использовать переменные этих типов.

Варианты заданий.

enum month {January, February, March, April, May, June, July, August, September, October, November, December};

1. По дате (день:месяц:год) определить и вывести дату следующего дня (учитывать вариант високосного года).

2. По дате (день:месяц:год) определить и вывести дату предыдущего дня (учитывать вариант високосного года).

3. Определить логическую функцию, которая возвращает значение 1 – если дата (день1:месяц1:год1) предшествует дате (день2:месяц2:год2), 0 – в противном случае.

4. По дате (день:месяц) определить порядковый номер дня текущего года.

enum week { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };

5. Считая, что год не високосный и его 1 января приходится на день недели wd1, определить wd – день недели, на который приходится день с датой (день:месяц).

enum year1 {odin, dva, try, chetyre, payt', shest', sem', vоsem', devayt'};

enum year2 {desayt', odinadzat', dvenadzat', trinadzat', chetyrnadzat', paytnadzat', shestnadzat', semnadzat', vosemnadzat', devaytnadzat'};

enum year3 {dvadzat', tridzat', sorok, payt'desat, shest'desat, sem'desa, vosem'desat, devaynocto};

6. Для целого числа k от 1 до 99 напечатать фразу «мне k лет», учитывая при этом, что при некоторых значениях k слово «лет» надо заменить на слово «год» или «года» (количество записать словами, например, «мне сорок два года» ).

7. Для натурального числа k от 1 до 99 напечатать фразу «мы нашли k грибов», согласовав окончание слова «гриб» с числом k (количество записать словами, например, «мы нашли четырнадцать грибов» )..

enum rimsk { I, V, X, L, C, D, M };

8. Напечатать значение переменной k римскими цифрами.

enum kurs { sever, vostok, ug, zapad };

enum prikaz { vpered, vpravo, nazad, vlevo };

9. Корабль сначала шел по курсу k1, а затем его курс был изменен согласно приказу pk. Определить k2 – новый курс корабля.

enum color { зеленый, красный, желтый, белый, черный};

enum year {крыса, корова, тигр, заяц, дракон, змея, лошадь, овца, обезьяна, петух, собака, свинья};

10. В старояпонском календаре был принят 60-летний цикл, состоявший из пяти 12-летних подциклов. 1984 год – год зеленой крысы – был началом очередного цикла. Написать программу, которая вводит год и печатает его название по старояпонскому календарю.

Примеры программ.

Пример 1. Написать программу, которая выполняет арифметические операции над двумя натуральными числами.

void Calculate (int a, int b)
{
char op;
while(1) // бесконечный цикл
{
printf("\n enter operation (+,-,*,/):");
op = getch();
switch(op) // оператор множественного выбора
{
case '+' : printf(" %d + %d = %d ", a, b, a + b); break;
case '-' : printf(" %d - %d = %d ", a, b, a - b); break;
case '*' : printf(" %d * %d = %d ", a, b, a * b); break;
case '/' : if (b != 0) printf(" %d / %d = %d ", a, b, a / b);
else printf("\n No operation /"); break;
default: return;
}
}
}
int main()
{
int x, y;
printf("\n Kalkulaytor. Enter numbers a b:");
scanf("%d %d", &x, &y);
Calculate (x, y);
getch();
}

Пример 2. Определить, на какую цифру заканчивается квадрат целого числа, если известна последняя цифра числа.

void Kvadrat ()
{
int number, n;
while(1)
{
printf("\n Enter number (END -1):");
scanf("%d", &number);
n = number % 10;

printf("Kvadrat chisla zakanchivaetcya ");
switch(n)
{
case 0: printf(" na 0"); break;
case 1: ; case 9: printf(" na 1"); break;
case 2: ; case 8: printf(" na 4"); break;
case 3: ; case 7: printf(" na 9"); break;
case 4: ; case 6: printf(" na 6"); break;
case 5: printf(" na 5"); break;
default:return;
}
}
}
int main()
{
printf("\n Kvadrat chisla.");
Kvadrat ();
}

Пример 3. Ввести номер дня недели, вывести день недели на английском языке и следующий за ним день.

enum week { Monday = 1, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };

void Print_week (week n) // функция печати дня недели

{

switch(n)
{
case 1: printf(" Monday."); return;
case 2: printf(" Tuesday."); return;
case 3: printf(" Wednesday."); return;
case 4: printf(" Thursday."); return;
case 5: printf(" Friday."); return;
case 6: printf(" Saturday."); return;
case 7: printf(" Sunday."); return;
default:printf(" ERROR!.");return;
}
}

void Date () // функция выводит день недели на английском языке и следующий за ним день
{
week n, n_week; // переменные перечислимого типа
while(1)
{
printf("\n Vvedi nomer dnay nedeli (1-7):");
scanf("%d", &n);
if ((n > 7) || (n < 1))
{
printf(" ERROR!."); return;
}

// вывод названия дня недели
printf("Today");
Print_week (n);

// определение следующего дня недели

if (n == 7) n_week = Monday;
else n_week = (week)((int)n + 1);

// вывод названия следующего дня недели
printf("Tomorrow");
Print_week (n_week);
}
}

int main()
{
printf("\n Week.");
Date ();
}

Пример 4. Напишите программу, которая считывает две даты: (число1, месяц1) , (число2, месяц2) и вычисляет количество дней, прошедших между ними.

enum month {January = 1 , February, March, April, May, June, July, August, September, October, November, December};
// 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
month Get_m (int number) // функция определения месяца
{
switch (number)
{
case 1: printf(" January "); return January;
case 2: printf(" February "); return February;
case 3: printf(" March "); return March;
case 4: printf(" April "); return April;
case 5: printf(" May "); return May;
case 6: printf(" June "); return June;
case 7: printf(" July "); return July;
case 8: printf(" August "); return August;
case 9: printf(" September "); return September;
case 10: printf(" October "); return October;
case 11: printf(" November "); return November;
case 12: printf(" December "); return December;
}
}
int Raznost (int d1, int m1, int d2, int m2) // функция нахождения разности дат
{
int month_1, month_2;
int raz = 0;

printf (" S %d ", d1);
month_1 = Get_m (m1);
printf (" po %d ", d2);
month_2 = Get_m (m2);
if (month_1 == month_2) return d2 - d1; // если даты находятся в одном месяце

switch (month_1) // количество дней от первой даты до конца первого месяца
{
case 1: ; case 3: ; case 5: ; case 7: ; case 8: ; case 10: ;
case 12: raz = raz + (31 - d1); break;
case 4: ; case 6: ; case 9: ;
case 11:raz = raz + (30 - d1); break;
case 2: raz = raz + (28 - d1);
}
month_1 = month_1 + 1;
while (month_1 < month_2) // количество дней в месяцах между первым и последним
{
switch (month_1)
{
case 1: ; case 3: ; case 5: ; case 7: ; case 8: ; case 10: ;
case 12: raz = raz + 31; break;
case 4: ; case 6: ; case 9: ;
case 11:raz = raz + 30; break;
case 2: raz = raz + 28;
}
month_1 = month_1 + 1;
}
raz =raz + d2; // количество дней в месяце со второй датой
return raz;
}
int main()
{
int my_day1, my_month1, my_day2, my_month2;

printf ("\n Raznost dat.");
while(1)
{
printf ("vvedi pervyi den mesayz:");
scanf ("%d %d", &my_day1, &my_month1);
printf ("vvedi vtoroi den mesayz:");
scanf ("%d %d", &my_day2, &my_month2);
if(my_month1 <= my_month2) break;
printf ("nevernui vvod!");
}

printf("kolichestvo dney = %d", Raznost(my_day1, my_month1, my_day2, my_month2));
}

Теоретические положения.

Конструкция switch - это удобная замена длинной if / else конструкции, которая сравнивает переменную с несколькими константными значениями, например int или char.

switch ( <переменная> )

{

case значение1: Выполнить если <переменная> == значение1 break;

case значение2: Выполнить если <переменная> == значение2 break;

...

default: выполнить, если ни один вариант не подошел break;

}

Переменная в скобках сравнивается со значениями, описанными после ключевого слова case.

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

break необходим для того, чтобы прервать выполнение switch.

Значения для сравнения, описанные после case, могут быть только константами.

Блок default — необязателен, но он полезен для обработки исключительных ситуации.

Иногда при написании программ могут понадобится переменные, которые могут принимать только строго определенные значения, которые известны заранее.

Очень удобно иметь сразу и набор доступных констант и тип переменной, который связан с этим набором:

enum color { зеленый, красный, желтый, белый, черный };

enum month {Jan uary = 1, February, March, April, May, June, July, August, September, October, November, December };

enum week { Monday = 1, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };

Более того, подобные переменные хорошо подходят для использования в операторе-переключателе switch, так как вы знаете все возможные значения заранее.

При работе с перечислениями важно помнить:

Для объявление перечисляемого типа используется ключевое слово enum.

Имя нового типа задаем сами.

Все возможные значения для данного типа перечислены в фигурных скобках.

После объявления перечисления необходима точка с запятой.

Значения констант в перечислении — это простой int, по умолчанию каждое следующее значение больше предыдущего на 1. Для первого — 0, для второго — 1 и т.д.

Вопросы и упражнения.

Запишите пример использования оператора - переключателя: для переменных х и у выбор функций (х в степени у, корень х из у, логарифм и т.д.).

Создайте перечисляемый тип, который включает в себя дисциплины ЕГЭ - упорядочите дисциплины по убывнию их важности с вашей точки зрения.

В каких случаях необходимо использовать метку default в операторе switch? Запишите примеры.

Запишите пример использования оператора - переключателя: определите, кратно ли число х двум, трем, пяти, семи и т.д. до числа/2, выводите все возможные делители числа (а не один из них).

Цели работы.

Знать:

массив как структуру данных:
как применять массивы для хранения, сортировки и поиска данных;
как объявлять массив, задавать начальные значения и ссылаться на отдельные элементы массива.

Уметь:

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

Варианты заданий.

Дан массив целых чисел. Найти сумму тех элементов массива, которые находятся между максимальным и минимальным числами. В сумму включить и оба этих числа.
Дан массив целых чисел. Вывести элементы массива, значениями которых являются степени числа 2 (например, 16, 4, 64, 8, 128).
Дан массив целых чисел. Вывести элементы массива, значениями которых являются полные квадраты (например, 9, 16, 64, 49, 121).
Дан массив целых чисел. Вывести элементы массива, значениями которых являются простые числа (например, 11, 7, 41, 89, 103).
Даны массивы целых чисел Х и А, вычислить S - сумму тех элементов массива X, индексы которых совпадают со значениями элементов массива A.
Написать программу нахождения наибольшего общего делителя для элементов массива целых чисел.
Преобразовать массив целых чисел Х по следующему правилу: элементы массива Х циклически сдвинуть на k позиций влево.
Дан массив целых чисел. Вывести те числа, которые больше своих «соседей», то есть предыдущего и последующего чисел.
Дан массив целых чисел. Вывести те из них, индексы которых являются числами Фибоначчи.
Дан массив вещественных чисел. Определить индекс того из них, которое наиболее близко к заданному целому числу.

Набор функций для работы с массивом целых чисел.

1. Ввод значений элементов массива.

#define N 25

void Enter_Array (int Array[], int &size)

{

while(1)

{

printf ("Введи размер массива (2 - %d): ", N);

scanf ("%d", &size);

if ((size >1) && (size <= N)) break;

else printf("Неверный ввод!\n");

}

printf ("Введи элементы массива: \n");

for (int i = 0; i < size; i ++) scanf ("%d", &Array [i]);

}

2. Вывод значений элементов массива.

void Output_Array (int Array[], int size)

{

printf ("\n Массив – результат: \n ");

for (int i = 0; i < size; i ++) printf ("%d ", Array [i]);

}

3.Определить среднее значение элементов массива.

float Medium (int Array[], int size)

{

for (int i = 0, Sum = 0; i < size; i++) Sum += Array[i];

return ((float) Sum / size);

}

4. Определить индексы минимального и максимального элементов массива.

void Mini_Max (int Array[], int size, int &min, int &max)

{

min = max = 0;

for (int i = 1; i < size; i++)

{

if (Array [i] < Array [min]) min = i;

if (Array [i] > Array [max]) max = i;

}

5. Удалить из массива нулевые элементы.

void Delete_Zeros (int Array[], int &size)

{

int i = 0, j;

while (i < size)

if (Array[i] == 0)

{ for (j = i; j < size - 1; j ++) Array [j] = Array [j + 1];

size --;

}

else i++;

}

6. Продублировать каждое вхождение заданного числа.

void Duplicate (int Array[], int &size, int Number)

{

int i = 0, j;

while (i < size)

if (Array[i] == Number)

{

if ((size + 1) > N) { puts ("Массив заполнен!"); return; }

size++;

for (j = size - 1; j > i; j --) Array[j] = Array[j - 1];

i += 2;

}

else i++;

}

7. Определить количество различных элементов в массиве

int Counter_Different (int Array[], int size)

{

int i=0, j, count = size;

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

for (j = i - 1; j >= 0; j --)

if (Array[i] == Array[j])

{ count --; break; }

return count;

}

8. Упорядочить элементы массива по возрастанию методом «пузырька».

void Sort_Bubble (int A[], int size)

{

int i, j, temp;

for (i = size - 1; i > 0; i --)

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

if (A[j] > A[j+1])

{ temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; }

}

9. Определить индекс элемента в упорядоченном массиве, значение которого совпадает с заданным числом (бинарный поиск).

int Binary_Search (int Array[], int size, int Key)

{

int i, left = 0, k, right = size - 1;

do { i = (left + right) / 2;

if (Key == Array[i]) return i;

if (Key > Array[i]) left = i + 1;

else right = i - 1;

} while (left <= right);

return - 1;

}

Теоретические положения.

Массив - поименованный набор элементов одного типа, располагающихся в последовательных ячейках памяти.

Элементы массива нумеруются от 0 до N - 1, где N – количество элементов.

#define N 20

. . .

int i, n, array [N];

float mas [] = {1.75, 0.27, 17.892, -0.379,123.56};

. . .

for (i = 0; i < N; i++) array [i] = i+1;

. . .

n = sizeof (mas) / sizeof (float);

for (i = 0; i < n; i++) mas [i] *= 10;

. . .

Каждый элемент имеет свой номер, доступ к нему осуществляется через имя массива и индекс.

Имя массива является константой и рассматривается как адрес первого элемента массива.

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

Начальный адрес массива array

Количество элементов массива N

Размер элемента sizeof (int)

Основные операции с массивами:

Индексирование – индексы выбираются из диапазона целых чисел от 0 до N – 1, которые определяют позицию элементов и обеспечивают прямой доступ к ним.

Адрес начала массива – имя массива является константой и рассматривается как адрес первого (с индексом 0) элемента массива.

Размер массива можно определить с помощью операции sizeof (имя_массива). Так как имя массива есть константный указатель на его начало, он «вспоминает» об объекте, который адресует и возвращает его размер.

Преимущества массивов:

Массивы позволяют объединять множества однотипных данных в осмысленные группы.

Имена массивов с индексами минимизируют потребность в слежении за многими элементами данных с разными именами.

Использование индексов обеспечивает непосредственный и автоматический доступ к любому элементу в массиве.

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

Вопросы и упражнения.

Какими двумя способами возможен доступ к элементу массива, запишите примеры.
Какие характеристики массива компилятор фиксирует в таблице - дескрипторе?
Как определить размер памяти, отводимой под массив?
Запишите последовательность действий для исключения из массива элемента с заданным значением.
Запишите последовательность операторов для добавления числа в необходимую позицию в массиве?
Какие две характеристики одинаковы для всех элементов массива?
Чем является индекс массива в языке С / С++? Почему не совпадает номер и индекс элемента массива?
Допустимо ли, чтобы в операторе описания (объявления) массива за именем следовали пустые квадратные скобки? Запишите примеры.
Каким образом в операторе описания (объявления) присвоить нулевые начальные значения всем элементам массива?
Будет ли ошибкой следующее объявление массива: int arr [5] = { 3, 5, 7, 12, 8, 9 }; ? Почему?
Почему следует избегать использования констант целого типа в операторе описания (объявления) массива ? Какой вариант предпочтительней?
Какие операции можно осуществлять над элементами массива целых чисел? Запишите примеры.
Как отследить выход за границы массива?
Какими тремя способами можно задать начальные значения элементам массива? Запишите примеры.
В каких случаях при описании массива квадратные скобки могут остаться пустыми? Запишите примеры.
Как описывается аргумент-массив? Запишите оба варианта.
Как запретить модификацию значений массива при передаче в функцию?
Какие преимущества дает передача массива в функцию по ссылке (указателю)?
Можно ли передать в функцию фрагмент массива? Запишите примеры.
Как передать массив в функцию по значению?

Цели работы.

Знать:

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

Уметь:

выбирать структуры для представления многомерных данных;
проектировать функции для работы с многомерными структурами данных;
передавать/возвращать отдельные элементы многомерных структур данных в/из функции.

Варианты заданий.

Дана матрица размером M*N. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент матрицы оказался в верхнем левом углу.
В матрице X размером M*N найти строку с минимальным по величине элементом. В этой строке найти максимальный по абсолютной величине элемент.
Дана матрица целых чисел. Упорядочить ее строки по возрастанию значений их наибольших элементов.
Дана матрица M на N. Переставляя её строки и столбцы, добиться того, чтобы наименьший элемент оказался в верхнем левом углу.
Определить k - количество "особых" элементов матрицы С, считая элемент "особым", если он больше суммы остальных элементов своего столбца. Вывести эти элементы.
В матрице размером M*N выбрать и вывести на экран строки, содержащие заданное значение К.
Преобразовать матрицу A размером M*M путём построчного вычитания элементов побочной диагонали.
Определить k - количество "особых" элементов матрицы С, считая элемент "особым", если в его строке слева от него находятся элементы, меньшие его, а справа - большие. Вывести эти элементы.
Определить значение и индексы наибольшего из отрицательных элементов матрицы X размером M*N.
Вычислить сумму положительных элементов матрицы А размером N*N, расположенных над главной диагональю.

Набор функций для работы с матрицей:

1. Ввод / вывод матрицы.

void Enter_ Matrix (int Array[][N], int &m, int &n)

{

int i, j;

printf ("\n Введи размерности матрицы:");

scanf ("%d %d", &m, &n);

printf (" Введи матрицу :\n");

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

for ( j = 0; j < n; j++) scanf ("%d", & Array [i][j]);

}

void Print_ Matrix (int Array [][N], int m, int n)

{

int i, j;

printf ("\n Матрица – результат :\n");

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

{ for( j=0; j < n; j++) printf ("%3d ", Array [i][j]);

printf("\n");

}

2. Поиск минимального и максимального элементов матрицы. Поменять их местами.

void Min_Max (int A [][N], int m, int n, int& Min, int& Max)

{

int i, j, s_min = 0, c_min = 0, s_max = 0, c_max = 0 ;

Min = Max = A [0][0];

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

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

{

if (A [i][j] < Min) {Min = A [i][j]; s_min = i; c_min = j;}

if (A [i][j] > Max) {Max = A [i][j]; s_max= i; c_max = j;}

}

A [s_min][c_min] = Max;

A [s_max][c_max] = Min;

}

3. Транспонирование матрицы.

void Reverse (int A [][N], int n)

{

int i, j, temp;

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

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

{ temp = A [i][j]; A [i][j] = A [j][i]; A [j][i] = temp; }

}

4. Сортировка строк матрицы по возрастанию их средних значений.

void Medium_Value (int A [][N], int m, int n)

{

int i, j, k, sum, tmp;

float Medium[N], temp;

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

{ sum = 0;

for(j = 0; j < n; j ++) sum += A [i][j];

Medium [i] = (float) sum / n;

}

for (i = 0; i < m - 1; i ++)

{ k = i;

for (j = i + 1; j < m; j++) if ((Medium[k] - Medium[j]) > 0) k = j;

temp = Medium[i]; Medium[i] = Medium[k]; Medium[k] = temp;

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

{ tmp = A [i][j]; A [i][j] = A [k][j]; A [k][j] = tmp; }

}

5. Удалить из матрицы строку и столбец со значением максимального элемента.

void Delete_Max ( int A [][N], int &m, int &n, int Smax, int Cmax)

{

int i, j;

if (Smax < m - 1)

for (i = Smax; i < m - 1; i++)

for (j = 0; j < n; j++) A [i][j] = A [i + 1][j];

m--;

if (Cmax < n - 1)

for (j = Cmax; j < n - 1; j++)

for (i = 0; i < m; i++) A [i][j] = A [i][j + 1];

n--;

}

Теоретические положения.

int matrix [N][M];

Одномерные массивы соответствуют векторам, двумерным массивам можно поставить в соответствие – матрицы.

Двумерные массивы – это вид удобной записи, так как память имеет одно измерение.

Наименьший адрес в памяти соответствует значению элемента первого столбца в первой строке matrix [0][0], наибольший адрес – значению элемента в последнем столбце последней строки матрицы matrix [N-1][M-1].

Доступ к элементам осуществляется по индексам строк и индексам столбцов.

Можем представить двумерный массив как одномерный, каждый элемент которого есть одномерный массив.

Двумерный массив может быть инициализирован присваиванием элементам по одной строке каждый раз:

int matrix [][4] = {{3,5,7}, {-2,-4,-6}, {1,7,13}};

При таком описании в памяти будет выделен блок для таблицы размером (3х4) х 2 байта, общим объемом – 24 байта. Последний элемент в каждой строке будет содержать нулевое значение.

Для доступа к элементу матрицы, компилятор расширяет таблицу – дескриптор массива, включая информацию о количестве столбцов и длине каждой строки:

Начальный адрес массива Matrix

Количество строк Row Count

Количество столбцов Column Count

Размер типа ST = sizeof (int)

Длина строки ST * Column Count

Вопросы и задания.

Запишите последовательность действий для исключения из многомерного массива элемента с заданным значением.
Запишите последовательность операторов для добавления элемента в необходимую позицию в многомерном массиве.
Каким образом двумерные (многомерные) массивы размещаются в памяти компьютера?
Как определить объем памяти, отводимой под многомерный массив?
Почему первый элемент в матрице имеет индексы 0, 0, а не 1,1? Дайте графическое представление матрицы в памяти.
Каким образом можно оперировать с двумерным массивом как с одномерным, используя одну пару квадратных скобок?
Сколько операций сравнения необходимо выполнить, чтобы найти индекс максимального элемента в массиве из N чисел?
Какими тремя способами можно получить из функции значение максимального элемента?
Если вычеркнуть из матрицы К строк, то сколько копий последней строки будет хранится в памяти?
Сколько операций присваивания нужно выполнить, чтобы поменять местами значения элементов первой и последней строки в матрице размером К*К.

Цели работы.

Знать:

представление переменных символьных типов в памяти компьютера;
основные правила работы с текстовой информацией.

Уметь:

объявлять символьные массивы;
использовать операторы ввода/вывода строк;
использовать библиотечные функции работы со строками;
передавать и возвращать строки в/из функции;
создавать свои функции работы со строками.

Варианты заданий.

Задание 1. Словом считать любую последовательность, содержащую только русские и латинские буквы. Разделители между словами и их количество может быть любым.

В каждом слове строки удалить все последующие вхождения первого символа этого слова.
В строке удалить все появления заданного символа, если он находится в начале слова.
В строке второе и последнее слово записать наоборот, за последним словом – точка.
В строке содержимое всех слов, длиннее К символов, заменить последовательностью из заданного символа, оставив без изменения только первое и последнее слова.
В строке выбрать слова, которые начинаются и заканчиваются одним и тем же символом.
В строке найти и подчеркнуть слово наибольшей длины, в котором нет заданной буквы.
Преобразовать исходную строку, приводя все слова к заданной длине следующим образом: если длина слова меньше заданной, дополнить его последней буквой, а если больше - обрезать.
В каждом слове строки удалить все предыдущие вхождения последнего символа этого слова.
В каждом слове строки все последующие вхождения первого символа этого слова написать заглавной буквой.
В строке каждое слово четной длины заключить в скобки заданного вида (), [], < >.

Задание 2. Создать строку (длина равна k), которая представляет собой заданную последовательность.

1. Последовательность 123456789101112131415…, в которой выписаны подряд все натуральные числа.

2. Последовательность 14916253649…, в которой выписаны подряд квадраты всех натуральных чисел.

3. Последовательность 18645124096…, в которой выписаны подряд все степени 8.

4. Последовательность 11235813213455…, в которой выписаны подряд все числа Фибоначчи.

5. Последовательность 10111213…9899, в которой выписаны подряд все двузначные числа. Значение k задается от 1 до 180.

6. Последовательность 110100100010000…, в которой выписаны подряд все степени 10.

7. Последовательность 1001111112211331…98899999, в которой выписаны подряд все двузначные числа и числа наоборот. Значение k задается от 1 до 360.

8. Последовательность 1248163264128256…, в которой выписаны подряд все степени 2.

9. Последовательность 182764125216343…, в которой выписаны подряд кубы всех натуральных чисел.

10. Последовательность 116256409665536…, в которой выписаны подряд все степени 16.

Набор функций для работы с символьным массивом:

1. Введенное натуральное число записать в виде строки.

void Long_to_String (long number, char string[])

{

int i = 0;

while(number != 0)

{

string [i] = '0' + (number % 10);

number /= 10;

i ++;

}

string [i] = '\0'

strrev (string);

}

2. Разбить дробную часть числа слева направо по три цифры.

char *Real_to_String (long double t)

{

char *string = new char[L], *p, temp[L];

long k = t;

int i = 0, Len, n;

Long_to_String (k, string); strcat (string, ".");

t = t – k;

do {

k = t * 10;

t *=10;

temp [i] = (k%10) + '0'

i++;

} while ((i < 10)&&((t-k)>0.000001));

temp[i] = '\0'

Len = strlen (temp);

n = Len / 3;

if ((Len % 3) == 0) n--;

for (i = 0, p = temp; i < n; i++, p += 3 )

{ strncat (string, p, 3); strcat (string, ",");}

strcat (string, p);

return string;

}

3. Исключить дублирование символов в строке.

void Delete_Double (char string[])

{

int i, j, k;

for (i = 0; string [i] != '\0' i++)

{

j = i+1;

while (string [j] != '\0')

if (string [i] == string [j])

{

for (k = j; string [k] != '\0' k++) string [k] = string [k+1];

string [k]='\0'

}

else j++;

}

4. Вывести количество вхождений каждого символа в строку.

void Statistic (char *Str)

{

int count = 0, i, j, key;

puts("\t Symbol \t Counter");

for (i = 0; Str[i] != '\0' i ++)

{

key = 0;

for (j = i - 1; j >= 0; j --)

if (Str[i] == Str[j]) { key = 1; break;}

if (key == 0)

{

for (j = i; Str[j] != '\0' j ++)

if (Str[i] == Str[j]) count ++;

printf ("\t %c \t %d \n", Str[i], count);

count = 0;

}

5. Заменить в строке все точки многоточием.

char* Three_Points (char *Str)

{

char Temp[N];

int i, j = 0, k;

for (i = 0; Str[i] != '\0' i ++)

if (Str[i] != '.') Temp [ j ++] = Str[i];

else for (k = 0; k < 3; k ++) Temp [ j++] = '.'

strcpy (Str, Temp);

return Str;

}

6. Удалить заданную подстроку из строки (без использования библиотечных функций).

char* Delete_Subset ( char* Str, char* Subset)

{

int i = 0, j, k, length = strlen (Subset);

while (Str [i] != '\0')

if (Str [i] == Subset [0])

{

k = i;

for (j = 1; j < length; j++) if ( Str [i + j] != Subset [j]) break;

if (j == length)

{

for (j = k; Str [ j + length] != '\0' j++)

Str [j] = Str [ j + length];

Str [j] = '\0'

}

else i ++;

}

else i ++;

return Str;

}

7. В строке поменять местами имена, используя библиотечные функции.

void Change_Names()

{

char Name[] = {"Ruslan Ludmila"}, Newname[L];

char *p;

puts ("Сначала:");

puts (Name);

p = strchr (Name,' '); // находим пробел

*p = '\0' // ставим «конец строки»

strcpy (Newname, p+1); // переписываем второе имя

strcat (Newname, " "); // добавляем пробел

strcat (Newname, Name); // переписываем первое имя

puts ("Результат:");

puts (Newname);

}

Библиотечные функции для работы с строкой:

ch = getch (); считывает один символ с клавиатуры без отображения на экране.

ch = getchar (); считывает символ из стандартного входного файла (stdin) с отображением его на экране.

putchar (ch); записывает символ в стандартный файл вывода (stdout).

isalnum (ch); возвращает ненулевое значение, если ch – код буквы или цифры.

isalpha (ch); возвращает ненулевое значение, если ch – код буквы.

isdigit (ch); возвращает ненулевое значение, если ch – код цифры (0…9).

tolower (ch); преобразует код буквы ch к нижнему регистру.

toupper (ch); преобразует код буквы ch к верхнему регистру.

gets (Str); считывает строку из стандартного входного файла (stdin).

puts (Str); записывает строку в стандартный файл вывода (stdout).

strcat (Str1, Str2); приписывает строку Str2 к строке Str1.

strchr (Str, ch); ищет в строке Str первое вхождение символа ch.

strcmp (Str1, Str2); сравнивает строки. Результат < 0, если Str1 < Str2; равен 0, если строки равны и > 0, если Str1 > Str2.

strcpy (Str1, Str2); копирует байты строки Str2 в строку Str1.

strdup (Str); выделяет память и копирует в неё строку Str.

strlen (Str); вычисляет длину строки.

strrev (Str); записывает строку наоборот.

strset (Str1, ch); заполняет строку Str заданным символом ch.

strstr (Str, SubStr); ищет в строке Str подстроку SubStr.

strlwr (Str); преобразует буквы верхнего регистра в строке в соответствующие буквы нижнего регистра.

strupr (Str); преобразует буквы нижнего регистра в строке в соответствующие буквы верхнего регистра.

strpbrk (Str, SubStr); ищет в строке Str первое появление любого символа из подстроки SubStr.

Теоретические положения.

Строкой называется последовательность символов, ограниченная символом с кодом 0, то есть '\0'.

Особенности: строка хранится в массиве символов, который может быть инициализирован при описании, а может быть заполнен программно:

char A[] = { 'С','т','р','о','к','а','\0' };

. . .

int i;

char B[N];

for (i=0; i

B [N] = '\0'

строка имеет переменную размерность, ограниченную символом '\0'. Работать с ней можно, просматривая от начала до конца, пока не встретится символ '\0':

for (i=0; B[i] !='\0' i++)...

соответствие размерности массива и длины строки транслятором не контролируется, за это несет ответственность программист, её написавший.

Способы определения строк:

- массив типа char char A[] = { 'С','т','р','о','к','а','1','\0' };

- массив типа char char B[] = “строка 2”;

- указатель на тип char char *C = “строка 3”;

- указатель на тип char char *D = { “строка 4” };

- указатель на тип char char *E ( “строка 5” );

- массив указателей на строки char *text[] = {“String 1”, “ String 2”};

Вопросы и упражнения.

В чем отличие символьных и литерных констант?
Что такое строка? Как производится инициализация переменных и строк?
Какими способами можно определять строки в программе?
Какой последовательностью операторов можно перевести число в строку и наоборот?
Существуют ли особенности работы с символьными массивами? Какие? Приведите примеры.
Перечислите три способа задания нулевых начальных значений элементам строки, запишите примеры.
При работе со строками может ли индекс быть выражением? Приведите примеры.
Назовите преимущества строки над символьным массивом.
Дайте два возможных варианта объявления аргумента-строки при передаче в функцию.
Напишите два способа определения длины строки.
Как передать в функцию и вернуть из функции один элемент массива? Приведите примеры.
Запишите прототипы основных функций работы со строками (библиотеки).

Цели работы.

Знать:

связь между указателями, массивами и строками;
как использовать указатели на функции.

Уметь:

объявлять и использовать указатели;
применять операции над указателями;
использовать указатели для передачи аргументов в функции;
создавать и возвращать указатель на массив/строку из функции.

Варианты заданий.

Выполнить задания, приведенные в темах "Массивы целых чисел" и "Символьные массивы" - работая только с указателями (исключаем индексацию).

Примеры программ.

Пример 1. Написать функцию, которая возвращает указатель на одну из пяти строк сообщения в зависимости от переданного ей значения. Используйте функции динамического распределения памяти для возврата строки в точности нужного размера.

char *Str(int n)
{
char *mess [ ] = {"Good morning!", "By-by!", "Happy New Year!", "How do your do?", "What is the matter?"};
return strdup ( mess [n] );
}
int main()
{
puts ("Result:");
for (int i = 0; i < 5; i++)
puts (Str ( rand () % 5)); // генерируем случайное число от 0 до 4
getch();
}

Пример 2. Написать функцию определения среднего значения положительных чисел, вводимых пользователем. Предоставить ему возможность вводить неограниченное количество чисел. Конец ввода – отрицательное число.

int* Middle(int &n)
{
int num, sum = 0 ;
int *p_int = new int;
n = 0;
while(1)
{
scanf("%d", &num);
if (num < 0)
     {
   printf("\n sred znach = %lf \n",(double)(sum * 1. / n));
      return p_int;
     }
p_int[n] = num;
sum = sum + num;
p_int = (int*)realloc(p_int, sizeof (int) * (n + 2)); // перераспределяем память под массив
n++;
}
}
int main()
{
int *mas, m;
puts("Enter numbers:");
mas = Middle(m);
puts("Vash massiv:");
for(int i = 0; i < m; i++) printf("%d\t", mas[i]);
}

Пример 3. Работа и с динамическим массивом.

#define N 20
// создаем динамический массив
int* Input (int &size)
{
int *arr;
while(1)
{
printf ("Enter size array(2 - %d): ", N);
scanf ("%d", &size);
if ((size >1) && (size <= N)) break;
else printf("NO!\n");
}
arr = new int[size]; // выделяем память под массив
printf ("Enter array: ");
for (int i = 0; i < size; i ++) scanf ("%d", arr+i);
return arr;
}
// вывод массива
void Output(int *Array, int size, char *s)
{
printf ("\n %s \n ", s);
for (int i = 0; i < size; i ++) printf ("%d ", *(Array + i));
printf ("\n");
}
// удаление из массива нулевых элементов
void Delete_Zeros (int *Array, int &size)
{
int i = 0, j;
while (i < size)
if (*(Array + i) == 0)
{
   for (j = i; j < size - 1; j ++) *(Array + j) = *(Array + j + 1);
   size --;
  }
else i++;
}

void Union (int *A, int al, int *B, int bl, int **C)
// С - это "указатель на указатель"
{
int i = 0, j;
*C = new int [al+bl]; // выделяем память под массив
// копируем значения из первого и второго массива в третий
for (j = 0; j < al; j ++, i++) *((*C) + i) = *(A + j);
for (j = 0; j < bl; j ++, i++) *((*C) + i) = *(B + j);
}

int main()
{
int arr[] = { -1,0,-4,5,0,33,7,0 };
int total, l, k = sizeof(arr) / sizeof (*arr); // определяем размер массива
int *ptr = Input (l);
int *rez;
// выводим "объединенный" массив
Union (arr, k, ptr, l, &rez);
Output (rez, l + k, "Union array :");
k = l + k;
Delete_Zeros(rez, k);
// выводим массив после удаления нолей
Output (rez, k, "After Delete_Zeros array :");
}

Теоретические положения.

Указатели - это переменные, которые содержат в качестве своих значений адреса других переменных.

Особенности указателей:

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

Основные операции с указателями:

Присваивание указателей.
Инициализация указателя.
Разыменование указателя (*).
Получение адреса указателя (&).
Инкремент, декремент.
Вычитание указателей.
Сложение (вычитание) указателя и целого числа.
Сравнение указателей: = =, !=, <, >, <=, >=.

Пример использования указателей.

Функция возвращает номер позиции первого вхождения подстроки в строку (-1, если подстроки нет).

int Find_Str (char* string, char* subset)

{

char *pnt = string; // инициализация, присваивание указателей

int j, k, Len = strlen (subset);

printf (" адрес указателя %p \n", &pnt); // взятие адреса указателя

printf (" значение указателя %p \n", pnt);

printf (" размер указателя %d \n", sizeof (pnt));

while (*pnt != '\0') // разыменование указателя

if (*pnt == subset[0])

{ for (j = 1; j < Len; j++)

if ((*(pnt + j)) != subset[j]) break; // сложение указателя

if (j == Len) return (pnt – string); // разность указателей

}

else pnt ++; // инкремент

return - 1;

}

Одно из отличительных свойств С ++ состоит в том, что имя массива генерирует указатель первого элемента массива. Более того, допускаются простые арифметические операции с указателями: если р является указателем на объект определенного типа, можно записать код, предполагающий последовательное расположение объектов данного типа в памяти. При этом для ссылки на первый объект используется запись *р, на второй - *(р+1), на третий - *(р+2) и т.д. Другими словами, записи *(а + i) и а [i] в языке С ++ эквивалентны. Это создаёт альтернативный механизм доступа к объектам массивов, который иногда оказывается удобнее индексации. Он чаще всего используется для массивов символов (строк).

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

При использовании в программе массива его размер должен быть известен заранее. Для этого применяются два основных механизма С ++. Первый механизм обеспечивает передачу аргументов командной строки главным программам в массиве argv с размером argc. Массив argv является составным и включает объекты, которые сами представляют собой массивы (строки). Пользователь может ввести значение N – размер массива. Второй базовый механизм – оператор new[], выделяющий область памяти, необходимую для массива во время выполнения. В этом случае он возвращает указатель на массив:

int main( int argc, char *argv[])

{

int i, N = atoi (argv[1]);

int *a = new int[N]; …

Вопросы и упражнения.

Дайте определение и описание указателя.
Перечислите основные операции над указателями.
Какова связь между массивами и указателями?
Опишите указатель на массив из 10 целых чисел и массив указателей на 20 переменных вещественного типа.
Какими способами возможен доступ к i-му элементу массива? Запишите оба варианта доступа.
Перечислите способы иницализации указателей. Запишите примеры.
Запишите примеры, когда указатель типа void приводится к необходимому типу.
Запишите примеры вызова функции распределения динамической памяти для переменных целого, символьного и вещественного типа, для масивов из элементов целого, символьного и вещественного типа.
void Insert (int *arr, int &size); Почему формальный параметр arr, определенный как указатель на массив, может менять свое значение в теле функции?
Какие операции нельзя применять к константным указателям?

Цели работы.

Знать:

особенности массивов указателей;
как массивы указателей передаются в функции;
как создавать массив указателей на функции.

Уметь:

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

Варианты заданий.

Выполните Задание №1 из лабораторной работы "Символьные массивы - строки" для текста (для выполнения следует использовать пример №2, расположенный ниже) .

Примеры программ.

Пример 1. Написать функцию, которая использует генерацию случайных чисел для создания предложений. Программа должна использовать четыре массива указателей на символьный тип, называемые: Артикль (А), Существительное (С), Глагол (Г), Предлог(П). Предложения создаются, перебирая массивы в следующем порядке: А – П, А, П. Слова должны быть разделены пробелами, предложение должно начинаться с заглавной буквы и заканчиваться точкой.

char *Sentence(int n)
{
char *article []   = {"the ","a ","one ","some ","any "},
         *noun [ ]   = {"boy ","girl ","dog ","town ","car "},
        *verb [ ]    = {"drove ","jumped ","ran ","walked ","skipped "},
         *preposition [ ]={"to ","from ","over ","under ","on "};
char **Ptr[ ] =      {article, noun, verb, preposition}, *text;
int i, j, l;
while(n>0)
{
j = rand() % 5;
l = strlen(Ptr[0][j]);
text = (char*) malloc(l + 1);
strcpy(text,Ptr[0][j]);
for (i = 1; i < 4; i++)
{
j = rand() % 5;
l = l + strlen(Ptr[i][j]);
text = (char*)realloc(text,l + 1);
strcat (text, Ptr[i][j]);
}
for (i = 0; i < 2; i++)
{
j = rand() % 5;
l = l + strlen(Ptr[i][j]);

text = (char*)realloc(text, l + 1);
strcat (text, Ptr[i][j]);
}
text[0] = toupper(text[0]);
text[l-1] = '.'
puts(text);
free(text);
n--;
}
return text;
}
int main()
{
puts("Генерация предложений.\n Результат:");
Sentence(23);
getch();
}

Пример 2. Определить, сколько слов в каждой строке текста.

Файлы включения , , ,

#define _CRT_SECURE_NO_WARNINGS
#define N 100 
#define L 15
// Функция ввода текста создает массив указателей на строки
char** Enter_Text()
{
   char temp[N];
   char** p = (char**) new char*;
   int n = 0; // счетчик количества строк
   while (1)
   {
       gets_s(temp);
       if (temp[0] == '\0') break;   // строка не введена
       p[n] = (char*)malloc(strlen(temp) + 1); // выделили память
       strcpy(p[n], temp);
       n++;
       p = (char**)realloc(p, sizeof(char*) * (n + 1));
   }
   p[n] = NULL;
   return p;
}
/* Функция проверяет, является ли символ элементом слова */
int Letter(unsigned char ch)
{
   if (isalnum(ch) == 1 || isalnum(ch) == 2) return 1;
   if (ch >= 192 && ch <= 255) return 1;
   return 0;
}

// Функция разбивает строку на слова
int Words(char* String, char w[][L])
{
   int i = 0, j, k = 0, key = 0, n = strlen(String);
   for (j = 0; j <= n; j++)
       if (Letter(String[j]))
       {
           w[k][i] = String[j];
           i++;
           key = 1;
       }
       else
           if (key)
           {
               w[k][i] = '\0';
               i = 0; 
               k++;
               key = 0;
           }
   return k;
}
/*Функция создания массива статистики */
int* Statistic(char** text)
{
   int i, * count;
   char _words[L][L];
   // Определение количества строк в тексте
   for (i = 0; text[i] != NULL; i++);
   // Выделение памяти для массива статистики
   count = new int[i + 1];
   // Подсчет количества слов в каждой строке
   for (i = 0; text[i] != NULL; i++)
   {
       count[i] = Words(text[i], _words); 
       for (int j = 0; j < count[i]; j++) puts(_words[j]);
   }
   count[i] = 0;
   return count;  // Вернуть указатель на массив статистики
}
// Вывод текста и массива статистики.
void Output_Text(char** text, int* stat)
{
   for (int i = 0; text[i] != NULL; i++)
   {
       printf("%s \t", text[i]);
       printf(" - %d slov\n", stat[i]);
   }
}
int main()
{
   SetConsoleCP(1251);
   SetConsoleOutputCP(1251);
   char** text;
   int* stat;
   puts("Подсчет слов в каждой строке текста.\nВведите текст:");
   text = Enter_Text();
   stat = Statistic(text);
   puts("\nResult:");
   Output_Text(text, stat);
}

Теоретические положения.

Массив указателей позволяет объединить в общую структуру данных множество переменных одного типа.

В этом его сходство с обычным массивом.

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

При использовании массива указателей последовательность элементов определяется последовательностью указателей в массиве.

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

Преимущества проявляются, когда сами элементы являются достаточно большими.

Массив строк («Страница»)

Массивы могут содержать указатели. Типичным использованием такой структуры данных является формирование массива строк. Элемент такого массива – строка, но строка является, по существу, указателем на её первый символ. Таким образом, каждый элемент в массиве строк в действительности является указателем на первый символ строки.

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

Средства распределения динамической памяти позволяют увеличивать и/или уменьшать размер массива указателей до требуемого объема.

Сортировка текста осуществляется посредством операций над элементами массива указателей, сами строки в памяти не перемещаются.

Вопросы и упражнения.

Запишите два способа доступа к элементу массива указателей.
Какие преимущества и недостатки при использовании двумерного массива символов и одномерного массива указателей на строки?
Запишите примеры создания статического и динамического массива указателей на строки. В чем преимущества и недостатки каждого их массивов?
В каком случае операция sizeof(указатель) возвращает размер массива, а в каком - размер указателя? Запишите примеры.
Какие из операций над указателями могут применяться к элементам массива указателей? Запишите примеры.

Цель работы

Приобретение практических навыков разработки рекурсивных алгоритмов.

Содержание отчета

1. Задание

2. Тестовые данные

3. Словесное описание этапов решения задачи рекурсивным способом

4. Блок-схема алгоритма рекурсивной функции

5. Текст программы с комментариями

Варианты заданий:

Задание 1

Вводится строка. Проверить, удовлетворяет ли её структура следующему определению:

<текст> = <элемент> | <элемент> <текст>

<элемент> = а | b | ..| z | (<текст>) | [<текст>] | {<текст>}

Иными словами – «Проверить баланс скобок трёх видов в строке»

Задание 2.

Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Вывести самый короткий путь из L-го пункта в M-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i < j), указывающих, что i-й и j-й пункты соединены дорогой, признак конца этой последовательности – пара нулей.

Задание 3.

Информация о городах содержит название и координаты. Все города соединены дорогами. Вывести самый короткий путь, проходящий через все города с возвратом в исходный город.

Задание 4.

Массив из n различных элементов упорядочить по возрастанию следующим методом быстрой сортировки. Алгоритм сортировки: взять средний по индексу элемент массива и переставить элементы массива так, чтобы слева от выбранного элемента оказались только меньшие элементы, а справа – только большие (тем самым выбранный элемент окажется на своем окончательном месте), после чего рекурсивно применить этот же метод к левой и к правой частям массива (относительно среднего элемента).

Задание 5.

Написать функцию sort(x), упорядочивающую по не убыванию двоичные числа массива х методом поразрядной сортировки. Алгоритм сортировки: все числа упорядочить по цифре в самом старшем разряд, для этого массив просматривается от начала (ищется число с 1 в заданном разряде) и конца (ищется число с 0 в заданном разряде) к середине и выбирается пара чисел для обмена. В результате массив разбивается на две части с 0 и 1 в старших разрядах, к каждой из которых применяется сортировка по цифре в разряде правее (при равенстве этих цифр сохранять упорядоченность по цифре в "предыдущем" разряде); и так далее до самого младшего разряда. В основе алгоритма поразрядной сортировки лежит абстрактная операция извлечения цифры в заданном разряде.

Задание 6.

Дано n чисел. Упорядочить их по не убыванию методом фон Неймана: вначале упорядочить пары соседних чисел (А₁ и А₂, А₃ и А₄ и т.д.); взять по две соседние упорядоченные пары и слить их в упорядоченные четверки; затем каждые две соседние четверки слить в упорядоченные восьмерки и т.д.

Задание 7.

Дан массив строк. Каждая строка – это слово. Необходимо построить линейный кроссворд (последняя буква предыдущего слова является первой буквой следующего) из максимального количества заданных слов.

Задание 8.

Комбинационный замок, состоит из N переключателей, каждый из которых может быть в положении «1» или «0». Выведите все возможные комбинации для замка, в которых половина переключателей должна находиться в положении «1».

Задание 9.

Дано n различных символов. Напечатать все возможные перестановки этих символов.

Задание 10.

Информация о городах содержит название и координаты. Все города соединены дорогами. Вывести самый короткий путь, проходящий через все города с запада на восток.

Теоретические положения

Рекурсия является важным инструментом решения вычислительных и математических задач. Она широко используется для определения синтаксиса языков программирования, а также в структурах данных при разработке алгоритмов сортировки и поиска для списков и деревьев. В математике рекурсию применяют в комбинаторике для разного рода подсчетов и вычисления вероятностей. Рекурсия действует по принципу “разделяй и властвуй”. Алгоритм определен рекурсивно, если это определение состоит из:

Одного или нескольких условий останова, которые могут быть вычислены для определенных параметров.

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

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

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

Любые задачи, которые можно решить рекурсивно, могут быть решены также и итеративно. Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и её результаты, то есть более нагляден и легче отлаживается. Другая причина – итеративное решение может не быть очевидным. В то же время, повторный запуск рекурсивного механизма вызовов функций приводит к росту расходов: к нарастающим затратам процессорного времени или требуемого объема памяти.

Многие задачи имеют простую и удобную формулировку, которая непосредственно переводится в рекурсивный код.

Примеры программных реализаций

Пример 1. Палиндромы – это числа, которые читаются одинаково слева направо и справа налево. Если исходное число не является палиндромом, то реверсируйте его цифры и сложите исходное число с числом, полученным в результате реверсирования. Если сумма не палиндром, то повторите те же действия и выполняйте до тех пор, пока не получите палиндром.

int revers ( int m )

{

int rev = 0;

while ( m > 0 )

{ rev = rev * 10 + m % 10; m = m / 10;}

return rev;

}

int palind(int n, int counter)

{

int a = revers(n);

if ( counter == 10)return 0;

if ( a == n ) return n;

palind(n + a ,counter + 1 );

}

int main ()

{

int number, rez;

printf ("Enter number: ");

scanf("%d", &number);

if ( rez = palind(number,0)) printf("Palindrom is %d", rez);

else puts ("No palindrom !");

}

Пример 2. Найти корень алгебраического уравнения методом деления отрезка пополам. Пусть x = ( a + b ) / 2 есть средняя точка в интервале [ a , b ]. Если f ( x ) = 0, то х – это корень. Если нет, то либо f ( a ) и f ( x ) имеют разные знаки ( f ( a ) * f ( x ) < 0 ) и корень лежит в интервале [ a , х ] , либо ( f ( х ) * f ( b ) < 0 ) и корень лежит в интервале [ x , b ]. Теперь выполняем эти же действия для нового интервала – половины исходного интервала. Процесс продолжается до тех пор, пока интервал не станет достаточно маленьким или пока не будет найдено точное значение корня.

float root (float a, float b, float eps)

{

float x = (a + b) / 2;

float Yx = (4 + x*x)*(exp(x)- exp(-x)) - 18;

if( Yx < eps ) return x;

float Ya = (4 + a*a)*(exp(a)- exp(-a)) - 18;

if( (Ya * Yx) < 0) root (a, x, eps );

else root (a, x, eps );

}

int main()

{

float x1, x2;

printf("\n Enter [x1;x2] :");

scanf ("%f %f", &x1, &x2);

printf("root = %f", root(x1,x2,0.00001));

}

Пример 3. Вводится с клавиатуры записанная без ошибок формула следующего вида:

< формула > = < цифра > | ( < формула > < знак > < формула >)

< знак > = + | - | * | /

< цифра > = 0 | 1 | 2| . . . | 9.

Вычислить эту формулу. Например: (( 5-3) * 4) = 8.

int Formula ()

{

int f, x, y;

char c, op;

c = getchar();

if(( c >= '0') && (c <= '9')) return ( c - '0');

else

{

x = Formula (); op = getchar(); y = Formula ();

switch (op)

{

case '+' : f = x + y; break;

case '-' : f = x - y; break;

case '*' : f = x * y; break;

case '/' : f = x / y; break;

}

getchar();

return f;

}

int main()

{

printf("\n Enter formulu:\n");

printf(" = %d", Formula ());

}

Контрольные вопросы

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

Информатика (группы АВТ-х12, АВТ-х13, АВТ-х14) — Методические указания по выполнению всех видов работ

Empty the recycle bin?

Оглавление / Contents

Пример 2. Определить, сколько слов в каждой строке текста.