Задача о последовательном делении

Постановка задачи

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

Графическая интерпретация задачи определяет три основных варианта решения:

перемещением правого конца отрезка (b):

a₀ b₃ b₂ b₁ b₀

перемещением левого конца отрезка (а):

a₀ a₁ a₂ a₃ b₀

перемещением двух концов отрезка (а и b):

a₀ a₁ a₂ a₃ b₃ b₂ b₁ b₀

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

Уточнение постановки задачи позволяет выполнить следующий этап – формирование математической модели.

Формирование математической модели

Исходные данные

a₀ = _ _ , _ _ – координата начала исходного отрезка;

b₀ = _ _ , _ _ – координата конца исходного отрезка;

= _ , _ _ _ _ – степень точности.

Расчётные зависимости

– начальное значение координаты;

– расчёт текущей координаты;

– длина i-го отрезка;

– условие прекращения вычислений.

Выбор метода решения

Анализ полученной математической формулировки позволяет сделать выводы:

· решение задачи требует многократного вычисления текущего размера отрезка , однозначно зависящего от текущей величины b_i, следовательно, процесс является циклическим, а параметр цикла есть L_i;

· начальное значение параметра , условие повторения цикла , невыполнение которого приводит к выходу из него;

· текущее значение конца отрезка b_i определяет текущее значение параметра цикла – длину отрезка L_i.

· закон изменения параметра цикла имеет вид , при условии рекуррентного изменения конца отрезка ;

· количество повторений цикла N не может быть определено до начала счёта.

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

Составление алгоритма решения

Относительная несложность математической модели позволяет представить алгоритм решения одношаговой схемой (рис. 7.10).

Рис. 7.10. Схема алгоритма задачи о последовательном делении

Программирование задачи

Идентификация переменных в соответствии со схемой алгоритма представлена в табл. 7.6:

Таблица 7.6

Обозначение в алгоритме	a₀	b₀	b_i	b_i-1	L_i
Обозначение в программе	a0	b0	bi	bi1	li	eps

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

Классический вариант программирования задачи

#include <stdlib.h> /* директивы */

#include <stdio.h> /* препроцессора */

#include <conio.h>

#include <windows.h>

main( ) /* заголовок головной функции */

{

float a0, b0, bi, bi1, li, eps; /* описатели переменных */

char buf[50]; /*описание символьного массива*/

CharToOem("Введите a0, b0, eps : ",buf);

printf("\n %s \n",buf);

scanf("%f%f%f", &a0, &b0, &eps);

printf("a0 = %.4f b0 = %.4f eps =%.6f ", a0, b0, eps);

bi1 = b0; /* формирование текущего значения конца отрезка bi*/

printf("\n -------------------------------"

"\n | a0 | bi | li |"

"\n -------------------------------");

{

bi = a0 + (bi1 - a0)/2.; /* расчет текущего значения bi*/

li = bi - a0; /* расчет текущей длины отрезка li*/

printf( "\n |%7.4f |%8.5f | %8.5f |", a0, bi, li);

bi1 = bi;

}while( li > eps ); /*условие повторения цикла*/

printf("\n -------------------------------\n");

getch();

}

13.5 29.43 0.01

13.5 29.43 0.001

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

Результаты решения представлены в приложении 7.9 (а, б).

Программирование задачи с графическим интерфейсом

Программирование задачи при использовании графического интерфейса предварим его разработкой. Для ввода значений концов отрезка a₀, b₀ и степени точности e планируем поля редактирования (EditA, EditВ, и EditEps). Для вывода расчетных значений a₀, b_i, L_i – поля-списки (ListBoxА0, ListBoxBi, ListBoxLi).

ListBoxLi

ListBoxBi

ListBoxA0

EditEps

EditВ

EditA

Управление процессом решения реализуют две командные кнопки, расположенные в нижней части окна. Назначение каждой определяется ее названием.

С учетом планируемого интерфейса выполним программирование задачи.

Программа решения

#include <stdlib.h> /* директивы */

#include <stdio.h> /* препроцессора */

void TIterDlgClient::BNClickedOK() /*заголовок функции*/

{

// INSERT>> Your code here.

float a0, b0, bi, bi1, li, eps; /* описатели переменных */

char buf[25]; /* описатель символьного массива*/

ListBoxA0->ClearList(); /* очистка */

ListBoxBi->ClearList(); /* полей - */

ListBoxLi->ClearList(); /*списков*/

EditA->GetText(buf,10); /* ввод значения */

a0=atof(buf); /* конца отрезка а0*/

EditB->GetText(buf,10); /* ввод значения */

b0=atof(buf); /* конца отрезка b0*/

EditEps->GetText(buf,10); /* ввод значения */

eps=atof(buf); /* точности eps*/

bi1 = b0; /* формирование текущего значения конца отрезка bi*/

{

bi = a0 + (bi1 - a0)/2.; /* расчет текущего значения bi*/

li = bi - a0; /* расчет текущей длины отрезка li*/

sprintf(buf,"%5.3f",a0); /* вывод текущего*/

ListBoxA0->AddString(buf); /* значения a0*/

sprintf(buf,"%5.3f",bi); /* вывод текущего*/

ListBoxBi->AddString(buf); /* значения bi*/

sprintf(buf,"%5.3f",li); /* вывод текущего*/

ListBoxLi->AddString(buf); /* значения li*/

bi1 = bi;

}while( li > eps ); /*условие повторения цикла*/

}

13.5 29.43 0.01

13.5 29.43 0.001

Внимание! Варианты использования итерационных циклов с приближенным решением и дополнительными расчетными компонентами рассмотрены в главе 8.

Результаты решения представлены в приложении 7.10 (а, б).

Заключение

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

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

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

Классификация итерационных циклов по критерию «характер результатов» – сходящиеся и расходящиеся.

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

Сходящиеся вычислительные процессы – обязательное условие итерационных циклов с приближенным решением.

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

Расходящиеся вычислительные процессы допустимы только в итерационных циклах с точным решением.

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

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

Максимальная эффективность – использование в смешанных вычислительных процессах в комплексе с ветвлениями (поиск экстремумов, сортировка и т. п.).

Вопросы для контроля

Какой циклический процесс называется итерационным?

Как классифицируются итерационные циклы по точности решения?

Каковы определения итерационных циклов с точным (приближенным) решениями?

Каковы основные математические зависимости для итерационных циклов?

Какие методики применимы для расчёта функций?

Как классифицируются итерационные циклы по организации вычисления функции?

Что такое рекуррентные вычисления?

Как классифицируются итерационные циклы по характеру изменения результатов?

Как связаны точность решения со сходимостью (расходимостью) итерационного процесса?

Какова зависимость определения числа повторений итерационного процесса?

Как формируется условие прекращения расчётов?

Каковы варианты графической интерпретации задачи о делении отрезка?

Какие строки программы не пишутся пользователем, а формируются ИСРП?

К какому виду и типу итерационного процесса относится расчет чисел Фибоначчи?

В каких итерационных циклах возможны два варианта решения и какие?

Каковы варианты решения задачи о последовательном делении?