9: Разложение на множители

Дано натуральное число n>1. Выведите все простые множители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность O(logn).

Ввод	Вывод
18	2 3 3

10: Палиндром

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

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

Ввод	Вывод
radar	YES
yes	NO

11: Вывести нечетные числа последовательности

Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.

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

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

1. Какое определение называется рекурсивным? Приведите собственные примеры рекурсивных определений.

2. Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? 3. Приведите собственные примеры содержательных задач, где для решения может быть использован рекурсивный вспомогательный алгоритм.

4. Что такое граничное условие, и каково его назначение в рекурсивной подпрограмме?

5. Что такое рекурсивный спуск?

6. Что такое рекурсивный подъём?

7. Что такое глубина рекурсии? Чему равна глубина рекурсии в приведённых выше примерах?

8. На каком этапе выполнения рекурсивной подпрограммы могут выполняться её операторы?

Лабораторная работа № 26-27 «Обработка структурных данных»

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

Образовательные результаты, заявленные во фгос третьего поколения:

Студент должен

уметь:

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

- оформлять документацию на программные средства;

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

знать:

- основные этапы разработки программного обеспечения;

- основные принципы технологии структурного и объектно-ориентированного программирования;

- методы и средства разработки технической документации.

Краткие теоретические и учебно-методические материалы по теме лабораторной работы

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

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

В языке Си структура определяется следующим образом:

struct [имя_структуры]

{

тип_1 элемент_1;

тип_1 элемент_1;

…

тип_N элемент_N;

}

[список описателей];

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

struct

{

char surname[15];

char name[15];

int course;

double mate;

};

stud1, *ps;

Если список отсутствует, описание структуры определяет новый тип, имя которого можно использовать в дальнейшем наряду со стандартными типами, например:

struct STUDENT /* описание нового типа*/

{

char surname[15];

char name[15];

int course;

double mate;

}

Определим переменную типа STUDENT и указатель на этот тип:

struct STUDENT stud1, *ps.

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

STUDENT stud2={“Иванов”, ”Иван”, 3, 4.2};

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

Доступ к полям структуры выполняется с помощью операции выбора . (точка) при обращении к полю через имя структуры и → при обращении через указатель, например:

struct STUDENT stud1, *ps;

…

stud1.mate =3.4;

cin>>stud1.surname;

*ps→ course=1;

cout<<stud1.surname;

Если элементом структуры является другая структура, то доступ к ее элементам выполняется через две операции выбора:

struct A {int a; double x;};

struct B {struct A b; double x;} s, x;

s.b.a=1;

s.b.x=0.5;

s.x=0.125;

x.b.a=2;

x.b.x=-0.5;

x.x=2.5;

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

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

а) Можно присваивать одну структуру другой, если они имеют одинаковый тип (шаблон). При этом происходит поэлементное копирование.

struct STUDENT stud1, stud2, *ps;

…

stud1=stud2;

(*ps)=stud1;

б) Функция может в качестве значения возвращать структуру:

struct complex {float real, im;};

struct complex make (float x, float y)

{

struct complex z;

z.real = x;

z.im y;

return z;

}

в) Можно получать адрес структуры с помощью операции взятия адреса.

student stud1, *ps;

struct ps=& stud1;

г) Можно передавать структуры в качестве аргумента функции:

struct complex add1 (struct complex a, struct complex b)

{

struct complex c;

c.real = a.real + b.real;

c.im = a.im + b.im;

return c;}

В этом случае структурные переменные передаются по значению. При вызове функциив качестве фактических аргументов указываются имена структурных переменных:

struct complex x,y,z;

…

z = add1(x, y);

д) Структуры можно передавать в функции и по адресу.

struct complex add2 (struct complex *pa, struct complex *pb)

{

struct complex c;

c.real = pa→real + pb→real;

c.im = pa→im + pb→im;

return c;

}

При вызове функции в этом случае в качестве фактических аргументов указываются адреса структур.

struct complex x,y,z;

…

z = add2(&x, &y);

В отличие от массива, имя структуры не имеет никакого значения.

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

struct STUDENT st[200];

Этот оператор создает в памяти 200 переменных типа структуры с шаблоном STUDENTи именами st[0], st[1],…st[199].

Для доступа к полю course 25-го элемента массива используем st[24].course.

При инициализации массивов структур следует заключать в фигурные скобки каждый элемент массива.

Пример:

Структура: студенты, поля – фамилия, имя, курс, средний балл. Поиск студентов по среднему баллу.

#include <iostream.h>

#include <conio.h>

#include <string.h>

//описание структуры

struct student

{char surname[15];

char name[15];

int course;

double mate;};

int main()

{const n=3;

int i,j;

//описание массива структур s и переменной t типа структуры

student s[n],t;

//установка флага "выравнивание по левому краю"

cout.setf(ios::left);

clrscr();

//ввод данных

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

{cout<<" Vvedite familiu\n"; cin>>s[i].surname;

cout<<" Vvedite imya\n"; cin>>s[i].name;

cout<<" Vvedite kurs\n"; cin>>s[i].course;

cout<<" Vvedite sr ball\n"; cin>>s[i].mate;

clrscr();}

//вывод данных

cout<<"\nFamiliya Imya Kurs Sr. ball\n\n";

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

{cout.width(18);cout<<s[i].surname;

cout.width(18);cout<<s[i].name;

cout.width(8);cout<<s[i].course;

cout.width(8);cout<<s[i].mate<<"\n";}//Поиск студентов по среднему баллу

double mate;

cout<<"\n\n Vvedite sr ball\n";

cin>>mate;

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

if (s[i].mate>mate)

{

cout.width(18);cout<<s[i].surname;

cout.width(18);cout<<s[i].name;

cout.width(8);cout<<s[i].course;

cout.width(8);cout<<s[i].mate<<"\n";}

//Сортировка по фамилии в алфавитном порядке

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

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

if (strcmp(s[i].surname,s[j].surname)>0)

{t=s[i];

s[i]=s[j];

s[j]=t; }

//Вывод отсортированного массива

cout<<"\n\nOtsortirovannyi massiv\n\n";

cout<<"Familiya Imya Kurs Sr. ball\n\n";

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

{cout.width(18);cout<<s[i].surname;

cout.width(18);cout<<s[i].name;

cout.width(8);cout<<s[i].course;

cout.width(8);cout<<s[i].mate<<"\n";}

getch();return 0;}