Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
thoga31

[Proposta] Fracção irredutível

Recommended Posts

thoga31

A fracção irredutível

Em boa matemática, devemos procurar sempre a fracção irredutível como resultado final, quando aplicável.

Não devemos deixar como resultado "10/8", mas sim "5/4".

Objectivo

Dado um input, quer em fracção, quer em decimal, devolver a fracção irredutível.

Optimizar o código para resolver o mais depressa possível. Dica: quando é dado em fracção de inteiros, trabalhá-los directamente sem a transformar num decimal.

Restrições

  • Não utilizar funções pre-existentes!
  • Aceita-se qualquer linguagem e/ou algoritmo.
  • Deverá aceitar, como visto nos exemplos 3 e 4 de input/output, o caso de se indicar entre parêntesis um algarismo repetido infinitamente.
  • O número mínimo de casas decimais para debitar uma fracção é 10, como comparando os exemplos 1 e 2.

Exemplo de input/output

1.

0.3333333333
> 1/3

2.

0.333
> 333/1000

3.

0.(3)
> 1/3

4.

0.1(6)
> 1/6

5.

10/8
> 5/4

Material de Apoio

Não aplicável.

Boas programações. :thumbsup:


Knowledge is free!

Share this post


Link to post
Share on other sites
Warrior

Por favor remove o primeiro exemplo, caso contrário é impossível sabe que arredondamento pretendes, uma vez que 0.3333333333 não é 1/3.

Share this post


Link to post
Share on other sites
thoga31

Por favor remove o primeiro exemplo, caso contrário é impossível sabe que arredondamento pretendes, uma vez que 0.3333333333 não é 1/3.

Para isto coloquei uma restrição que diz o seguinte:

O número mínimo de casas decimais para debitar uma fracção é 10, como comparando os exemplos 1 e 2.


Knowledge is free!

Share this post


Link to post
Share on other sites
Warrior

Ah, ok.

Não esperava ver isso nas restrições mas como parte do problema. Fica a nota para os mais distraídos.  (como eu)

Share this post


Link to post
Share on other sites
thoga31

Não és o primeiro B)

Eu segui as indicações no sticky desta secção, e como isso é uma restrição, ficou no fim.

Vou trocar, fica melhor isso antes do input/output. :thumbsup:

EDIT: done.


Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

Reducao em C

Tem uns atoi() e sprintf() nao verificados ... mas enfim :)

Os atoi() deveriam ser substituidos por strtol()

Os sprintf() sao mais dificeis de substituir ... mas com C99 facilmente se substituem por snprintf()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int euclid_gcd(int a, int b) {
 if (b == 0) return a;
 return euclid_gcd(b, a % b);
}

void reducesimple(char *buf,
                 int integer,
                 const char *floating)
{
 int flen = strlen(floating);
 int scale = 1;
 int gcd;
 int decimal;
 while (flen--) scale *= 10;
 decimal = atoi(floating);
 gcd = euclid_gcd(decimal, scale);
 sprintf(buf, "%d + %d/%d", integer, decimal / gcd, scale / gcd);
}

void reducerational(char *buf,
                   int numerator,
                   int denominator)
{
 int whole = numerator / denominator;
 int rest = numerator % denominator;
 int gcd = euclid_gcd(rest, denominator);
 if (!whole) {
   sprintf(buf, "%d/%d", rest / gcd, denominator / gcd);
 } else {
   sprintf(buf, "%d + %d/%d", whole, rest / gcd, denominator / gcd);
 }
}

void reducerepeating(char *buf,
                    int integer,
                    const char *floating,
                    const char *repeating)
{
 int flen, rlen;
 int num = 1, den = 1;
 int gcd;
 int fscale = 1, rscale = 9;
 int part1, part2;

 part1 = atoi(floating);
 part2 = atoi(repeating);

 rlen = strlen(repeating);
 while (--rlen) { rscale *= 10; rscale += 9; }
 flen = strlen(floating);
 while (flen--) { rscale *= 10; fscale *= 10; }

 num = part1 * rscale + fscale * part2;
 den = fscale * rscale;
 gcd = euclid_gcd(num, den);
 sprintf(buf, "%d + %d / %d", integer, num / gcd, den / gcd);
}

