ОСНОВИ ПРОГРАМУВАННЯ | Вступ | Алгоритми і величини | Основою програмістської грамотності є розвинене алгоритмічне мислення. | Лінійні обчислювальні алгоритми | Розгалуження і цикли в обчислювальних алгоритмах | Допоміжні алгоритми і процедури | Історія і класифікація мов програмування | Структура і способи опису мов програмування високого рівня | Перше знайомство з Паскалем |

загрузка...
загрузка...
На головну

Обчислення рекурентних послідовностей

  1. А) Обчислення обсягу тіла по відомим площами паралельних перерізів.
  2. А) Обчислення площ в прямокутній системі координат.
  3. Обчислення подвійних інтегралів методом квадратур.
  4. Обчислення допускаються контактних напруг зубів
  5. Обчислення значень в формулах
  6. Обчислення і аналіз відхилень
  7. Обчислення невласних інтегралів

Рекурентна послідовність. З курсу математики відомо поняття рекуррентной послідовності. Це поняття вводиться так: нехай відомо k чисел a1, ..., аk. Ці числа є першими числами числової послідовності. Наступні елементи даної послідовності обчислюються так:

Тут F- функція від k аргументів. Формула виду

називається рекуррентной формулою. Величина k називається глибиною рекурсії.

Іншими словами, можна сказати, що рекуррентная послідовність - це нескінченний ряд чисел, кожне з яких, за винятком k початкових, виражається через попередні.

Прикладами рекурентних послідовностей є арифметична (1) і геометрична (2) прогресії:

Рекурентна формула для зазначеної арифметичної прогресії:

Рекурентна формула для даної геометричній прогресії:

Глибина рекурсії в обох випадках дорівнює одиниці (таку залежність ще називають однокрокової рекурсією). В цілому рекуррентная послідовність описується сукупністю початкових значень і рекуррентной формули. Все це можна об'єднати в одну ветвящуюся формулу. Для арифметичної прогресії:

Для геометричній прогресії:

Наступна числова послідовність відома в математиці під назвою чисел Фібоначчі:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Починаючи з третього елемента кожне число дорівнює сумі значень двох попередніх, т. Е. Це рекуррентная послідовність з глибиною рівної 2 (двокрокова рекурсія). Наведемо її в ветвящейся формі:

Введення уявлення про рекурентних послідовностях дозволяє по-новому поглянути на деякі вже відомі нам завдання. Наприклад, факторіал цілого числа п! можна розглядати як значення n-го елемента наступного ряду чисел:

Рекуррентное опис такої послідовності виглядає наступним чином:

Програмування обчислень зворотних послідовностей. З рекурентних послідовностями пов'язані завдання такого роду:

1) обчислити заданий (n-й) елемент послідовності;

2) математично обробити певну частину послідовності (наприклад, обчислити суму або твір перших n членів);

3) підрахувати кількість елементів на заданому відрізку послідовності, які відповідають певним властивостям;

4) визначити номер першого елемента, що задовольняє певній умові;

5) обчислити і зберегти в пам'яті заданий кількість елементів послідовності.

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

Приклад 1. Обчислити n-й елемент арифметичної прогресії (1).

Var M, I: 0..Maxint;

A: Real;

Begin

Write ( 'N =');

ReadLn (N);

A: = l;

For I: = 2 To N Do

A: = A + 2;

WriteLn ( 'A (', N: l, ') =', A: 6: 0)

End.

Рекурентна формула ai = ai-1 + 2 перейшла в оператор А: = А + 2.

Приклад 2. Підсумувати перші п елементів геометричної прогресії (2) (не користуючись формулою для суми перших n членів прогресії).

Var N, 1: 0..Maxint;

A, S: Real;

Begin

Write ( 'N ='); ReadLn (N);

A: = l;

S: = A;

For I: = 2 To N Do

Begin

A: = 2 * A;

S: = S + A

End;

WriteLn ( 'Сума дорівнює', S: 6: 0)

End.

При обчисленні рекуррентной послідовності з глибиною 2 вже не можна обійтися однією змінною. Це видно з такого прикладу.

Приклад 3. Вивести на друк перші п (п ? 3) чисел Фібоначчі. Підрахувати, скільки серед них парних чисел.

Var N, I, K, F, F1, F2: 0..Maxint;

Begin

Fl: = l; F2: = l;

K: = 0;

WriteLn ( 'F (l) =', Fl, 'F (2) =', F2);

For I: = 3 To N Do

Begin

F: = F1 + F2;

WriteLn ( 'F (', I: l, ') =', F);

If Not Odd (F) Then K: = K + 1;

F1: = F2; F2: = F

End;

WriteLn ( 'Кількість парних чисел в послідовності одно', к)

End.

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

Приклад 4. Для заданого матеріального х і малої величини ? (наприклад, ? = 0,000001) обчислити суму ряду

включивши в неї тільки доданки, що перевищують ?. Відомо, що сума такого нескінченного ряду має кінцеве значення, рівне еx, де е = 2,71828 ... - підстава натурального логарифма. Оскільки елементи цього ряду є спадаючу послідовність чисел, яка прагне до нуля, то підсумовування потрібно виробляти до першого доданка, по абсолютною величиною не перевищує ?.

