Ir para o conteúdo
thoga31

[Proposta] Fracção irredutível

Mensagens Recomendadas

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! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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();

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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. ;)

Editado por thoga31

Knowledge is free! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.