void reduce(char *buf, const char *expression) {
 int chk1, chk2, chk3, chk4;
 int integer, numerator, denominator;
 char floating[11], repeating[11];

 chk1 = sscanf(expression, "%d.%10[0123456789]", &integer, floating);
 chk2 = sscanf(expression, "%d/%d", &numerator, &denominator);
 chk3 = sscanf(expression, "%d.%10[0123456789](%10[0123456789])", &integer, floating, repeating);
 chk4 = sscanf(expression, "%d.(%10[0123456789])", &integer, repeating);
 if ((chk3 == 3) || (chk4 == 2)) {
   if (chk4 == 2) *floating = 0;
   reducerepeating(buf, integer, floating, repeating);
 } else {
   if (chk2 == 2) {
     reducerational(buf, numerator, denominator);
   } else {
     if (chk1 == 2) {
       reducesimple(buf, integer, floating);
     } else {
       strcpy(buf, "invalid expression");
     }
   }
 }
}

int main(void) {
 char buf[1000], src[1000];
 while (fgets(src, sizeof src, stdin)) {
   src[strlen(src) - 1] = 0;
   reduce(buf, src);
   printf("%s ==> %s\n", src, buf);
 }
 return 0;
}

Podes ver o programa a correr no ideone: https://ideone.com/ngZrS

----------------------------------------------------------------------------

Alteracao 1 (nao reflectida no ideone): onde e que eu tinha a cabeca? ???

  flen = strlen(floating);
 while (flen--) rscale *= 10;
 flen = strlen(floating);
 while (flen--) fscale *= 10;

passou a (linhas assinaladas)

  flen = strlen(floating);
 while (flen--) { rscale *= 10; fscale *= 10; }


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
KTachyon

Lex/Yacc (ou Flex/Bison) + C:

frac.l

%{
#include "y.tab.h"
#include <stdio.h>
#include <stdlib.h>
%}

%%

[0-9]                { yylval.value = atoi(yytext); return DIGIT; }
[.()\n/]            { return yytext[0]; }
.                    { printf("Invalid expression\n"); exit(0); }

%%

int yywrap() { return 1; }

frac.y:

%{
#include "functions.h"
#include <stdio.h>
#include <stdlib.h>
%}

%union {int value;}
%start statement

%token <value> DIGIT
%type <value> number

%%

statement: DIGIT '.' number '\n'                { buildFracc($1, $3, 0); exit(0); }
         | DIGIT '.' '(' DIGIT ')' '\n'            { buildFracc($1, 0, $4); exit(0); }
         | DIGIT '.' number '(' DIGIT ')' '\n'    { buildFracc($1, $3, $5); exit(0); }
         | number '/' number '\n'                { simplify($1, $3); exit(0); }
         ;
         
number   : number DIGIT                            { $$ = digitCount > 9 ? $2 : 10*$1 + $2; digitCount++; }
         | DIGIT                                { $$ = $1; digitCount++; }
         
%%

int main() {
    digitCount = 1;
    return yyparse();
}

functions.h:

int decimalDivisor(int decimal);
void buildFracc(int n, int dec, int rep);
void simplify(int num, int den);

int digitCount;

functions.c:

#include <stdio.h>
#include <stdlib.h>
#include "functions.h"

int decimalDivisor(int decimal) {
    int divisor = 1, num = decimal;
    
    while (num > 0) {
        divisor *= 10;
        num /= 10;
    }
    
    return divisor;
}

