Материал: metodichka_u_praktika

Закінчення таблицею. 8.1

Робота №9

Програмування з використанням рекурсії

9.1. Поняття рекурсії

Вирішити завдання рекурсивно – це означає розкласти її на підзадачі, які потім аналогічним чином (тобто рекурсивно) розбиваються на ще менші підзадачі. На певному рівні підзадачі стають настільки простими, що можуть бути вирішені тривіально.

У рекурсивному алгоритмі поважно передбачити спосіб його зупинки, тобто ввести умову, при якій рекурсивне звернення до функції припиняється.

9.2. Приклад виконання роботи

Умова 1. Написати програму для обчислення двома методами. Один метод обчислює суму без використання рекурсії, інший ( з використанням рекурсії.

#include <iostream.h>

#include <math.h>

double sum(int);

double sumr(int);

int main ()

{

int n;

cout << "vvedite n "; cin >> n;

cout << "s (ne rekurs) = " << sum(n) << endl;

cout << "s (rekurs) = " << sumr(n) << endl;

return 0;

}

double sum(int n)

{

for (double s=0, int i=1; i<=n; i++) s += (pow(i+1,2))/i;

return s;

}

double sumr(int n)

{

if (n==1) return 4;

else return sumr(n-1)+pow(n+1,2)/n;

}

Умова 2. Знайти max (a1 ..., an), розбивши завдання на елементарні підзадачі: max(max (max (a1...an–2), an–1), an) . .

int maxr2(int i)

{

if (i==0) return а[0];

else {

int mx=maxr2(i-1);

if (а[i]>mx) return а[i];

else return mx;

}

}

Умова 3. Завдання про Ханойську башту. Є три стержні s1, s2, s3. На першому з них нанизані n дисків різних діаметрів, створюючих правильну піраміду, – чим вище розташований диск, тим менше його діаметр. Потрібно перемістити всю башту на другий стержень, причому диски можна переносити поодинці, не можна поміщати диск на диск меншого діаметру, для проміжного зберігання можна використовувати третій диск.

void hanr(int n, int s1, int s2, int s3)

{

if (n>0) {

Hanr(n-1,s1,s3,s2);

cout << "perenesty s "<<s1<<" na "<<s2<<endl;

Hanr(n-1,s3,s2,s1);

}

}

9.3. Індивідуальні завдання

Вирішити завдання двома способами – із застосуванням рекурсії і без неї.

1. Обчислити середнє значення елементів одновимірного масиву.

2. Обчислити твір елементів одновимірного масиву.

3. Підрахувати кількість цифр в заданому числі.

4. У впорядкованому масиві цілих чисел ai, i = 1 ... n знайти номер елементу з методом бінарного пошуку, використовуючи очевидне співвідношення: якщо, тоді, інакше . Якщо елемент з відсутній в масиві, то вивести відповідне повідомлення.

5. Знайти найбільшого загального дільника чисел M і N використовуючи метод Ейлера: якщо M ділиться на N, то НОД (N, M) = N, інакше НОД (N, M) = = НОД (M % N, N).

6. Обчислити значення полінома міри n за формулою

.

7. Обчислити значення, використовуючи формулу, як початкове наближення використовувати значення x0 = (1+a)/2.

8. Знайти максимальний елемент в масиві a1 ..., an, використовуючи метод ділення навпіл max (a1 ..., an) = max (max (a1 ..., an/2), max (an/2+1 ..., an)).

9. Обчислити .

10. Обчислити твір n ( 2 (n парне) співмножників

11. Обчислити по наступному алгоритму:, якщо N парне;, якщо N непарне.

12. Обчислити

13. Обчислити твір двох цілих позитивних чисел по наступному алгоритму:, якщо b парне;, якщо b непарне. Якщо b = 0, то p = 0.

14. Обчислити значення суми S = 1/1! + 1/2! + ... + 1/k!

15. Перевірити, чи є заданий рядок палиндромом.

Робота №10 Програмування з використанням файлів

10.1. Організація роботи з файлами

Розрізняють два види файлів: текстові і двійкові.

Текстові файли зберігають інформацію у вигляді послідовності символів. У текстовому режимі кожен розділовий символ рядка автоматично перетвориться в пару (повернення каретки – перехід на новий рядок).

Бінарні (або двійкові) файли призначені для зберігання лише числових значень даних. Структура такого файлу визначається програмно.

Функції для роботи з файлами розміщені в бібліотеках stdio.lib (#include <stdio.h>) і io.lib (#include <io.h>). Кожен файл має бути пов'язаний з деяким покажчиком. Цей покажчик має типа FILE і використовується у всіх операціях з файлами.

Формат оголошення покажчика на файл наступний:

FILE *указатель на файл;

Макрос NULL визначає порожній покажчик.

Макрос EOF, часто визначуваний як –1, є значенням, повертаним тоді, коли функція введення намагається виконати читання після кінця файлу.

Макрос FOPEN_MAX визначає ціле значення, рівне максимальному числу одночасно відкритих файлів.

10.2. Функції для роботи з файлами

Функція

FILE *fopen(const char *имя_файла,

const char *режим_открытия);

відкриває файл і пов'язує його з потоком. Повертає покажчик на відкритий файл. Імя_файла – це покажчик на рядок символів, в якому зберігається ім'я файлу і дорога до нього. Режім_откритія – це покажчик на рядок символів, в якому вказується режим відкриття файлу. Допустимі режими:

r ( відкриття текстового файлу для читання;

w ( cоздатие текстового файлу для запису;

а ( додавання інформації в кінець текстового файлу.

При роботі з текстовими файлами до символу, вказуючого режим відкриття, додається символ «t» (за умовчанням), а при роботі з бінарними – «b». Якщо необхідно і читати і записувати у файл, то додається символ «+». При виникненні помилки під час відкриття файлу, функція fopen повертає значення NULL.

Функція

int fclose(FILE *указатель_на _файл);

закриває потік, який був відкритий за допомогою виклику fopen() і записує у файл всі дані, які ще залишалися в дисковому буфері. Доступ до файлу після виконання функції буде заборонений.

Повернення нуля означає успішну операцію закриття. У разі ж помилки повертається EOF.

Функція

int fcloseall(void);

закриває всі відкриті файли. Повертає кількість закритих файлів або EOF, якщо виникає помилка.

Функція

int putc(int символ, FILE * указатель_на _файл);

записує один символ в поточну позицію вказаного відкритого файлу. Функція

int getc(FILE * указатель_на _файл);

читає один символ з поточної позиції вказаного відкритого файлу.

Функція

int feof(FILE * указатель_на _файл);

повертає відмінне від нуля значення (true), якщо кінець файлу не досягнутий, і нуль (false), якщо досягнутий кінець файлу.

Функція

int fputs(const char * рядок, FILE * указатель_на _файл);

записує рядок символів в поточну позицію вказаного відкритого файлу.

Функція

char *fgets(char *строка, int довжина

FILE * указатель_на _файл);

читає рядок символів з поточної позиції вказаного відкритого файлу до тих пір, поки не буде прочитаний символ переходу на новий рядок, або кількість прочитаних символів не стане рівною довжина – 1.

Функція

int *fprintf(FILE * указатель_на _файл

const char * управляющая_строка);

записує форматовані дані у файл. Управляющая_строка визначає рядок форматування аргументів, заданих своїми адресами. Зазвичай цей рядок складається з послідовності символів «%», після яких слідує символ типа даних:

I або I ( десяткове, вісімкове або шістнадцятиричне ціле;

D або d ( десяткове ціле;

U або u ( десяткове ціле без знаку;

E або e ( дійсне з плаваючою крапкою;

s ( рядок символів;

з ( символ.

Функція

int *fscanf(FILE * указатель_на _файл

const char * управляющая_строка);

читає форматовані дані з файлу. Рядок форматування будується аналогічно функції fprintf.

Функція

void rewind(FILE * указатель_на _файл);

встановлює покажчик поточної позиції виділеного файлу в початок файлу.

Функція

int ferror(FILE * указатель_на _файл);

визначає, чи сталася помилка під час роботи з файлом. Функція

size_t fwrite(const void * записываемое_данное

size_t размер_элемента, size_t число_элементов

FILE *указатель_на _файл);

записує у файл задане число даних певного розміру. Розмір даних задається в байтах. Тип size_t визначається як ціле без знаку.

Функція

size_t fread(void * считываемое_данное

size_t размер_элемента, size_t число_элементов

FILE *указатель_на _файл);

прочитує з файлу вказане число даних заданого розміру. Розмір задається в байтах. Функція повертає число прочитаних елементів. Якщо число прочитаних елементів не дорівнює заданому, то при читанні виникла помилка або зустрівся кінець файлу.

Функція

int fileno(FILE * указатель_на _файл);

повертає значення дескриптора вказаного файлу (дескриптор – логічний номер файлу для заданого потоку).

Функція

long filelength(int дескриптор);

повертає довжину файлу з відповідним дескриптором в байтах.

Функція

int fseek(FILE * указатель_на _файл, long int число_байт

int точка_отсчета);

встановлює покажчик в задану позицію. Задана кількість байт відлічується від позиції, яка задається наступними макросами: SEEK_SET – початок файлу, SEEK_CUR – поточна позиція, SEEK_END – кінець файлу.

10.3. Приклад виконання роботи

Умова. Написати програму, що вводить у файл або ведомость студентів, що склали іспити, що читає з файлу. Кожна структура повинна містити прізвище, а також оцінки по математиці і програмуванню. Вивести список студентів, що склали іспит по програмуванню з оцінкою 4, і записати цю інформацію в текстовій файл.

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

FILE *fl;

typedef struct

{

char fio[30];

unsigned char matem;

unsigned char oaip;

} TStudent;

TStudent stud[30]; // Масив структур

char name[20]; // Ім'я файлу

int nst=0; // Число введених структур

int menu(); // Меню

void nnf(); // Ввести ім'я файлу

void newf(); // Створити новий файл

void spisok(); // Ввести список

void opf(); // Відкрити файл

void resc(); // Вивести результат на екран

void resf(); // Вивести результат у файл

int main()

{

while (true)

{

switch (menu())

{

case 1: nnf(); break;

case 2: newf(); break;

case 3: spisok(); break;

case 4: opf(); break;

case 5: resc(); break;

case 6: resf(); break;

case 7: return 0;

default: "Viberite pravilno!";

}

puts("Press any key to continue");

getch(); system("cls");

}

}

int menu() // Меню

{

cout << "VIBERITE:" << endl;

cout << "1. Vvod file name" << endl;

cout << "2. New file" << endl;

cout << "3. Vvesti spisok" << endl;