Глава 15. Десятичные дроби

Разработка
	Глава 15. Десятичные дроби

Разработка

Наивное решение

Прежде всего извлечём числитель и знаменатель из параметра, переданного в командной строке:

Perl
my ($p, $q)=split '/', shift;

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

Perl
print int($p/$q);

if($p %= $q)
{
	print ',';
}
else
{
	print "\n";
	exit;
}

Обратим внимание на то, что ещё при проверке условия переменной $p присваивается остаток от деления $p на $q.

Оставшаяся часть программы посвящена поиску и накоплению числителей в массиве @p. Во внутреннем цикле производится поиск нового числителя ($p) в массиве. Если поиск успешен, индекс $i найденного элемента указывает на начало периодической части. В этом случае непериодическая часть превращается в цифры, которые тут же выводятся. Если $p отлична от нуля, в скобках выводятся также цифры периода. Затем, перед завершением программы, не забываем вывести символ конца строки:

Perl
my @p;
while()
{
	for(my $i=0; $i<@p; $i++)
	{
		if($p==$p[$i])
		{
			print for map { int(10*$_/$q) } @p[0..$i-1];
			if($p)
			{
				print '(';
				print for map { int(10*$_/$q) } @p[$i..$#p];
				print ')';
			}
			print "\n";
			exit;
		}
	}
	push @p, $p;
	$p=(10*$p) % $q;
}

Решение методом Черепахи и Зайца

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

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

Но это потребует совершенно ненужных вычислительных затрат. Вывести непериодическую часть десятичной дроби ничего не мешает уже во время второго забега, а период во время третьего. Действительно, непериодическую часть последовательности числителей пробегает на втором этапе Черепаха, а Заяц пробегает период на третьем.

Для организации первого забега будет удобно применить цикл с постусловием, поскольку и Черепаха, и Заяц на старте занимают одно и то же положение, и должны сделать как минимум один шаг, прежде чем программа проверит, не встретились ли они. Значения последовательности числителей, достигнутые Черепахой и Зайцем, будут храниться соответственно в переменных $t и $h:

Perl
my $t=my $h=$p;
do
{
	$t=(10*$t) % $q;
	$h=(10*$h) % $q for 0, 1;
}
until($t==$h);

Второй этап программируется довольно прямолинейно. Последовательные значения, пробегаемые Черепахой, превращаются в цифры и выводятся:

Perl
$t=$p;
until($t==$h)
{
	print int(10*$t/$q);
	$t=(10*$t) % $q;
	$h=(10*$h) % $q;
}

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

Perl
if($h)
{
	print '(';
	do
	{
		print int(10*$h/$q);
		$h=(10*$h) % $q;
	}
	until($t==$h);
	print ')';
}

Вывод символа конца строки увенчает программу:

Perl
print "\n";


Идеи реализации		Готовая программа