void simplify(int num, int den) {
    int min = num > den ? den : num;
    int i;
    
    for (i = 2; i <= min; i++) {
        if (((num % i)==0) && ((den % i)==0)) {
            num /= i;
            den /= i;
            i = 1;
            min = num > den ? den : num;
        }
    }
    
    printf("%d/%d\n", num, den);
}

void buildFracc(int n, int dec, int rep) {
    int den, num;
    
    if (digitCount < 10) {
        den = decimalDivisor(dec);
    }
    else if (digitCount >= 10 && rep > 0) {
        printf("Invalid expression\n");
        return;
    }
    else if (digitCount >= 10) {
        den = 1;
        rep = dec;
        dec = 0;
    }

    num = n * den + dec;
    
    if (rep > 0) {
        int rNum = rep;
        num *= 9;
        den *= 9;
        num += rNum;
    }
    
    simplify(num, den);
}


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

@pmg, foste mais além do que o pedido (excellent! B)), está muito fixe, está perfecto :thumbsup:


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Eu só hoje comecei a tentar resolver este desafio em VB.NET, mas ainda não acabei. Mas já faz o principal:

Module ConsoleFRAC

    Sub Main()
        Dim Linha As String = String.Empty
        Do
            Console.Write("Valor decimal? ")
            Linha = Console.ReadLine()
            If Linha.ToUpper = "FIM" Then
                Exit Do
            Else
                Console.WriteLine(Frac(Linha))
            End If
        Loop
    End Sub

    ''' <summary>
    ''' Retorna um valor decimal na forma fraccionária: "numerador/denominador".
    ''' </summary>
    ''' <param name="Valor">O valor decimal a ser convertido em fracção</param>
    ''' <returns></returns>
    ''' <remarks></remarks>
    Function Frac(ByVal Valor As Decimal) As String
        Dim numero As Decimal
        Dim resultado As String = String.Empty
        Try
            numero = Convert.ToDecimal(Valor)
            If Not (Math.Round(numero) = numero) Then
                Dim valido As Boolean = False
                Dim existe As Boolean = False
                Dim i As Integer = 0
                Dim j As Integer = 1
                While Not valido
                    i += 1
                    If (Math.Abs(numero) > 1) Then
                        j = 1
                    Else
                        j = i
                    End If
                    While (i / j > numero)
                        j += 1
                        If (i / j = numero) OrElse j = Integer.MaxValue Then
                            valido = True
                            existe = True
                        End If
                        resultado = Convert.ToString(i) & "/" & Convert.ToString(j)
                    End While
                    If (i = Integer.MaxValue) Then valido = True
                End While
                If existe Then
                    resultado = Convert.ToString(numero) & " = " & Convert.ToString(i) & "/" & Convert.ToString(j)
                Else
                    resultado = "Não encontrado"
                End If
            Else
                resultado = Convert.ToString(numero) & "/1"
            End If
        Catch ex As Exception
            MsgBox(ex.Message, MsgBoxStyle.OkOnly + MsgBoxStyle.DefaultButton1, "Erro")
        End Try
        Return resultado
    End Function

End Module

É o método mais tradicional, ainda tenho de desenvolver mais para que seja eficaz e eficiente, coisa que não é para já. :)


Knowledge is free!

Share this post


Link to post
Share on other sites
mjamado

Tinha algum tempo para matar antes de começar o The Big Bang Theory, e como já tinham soluções em C, cá fica uma solução em PHP (classe e forma de usar):