Якщо складові в цьому виразі визначити таким чином:

то узагальнена формула для i-го елемента буде наступною:

Неважко побачити, що між елементами даної послідовності є рекуррентная залежність. Її можна знайти інтуїтивно, але можна і вивести формально. Правда, для цього потрібно здогадатися, що рекурсія - однокрокової, і що кожен наступний елемент виходить шляхом множення попереднього на деякий множник, т. Е.

Використовуючи узагальнену формулу, маємо:

Звідси:

дійсно:

Отже, дана рекуррентная послідовність може бути описана наступним чином:

І нарешті, наведемо програму, вирішальну поставлену задачу.

Var A, X, S, Eps: Real;

I: Integer;

Begin

Write ( 'X ='); ReadLn (X);

Write ( 'Epsilon ='); ReadLn (Eps);

A: = l; S: = 0; I: = 0;

While Abs (A)> Eps Do

Begin

S: = S + A;

I: = I + 1;

A: = A * X / I

End;

WriteLn ( 'Сума ряду дорівнює', S: 10: 4)

End.

Як і раніше, значення однокрокової рекуррентной послідовності обчислюються в одній змінної.

Кожне повторне виконання циклу в цій програмі наближає значення S до шуканого (уточнює значущі цифри в його записи). Такий обчислювальний процес в математиці називається ітераційним процесом. Відповідно, цикли, які реалізують ітераційний обчислювальний процес, називаються ітераційними циклами. Для їх організації використовуються оператори While або Repeat.

Приклад 5. Для заданого натурального N і речового х (х> 0) обчислити значення виразу:

В цьому випадку рекурентність не настільки очевидна. Спробуємо знайти її методом індукції. Будемо вважати, що шукане вираз є N-й елемент послідовності такого вигляду:

Звідси видно зв'язок:

Тепер поставлена ??задача вирішується дуже просто:

Var A, X: Real; I, N: Integer;

Begin

Write ( 'X ='); ReadLn (X);

Write ( 'N ='); ReadLn (N);

A: = Sqrt (X);

For I: = 2 To N Do

A: = Sqrt (X + A);

WriteLn ( 'Відповідь:', а)

End.

До вирішення всіх перерахованих вище завдань можна підійти інакше.

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

Зробимо це для загального випадку, визначивши арифметичну прогресію з першим членом а 0 і різницею d:

Відповідна підпрограма-функція виглядає так:

Function Progres (АТ, D: Real; I: Integer): Real;

Begin

If I = 1

Then Progres: = AO

Else Progres: = Progres (A0, D, I-1) + D

End;

Наступна програма виводить на екран перші 20 чисел Фібоначчі, значення яких обчислює рекурсивна функція Fibon.

Var До: Byte;

Function Fibon (N: Integer): Integer;

Begin

If (N = 1) Or (N = 2)

Then Fibon: = 1

Else Fibon: = Fibon (N-1) + Fibon (N-2)

End;

Begin

For K: = l To 20 Do WriteLn (Fibon (K))

End.

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

Рекурентні послідовності часто використовуються для вирішення різного роду еволюційних задач, т. Е. Завдань, в яких простежується якийсь процес, що розвивається в часі. Розглянемо таку задачу.

Приклад 6. У ході лікувального голодування маса пацієнта за 30 днів знизилася з 96 до 70 кг. Було встановлено, що щоденні втрати маси пропорційні масі тіла. Обчислити, чому дорівнювала маса пацієнта через k днів після початку голодування для k = 1, 2, ..., 29.

Позначимо масу пацієнта в i-й день через рi (i = 0, 1, 2, ..., 30). З умови задачі відомо, що р0 = 96 кг, p30 = 70 кг.

Нехай К-коефіцієнт пропорційності убування маси за один день. тоді

Отримуємо послідовність, описану наступною рекуррентной формулою:

Однак нам невідомий коефіцієнт К. Його можна знайти, використовуючи умова p30 = 70.

Для цього будемо робити зворотні заміни:

Далі програмування стає тривіальним.

Var I: Byte; P, Q: Real;

Begin

P: = 96;

Q: = Exp (l / 30 * Ln (70/96));

For I: = l To 29 Do

Begin

P: = Q * P;

WriteLn (I, '- й день', р: 5: 3, 'кг')

End

End.

Основні поняття і засоби комп'ютерної графіки в Турбо Паскалі

До сих пір ми використовували екран комп'ютера тільки для виведення символьної інформації - чисел, текстів. Однак Турбо Паскаль дозволяє виводити на екран малюнки, креслення, графіки функцій, діаграми і т. П., Все те, що прийнято називати комп'ютерною графікою.

Починаючи з четвертої версії Турбо Паскаля для IBM PC з'явилася потужна графічна бібліотека, організована в модуль Graph. У додатку 2 в довідковій формі дано опис основних компонент цього модуля. У розглянутих нижче прикладах програм використовується модуль Graph. Для його підключення на початку програми необхідно написати рядок:



підпрограми | Uses Graph;
загрузка...
© um.co.ua - учбові матеріали та реферати