|
Реферат: Аппроксимация (Компьютеры)
Министерство общего и профессионального образования Российской Федерации
Московский Государственный Строительный Университет
Кафедра информатики и прикладной математики
КУРСОВАЯ РАБОТА ПО ИНФОРМАТИКЕ
на темы:
1. Аппроксимация.
2. Разработка модуля исключения нуль-уравнений в комплексе “Решение
задачи линейного программирования”.
Выполнил студент ЭОУС – I – 2: Моносов А. Л.
Преподаватель: доцент Марьямов А. Г.
Москва 1999.
Оглавление.
I. Математическая часть. Название…………………………………3.
1.1 Постановка задачи………………………………………………….3.
2.1 Изложение метода………………………………………………….4.
3.1 Блок-схема алгоритма. Описание исходных данных и
результатов………………………………………………………………5.
4.1 Листинг программы, исходных данных и результатов……………6.
5.1 Список переменных основной программы………………………10.
6.1 Заголовки процедур и функций. Список их переменных……….10.
7.1 Ручной расчет……………………………………………………..11.
8.1 Обсуждение результатов с целью доказательства правильности алгоритма
и программы………………………………………………..12.
9.1 Выводы…………………………………………………………….13.
II. Экономическая часть. Название………………………………..14.
1.2 Постановка задачи линейного программирования и задание на разработку
модуля……………………………………………………...14.
2.2 Описание исходных данных и результатов решения задач линейного
программирования………………………………………...18.
3.2 Описание модуля типов…………………………………………..19.
4.2 Укрупненная блок-схема задачи линейного программирования..20.
5.2 Параметры и заголовки процедур задачи линейного
программирования……………………………………………………..21.
6.2 Блок-схема и параметры реализованной процедуры……………21.
7.2 Листинг модуля, исходных данных и результатов машинного
расчета………………………………………………………………….23.
8.2 Ручной расчет задачи линейного программирования…………...24.
9.2 Выводы…………………………………………………………….26.
Список использованной литературы. ……………………………..27.
I. Математическая часть. Аппроксимация.
1. Постановка задачи.
Пусть величина y является функцией аргумента x. Это означает, что любому
значению x из области определения поставлено в соответствии значение y.
Вместе с тем на практике часто неизвестна явная связь между y и x, т.е.
невозможно записать эту связь в виде y=f(x). В некоторых случаях даже при
известной зависимости y=f(x) она настолько громоздка (например, содержит
трудно вычисляемые выражения, сложные интегралы и т.п.), что ее
использование в практических расчетах затруднительно.
Наиболее распространенным и практически важным случаем, когда вид связи
между параметрами x и y неизвестен, является задание этой связи в виде
некоторой таблицы {xi yi}. Это означает, что дискретному множеству значений
аргумента {xi} поставлено в соответствие множество значений функции {yi}
(i=0,1…n). Эти значения - либо результаты расчетов, либо экспериментальные
данные. На практике нам могут понадобиться значение величины y и в других
точках, отличных от узлов xi. Однако получить эти значения можно лишь путем
очень сложных расчетов или провидением дорогостоящих экспериментов.
Таким образом, с точки зрения экономии времени и средств мы приходим к
необходимости использования имеющихся табличных данных для приближенного
вычисления искомого параметра y при любом значении (из некоторой области)
определяющего параметра x, поскольку точная связь y=f(x) неизвестна.
Этой цели и служит задача о приближение (аппроксимации) функций: данную
функцию f(x) требуется приближенно заменить (аппроксимировать) некоторой
функцией g(x) так, чтобы отклонение (в некотором смысле) g(x) от f(x) в
заданной области было минимальным. Функция g(x) при этом называется
аппроксимирующей.
Для практики весьма важен случай аппроксимации функции многочленом:
g(x)=a0+a1x+a2x2+…+amxm (2.1)
При этом коэффициенты aj будут подбираться так, чтобы достичь
наименьшего отклонения многочлена от данной функции.
Если приближение строиться на заданном множестве точек {xi}, то
аппроксимация называется точечной. К ней относятся интерполирование,
среднеквадратичное приближение и др. При построении приближения на
непрерывном множестве точек (например, на отрезке [a,b] аппроксимация
называется непрерывной или интегральной).
2.1 Изложение метода (Точечная аппроксимация).
Одним из основных типов точечной аппроксимации является
интерполирование. Оно состоит в следующем: для данной функции y=f(x) строим
многочлен (2.1), принимающий в заданных точках xi те же значения yi, что и
функция f(x), т.е. g(xi)=yi, i=0,1,…n.
При этом предполагается, что среди значений xi нет одинаковых, т.е.
xi(xk при этом i(k. Точки xi называются узлами интерполяции, а многочлен
g(x) - интерполяционным многочленом.
Рис. 1
Таким образом, близость интерполяционного многочлена к заданной функции
состоит в том, что их значения совпадают на заданной схеме точек (рис.1,
сплошная линия).
Максимальная степень интерполяционного многочлена m=n; в этом случае
говорят о глобальной интерполяции.
При большом количестве узлов интерполяции получается высокая степень
многочлена (2.1) в случае глобальной интерполяции, т.е. когда нужно уметь
один интерполяционный многочлен для всего интервала изменения аргумента.
Кроме того, табличные данные могли быть получены путем измерений и
содержать ошибки. Построение аппроксимируемого многочлена с условием
обязательного прохождения его графика через эти экспериментальные точки
означало бы тщательное повторение допущенных при измерениях ошибок. Выход
из этого положения может быть найден выбором такого многочлена, график
которого проходит близко от данных точек (рис.1, штриховая линия).
Одним из таких видов является среднеквадратичное приближение функции с
помощью многочлена (2.1). При этом m ( n; случай m = n соответствует
интерполяции. На практике стараются подобрать аппроксимирующий многочлен
как можно меньшей степени (как правило, m=1, 2, 3).
Мерой отклонения многочлена g(x) от заданной функции f(x) на множестве
точек (xi,yi) (i=0,1,…,n) при среднеквадратичном приближении является
величина S, равная сумме квадратов разности между значениями многочлена и
функции в данных точках:
n
S = ([g(xi)-yi]2
i=0
Для построения аппроксимирующего многочлена нужно подобрать коэффициенты
a0, a1,…,am так, чтобы величина S была наименьшей. В этом состоит метод
наименьших квадратов.
n
dS/da1=2([ g(xi)-yi]2*1=0;
i=1
n
dS/da2=2([ g(xi)-yi]2*xi=0;
i=1
…
n
dS/dam+1=2([ g(xi)-yi]2*xim=0.
i=1
C
A B
|n |( xi |… |( xim | |a1 | |(yi |
|( xi |( xi2 |… |( | |a2 | |(yixi |
| | | |xim+1 | | | | |
|… |…… |… |…… | |… | |… |
|( xim|( |… |( xi2m| |am+1| |(yixim|
| |xim+1 | | | | | | |
3.1 Блок-схема алгоритма. Описание исходных данных и результатов.
Исходные данные, а именно:
m-число узлов аппроксимации.
n - степень аппроксимирующего многочлена.
X - вектор узлов аппроксимации.
Y - вектор значений аппроксимируемой функции.
Все эти значения мы заносим в файл jan.dat, который работает только на
чтение и файловой переменной является f1.
Результаты:
Все результаты выводятся в файл jan.res, работающий на запись и имеющий
файловую переменную f2.
Первоначально в этот файл выводятся исходные данные, которые берутся из
файла jan.dat, но при этом уже с описанием, то есть не просто числа, а
скоментарием, что они означают.
Затем выводятся результаты вычисления, проведенной машиной, при этом все
результаты отформатированы:
Выводится матрица С системы линейных уравнений для аппроксимации вместе
с вектором правых частей. Затем выводится решение этой системы уравнений,
что является вектором коэффициентов аппроксимирующего многочлена по
возрастанию степени. И в конце выводится вектор погрешности аппроксимации
Z.
4.1 Листинг программы, исходных данных и результатов.
program approx;
uses crt,gausstpu;
const nm=20;
type vect1=array[1..nm] of real;
var c:matr;
a,b:vect;
x,y,z:vect1;
n,i,j,m:integer;
f1,f2:text;
procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);
var i,j:integer;
r:vect;
begin
for i:=1 to n do
r[i]:=1;
for j:=1 to m+1 do begin
c[1,j]:=0;
b[j]:=0;
for i:=1 to n do begin
c[1,j]:=c[1,j]+r[i];
b[j]:=b[j]+r[i]*y[i];
end;
for i:=1 to n do
r[i]:=r[i]*x[i];
end;
for i:=1 to m do begin
for j:=1 to m do
c[i+1,j]:=c[1,j+1];
c[i+1,m+1]:=0;
for j:=1 to n do
c[i+1,m+1]:=c[i+1,m+1]+r[j];
for j:=1 to n do
r[j]:=r[j]*x[j];
end;end;
begin
assign(f1,'jan.dat');reset(f1);
assign(f2,'jan.res');rewrite(f2);
readln(f1,n);writeln(f2,'Число узлов аппроксимации n=',n:3);
readln(f1,m);writeln(f2,'Степень многочлена m=',m:2);
writeln(f2,'Вектор узлов аппроксимации x[i]');
for i:=1 to n do begin
read(f1,x[i]);
write(f2,x[i]:4:2,' ');
end;
writeln(f2);
writeln(f2,'Вектор значений аппроксимируемой функции y[i]');
for i:=1 to n do begin
read(f1,y[i]);
write(f2,y[i]:4:2,' ');
end;
Create_BC(n,m,x,y,c,b);
writeln(f2);
writeln(f2,'Матрица системы линейных уравнений для аппроксимации и вектор
правых частей);
for i:=1 to m+1 do begin
for j:=1 to m+1 do
write(f2,c[i,j]:8:1);writeln(f2,b[i]:8:1);end;
gauss(m+1,c,b,a);
for i:=1 to n do begin
z[i]:=0;
for j:=m+1 downto 1 do
z[i]:=z[i]*x[i]+a[j];
z[i]:=z[i]-y[i];end;
writeln(f2);
writeln(f2,'Вектор коэфициентов аппроксимирующего многочлена по
возрастанию);
writeln(f2,'степени (m+1 элементов)');
for i:=1 to m+1 do
writeln(f2,'a[',i:1,']=',a[i]:6:2);
writeln(f2,'Вектор погрешности аппроксимации в узлах X);
for i:=1 to n do
writeln(f2,'z[',i:1,']=',z[i]:5:3);
close(f1);close(f2);
end.
Исходный файл jan.dat:
10
2
1 6 0 3 8 2 12 9 2 5
9 4 13 7 3 9 3 1 4 2
Файл результатов jan.res:
Число узлов аппроксимации n=10
Степень многочлена m=2
Вектор узлов аппроксимации x[i]
1.00 6.00 0.00 3.00 8.00 2.00 12.00 9.00 2.00 5.00
Вектор значений аппроксимируемой функции y[i]
9.00 4.00 13.00 7.00 3.00 9.00 3.00 1.00 4.00 2.00
Матрица системы линейных уравнений для аппроксимации и вектор правых частей
10.0 48.0 368.0 55.0
48.0 368.0 3354.0 159.0
368.0 3354.0 33428.0 1023.0
Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени
(m+1 элементов)
a[1]= 11.66
a[2]= -2.31
a[3]= 0.13
Вектор погрешности аппроксимации в узлах X
z[1]=0.479
z[2]=-1.381
z[3]=-1.343
z[4]=-1.070
z[5]=-1.247
z[6]=-1.430
z[7]=-0.244
z[8]=0.723
z[9]=3.570
z[10]=1.454
5.1 Список переменных основной программы.
В основной программе используются раздел констант и типов:
const nm=20;
type vect1=array[1..nm] of real;
Следующие переменные так же используются в программе, которые описываются в
разделе var:
|Переменная |Тип |Описание переменной |
| |переменной | |
|С |matr |Матрица системы линейных уравнений |
| | |для аппроксимации |
|А |vect |Вектор коэфициентов аппроксимирующего|
| | |многочлена по возрастанию степени |
| | |(m+1 элементов) |
|Х |vect1 |Вектор узлов аппроксимации |
|B |vect |Вектор правых частей |
|Y |vect1 |Вектор значений аппроксимирующей |
| | |функции |
|Z |vect |Вектор погрешности аппроксимации в |
| | |узлах Х |
|n |integer |Число узлов аппроксимации |
|m |integer |Степень многочлена |
|i |integer |Необходима для нумерации элементов |
| | |массивов. |
|j |integer |Необходима для нумерации элементов |
| | |массивов. |
|f1 |text |Файловая переменная для файла |
| | |исходных значений |
|f2 |text |Файловая переменная резуртирующего |
| | |файла |
6.1 Заголовки процедур и функций. Список их переменных.
В своей программе я использовал следующие модули, которые описываются в
операторе uses и процедуры:
Crt - стандартный модуль подключения экрана и клавиатуры для работы с
программой.
Gauss - процедура решения системы линейных уравнений методом Гаусса. Она
берется из модуля Gausstpu, где интерфейсная часть имеет вид:
Interface
Const nmax=20
Type
Поэтому при объявлении матрицы С ссылаться надо на matr, а векторов A и B
на vect.
Create_BC - процедура расчета матрицы С (С - матрица системы линейных
уравнений для аппроксимации). Заголовок этой процедуры выглядит так:
procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);
var i,j:integer;
r:vect;
А вот такие переменные используются только в этой процедуре, остальные
засылаются из основной программы:
|Переменная |Тип |Описание переменной |
| |переменной | |
|i |integer |Используются в циклах для перебора |
| | |численных значений |
|j |integer |Используются в циклах для перебора |
| | |численных значений |
|R |vect |Рабочий вектор |
7.1 Ручной счет.
Составляем матрицу системы уравнений по следующему принципу:
|n |(xi |(xi2|(yi |
|(xi |(xi2|(xi3|(xiyi|
|(xi2 |(xi3|(xi4|(xi2y|
| | | |i |
Для этого вычисляем необходимые значения:
n=10;
(xi=1+6+0+3+8+2+12+9+2+5=48;
(xi2=12+62+02+32+82+22+122+92+22+52=368;
(yi=9+4+13+7+3+9+3+1+4+2=55;
(xi3=13+63+03+33+83+23+123+93+23+53=3354;
(xiyi=1*9+6*4+0*13+3*7+8*3+2*9+12*3+9*1+2*4+5*2=159;
(xi3=14+64+04+34+84+24+124+94+24+54=33428;
(xi2yi=12*9+62*4+02*13+32*7+82*3+22*9+122*3+92*1+22*4+52*2=1023.
Получается следующая матрица:
|10 |48 |368 |55 |
|48 |368 |3354 |159 |
|368 |3354 |33428 |1023|
Которая эквивалентна такой системе уравнений:
10a1 + 48a2 + 368a3 = 55
48a1 + 368a2 + 3354a3 = 159
368a1 + 3354a2 + 33428a3 = 1023
Мы решаем эту систему уравнений методом Гаусса:
|10 |48 |368 |55 |
|0 |137,6 |1587,6 |-105 |
|0 |1587,6|19885,6 |-1001 |
|10 |48 |368 |55 |
|0 |137,6|1587,6 |-105 |
|0 |0 |1568,203488|210.4680233 |
Получаем упрощенную систему уравнений:
1568,203488a3 = 210,4680233
137,6a2 + 1587,6a3 = -105
10a1 + 48a2 + 368a3 = 55
Решая которую получаем следующие окончательные значения, которые
являются ответом:
a3=210,4680233/1568,203488=0,134209638
a2=(-105-1587,6 a3)/137,6=-2,311564115
a1=(55-48a2-368a3)/10=11,65659307
8.1 Обсуждение результатов с целью доказательства правильности алгоритма и
программы.
Полученные результаты показывают, что алгоритм и программа составлены
верно, так как значения полученные при ручном счете близки к машинным
вычислением.
9.1 Выводы.
Данная программа очень эффективна, так как машина выполняет все действия
гораздо быстрее, чем человек при ручном счете. Так же во время ручного
счета могут произоити ошибки, что приведет к повторному перещитыванию, а у
машины, при правильном алгоритме, таких сбоев не бывает (если только
"зависает"). Следовательно эта программа во многом облегчает жизнь
человеку.
II. Экономическая часть. Разработка модуля исключения нуль-уравнений в
комплексе “Решение задачи линейного программирования”.
1.2 Постановка задачи линейного программирования и задание на разработку
модуля.
Рассмотрим задачу оптимального планирования производства [1]. Пусть
предприятие выпускает n изделий, для производства которых используется m
ингредиентов. Ингредиенты это – детали определенного сортамента, станки,
работники, электроэнергия и т.д., иначе говоря, все что требуется для
осуществления производственного цикла. Запасы ингредиентов задаются
вектором b=(b1, b2,…, bm ), где bi - запас i-го ингридиента (i=1,…,m).
Задана матрица А, элемент которой aij определяет расход i-го ингридиента
для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан
вектор рыночных цен изделий p=(p1, p2,…, pn), где p - цена j-го изделия
(j=1,…,n).
Требуется составить такой план производства х=(х1, х2,…, хn), чтобы при
выполнение условий
|a11x1 + a12x2 + … + a1nxn (|
|b1 |
|a21x1 + a22x2 + … + a2nxn (|
|b2 |
|…………………………….……………………. |
|am1x1 + am2x2 + … + amnxn (|
|bm |
|xj ( 0, (j=1,…,n). |
достигался максимум функции
Z= p1x1 + p2x2 + … + pnxn
Функция Z называется целевой.
i-е ограничение из (1) означает, что нельзя израсходовать i-го
ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество
(. Переменные, удовлетворяющие условию xj(0, называются несвободными. В
нашей задаче это означает, что при xj=0 - ничего не производится или при
xj>0 производится некоторое количество изделий.
Переменные, на которые условия неотрицательности не накладываются,
называются свободными.
Задача (1)-(1') и есть задача оптимального производственного
планирования, решение которой обеспечивает достижение в конкретных условиях
максимальной прибыли.
Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов
по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в
задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для
производства тех же n изделий. При этом количество приобретаемых
ингридиентов определяется вектором b=(b1, b2, …, bm). Задана та же матрица
А, элемент которой aij определяет расход i-го ингридиента для производства
j-го изделия. Кроме того задан вектор цен p=(p1, p2, …, pn) на продукцию
предприятия. Требуется отыскать вектор цен ингридиентов u=(u1, u2, …, um),
где ui - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись
условия:
|a11u1 + a21u2 + … + am1um (|
|p1 |
|a12u1 + a22u2 + … + am2um (|
|p2 |
|…………………………….……………………. |
|a1nu1 + a2nu2 + … + amnum (|
|pn |
|ui ( 0, (i=1,…,m) |
при достижении минимума целевой функции
W=b1u1 + … + bmum
j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на
производство j-го изделия, не меньше рыночной цены этого изделия.
Условие несвободности uj(0 означает, что j-й ингредиент либо бесплатен
(uj=0), либо стоит положительное количество рублей (uj >0).
Опорным решением задачи (1)-(1') называется точка множества (, в которой
не менее чем n ограничений из (1) обращается в верное равенство. Это - так
называемая, угловая точка множества. Для n=2 это - вершина плоского угла.
Опорным решением задачи (2)-(2') называется точка, в которой не менее
чем m ограничений из (2) обращается в верное равенство.
В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В
задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не
является.
Опорное решение, доставляющее максимум функции (1') или минимум функции
(2') называется оптимальным. В работе [1] показано, что оптимальное решение
можно всегда искать среди опорных решений.
Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и
равенства. Тогда условимся писать эти равенства первыми. Если их количество
равно k, то область ( запишется в виде:
|a11x1 + a12x2 + … + a1nxn = |
|b1 |
|…………………………….……………………… |
|ak1x1 + ak2x2 + … + aknxn = |
|bk |
|ak+1, 1x1+ak+1, 2x2+…+ak+1, n|
|xn(bk+1 |
|…………………………….……………………… |
|am1x1 + am2x2 + … + amnxn ( |
|bm |
|xj ( 0, (j=1,…,n) |
Требуется найти максимум функции
Z=p1x1 + p2x2 + … + pnxn
В общем случае среди переменных xj могут быть свободные. Номера
свободных переменных будем хранить в отдельном массиве.
При формировании двойственной задачи к задаче (3)-(3') i-му ограничению
- равенству будет соответствовать свободная переменная ui (i=1,…,k), а
свободной переменной xj ограничение - равенство:
a1j u1 + a2j u2 + … + amj um =pj
Введем вспомогательные переменные yi(0 (i=1,…,n) и запишем ограничения
(3) и функцию Z в виде:
|0 = a11 (-x1) + a12 (-x2) + … + a1n |
|(-xn) + a1, n+1 |
|…………………………………………………….……………………………………… |
|0 = ak1 (-x1) + ak2 (-x2) + … + akn|
|(-xn) + ak, n+1 |
|yk+1 = ak+1, 1 (-x1) + ak+1, 2(-x2)+ … + ak+1, |
|n(-xn) + ak+1, n+1 |
|…………………………………………………….……………………………………… |
|ym = am1 (-x1) + am2 (-x2) + … + amn(-xn) |
|+ am, n+1 |
|Z = am+1, 1 (-x1) + am+1, 2(-x2)+ … + am+1, |
|n(-xn) + am+1, n+1 |
Условие несвободности отдельных или всех переменных здесь не отмечено.
Обозначения:
ai, n+1 = bi (i=1, …, m),
am+1, j = -pj (j=1, …, n)
am+1, n+1 = 0.
Таким образом, матрицу а мы дополнили столбцом свободных членов и
строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на
противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:
Прямая задача Таблица 1
| |-x1 |-x2 | |-xn |1 |
|0 = |a11 |a12 |… |a1n |a1, n+1|
|…… |…………………………… |……… |
|0 = |.. |ak, n+1|
|yk+1 =|ak1 |ak2 |… |akn |ak+1, |
| | | | | |n+1 |
|…… |ak+1, 1|ak+1, 2|… |ak+1,|……… |
| | | | |n | |
|ym = |…………………………… |……… |
| |am1 |am2 |… |amn |am, n+1|
|Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | |n |n+1 |
Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.
Прямая и двойственная задачи Таблица 2
| | |v1 = |v2 = | |vn = |W = |
| | |-x1 |-x2 | |-xn |1 |
|u1 |0 = |a11 |a12 |… |a1n |a1, n+1 |
| |…… |……………...……………… |……… |
|uk |0 = |ak1 |ak2 |… |akn |ak, n+1 |
|uk+1 |yk+1 =|ak+1, 1|ak+1, 2|… |ak+1,|ak+1, |
| | | | | |n |n+1 |
| |…… |…………………………… |……… |
|um |ym = |am1 |am2 |… |amn |am, n+1 |
|1 |Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | | |n |n+1 |
vj - вспомогательные переменные двойственной задачи.
Тогда j-е ограничение из таблицы имеет вид:
vj = a1j u1 + a2j u2 + … + amj um + am+1, j ( 0, если xj ( 0
Если переменная xj свободна, то ей соответствует ограничение-равенство
двойственной задачи:
0=a1j u1 + a2j u2 + … + amj um + am+1, j
т.е. вместо vj фактически будет нуль.
Кроме того первые k переменных двойственной задачи свободны, а остальные
несвободны.
Целевая функция двойственной задачи
W= a1, n+1 u1 + a2, n+1 u2 + … + am, n+1 um + am+1, n+1
Совмещение в одной таблице прямой и двойственной задачи неслучайно.
Решая прямую задачу, мы получаем о дновременно решение двойственной задачи,
причем
max Z = min W = am+1, n+1
Сделаем замену переменных в таблице 1 , перебросив вспомогательную
переменную yr на верх таблицы со знаком минус, а основную пременную xs на
бок таблицы (ars(0). Это означает движение из вершины x=(0, …, 0) в другую
вершину многогранника ( по его ребру. Элемент аrs называется разрешающим,
строка r - разрешающей строкой, столбец s - разрешающим столбцом. Такая
замена переменных носит название модифицированных жордановых исключений
(МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или
разрешающей строке, назовем рядовыми.
2.2 Описание исходных данных и результатов решения задачи линейного
программирования.
Обсудим исходные данные (текстовой файл simp.dat) и результаты решения
задачи линейного программирования (текстовой файл simp.res). В начале файла
simp.dat расположены, так называемые, представительские данные - строковые
данные, каждое из которых распологается в файле с новой строки:
1. Строка с номером варианта,
2. Строка с русским названием модуля,
3. Строка с координатами студента (ФИО, факультет, курс, группа),
4. Строка с датой исполнения.
Далее следуют строки файла с числовыми исходными данными:
1. Управляющий вектор kl - отдельная строка состоящая из трёх чисел kl1 ,
kl2 , kl3:
kl1=0, если необходимо получить решение только прямой задачи.
kl1=1, если необходимо получить решение только двойственной задачи.
kl1=2, если необходимо получить решение обеих задач.
kl2=0, если нет свободных переменных, иначе kl2 равен числу этих нуль-
уравнений.
2. Число ограничений и переменных (отдельная строка ввода).
3. Коэффициенты расширенной матрицы a, начиная с отдельной строки ввода.
4. Вектор номеров свободных переменных, если они есть, начиная с отдельной
строки ввода.
Результаты решения зависят от значения kl .
Если kl1=0, то при благоприятном исходе это будет вектор оптимального
решения прямой задачи и оптимальное значение целевой функции. При
неблагоприятном исходе, это одно из сообщений: либо "Система ограничений
несовместна", либо "Целевая функция неограничена".
Если kl2=1, то же для двойственной задачи.
Если kl2=2, то сначала выдается решение прямой, а потом двойственной
задачи. При не благоприятном исходе сообщения справедливы только для прямой
задачи (для двойственной аналогичные сообщения не выдаются). Результаты
помещаются в файл simp.res.
3.2 Описание модуля типов.
Для задания типов и файловых переменных вводного и выводного текстовых
файлов используется модуль типов unit typesm, структура которого приведена
ниже
unit typesm;
interface
const
mmax=20; nmax=20; e=1e-5;
type
klt =array[1..3] of integer;
at =array[1..mmax+1,1..nmax+1] of real;
vec1it =array[1..nmax] of integer;
vec2it =array[1..mmax] of integer;
vec1rt =array[1..nmax] of real;
vec2rt =array[1..mmax] of real;
var
fi, fo:text;
implementation
end.
В разделе констант заданы константы nmax и mmax, задающие максимальное
число строк расширенной матрицы a без единицы, а также пороговая константа
е, используемая в модуле поиска разрешающей строки. Константа е
используется для обеспечения устойчивости алгоритма (модуль разрешающего
элемента не должен быть слишком мал, а именно, больше е).
Ниже приведена таблица фактических и формальных параметров подпрограмм
задач линейного программирования. Обозначения формальных и фактических
параметров совпадают.
|N/N |Назначение |Обозначение |Тип |
|1. |Управляющий вектор |k1 |ki1t |
|2. |Число ограничений |m |intege|
| | | |r |
|3. |Число переменных |n |intege|
| | | |r |
|4. |Матрица коэффициентов |a |at |
|5. |Вектор номеров свободных переменных |i1 |vec1it|
|6. |Отслеживающий вектор основных |p1 |vec1it|
| |переменных прямой задачи | | |
|7. |Отслеживающий вектор вспомогательных|q1 |vec1it|
| |переменных двойственной задачи | | |
|8. |Отслеживающий вектор вспомогательных|p2 |vec2it|
| |переменных прямой задачи | | |
|9. |Отслеживающий вектор основных |q2 |vec2it|
| |переменных двойственной задачи | | |
|10. |Разрешающая строка |r |intege|
| | | |r |
|11. |Разрешающий столбец |s |intege|
| | | |r |
|12. |Вектор-решение прямой задачи |x |vec1rt|
|13. |Вектор-решение двойственной задачи |u |vec2rt|
4.2 Укрупненная блок-схема задачи линейного программирования.
[pic]
5.2 Параметры и заголовки процедур задачи линейного программирования.
В основной программе используются следующие переменные, которые описаны
в разделе var:
m,n,r,s:integer;{числовые переменные целого типа}
Процедуры программы:
|N/N |Назначение |Заголовок |
|1. |Ввод и контроль исходных |input(var k1:k1t; var |
| |данных и вывод их в файл |m,n:integer; var a:at, var |
| |результатов |i1:vec1it; var p1,q1:vec1it; |
| | |var p2,q2:vec2it) |
|2. |Исключение свободных |issp(var k1:k1t; m,n:integer; |
| |переменных |var a:at; var i1,p1,q1:vec1it;|
| | |var p2,q2: vec2it) |
|3. |Исключение нуль-уравнений |isnu(var k1:k1t; m,n:integer; |
| | |var a:at; var p1,q1:vec1it; |
| | |var p2,q2: vec2it) |
|4. |Поиск опорного решения |opor(m,n:integer; var a:at; |
| | |var p1,q1:vec1it; var p2,q2: |
| | |vec2it) |
|5. |Поиск оптимального решения |optim(m,n:integer; var a:at; |
| | |var p1,q1:vec1it; var p2,q2: |
| | |vec2it) |
|6. |Вывод решения прямой задачи|outp(m,n:integer; var a:at; |
| | |var p2: vec2it; x:vec1rt) |
|7. |Вывод решения двойственной |outd(m,n:integer; var a:at; |
| |задачи |var q1: vec1it; u:vec2rt) |
|8. |МЖИ |mji ( m,n:integer; var a:at; |
| | |r,s:integer) |
|9. |Поиск разрешающей строки |nstro(m,n:integer; var a:at; |
| | |r,s:integer var p2:vec2it) |
6.2 Блок-схема и параметры реализованной процедуры.
Обращащение: isnu(k1,m,n,a,p1,q1,p2,q2). Используются модули typesm,
mjim.
Параметры подпрограммы isnu:
|Наименование |Обозначение |
|Число ограничений |m |
|Число переменных |n |
|Матрица задачи |a |
|Отслеживающие векторы |p1, q1, p2, q2 |
В итоге успешной работы алгоритма все нуль-уравнения будут исключены, и
в отслеживающем векторе p1 это будет отмечено как -1, что даст возможность
в дальнейшем соответствующие столбцы матрицы А при выборе разрешающего
элемента не трогать. Если же алгоритм применить нельзя, то будет выдано
сообщение (см. блок-схему), и работа программы закончится.
7.2 Листинг модуля, исходных данных и результатов машинного расчета.
unit isnum;
interface
uses typesm,mjim;
procedure isnu(var k1:k1t;m,n:integer; var a:at;
var p1,q1:vec1it; var p2,q2:vec2it);
implementation
procedure isnu;
var p:real;k,s,r,j,t:integer;
begin
for r:=1 to k do begin
if p2[r]0 then begin
if abs(a[r,j])>p then begin p:=abs(a[r,j]);s:=j;end;
end;end;
if p=0 then begin writeln(fo,'Исключить r',r:6,'-ое нуль-уравнение
нельзя');
close(fi);close(fo);halt end;
mji(m,n,a,r,s);
p2[r]:=p1[s];p1[s]:=-1;
t:=q2[r];q2[r]:=q1[s];q1[s]:=t;
end;
end.
Исходный файл simp.dat:
12
Исключение нуль-уравнений
Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.
12.05.98
2 2 0
5 3
-2 -1 1 -2
1 -1 0 -1
-1 -1 0 -2
0 1 0 2
2 1 0 4
4 4 0 0
1 2
Файл результатов simp.res:
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ
КАФЕДРА ИНФОРМАТИКИ И ПРИКЛАДНОЙ МАТЕМАТИКИ
Лабораторная работа по информатике
Факультет ЭОУС, 2-ой семестр обучения
Решение задачи линейного программирования
Вариант 12
модуль: Исключение нуль-уравнений
Исполнил студент Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.
Дата исполнения: 12.05.98
Управляющий вектор:
2 2 0
Число ограничений: 5
Число переменных: 3
Матрица задачи
Н-р Коэффициенты Св. члены
строки
1 -2.00000 -1.00000 1.00000 -2.00000
2 1.00000 -1.00000 0.00000 -1.00000
3 -1.00000 -1.00000 0.00000 -2.00000
4 0.00000 1.00000 0.00000 2.00000
5 2.00000 1.00000 0.00000 4.00000
6 4.00000 4.00000 0.00000 0.00000
Вектор номеров свободных переменных:
1 2
Вектор решения прямой задачи:
1.00000 2.00000 3.00000
Значение целевой функции прямой задачи= 12.00000
Вектор решения двойственной задачи:
0.00000 4.00000 0.00000 8.00000 0.00000
Значение целевой функции двойственной задачи= 12.00000
8.2 Ручной расчет задачи линейного программирования.
Требуется максимизировать функцию
z=4x1+5x2
при ограничениях:
-2x1-x2+x3=-2
x1-x2( -1
- x1 - x2 ( -2
0x1+ 1x2 ( 2
2x1 + 1x2 ( 4
x3 ( 0
Коэфициенты ограничений, записанных в таком виде, переписываются со
своими знаками, в последней строке таблицы записываются коэффициенты
целевой функции с противоположными знаками. Сперва следует исключить
свободные переменные, перекинув их на бок таблицы:
| |-x1 |-x2 |-x3 |1 |
|0= |-2 |-1 |1 |-2 |
|y2= |1 |-1 |0 |-1 |
|y3= |-1 |-1 |0 |-2 |
|y4= |0 |1 |0 |2 |
|y5= |2 |1 |0 |4 |
|z= |-4 |-4 |0 |0 |
| |-x1 |-y4 |-x3 |1 |
|0= |-2 |1 |1 |0 |
|y2= |1 |1 |0 |1 |
|y3= |-1 |1 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-1 |0 |2 |
|z= |-4 |4 |0 |8 |
| |-y2 |-y4 |-x3 |1 |
|0= |-2 |3 |1 |2 |
|*x1= |1 |1 |0 |1 |
|y3= |-1 |2 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-3 |0 |0 |
|z= |4 |8 |0 |12 |
После этого следует исключить нуль-уравнение:
| | | |* | |
| |-y2 |-y4 |-y1 |1 |
|x3= |-2 |3 |1 |2 |
|*x1= |1 |1 |0 |1 |
|y3= |-1 |2 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-3 |0 |0 |
|z= |4 |8 |0 |12 |
Мы видим, что свободные члены в непомеченных строках неотрицательны,
следовательно опорное решение получено и надо перейти к поиску оптимального
решения. Находим непомеченные столбцы с отрицательными коэфициентами
целевой функции, исключая последний. У нас таких нет, поэтому оптимальное
решение получено и переходим к извлечению результатов. Для этого составим
еще одну таблицу, где содержаться переменные прямой и двойственной задач.
Для извлечения решений нужны только столбец свободных членов и строка
коэффициентов целевой функции. Поэтому внутренняя часть таблицы не
преведена.
| | |u2= |u4= |u1= |w= |
| | |-y2 |-y4 |-y1 |1 |
|v3= |x3= |-2 |3 |1 |2 |
|v1= |x1= |1 |1 |0 |1 |
|u3= |y3= |-1 |2 |0 |0 |
|v2= |x2= |0 |1 |0 |2 |
|u5= |y5= |2 |-3 |0 |0 |
|1 |z= |4 |8 |0 |12 |
В итоге получаем следующие результаты:
1. Прямая задача. Переменные прямой задачи, находящиеся сверху таблицы
равны в решении 0, а сбоку - соответствующим свободным членам:
x1=1; x2=2; x3=2.
2. Двойственная задача. Переменные двойственной задачи, находящиеся сверху
таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:
u1=0; u2=4; u3=0; u4=8; u5=0.
Значение целевых функций обеих задач zmax= wmin=12.
9.2 Выводы.
Полученные результаты при ручном расчёте совпадают с данными машинного
счёта. Это подтверждает правильность составления алгоритма и написания
программы.
Список использованной литературы.
. Турчак Л. И. "Основы численных методов".
. Марьямов А. Г. "Применение модульного способа програмирования в среде
Turbo Pascal 7.0 с целью решения полной задачи линейного
программирования".
-----------------------
C1j=C1j+Ri
Bj=Bj+Ri*Yi
C1j=0, Bj=0
Ri=1
Ввод
n, m, X, Y
Y0 Y1 . . . Yn
Y
X
X0 X1 . . . Xn
Ri=Ri*Xi
Ci+1, j=Ci, j+1
Ci+1, m+1=0
Ci+1, m+1=Ci+1, m+1 +Rj
Rj=Rj*Xj
Решение системы линейных уравнений Gauss(m+1,C,B,A)
Zi=0
Zi=Zi*Xi+Aj
Zi=Zi*Yi
K
Вывод A, Z
i=1
i=n
j=1
j=m+1
Расчет первой строки матрицы С и вектора В
i=1
i=n
i=1
i=n
i=1
i=m
j=1
j=m
j=1
j=n
j=1
j=n
i=1
i=n
j=m+1
j=1
шаг=-1
Расчет остальных строк матрицы С
(1)
(1')
(2)
(2')
(3)
(3')
(4)
{
{
{
p1(|p2r|)=-1
p2r0
|arj|>p
p=|arj| s=j
P=0
MJI(m,n,a,r,s)
p2r=p1s p1s=-1
t=q2r q2r=q1s q1s=t
B
"Искл. r-ое нуль-ур. Нельзя"
Закрыть файлы
К
r=1
r=k
да
нет
j=1
j=n
нет
нет
да
да
да
нет
=
Реферат на тему: Арифметические основы ЦВМ
АРИФМЕТИЧЕСКИЕ ОСНОВЫ ЦВМ
1.1. Системы счисления
В повседневной практике для представления чисел люди пользуются почти
исключительно десятичной системой счисления. Лишь в редких случаях
встречаются остатки других систем - римский счет, двенадцатиричная система
(часы), шестидесятиричная (минуты).
Однако система изображения чисел, которая веками складывалась
применительно к ручному труду, не позволяет получить наиболее эффективные
методы выполнения вычислений. По этой причине в вычислительной технике
применяются другие системы счисления и чаще всего - двоичная.
Введем несколько определений.
Cистема счисления - совокупность символов и правил для обозначения
чисел.
Разделяют системы счисления позиционные и непозиционные.
Непозиционная система счисления задается перечислением изображаемых в ней
значений. Позиционная система счисления характеризуется основанием и тем,
что числа, как правило, представляются несколькими разрядами (являются
многоразрядными), а вес любого разряда определяется его позицией в числе.
Oснование позиционной системы счисления определяет количество
различных цифр (символов), допустимое в системе счисления. Это же число
определяет, во сколько раз вес цифры данного разряда меньше веса цифры
соседнего старшего разряда.
Так, в десятичной системе счисления, основание которой равно 10,
различают 10 арабских цифр - 0, 1, 2, ..., 9. Следовательно, при ее
использовании для записи числа, не превышающего девяти, достаточно одной
цифры, и такое число записывается как одноразрядное. А в случае записи
числа, большего девяти, оно представляется как многоразрядное. При этом
вес каждого более старшего (расположенного слева от текущего) разряда
в десять (основание системы счисления) раз больше текущего.
Так, например, число 359 - трехразрядное, и в нем 9 - цифра разряда
единиц, 5 - цифра разряда десятков, 3 - цифра разряда сотен (в 10 раз
превышает вес разряда десятков). При этом значение трехразрядного числа 359
получается суммированием трех слагаемых : 3 сотни + 5 десятков + 9 единиц.
Общее правило определения веса разряда многоразрядного числа таково:
Если пронумеровать разряды целого числа справа налево, начиная от
0 для разряда единиц, то вес любого разряда получается возведением
основания системы счисления в степень, значение которой равно
номеру разряда.
Так, вес самого младшего разряда целых чисел равен 1, поскольку номер
разряда равен 0, а любое число, в том числе и число 10, возведенное в
нулевую степень, дает в результате единицу. Вес следующего слева разряда
равен 10 в степени 1, т.е. равен десяти, и т.д.
Это же правило справедливо и для записи дробных чисел. При этом
разрядам справа от разряда единиц, имеющего номер 0, присваиваются
отрицательные значения: -1, -2, и т.д., а их веса получаются также при
возведении основания 10 в соответствующую степень. Так, например,
вес третьего разряда в дробной части числа 42,9724 будет равен 10 в
степени (-3), т.е. равен одной тысячной.
Указанное правило можно проиллюстрировать следующим образом:
|Число |7 |5 |0 |6 |8 |, 2|5 |9 |
|Номер разряда |4 |3 |2 |1 |0 |-1 |-2 |-3 |
|Вес разряда |10000 |1000 |100 |10 |1 |0,1 |0,01 |0,001|
Как видно из примера, в позиционной системе счисления достаточно
знать значение основания системы счисления, символы, изображающие
отдельные цифры, и указанное правило, чтобы представить любое число.
В вычислительной технике широко применяют двоичную, восьмеричную и
шестнадцатиричную систему счисления.
Двоичная система счисления имеет основание 2, и, следовательно, две
разных цифры - 0 и 1; восьмеричная - восемь разных цифр - 0, 1, 2, 3, 4,
5, 6, 7, а шестнадцатиричная - шестнадцать цифр - десять арабских цифр от 0
до 9 и еще шесть символов -
А (цифра, изображающая десять), D (цифра тринадцать),
В (цифра одиннадцать), E (цифра четырнадцать),
С (цифра двенадцать), F (цифра
пятнадцать).
Проще всего сопоставить запись одних и тех же чисел в этих системах
счисления можно с использованием таблицы 1, приведенной на следующей
странице.
Мы уже говорили о том, что современные цифровые ЭВМ все используют в
качестве основной двоичную систему счисления. К ее достоинствам
относится:
. простота выполнения арифметических и логических операций, что влечет
за собой простоту устройств, реализующих эти операции;
. возможность использования аппарата алгебры логики (булевой алгебры)
для анализа и синтеза операционных устройств ЭВМ.
К неудобствам двоичной системы счисления относится необходимость
перевода чисел из десятичной в двоичную и наоборот, а также то, что
запись числа в двоичной системе громоздка (требует большего числа разрядов,
чем привычная для человека десятичная). По этой и ряду других причин,
кроме двоичной применяются восьмеричная и шестнадцатиричная системы
счисления.
Таблица 1.1
| |
|С и с т е м а с ч и с л е н и я |
|10 | 2 |8 |16 |
|0 | 0 | 0 | 0 |
|1 | 1 | 1 | 1 |
|2 | 0 1 | 2 | 2 |
|3 | 1 1 | 3 | 3 |
|4 | 1 0 0 | 4 | 4 |
|5 | 1 0 1 | 5 | 5 |
|6 | 1 1 0 | 6 | 6 |
|7 | 1 1 1 | 7 | 7 |
|8 | 1 0 0 0 |1 0 | 8 |
|9 | 1 0 0 1 |1 1 | 9 |
|10 | 1 0 1 0 |1 2 | A |
|11 | 1 0 1 1 |1 3 | B |
|12 | 1 1 0 0 |1 4 | C |
|13 | 1 1 0 1 |1 5 | D |
|14 | 1 1 1 0 |1 6 | E |
|15 | 1 1 1 1 |1 7 | F |
|16 |1 0 0 0 0 |2 0 |1 0 |
Совместное использование указанных систем обусловлено двумя причинами:
. в восьмеричной и шестнадцатиричной системах любое число записывается
более компактно, нежели двоичное;
. простотой преобразования из двоичной в восьмеричную (шестнадцатирич-
ную) систему счисления и наоборот.
Приведем правила перевода чисел из двоичной системы в восьмеричную
(шестнадцатиричную) и наоборот.
П1 .Правило перевода “8с/с -> 2c/c”
При переводе многоразрядного числа каждую цифру исходного
восьмеричного числа представить всегда точно тремя двоичными цифрами,
взятыми из приведенной выше таблицы. При этом, если для записи
соответствующей восьмеричной цифры в виде двоичной требуется менее трех
двоичных цифр, двоичный эквивалент дополняется слева нулями (незначащие
нули не исказят значения числа). Таким образом, например, при записи
четырехразрядного восьмеричного числа должно получиться
двенадцатиразрядное двоичное. После окончания такого преобразования можно
отбросить старшие для всего числа незначащие двоичные цифры.
Отметим, что три цифры принято называть триадой. Поэтому можно
сказать, что при описываемом переводе каждая восьмеричная цифра заменяется
соответствующей ей триадой двоичных цифр.
Если исходное число дробное, т.е. имеет целую и дробную часть, то
в двоичном числе запятая ставится между триадами, представляющими
соответствующие цифры исходного числа.
Пример.
Преобразуем восьмеричное число 371,62.
Для этого запишем для каждой цифры соответствующую триаду:
3 --> 011
7 --> 111
1 --> 001
6 --> 110
2 --> 010
Теперь можно записать число в двоичной форме (для наглядности между
триадами поместим пробелы):
371,62 -> 011 111 001 , 110 010
И, наконец, запишем полученное двоичное число так, как это принято в
математике, без незначащих нулей, а также отбросив правые нули в
дробной части числа:
371,62 -> 11111001,11001
П2. Правило перевода “2с/с -> 8c/c”
При переводе многоразрядного двоичного числа в восьмеричную форму
поступают следующим образом: Исходное число разбивают на триады. При этом
для целой части числа разбиение проводят от местонахождения запятой
влево, а для дробной части - от этого же места вправо. Затем самая левая
группа при необходимости дополняется незначащими нулями до образования
триады, а самая правая группа только в дробной части дополняется нулями
справа также до образования полной триады. После этого каждая триада
заменяется соответствующей восьмеричной цифрой. Местоположение запятой
сохраняется по тем же правилам, что и в правиле П1.
Пример.
Представить двоичное число 1101100,01111101 в форме восьмеричного.
Разобьем исходное число на группы по три цифры, приняв в качестве
точки отсчета местоположение запятой (для наглядности между триадами
поместим пробелы):
1 101 100 , 011 111 01
Теперь дополним до трех цифр нулями самую левую группу слева и самую
правую группу справа:
001 101 100 , 011 111 010
И, наконец, заменим каждую триаду соответствующей восьмеричной
цифрой:
001 101 100 , 011 111 100 --> 154,372
П3. Правило перевода “16с/с -> 2c/c”
При переводе многоразрядного шестнадцатиричного числа в двоичную
форму каждую цифру исходного числа заменяют группой точно из четырех
двоичных цифр (заменяют тетрадой двоичных цифр). Местоположение запятой
сохраняется по тем же правилам, что и в правиле П1. В окончательной
записи можно отбросить самые левые (незначащие) нули и самые правые нули
дробной части.
Пример. Преобразовать шестнадцатиричное число “6C,7D” в двоичную
форму.
Для этого запишем для каждой цифры соответствующую тетраду:
6 --> 0110
C --> 1100
7 --> 0111
D --> 1101
Теперь можно записать число в двоичной форме (для наглядности между
тетрадами поместим пробелы):
6C,7D -> 0110 1100 , 0111 1101
И, наконец, запишем полученное двоичное число так, как это принято в
математике, без незначащих нулей:
6C,7D -> 1101100,01111101
П4. Правило перевода “2с/с -> 16c/c”
При переводе многоразрядного двоичного числа в шестнадцатиричную форму
поступают следующим образом. Исходное число разбивают на тетрады. При этом
для целой части числа разбиение проводят от местонахождения запятой влево,
а для дробной части от этого же места вправо. Затем самая левая группа
при необходимости дополняется незначащими нулями до образования тетрады, а
самая правая группа только в дробной части дополняется нулями справа
также до образования полной тетрады. После этого каждая тетрада
заменяется соответствующей шестнадцатиричной цифрой. Местоположение
запятой сохраняется по тем же правилам, что и в правиле П1.
Пример. Представить двоичное число 1101100,01111101 в форме
шест-надцатиричного.
Разобьем исходное число на группы по четыре цифры, приняв в качестве
точки отсчета местоположение запятой (для наглядности между тетрадами
поместим пробелы):
110 1100 , 0111 1101
Теперь дополним до четырех цифр нулями слева самую левую группу:
0110 1100 , 0111 1101
И, наконец, заменим каждую тетраду соответствующей шестнадцатиричной
цифрой:
0110 1100 , 0111 1101 -> 6С,7D.
Шестнадцатиричная и восьмеричная системы счисления используются для
более компактной и удобной записи двоичных чисел.
Так, известность шестнадцатиричной системе принесло то, что с ее
использованием удобно представлять программы в кодах большинства
современных ЭВМ.
1.2. Перевод чисел из одной системы счисления
в другую
Поскольку в практической деятельности люди привыкли оперировать
десятичной системой счисления, а в ЭВМ числа представляются в двоичной,
необходимо научиться преобразовывать числа из одной системы счисления в
другую. Рассмотренные выше правила перевода из двоичной системы счисления в
восьмеричную и шестнадцатиричную и наоборот носят частный характер и
не могут быть распространены на другие системы. Здесь же мы рассмотрим
общие правила перевода, справедливые для любой пары систем счисления, хотя
и более громоздкие и трудоемкие по сравнению с рассмотренными выше.
Правила перевода целых и дробных чисел не совпадают, поэтому приведем
три правила перевода чисел из системы счисления с основанием R в систему
счисления с основанием Q.
Правило 1. Перевод целых чисел
Для перевода целого числа N, представленного в системе
счисления (с/с) с основанием R, в с/с с основанием Q необходимо данное
число делить на основание Q по правилам с/с с основанием R до
получения целого остатка, меньшего Q. Полученное частное снова
необходимо делить на основание Q до получения нового целого остатка,
меньшего Q, и т.д., до тех пор, пока последнее частное будет меньше
Q. Число N в с/с с основанием Q представится в виде не упорядоченной
последовательности остатков деления в порядке, обратном их
получению (иными словами, старшую цифру числа N дает последнее
частное).
Пример. Преобразовать десятичное число 67 в двоичную форму.
Основание исходной системы счисления R=107. Основание новой системы
счисления Q=2.
Согласно приведенному правилу надо исходное число 67 делить на
основание новой системы (на 2) по правилам десятичной системы счисления
(исходная с/с).
Поскольку процесс деления на 2 очень прост, воспользуемся следующим
приемом: в левом столбце будем писать текущие частные, а в правом - текущие
остатки от их деления на 2 (это может быть либо 0, либо 1):
67 1 При делении 67 на 2 получается частное 33 и остаток 1;
33 1 при делении 33 - частное 16 и остаток 1 и т.д.
16 0
8 0
4 0
2 0
1 1 старшая цифра
0,4486 * 2 = 0,8972 0
0,8942 * 2 = 1,7944 1
0,7944 * 2 = 1,5888 1
0,5888 * 2 = 1,1776 1
0,1776 * 2 = 0,3552 0
0,3552 * 2 = 0,7104 0
Искомое представление число 0,7243 в двоичной системе счисления
-> 0,101110.
Обратите внимание, что для получения шести цифр дроби выполнено семь
умножений
Это связано с необходимостью выполнить округление, чтобы представить
дробь заданной длины более точно.
Из последнего примера, конечная дробь в одной системе счисления
может стать бесконечной в другой. Это утверждение справедливо для всех
случаев, когда одна система счисления не может быть получена
возведением в целую степень основания другой.
Примеры.
. Десятичная дробь 0,2 представляется бесконечной дробью
0,33333... в шестнадцатиричной системе счисления (основания с/с 10 и
16).
. Шестнадцатиричная дробь 0,В1 представляется конечной дробью
0,10110001 в двоичной системе счисления (основания с/с 16 и 2).
Правило 3. Перевод неправильной дроби
Перевод неправильной дроби из одной системы счисления в другую
осуществляется отдельно для целой и дробной части по правилам, изложенным
выше.
1.3. Двоичные коды для десятичных цифр
В ряде случаев в вычислительной технике применяется не только
двоичная, но и десятичная система счисления. Однако и в этом случае для
представления десятичных цифр используется оборудование, разработанное для
представления двоичных цифр. В этом случае говорят о двоично-десятичных
кодах десятичных цифр.
Согласно формулы Хартли для представления 10 различных цифр требуется
четыре бита информации:
3 бита < I = log(10) < 4 бита.
Таким образом, при необходимости представить десять разных десятичных
цифр комбинациями двоичных цифр, каждую из них можно представить минимум
тетрадой двоичных чисел. Большинство кодов десятичных цифр использует
тетрады, хотя есть и коды, в которых для кодирования используется большее
число битов.
Наиболее распространены двоично-десятичные коды, в которых для
представления десятичных цифр используются позиционные методы кодирования.
Так, если рассматривать четыре двоичных разряда тетрады как
четырехразрядное двоичное число, то веса ее отдельных разрядов слева
направо будут равны соответственно 8, 4, 2 и 1.
Поэтому первый двоично-десятичный код, который мы рассмотрим,
обозначается как код “8421”. Его можно назвать кодом с естественными
весами.
В этом коде каждая десятичная цифра представляется ее двоичным
эквивалентом :
цифра 0 как 0000,
цифра 1 как 0001,
цифра 2 как 0010,
цифра 5 как 0101,
цифра 8 как 1000,
цифра 9 как 1001.
В то же время, имея четыре двоичных цифры, можно представить не 10,
а 16 различных комбинаций. Таким образом, при использовании кода “8421”
шесть комбинаций : 1010, 1011, ..., 1111 останутся неиспользованными,
т.е. не будут изображать ни одной из десятичных цифр. Эти комбинации
считаются запрещенными.
а) Коды с избытком
Кроме рассмотренной системы кодирования достаточно широко
используются также так называемые коды с избытком. Рассмотрим группу
кодов “8421” с избытком”.
Код “8421” с избытком W” строится по следующим правилам:
При кодировании десятичной цифры, к ней вначале прибавляют W, и
затем полученное число представляют как двоичное в коде “8421”.
Значение W может быть равным 1, 2, 3, 4, 5 или 6. При любом значении
избытка W шесть из шестнадцати комбинаций останутся неиспользованными.
Только для разных избытков эти значения будут разными.
Пример. Рассмотрим код “8421” с избытком 3”.
а)Представим цифру 8 в данном коде.
Вначале увеличим 8 на 3. Получится 11.
Затем запишем 11 в коде “8421”. Получится 1011.
Число 1011 и есть представление цифры 8 в данном коде.
б)Восстановим цифру, которая изображается комбинацией 0101.
Вначале представим десятичное число, рассматривая комбинацию 0101, как
его изображение в коде “8421”. Получится число 5.
Затем вычтем из него (из 5) избыток 3. Получится 2.
Это и есть искомый ответ: Комбинация 0101 изображает десятичную цифру 2
в коде “8421” с избытком 3”.
в)Восстановим цифру, которая изображается комбинацией 1110.
Восстановим десятичное число. Получится 14.
Вычтем из него избыток 3. Получится 11.
Поскольку 11 не является десятичной цифрой (это двухразрядное десятичное
число), делаем вывод, что комбинация 1110 не изображает никакой
десятичной цифры и является запрещенной.
б) Код “2421”
Кроме кодов с естественными весами разрядов применяются и другие.
Одним из широко известных кодов является позиционный код, построенный с
использованием тетрады двоичных цифр, веса которых слева направо равны
соответственно : 2, 4, 2 и 1.
Представим коды цифр в таблице:
|Цифра |Код “2421” |Цифра |Код “2421” |
|0 | 0000 |5 | 0101 или 1011|
|1 | 0001 |6 | 0110 или 1100|
|2 | 0010 или 1000|7 | 0111 или 1101|
|3 | 0011 или 1001|8 | 1110 |
|4 | 0100 или 1010|9 | 1111 |
Как видно из таблицы, ряд десятичных цифр могут быть представлены
двумя не совпадающими двоичными комбинациями.
Например, комбинации 0100 и 0010 изображают цифру 2, комбинации 1010
и 0100 изображают цифру 4 и т.д. Отличительной особенностью данного кода
является то, что в нем нет неиспользованных (запрещенных) комбинаций.
в) Код “2 из 5”
Данный код принадлежит к непозиционным кодам. Как и все непозиционные
| |