class FractionReduce
{
private $input;

public function __construct($in)
{
	$this->input = $in;
}

public function GetReducedFraction()
{
	$matches = array();

	if(preg_match("/(\d+)\.([\d\(\)]+)/", $this->input, $matches))
	{
		if((strlen($matches[2]) > 9) && ($matches[2] == str_repeat($matches[2][0], strlen($matches[2]))))
			$matches[2] = "(" . $matches[2][0] . ")";

		$res = $this->decToFrac($matches[2]);
		return $this->reduceFrac($matches[1] * $res[1] + $res[0], $res[1]);
	}
	elseif(preg_match("/(\d+)\/(\d+)/", $this->input, $matches))
		return $this->reduceFrac($matches[1], $matches[2]);
	else
		return false;
}

private function decToFrac($dec)
{
	$matches = array();

	if(preg_match("/(\d*)\((\d+)\)/", $dec, $matches))
	{
		$numerator = $matches[2];
		$denominator = str_repeat("9", strlen($matches[2])) . str_repeat("0", strlen($matches[1]));

		if($matches[1] > 0)
		{
			$preNumerator = $matches[1];
			$preDenominator = "1" . str_repeat("0", strlen($matches[1]));

			$numerator = $preNumerator * $denominator + $preDenominator * $numerator;
			$denominator = $preDenominator * $denominator;
		}
	}
	else
	{
		$numerator = $dec;
		$denominator = "1" . str_repeat("0", strlen($dec));
	}

	return array($numerator, $denominator);
}

private function reduceFrac($numerator, $denominator)
{
	$gcd = $this->getGCD($numerator, $denominator);
	return ($numerator / $gcd) . "/" . ($denominator / $gcd);
}

private function getGCD($num1, $num2)
{
	do
	{
		$remainder = $num1 % $num2;
		$num1 = $num2;
		$num2 = $remainder;
	}
	while($num2 > 0);

	return $num1;
}
}

$fr = new FractionReduce("0.75");
echo $fr->GetReducedFraction(); // 3/4

Não testei exaustivamente, mas acho que faz tudo o que é suposto.

Uma nota importante: como deverá ser bastante claro, usei e abusei do facto do PHP ser de tipagem dinâmica - algumas verificações pelo meio não faziam mal a ninguém, mas, hey, é só um desafio...

UPDATE: está online aqui.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
mAiN_iNfEcTiOn

Bem malta... eu bem tentei, mas não consigo perceber como obter 1/3 no 0.3333333333 (a minha arch é amd64 e portanto atinge os 17 '3' :) )

Não contempla, ainda, o caso 4 -> 0.1(6)

Vou colocar aqui o meu código... os casos fáceis (como 0.333 e 10/8) ele resolve... o problema é o resto. Tentei ao máximo não usar a "tipagem dinâmica" a que o mjamado se refere:


class Fraction
{
  protected $input = NULL;
  
  public function input( $input ) 
  {
    if( preg_match_all("(\d\.\d+)", $input, $matches) )
      $this->input = (float) $input;
    elseif( preg_match_all("((\d+)\.\((\d{1})\))", $input, $matches) )
    {
      $input = $matches[1][0];
      for($contador=1;$contador<11;$contador++);
        $input += ($matches[2][0]*pow(0.1,$contador));
    }
    elseif( preg_match_all("((\d+)\/(\d+))", $input, $matches) )
    {
      $input = (float) ($matches[1][0]/$matches[2][0]);
    }
    else
      return false;
    
    $this->input = $input;
  }

  public function getFraction( )
  {
    $decCases = 0;
    while( floor($this->input) != ceil($this->input) && ++$decCases )
      $this->input *= 10;
    
    $this->input = (int) round($this->input,10);
    $decCases = (($decCases>10) ? 10 : $decCases);
    return array($this->input,pow(10,$decCases));
  }

  public function reduceFraction( $fraction )
  {
    $numerador = $fraction[0];
    $denominador = $fraction[1];
    
    if( ($numerador > $denominador) && ( ($numerador%$denominador) == 0 ) )
      return ($numerador/$denominador) . '/1';
    elseif( ($numerador < $denominador) && ( ($denominador&$numerador) == 0 ) )
      return '1/'.($denominador/$numerador);
    else
    {
      $novo_denominador = 2;
      do
      {
        if
        ( 
          ( ($denominador%$novo_denominador) == 0 ) &&
          ( ($numerador%$novo_denominador) == 0 )
        )
          return $this->reduceFraction( array( (int) ($numerador/$novo_denominador), (int) ($denominador/$novo_denominador) ) );
          
        $novo_denominador++;
      }while( $novo_denominador<11 );
      
      return $numerador .'/'.$denominador;
    }
  }
}

