Программное представления действительных чисел рациональными дробями - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Программное представления действительных чисел рациональными дробями - страница №1/1

Программное представления действительных чисел рациональными дробями
Нередко возникает необходимость представлять конечный результат численных расчетов или какие-либо промежуточные значения не в виде действительного числа (десятичной дроби), а в виде рационального числа (обыкновенной дроби). В данной статье рассматривается два алгоритма представления действительного числа обыкновенной дробью. Для определенности используем десятичную систему счисления. Все множество десятичных дробей можно поделить на два подмножества: множество конечных десятичных дробей, множество бесконечных десятичных дробей. К последнему подмножеству относятся десятичные периодические дроби и иррациональные числа (дроби).

Рациональную дробь будем представлять в виде структуры (записи, если используете Pascal/Delphi), состоящей из трех полей: целочисленное поле для хранения значения числителя дроби, целочисленное поле для хранения значения знаменателя дроби и поле типа AnsiString, хранящее в себе символ знака минус, если число отрицательное или символ пробел, если число положительное:


Листинг 1. Структура рационального числа
struct RatFrac

{

int num; //числить дроби



int denom; //знаменатель дроби

AnsiString sign; //знак перед числителем

};
Так как мы будем использовать стандартный целочисленный тип int, то нужно позаботиться о том, чтобы у нас не было выхода за диапазон этого типа. Для этого дроби с 8 знаками после десятичного разделителя и меньше будем считать конечными. А дроби с числом десятичных знаков больше 8 после десятичного разделителя будем считать бесконечными. Таким образом, бесконечные десятичные дроби мы будем приближать с точностью 10^-8. Еще нам понадобятся две функции, представленные в листинге 2:
Листинг 2.
//Функция нахождения НОД двух натуральных чисел

int NOD(int a, int b)

{

while (a!=b)

{

if (a>b) a=a-b;

else b=b-a;

}

return a;

}

//Функция нахождения числителя



int Numerator(AnsiString s)

{

AnsiString buf; //1



int i,k;

for (i = 1; i < s.Length() ; i++) 

{

if (s[i]==',')

{

k=i;


break;

}

}



buf=s.SubString(k+1,s.Length()); //2

return StrToInt(buf); //3 

}
Первая из них находит НОД числителя и знаменателя, а вторая преобразует строку символов после десятичного разделителя в числитель еще несокращенной обыкновенной дроби. Принцип работы функции NOD пояснять нет необходимости. Функция Numerator в качестве своего параметра принимает строку, представляющую собой вещественное число с запятой в качестве разделителя дробной и целой части числа. Строковая переменная buf (оператор 1) предназначена для занесения в нее части строки s после символа «запятая» (оператор 2). Затем эта строка преобразуется в целое число типа int и это значение возвращается функцией (операторы 3). В листинге 3 представлена функция определения числа знаков в строке после запятой:


Листинг 3. Функция нахождения числа знаков после десятичной запятой
int NumNil(AnsiString s)

{

int buf,k;



for (int i = 1; i < s.Length() ; i++)

{

if (s[i]==',')

{

k=i;


break;

}

}



buf=s.Length()-k;

return buf;

}
Эта функция возвращает число символов после десятичного разделителя. Если это число меньше либо равно 8, то программа будет считать десятичную дробь конечной и будет применен алгоритм представления конечных десятичных дробей рациональными дробями. Но, а если больше 8, то бесконечной и будет применен алгоритм поиска подходящей рациональной дроби к действительному числу с точностью .


Листинг 4. Функция нахождения приближения рациональной дробью
AnsiString RealToRat(AnsiString s)

{

double realNum, gamma[20];



int masNum[20], masDenom[20], intPart, Num, Denum, nod, Znam;

//Массивы числителей и знаменателей подходящих дробей,

//переменные целая часть числа, числитель, знаменатель, НОД и

//знаменателя несокращенной дроби


RatFrac Frace; //Подходящая с заданной точностью дробь

int a[20]; //массив элементов разложения числа в цепную дробь

int i=1, n;

n=NumNil(s);

realNum=StrToFloat(s);

//Установка знака перед дробью



if (realNum<0) Frace.sign='-';

else

if (realNum>=0) Frace.sign=' ';

//Если число знаков после десятичного разделителя больше 8, то искать подходящую дробь



if (n>8)

{

gamma[0]=fabs(realNum);



//Алгоритм приближения действительных чисел рациональными дробями c точностью 10^-8

a[0]=floor(gamma[0]);

gamma[1]=1/( gamma[0]-a[0]);

a[1]=floor(gamma[1]);

masNum[0]=a[0]; masDenom[0]=1;

masNum[1]=a[0]*a[1]+1; masDenom[1]=a[1];

//Цикл поиска подходящих дробей

do

{

i++;



if ((gamma[i-1]-a[i-1])!=0)

{

gamma[i]=1/( gamma[i-1]-a[i-1]);



} else

if ((gamma[i-1]-a[i-1])==0) break;
a[i]=floor(gamma[i]);

masNum[i]=masNum[i-1]*a[i]+masNum[i-2];

masDenom[i]=masDenom[i-1]*a[i]+masDenom[i-2];

} while (masDenom[i-1]*masDenom[i]

//Цикл закончится, когда будут найде минимальные подходящие числитель и знаменатель

Frace.num=masNum[i-1];

Frace.denom=masDenom[i-1];


return Frace.sign+"("+IntToStr(Frace.num)+

"/"+IntToStr(Frace.denom)+")";

} else

//Если число знаков после десятичного разделителя меньше либо равно 8, то вычислить числитель и знаменатель для рационального числа



if (n<=8)

{

intPart=(int)floor(fabs(realNum));

Znam=(int)pow10(n);

Num=Numerator(s);


Frace.num=Znam*intPart+Num;

Frace.denom=Znam;


nod=NOD(Frace.num, Frace.denom);

Frace.num=Frace.num/nod;

Frace.denom=Frace.denom/nod;
return Frace.sign+"("+IntToStr(Frace.num)+

"/"+IntToStr(Frace.denom)+")";



}

}
В листинге 4 приведена основная функция, использующая все вышеописанные функции. Она находит числитель и знаменатель подходящей дроби к числу в зависимости от числа знаков после десятичного разделителя. Затем возвращает строковое представление найденной дроби в формате знак(числитель/знаменатель). Ниже представлены два скриншота программы в действии: первый для десятичной дроби с числом знаков после десятичного разделителя меньше 8, второй для числа знаков больше 8:




Заключение
Рассматриваемый в данной статье программный способ представления десятичных дробей рациональными числами хорошо применим к конечным числовым результатам, но в то же время не применим для промежуточных вычислений в силу того, что функция RealToRat возвращает строку, а не само число. Однако данный недостаток несложно устранить, изменив саму эту функцию в программе. К существенным недостаткам этого способа можно отнести следующие:


  1. Из-за ограниченности диапазона целочисленного типа int нельзя представить данным способом вещественное число с достаточно большой целой частью. Можно конечно использовать тип __int64, но и его, в конечном счете, для представления большинства вещественных чисел будет не хватать;




  1. Нет возможности данным способом представлять числа в формате с плавающей точкой (запятой).

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

Основным достоинством этого способа является реализация рационального числа в виде структуры из трех полей. Благодаря такому способу реализации рациональных чисел можно также реализовать программно и арифметические операции над ними для выполнения промежуточных результатов. Как и писалось выше, для этого нужно изменить функцию RealToRat так чтобы она возвращала не строковое представление рациональной дроби, а саму дробь. Освоившим язык С++ эта задача не покажется трудной.