C :: Aufgabe #240

1 Lösung Lösung öffentlich

Ägyptische Bruchrechnung

Fortgeschrittener - C von hollst - 22.12.2019 um 22:50 Uhr
Gegeben seien zwei positive Ganzzahlen Z (wie Zaehler) und N (wie Nenner) mit N > Z
und Z sei kein Teiler von N.

Der Bruch Z/N ist immer als Summe der Kehrwerte positiver Ganzzahlen (Stammbrüche) darstellbar,
wobei es meist mehrer Möglichkeiten der Darstellung gibt.

Beispiele:

5/6 = 1/2 + 1/3 = 1/2 + 1/4 + 1/12 = 1/2 + 1/4 + 1/13 + 1/156 = ...

17/39 = 1/3 + 1/10 + 1/390 = ...

Man schreibe ein Programm, das Z und N entgegennimmt und die Zahlen der Stammbrüchesumme mit den wenigsten Summanden ausgibt.

Also obere Beispiele:

Input 5 und 6, Output 2 und 3,
Input 17 und 39, Output 3, 10 und 390.

Viel Spaß.

Lösungen:

vote_ok
von shanks3042 (120 Punkte) - 29.01.2020 um 04:02 Uhr
Quellcode ausblenden C-Code
// -----------------------------------------------------------------------------
//  egypt_calculator.c
//
//  This program calculates the unit fractions of a given fraction
//
//  Author: shanks3042
//  Last edited: 29. Jan 2020
// -----------------------------------------------------------------------------


#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>


#define MAX (UINT_MAX -1)


typedef enum _ErrorCode_
{
  INVALID_INPUT = -2,
  OUT_OF_RANGE = -1,
  EVERYTHING_OK = 0,

} ErrorCode;


ErrorCode printErrorMessage(ErrorCode error_code);
uint64_t readInput(int part_of_fraction);
int getUnitFractions(uint64_t counter, uint64_t divider);
void fractionCalculator(uint64_t* fraction1, uint64_t* fraction2, char operator);
uint64_t leastCommonDenominator(uint64_t denominator1, uint64_t denominator2);


int main(int argc, char* argv[])
{
  
  uint64_t counter = 0;
  uint64_t divider = 1;
  int error_code = 0;

  counter = readInput(0);  
  if(counter < 0 || counter > MAX)
    return printErrorMessage(OUT_OF_RANGE);

  divider = readInput(1);
  if(divider < 0 || divider > MAX)
    return printErrorMessage(OUT_OF_RANGE);
  
  error_code = getUnitFractions(counter, divider);

  return printErrorMessage(error_code);

}

// This functions prints an error message if an error occured
// @param ErrorCode error_code: the error code that occured
// @return: the error code
//
ErrorCode printErrorMessage(ErrorCode error_code)
{
  switch (error_code)
  {
    case INVALID_INPUT:
      puts("The counter has to be smaller than the divider");
      break;
    case OUT_OF_RANGE:
      printf("Number out of range: allowed range is 1 to %u\n", MAX);
      break;
    default:
      break;
  }
  return error_code;
}

// This functions reads the input and converts it to an uint_64t number if it
// is valid
//
// @param part_of_fraction: 0 - prints the message to enter the counter of the fraction
//                          1 - prints the message to enter the divider of the fraction
//
// @return: the input converted to uint64_t
//          -2 if input is too large
//
uint64_t readInput(int part_of_fraction)
{
  unsigned int size = 20;
  char input[size];
  char c;
  int number;  

  switch (part_of_fraction)
  {
    case 0:
      printf("Please enter the counter of the fraction: ");
      break;
    case 1:
      printf("Please enter the divider of the fraction: ");
      break;
    default:
      break;
  }

  scanf("%20s", input);
  if ((c = getchar()) != '\n' && c != EOF) 
    return OUT_OF_RANGE;

  //puts("");

  number = strtoul(input, NULL, 10);

  return number;
  
}

//This function calculates the unit fractions of a given fraction
// 
//@param uint64_t divider: the denominator of the fraciton
//@param uint64_t counter: the counter of the fraction
// @return:  0 - success
//          -2 if input is invalid
// 
int getUnitFractions(uint64_t counter, uint64_t divider)
{

  uint64_t fraction1[2] = {counter, divider};
  uint64_t rest_fraction[2] = {1, 0};
  uint64_t rest = 0;
  int error_code = 0;
  int index = 0;
  double temp = 0.0;


  fractionCalculator(fraction1, rest_fraction, '-');

  if(counter >= divider)
    return INVALID_INPUT;
  
  if( (divider % counter) == 0)
  {
    printf("Result: %lu\n", (divider / counter));
    return EVERYTHING_OK;
  }
    
  printf("Result: ");
  for(index = 0; ; index++)
  {
     temp = (double)fraction1[1] / (double)fraction1[0];
     rest = (uint64_t)ceill(temp);
     rest_fraction[0] = 1;
     rest_fraction[1] = rest;

     fractionCalculator(fraction1, rest_fraction, '-');

     if (rest == 0)
       break;

    if (index != 0)
      printf(" , ");

    printf("%lu ", rest);

  }
  puts("");
  return error_code;
}

// This function is used to do some calculations with fractions
// 
// @param uint64_t* fraction1: an array that contains the counter and denominator
//                             of a fraction e.g 2/3 = {2, 3}
// @param uint64_t* fraction1: an array that contains the counter and denominator
//                             of a fraction
// @param char operator: a valid operator (e.g. +, - * / )
//                       currently only substraction is implemented
//
void fractionCalculator(uint64_t* fraction1, uint64_t* fraction2, char operator)
{
  unsigned int index = 0;
  uint64_t lcd; 
  uint64_t multiplier1; 
  uint64_t multiplier2;

  for(index = 0; index < 2; index++)
  {
    if(fraction1[index] == 0 || fraction2[index] == 0)
      return;
  }

  lcd = leastCommonDenominator(fraction1[1], fraction2[1]);
  multiplier1 = lcd / fraction1[1];
  multiplier2 = lcd / fraction2[1];

  if( operator == '+' || operator == '-')
  {
    for(index = 0; index < 2; index++)
    {
      fraction1[index] *= multiplier1;
      fraction2[index] *= multiplier2;
    }
  }

  switch (operator)
  {
  case '-':
    fraction1[0] -= fraction2[0];    
    break;
  
  default:
    break;
  }

}

// Calculates the least common denominator of 2 numbers
//
// @param uint64_t denominator1 the first denominator
// @param uint64_t denominator2: the second denominator
// @param return: the least common denominator of the given numbers
//
uint64_t leastCommonDenominator(uint64_t denominator1, uint64_t denominator2)
{
  uint64_t lcd;
  uint64_t divider;

  if(denominator1 == denominator2)
    return denominator1;

  if(denominator1 > denominator2)
  {
    lcd = denominator1;
    divider = denominator1 % denominator2;
  }
    
  else 
  {
    lcd = denominator2;
    divider = denominator2 % denominator1;
  }
    

  //printf("divider: %lu\n", divider);
  if(divider == 0)
   return lcd;
  lcd = denominator1 * denominator2;
  
  return lcd;
}