$fraction = new Fraction( );
$fraction->input( 0.3333333333 );
var_dump( $fraction->reduceFraction( $fraction->getFraction() ) );

$fraction->input( 0.333 );
var_dump( $fraction->reduceFraction( $fraction->getFraction() ) );

$fraction->input( "0.(3)" );
var_dump( $fraction->reduceFraction( $fraction->getFraction() ) );

$fraction->input( "10/8" );
var_dump( $fraction->reduceFraction( $fraction->getFraction() ) );
die();

Share this post


Link to post
Share on other sites
KTachyon

Bem malta... eu bem tentei, mas não consigo perceber como obter 1/3 no 0.3333333333 (a minha arch é amd64 e portanto atinge os 17 '3' :) )

Não contempla, ainda, o caso 4 -> 0.1(6)

Como são repetições de apenas um dígito, podes utilizar múltiplos de 1/9 para obter a parte que falta que te dá a repetição. Como 1/9 = 0.(1), podes brincar com essa equação para obter todos os casos de repetição pedidos. No caso 4, por exemplo:

0.1 = 1/10

0.0(6) = 6/90 = 1/15


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

BUMP!

Lembrei-me deste desafio e decidi resolvê-lo em Python.

http://ideone.com/VtqiXe

def mdc(n, d):
   f = [i for i in range(2, max([n, d]) // 2) if n%i == d%i == 0]
   if f == []:
       return str(int(n // d)) if n % d == 0 else "{0}/{1}".format(int(n), int(d))
   else:
       return "{0}/{1}".format(int(n // max(f)), int(d // max(f))) if mdc(n // max(f), d // max(f)) == "{0}/{1}".format(int(n // max(f)), int(d // max(f))) else mdc(n // max(f), d // max(f))

def frac(n):
   n2 = n
   contador = 1
   while not int(n2) == n2:
       n2 = round(n2 + n, 10)
       contador += 1
   return mdc(int(n2), int(contador))

numero = input()

import sys
try:
   if numero.count(".") == 0 and numero.count("/") == 1:
       partes = numero.split("/")
       print(mdc(int(partes[0]), int(partes[1])))
   else:
       partes = numero.split(".")

       if len(partes[1]) == partes[1].count(partes[1][0]) >= 10:
           partes[1] = '(' + partes[1][0] + ')'

       if partes[1].count(")") == partes[1].count("(") == 1:
           if partes[1].endswith(")"):
               dec = partes[1].split("(")
               dec[1] = dec[1].strip(")")

               denominador = 9 * (len(dec[0]) * 10)
               if denominador == 0:
                   denominador = 1
               numerador = int(dec[1])
               fraccao1 = mdc(numerador, denominador).split("/")
               if dec[0] != '':
                   fraccao2 = frac(int(dec[0]) / 10).split("/")
               else:
                   fraccao2 = ['0', '1']
               if len(fraccao2) == 1:
                   fraccao2.append('1')
               if len(fraccao1) == 1:
                   fraccao1.append('9')

               print(mdc(int(partes[0]) * int(fraccao1[1]) * int(fraccao2[1]) + int(fraccao1[0]) * int(fraccao2[1]) + int(fraccao2[0]) * int(fraccao1[1]), int(fraccao1[1]) * int(fraccao2[1])))

           else:
               print("Formato invalido")
       else:
           print(frac(float(numero)))
except:
   print("Erro: {0}".format(sys.exc_info()[0]))

A dica do @KTachyon para os números com parêntesis é muito boa. Optimiza bastante o cálculo nestas situações. ;)

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.