Процедура за структурою подібна до програми, її вигляд


НазваПроцедура за структурою подібна до програми, її вигляд
Дата конвертації27.03.2013
Розмір445 b.
ТипПрезентации


Поняття основного та допоміжного алгоритму. Формальні та фактичні, глобальні та локальні параметри




  • Процедура за структурою подібна до програми, її вигляд:

  • PROCEDURE ім'я (список формальних параметрів);

  • {блок описів}

  • Begin

  • {блок операторів}

  • End;





Підпрограми-функції

  • Функція – це підпрограма для проведення математич-ного обчислення виразу чи функції. Результат її вико-нання – певне числове значення, яке повертається у програму.

  • При використанні підпрограм змінні бувають: локальні – описані в підпрограмах, глобальні – описані в основній програмі.



Місце описання підпрограм

  • Всі підпрограми описуються перед командами основної програми.



Підпрограма-функція

  • Загальний вигляд описання підпрограми-функції:

  • Function ім’я (формальні величини):тип результату;

  • Var описання локальних змінних;

  • Begin

  • Команди функції (виконувана частина);

  • ім’я : = змінна-результат обчислень;

  • End;



Рекурсія



У природі нам доводиться спостерігати самоподібні об'єкти, тобто такі, кожна частина яких повторює структуру всього об'єкта.

  • У природі нам доводиться спостерігати самоподібні об'єкти, тобто такі, кожна частина яких повторює структуру всього об'єкта.

  • Наприклад, розглянемо капустину сорту «Броколі»



Листок папороті складається з маленьких листочків такої ж структури, як і він сам.

  • Листок папороті складається з маленьких листочків такої ж структури, як і він сам.



Візьмемо відомий вірш Джонатана Свіфта «Хатка, яку збудував собі Джек».

  • Ось хатка, яку збудував собі Джек.

  • А це — комора, в коморі — пшениця,

  • З якої так смачно пекти паляницю

  • У хатці, яку збудував собі Джек.

  • А це — веселая пташка синиця,

  • Яка викрадає з комори пшеницю,

  • З якої так смачно пекти паляницю

  • У хатці, яку збудував собі Джек.

  • А це — кіт,

  • Він сміливо виходить з воріт,

  • Бо дуже він хоче спіймати синицю

  • Яка викрадає з комори пшеницю,

  • З якої так смачно пекти паляницю

  • У хатці, яку збудував собі Джек.



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

  • Термін рекурсія походить від латинських слів, що означають повернення, та повторення.

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



Програми можуть містити виклик однієї або декількох підпрограм. Підпрограми можуть, в свою чергу, викликати інші підпрограми.

  • А чи може підпрограма викликати саму себе?



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

  • Рекурсивні алгоритми зазвичай виникають там, де вихідну задачу можна звести до такої ж самої, але з іншими аргументами або в інших обставинах.



Типова конструкція рекурсивної процедури повинна мати наступний вигляд:

  • Типова конструкція рекурсивної процедури повинна мати наступний вигляд:

  • Procedure Rec (t:integer);

  • Begin

  • <Дії на початку рекурсії>

  • If <Перевірка умови> Then Rec(t+1);

  • <Дії на виході з рекурсії>

  • End;

  • Саме головне при написанні рекурсії усвідомити, як правильно задати умову, яка буде заглиблювати нас у рекурсію або, навпаки, виводити з неї.



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



Обчислення факторіалу числа: n!=1*2*3*…*n

  • 1)Звичайний спосіб:

  • Fact:=1; for i:=1 to n do Fact=Fact * і ;

  • 2) Рекурсивний спосіб:

  • n!= 1, при n=0 (0!=1,1!=1 за визначенням) ;

  • (n-1)!* n , при n>0.

  • Текст функції:

  • Function Fact( n : integer) : integer;

  • begin

  • If n=0 then Fact:=1 else Fact:= Fact(n-1) * n

  • end;



Виконання комп’ютером відкладених викликів функції можливе завдяки використанню стекa. Стек – модель оперативної пам’яті, де дані запам’ятовуються і зберігаються за принципом "перший прийшов – останнім вийшов" (аналогом стеку є ріжок для набоїв у автоматі).







Обчислення степеня з натуральним показником хк

  • 1)Звичайний спосіб:

  • р:=1; for i:=1 to к do р=р*х ;

  • 2)Рекурсивний спосіб:

  • 1, при к = 0;

  • Хк=

  • хк-1*х, при к > 0.

  • Function Power( k : integer; x : real) : integer;

  • begin

  • If k=0 then Power:=1

  • else Power:=Power(k-1,x) * х

  • end;



