Текущ брой на Списание ИнфоМан
 


USACO квалификационен кръг - октомври, SILVER Division, Задача nearfr

Уловието на задачата може да прочетете тук.

Решение

Числителят на дроб със знаменател y, която е равна на дробта a/b,е x = a*y / b(равенството се получава след привеждане под общ знаменател на a/b = x/y).Следователно най-близката до a/b дроб за даден знаменател yс числител цяло число, се получавакато вземем за числител:

·          най-голямото цяло число x1, за което x1<xили

·          най-малкото цяло число x2, за което x<x2.

Тeзи числа се намират с константна сложност O(1).

Търсената най-близка до дадената дроб има знаменател в интервала [1;32767]. Този интервал е достатъчно малък, за да се намерят x1 и x2за всеки възможен знаменател.

И така, от намерените 2*32767 на брой дроби, избираме най-близката до дадената.Това се осъщесвява с константен брой операции – c * 32767.

Забележка: Проверката започва от малките към големите знаменатели. По този начин в случаите, в които има няколко равни една на друга дроби, които са отговор на задачата – например 1/2, 2/4 и 3/6 – първо да бъде намерена съкратената дроб (1/2) и след това несъкратената няма да бъде взета предвид, защото не е по-близка. Така няма нужда от допълнително съкращаване на най-близката дроб след намирането и.

Примерна реализация


#include <stdio.h>
#include <math.h>

#define MAX_DENOM 32767

int main()
{
	int a,b;        //Nominator and denominator 
                    //of the input fraction
	int x1,x2,y;    //Nominators and denominator 
                    //of the two possible nearest fractions
	int X,Y;        //Nominator and denominator 
                    //ot the nearest fraction
	double dif = 1; //The smallest difference between fractions
	
	freopen("nearfr.in","r",stdin);
	freopen("nearfr.out","w",stdout);
	
	scanf("%d%d",&a,&b);

	//For each possible denominator the 
	//two nearest fractions are checked
	for(y=1; y <= MAX_DENOM; y++)
	{
		//x1 and x2 are determined
		if((a*y)%b!=0) 
		{
			x1 = (a*y)/b;
			x2 = x1+1;
		}
		else
		{
			x1 = (a*y)/b-1;
			x2 = x1+2;
		}
		
		//If x1/y is valid, it is compared 
		//to the nearest so far - X/Y
		if(x1>0) 
		{
			if(dif>fabs((double)a/b - (double)x1/y))	
			{
				dif = fabs((double)a/b - (double)x1/y);
				X = x1;
				Y = y;
			}
		}
		//If x2/y is valid, it is compared 
		//to the nearest fraction so far - X/Y
		if(x2<=MAX_DENOM)
		{
			if(dif>fabs((double)a/b - (double)x2/y))	
			{
				dif = fabs((double)a/b - (double)x2/y);
				X = x2;
				Y = y;
			}
		}
	}
	//The nearest fraction to a/b
	printf("%d %d\n",X,Y); 
	return 0;
}


Автор: Орлин Тенчев


обратно към текущ брой