Задача о n ферзях
Методы решения задачи по расстановке фигур на шахматной доске. Сущность рекуррентного алгоритма и составление его программы. Особенности алгоритма поиска с возвратом, статистический анализ эффективности и вероятность успеха по эвристическому алгоритму.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 29.11.2012 |
| Размер файла | 413,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Введение
Задача о восьми ферзях -- широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8Ч8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
1. Решения задачи доски 8*8
1.1 Постановка задачи
Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8Ч8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы.
Конечная цель, поставленная перед решающим эту задачу, может формулироваться в нескольких вариантах:
1) Построить одно, любое решение задачи.
2) Аналитически доказать, что решение существует.
3) Определить количество решений.
4) Построить все возможные решения.
5) Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске NЧN клеток (при этом при 1<N<4 задача не имеет решения).
Мы же подробнее рассмотрим классический “шахматный” случай для доски 8*8. А позже адаптируем возможные алгоритмы на доску размером N*N.
1.2 Рекуррентный алгоритм решения
Рассмотрим шахматную доску, клетки которой помечены с помощью системы координат следующим образом:
Можно заметить, что два ферзя, которые находятся в клетках с координатами (x1, y1) и (x2, y2), будут бить друг друга если выполняется хотя бы одно из следующих равенств:
1) x1 = x2, то есть ферзи находятся на одной вертикали;
2) y1 = y2, то есть ферзи находятся на одной горизонтали;
3) x1+y1 = x2+y2, то есть ферзи находятся на одной диагонали, идущей снизу вверх слева направо. Это равенство верно только для приведенной нумерации клеток шахматной доски;
4) x1?y1 = x2?y2, то есть ферзи находятся на одной диагонали, идущей сверху вниз слева направо. Это равенство также верно только для приведенной нумерации клеток шахматной доски.
Очевидно, что все восемь ферзей находятся на разных вертикалях шахматной доски, иначе найдутся два из них, которые бьют друг друга. Поэтому нам нужно перебрать для каждого ферзя все возможные горизонтали, где он может встать и проверить, чтобы все ферзи не были под боем. Заведем массив q, индекс которого соответствует номеру ферзя, а значение qi указывает, на какой по счету горизонтали находится i-й ферзь.
Поскольку решение предполагает переборный алгоритм, заведем восемь переменных q1,...,q8, которые будут пробегать от 1 до 8 и устанавливать соответствующего ферзя на выбранную горизонталь. Например, если qi=4, это значит, что i-го ферзя необходимо поставить на 4-ю горизонталь. Зададим функцию boy(c), которая в качестве аргумента будет принимать номер ферзя и проверять, не бьют ли ферзя с номером «c» ферзи с 1-го до «c ? 1»-го. Эта функция возвращает значение «истина» в случае если «c»-го ферзя бьет хотя бы один ферзь и «ложь» в противном случае. Это делается следующим алгоритмом:
Функция проверки «мирных» ферзей:
Алгоритм основной программы:
Данный алгоритм ищет все возможные решения задачи и выводит их число: 92. Этот алгоритм, реализованный на языке Pascal, показан в Приложении №1.
Интересно отметить, что эти 92 расположения разбиваются на 12 групп: при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам:
Например, из расстановки, показанной на рис. а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. в. А при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, - на рис. г. При помощи других поворотов и отражений доски можно получить еще пять решений. Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок. Вот один из таких наборов:
1) см. рис. а;
2) см. рис. б;
3) a4, b1, c5, d8, e6, f3, g7, h2;
4) a4, b2, c5, d8, e6, f1, g3, h7;
5) a4, b2, c7, d3, e6, f8, g1, h5;
6) a4, b2, c7, d3, e6, f8, g5, h1;
7) a3, b5, c2, d8, e6, f4, g7, h1;
8) a4, b1, c5, d8, e2, f7, g3, h6;
9) a4, b7, c3, d8, e2, f5, g1, h6;
10) a6, b4, c2, d8, e5, f7, g1, h3;
11) a4, b8, c1, d5, e7, f2, g6, h3;
12) a4, b2, c7, d5, e1, f8, g6, h3.
Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. б является симметрической. Другие одиннадцать основных расстановок - простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.
1.3 Алгоритмы Лас-Вегаса или алгоритм поиска с возвратом
Алгоритмы Лас-Вегаса никогда не возвращают неправильный ответ, хотя иногда они не возвращают вообще никакого ответа. Чем дольше работают эти алгоритмы, тем выше вероятность того, что они вернут правильный ответ. Алгоритм Лас-Вегаса принимает случайное решение, а затем проверяет, приводит ли это решение к успеху. Программа, использующая алгоритм Лас-Вегаса, вызывает его раз за разом, пока он не достигнет результата. Если обозначить через success(aj) и failure(a;) время, необходимое для того, чтобы получить соответственно положительный или отрицательный ответ на входных данных, а через р(х) вероятность успешного завершения работы алгоритма, то мы приходим к равенству:
time(x) = р(х) * success(a;) + (1 - р ( х ) ) * (failure(:r) + time(a;)).
Это равенство означает, что в случае успеха затраченное время совпадает с временем получения успешного результата, а в случае неудачи затраченное время равно сумме времени на достижение неудачного результата и еще на один вызов функции. Решая это уравнение относительно times(a;), мы получаем:
time(a;) = р(х) * success(a;) + (1 - р(х}} * failure(a;) + (1 -- p(a;))time(a;).
time(a;) -- (1 -- p(a;))time(a;) = p(x) * success(z) + (1 -- p ( x ) ) * failure(a;).
time(a;) -- time(x) + р(х) * time(a;) = р(х) * success(x) + (1 -р(х)} *failure(x).
р(х) * time(ar) -- р(х) * success(x) + (1 - р ( х ) ) * failure(o).
time(x) = success(a;) + ((1 -p(x))/p(x)} * failure(a;).
Эта формула означает, что время выполнения зависит от времени получения успешного результата, безуспешного результата и вероятности каждого из этих исходов. Интересно, что при убывании вероятности р(х) успешного результата время выполнения все равно может быть невысоким, если скорость получения безуспешного результата возрастает. Поэтому эффективность можно повысить, если быстрее получать безуспешный результат.
Как такой подход работает на практике? Обратимся к задаче о расстановке восьми ферзей на шахматной доске так, чтобы они не били друг друга:
На рис. изображено одно из решений этой задачи. Рекурсивный алгоритм ее решения помещает ферзя в первой клетке первой вертикали, а затем вызывает себя для того, чтобы поставить ферзя на вторую горизонталь. Если в какой-то момент алгоритму не удается найти положения для очередного ферзя на очередной горизонтали, то алгоритм возвращается на предыдущий шаг и пробует другое размещение ферзя на предыдущей строке.
Имеется вероятностная альтернатива детерминированному рекурсивному алгоритму. Мы можем поочередно размещать ферзей на доске случайным образом на очередной свободной горизонтали доски. Отличие алгоритма Лас-Вегаса от стандартного рекурсивного алгоритма состоит в том, что при невозможности разместить очередного ферзя алгоритм попросту сдается и сообщает о неудаче. Рекурсивный же алгоритм пытается добиться положительного результата. Вот как выглядит алгоритм Лас-Вегаса для расстановки восьми ферзей:
Queens(result)
result содержит номера вертикалей для ферзей с соответствующих горизонталей возвращает 1 в случае успеха и 0 в случае неудачи
row=l
repeat
// ферзи уже расставлены в горизонталях l..row-l
spotsPossible=0
for i=l to 8 do
if клетка (row.i) атакована then
spotsPossible=spotsPossible+l
if uniform(l,spotsPossible)=l then
try=i
end if
end if
end for
if spotsPossible>0 then
result[row]=try
row=row+l
end if
return (spotsPossible>0)
Посмотрим, как работает этот алгоритм. В цикле «repeat» мы проходим по всем восьми горизонталям доски. Для каждой из горизонталей мы последовательно просматриваем все ее клеточки и если клетка не атакована, то переменная «spotsPossible» увеличивается на единицу. Следующий оператор «if» выглядит несколько странно, но посмотрим, что происходит, если опустить первую горизонталь, на которой не атакована ни одна клетка. На первой вертикали функция «uniform» генерирует случайное число между 1 и 1, т.е. 1, поэтому переменная «try» будет указывать на первую вертикаль. Во второй вертикали «uniform» генерирует число между 1 и 2, которое с 50%-ной вероятностью будет единицей и с 50%-ной вероятностью двойкой, поэтому вероятность того, что новым значением переменной «try» станет двойка, равна 50%. В третьей вертикали «uniform» генерирует число между 1 и 3; это число с вероятностью 33% будет 1, и также с вероятностью 33% значение «try» станет равно 3. Окончательно мы заключаем, что для каждой из свободных вертикалей вероятность быть опробованной на данном проходе равна 1/«spotsPossible». Затем все повторяется для остальных горизонталей. Такие действия продолжаются до тех пор пока либо значение «spotsPossible» не станет нулевым, ввиду отсутствия неатакованных клеток, либо переменная «rows» не примет значение 9, поскольку все ферзи будут расставлены. В первом случае алгоритм завершает свою работу и сообщает о неудачном исходе. Во втором проблема расстановки восьми ферзей решена, и алгоритм сообщает об удачном исходе.
Полный статистический анализ алгоритма показывает, что вероятность успеха равна 0.1293, а среднее число повторений, необходимых для его достижения, около 6.971. Приведенное выше уравнение показывает, что алгоритм выполнит при этом 55 проходов. Рекурсивному же алгоритму понадобится, по крайней мере, вдвое больше проходов.
2. Решения задачи доски N*N
2.1 Рекуррентный алгоритм
На доске 1х1 один ферзь ставится на одно-единственное поле, и решение существует. На доске 2х2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзя поставить некуда. На доске 3х3 умещаются только два мирных ферзя. Итак, для досок 2х2 и 3х3 задача не имеет решения. Эти два случая представляют собой исключение. Для всех N > 3 на доске NxN можно расставить n не угрожающих друг другу ферзей.
На доске 4x4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5x5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5х5.
Заметим, что в общем случае N расстановок (решений задачи) могут заполнить при наложении всю доску NхN только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.
Классическим решением задачи N ферзей является прямой перебор с отсечением. Прямой перебор заключается в испытании на конфликтность всех возможных комбинаций. Например, на доске существуют N^2 позиции, таким образом, мы имеем N^2 возможных позиций для первого ферзя, N^2-1 для второго и т.д. Общее число возможных расположений всех ферзей составляет (N^2, N) = (N^2)!/((N^2-N)! * n!). Если перебрать все эти позиции, можно найти все правильные решения. Для n=10 число всех позиций равно ~1.73*10^13.
Поскольку в неконфликтном расположении на одной горизонтали может стоять только один ферзь, то мы можем ограничиться расстановкой одного ферзя на первой горизонтали, второго - на второй и т.д. Это дает нам N возможных положений для каждого ферзя и N^N различных расположений. Для N=10 это будет 10^10. Заметим, что на каждой вертикали также может быть только один ферзь: i-й ферзь имеет только n-i+1 возможных положений, поскольку предыдущие i-1 ферзей уже заняли i-1 вертикалей. Теперь общее количество возможностей сократилось до N! или 3.6*10^6 вариантов для n=10.
И последний способ уменьшить количество возможных вариантов - контролировать положение ферзей на одной диагонали. Хотя это просто запрограммировать, бывает трудно дать оценку количества перебираемых вариантов.
2.2 Алгоритмы Лас-Вегаса или алгоритм поиска с возвратом
Если решать более общую задачу об N ферзях, то такой перебор вариантов даже с использованием описанных выше сокращений будет весьма долго работать уже при N = 20, так как 20! = 2.433Ч10^18.
2.3 Эвристический алгоритм
Эвристический алгоритм (эвристика) -- алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев. Эвристический алгоритм -- это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.
Для решения поставленной задачи эвристический алгоритм будет выглядеть так:
1) Разделить N на 12 и запомнить остаток (N будет равно 8 для задачи о восьми ферзях).
2) Занести в список все четные числа от 2 до N по порядку.
3) Если остаток равен 3 или 9, перенести 2 в конец списка.
4) Добавить в список все нечетные числа от 1 до N по порядку, но, если остаток равен 8, перевернуть пары соседних чисел (например: 3, 1, 7, 5, 11, 9, …).
5) Если остаток равен 2 и N ? 3, поменять местами 1 и 3, затем, если N ? 5, перенести 5 в конец списка.
6) Если остаток равен 3 или 9, переместить 1 и 3 (именно в этом порядке, а не в котором они сейчас) в конец списка.
7) Разместить ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем поместить следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т.д..
Примеры реализации этого алгоритма на доске 8х8 рассмотрены в Приложении №2.
Заключение
В работе рассмотрены несколько видов алгоритмов: рекуррентный, алгоритм с возвратом (алгоритм Лас-Вегаса) и эвристический.
Для «доски» 8х8 более эффективным является алгоритм с возвратом. Но он выводит лишь одно решение. Рекуррентный выводит все 92, но его работа может занимать больше времени. Эвристический так же находит лишь одно существующее решение.
Анализируя данные алгоритмы на «доске» NxN нужно отметить, что их эффективность напрямую зависит от размера «доски». При небольшом размере по эффективности преобладает Алгоритм Лас-Вегаса. Но при увеличении размера увеличивается шанс, что алгоритм не вернет ответа, т.к. пройти придется большое количество действий (предельный размер «доски» для этого алгоритма 20х20). Рекуррентный алгоритм находит все решения, независимо от размера доски, но при увеличении «доски», его эффективность так же снижается. Эвристический находит лишь одно существующее решение, независимо от размера «доски» (кроме случаев 2х2 и 3х3, там решений не существует). Но существует шанс, что найденное решение может быть ошибочно, и проверить его, при большом размере «доски» довольно проблематично.
Список литературы
1) М. Гарднер Математические досуги. - М.: Мир, 2000.
2) Дж. Макконел Основы современных алгоритмов. - М.: Техномир, 2004.
3) Е. Корнилов Программирование шахмат и других логических игр. - С.-П.: БХВ-Петербург, 2005.
4) А. Левитин Введение в анализ и разработку алгоритмов - М.: Вильямс, 2006.
5) Вирт Н. Алгоритмы и структура данных - С.-П.: Невский Диалект, 2005.
6) А. Ахо, Дж. Хопфорт, Дж. Ульман Построение и анализ вычислительных алгоритмов - М.: Мир, 1979.
7) Д. Кнут Искусство программирования т.1,2,3 - М.: 1968.
Приложение №1
Приложение №2
фигура шахматная рекуррентный эвристический
Доска 8х8:
1) Для такой доски остаток равен 8.
2) Заносим в список все четные числа от 2 до 8: 2,4,6,8.
3) Остаток не равен 3 или 9, оставляем список без изменений.
4) Заносим в список все нечетные числа от 2 до 8. Т.к. остаток равен 8, то переворачиваем пары соседних чисел: 2,4,6,8,1,3,5,7.
5) Т.к. остаток не равен 2, оставляем список без изменений.
6) Т.к. остаток не равен 3 или 9, оставляем список без изменений.
7) Размещаем ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем помещаем следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т.д..
Проверим расположение:
Как мы видим, данное расположение полностью удовлетворяет условиям задачи.
Размещено на Allbest.ru
...Подобные документы
Задача о восьми ферзях как широко известная задача по расстановке фигур на шахматной доске. Характеристика алгоритмов решения задачи для доски 8х8. Рассмотрение особенностей программы, использующей алгоритм Лас-Вегаса, проведения статистического анализа.
контрольная работа [382,3 K], добавлен 06.08.2013Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация [441,5 K], добавлен 19.10.2014Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.
курсовая работа [2,0 M], добавлен 12.02.2013Методика и основные этапы разработки программы, которая бы наглядно продемонстрировала варианты размещения ферзей на шахматной доске, удовлетворяя правилам задачи. Исследование свойств расстановок мирных ферзей. Написание текста программы и ее листинг.
контрольная работа [81,1 K], добавлен 29.04.2011Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
курсовая работа [586,3 K], добавлен 04.04.2015Составление алгоритма и разработка в среде программирования Delphi 7 программы, вычисляющей макроэкономические индексы цен. Реализация программы в виде 4 форм и 1 диалогового окна. Описание алгоритма решения задачи. Текст программы, руководство оператора.
курсовая работа [1,4 M], добавлен 04.06.2013Основные принципы разработки программ. Разработка алгоритма решения задачи о пересечении двухвыпуклым многоугольником. Реализация разработанного алгоритма на языке программирования. Тесты для проверки работы программы. Графическая иллюстрация решения.
курсовая работа [53,3 K], добавлен 20.11.2015Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.
курсовая работа [2,5 M], добавлен 22.11.2012Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи.
курсовая работа [713,3 K], добавлен 19.10.2012Описание решения задачи, ее постановка, общий подход к решению. Представление исходных данных, условий задачи и целей ее решения. Составление алгоритма решения поставленной задачи. Написание программного обеспечения и тестирование конечного продукта.
курсовая работа [1,1 M], добавлен 03.07.2011Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
курсовая работа [1000,7 K], добавлен 23.06.2012Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Основные аналитические соотношения. Блок схемы и алгоритм решения задачи. Проверка работоспособности алгоритма вручную. Таблица идентификации переменных. Формы входной и выходной печати. Разработка и отладка программы. Инструкция для работы с программой.
курсовая работа [69,8 K], добавлен 13.02.2012Основные этапы создания алгоритмов, представление в виде программы. Рассмотрение методов решения задач. Метод поэтапных уточнений. Различие между численными и логическими алгоритмами. Реализация цикла со счетчиком. Процесс разработки сложного алгоритма.
презентация [1,3 M], добавлен 22.10.2013Определение понятия алгоритмов, принципы их решения людьми и всевозможными техническими устройствами. Применение компьютера для решения задач. Особенности использования метода последовательного укрупнения при создании шахматной доски по алгоритму.
презентация [1,1 M], добавлен 06.02.2012Составление программы на алгоритмическом языке Turbo Pascal. Разработка блок-схемы алгоритма её решения. Составление исходной Pascal-программы и реализация вычислений по составленной программе. Применение методов Рунге-Кутта и Рунге-Кутта-Мерсона.
курсовая работа [385,0 K], добавлен 17.09.2009Оценка погрешности и точности в математике. Составление программы и алгоритма для численного дифференцирования с заданной допустимой погрешностью на алгоритмическом языке Turbo Pascal 7.0. Составление алгоритма и программы аппроксимации функции.
курсовая работа [810,6 K], добавлен 24.03.2012Содержание термина "планирование эксперимента". Сущность метода наименьших квадратов. Разработка программы анализа статистической оценки качества проектируемой системы: составление и графическое представление алгоритма решения, листинг программы.
курсовая работа [4,1 M], добавлен 16.09.2011Особенности разработки программы и выбор методов решения задачи. Составление алгоритма, распределение регистров программы и формирование файлов. Описание процедуры очистки памяти, сложения, вычитания, умножения. Тестирование и листинг программы.
лабораторная работа [51,2 K], добавлен 14.05.2011