Обчислення чисел Фібоначчі Fk= Fk-1 + Fk-2 , F1= F2=1

  • 1)Звичайний спосіб:

  • x:=1; z:=1; {-перші два числа Фібоначчі }

  • for i:=1 to k do begin y:=x; x:=z; z:=x+y;

  • write (z:5) end;

  • 2)Рекурсивний спосіб:

  • Function Fib (k:integer):integer;

  • begin

  • If k<3 then Fib :=1

  • else Fib := Fib (k-1)+Fib(k-2) end;



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

  • рекурсивний алгоритм коротший і наглядніший.

  • Недоліки:

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



Обчислення 15-го числа Фібоначчі Fk= Fk-1+ Fk-2 (рекурсивний спосіб)

      • F15
      • F14 F13
      • F13 F12 F12 F11
      • F12 F11 F11 F10 F11 F10 F10 F9
      • F11 F10 . . . . . . . . . . . . . . . . . . . . F8 F7
      • F9 F8 .. . . . . . . . . . . . . . . . F7 F6


Увага!

  • При обчисленні 31-го числа Фібоначчі рекурсивним способом комп’ютер виконає >1 млн. операцій додавання,

  • 45-го > 1 млрд.!!! (що може призвести до переповнення стеку).

  • Для порівняння:

  • обчислення за звичайним способом потребує 31 та 45 операцій додавання відповідно!



Задача про Ханойські вежі.

  • Потрібно перекласти диски з осі А на вісь С, користуючись віссю В так, щоб більший диск не класти на менший. За один раз можна перекладати один диск.



Програма

  • procedure Xanoj(n : integer; A,B,C: char); begin

  • If n=1 then writeln(‘перекласти диск з осі’, A, ’на вісь’, C)

  • else begin

  • Xanoj(n-1, A, B, C);

  • writeln(‘перекласти диск з осі’, A, ’на вісь’, C)

  • Xanoj(n-1, B, C, A);

  • end end; {кінець процедури}

  • Var n: integer ;

  • begin writeln(‘задайте кількість дисків’); readln(n);

  • Xanoj(n,’A’,’B’,’C’) end. {кінець головної програми}





Схожі:

Процедура за структурою подібна до програми, її вигляд iconПроцедура за структурою подібна до програми, її вигляд
Поняття основного та допоміжного алгоритму. Формальні та фактичні, глобальні та локальні параметри Процедура за структурою подібна...
Процедура за структурою подібна до програми, її вигляд iconВластивості об’єктів сторінок Standard, Additional, Win32 середовища Delphi Вигляд палітри компонентів Standard
Форма (об'єкт типу tform) основа програми. Властивості форми визначають вигляд вікна програми
Процедура за структурою подібна до програми, її вигляд icon1. Стандартний вигляд курсору ос “windows”. Графічний значок папки. Який вигляд на робочому столі мають піктограми різних програм?
Мій Комп’ютер"? Який вигляд має курсор у різних програмах? На якому диску розміщена програма "Калькулятор" на вашому пк? Як виглядає...
Процедура за структурою подібна до програми, її вигляд iconБлочно-модульна структура програми. Блочно-модульна структура програми
Процедура і функція: опис, правила виклику, приклади використання при створенні алгоритмів розв'язку задач
Процедура за структурою подібна до програми, її вигляд iconОко людини є сферичною структурою (очним яблуком), що знаходиться в Око людини є сферичною структурою (очним яблуком), що знаходиться в
Око людини є сферичною структурою (очним яблуком), що знаходиться в Око людини є сферичною структурою (очним яблуком), що знаходиться...
Процедура за структурою подібна до програми, її вигляд iconОрганолептичні – зовнішній вигляд, вигляд на розрізі, запах, смак, консистенція. Органолептичні
Зростання дефіциту якісної м`ясної сировини і необхідність пошуку нових інгредієнтів для створення комбінованих м`ясних виробів з...
Процедура за структурою подібна до програми, її вигляд iconРівняння прямої на площині Загальний вигляд рівняння прямої
Оскільки точки І мають рівні абсциси, то пряма являється паралельною осі оу І її рівняння має вигляд
Процедура за структурою подібна до програми, її вигляд iconВиникнення та розквіт Київської Русі Софійський собор в Києві (перша половина 11 ст.). Сучасний вигляд
Спасо-Преображенський собор в Чернігові. Сучасний вигляд. Закладений у 1036р князем Мстиславом Володимировичем, закінчений за князя...
Процедура за структурою подібна до програми, її вигляд iconСучасний естетичний вигляд школи Сучасний естетичний вигляд школи
Участь у міських заходах, конкурсах, спортивних змаганнях та висока результативність
Процедура за структурою подібна до програми, її вигляд iconРішення проблем інтернаціональної комунікації сучасної молоді; унікальний за своєю структурою не має аналогу серед вишів України; лояльний програми І проекти клубу можуть бути ініційовані будь-яким членом клубу
Креативний пропонує нестандартні рішення проблем інтернаціональної комунікації сучасної молоді

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка