Как реализовать сумму дробей?

Question

[timkin1]

Подскажите, пожалуйста, как реализовать программу для подсчета суммы дробей без использования массивов. Программе на вход подается число (от 1 до 5), которое равно количеству пар чисел x и y. А на выходе необходимо вывести сумму дробей вида x1/y1+x2/y2+..+Xn/Yn.

Прошу помочь придумать алгоритм.

Answer 1

[Rsa97]

А что там придумывать? Сложение - первый класс начальной школы, операции с дробями - пятый класс.
Просто последовательно складывайте дроби в натуральном представлении.

Comments

[longclaps]

Переполнение в итоговых числителе/знаменателе обрабатывать будем?

[Rsa97]

longclaps, Зачем? Просто реализуем свою длинную арифметику.

[Антон Жилин]

Rsa97, у меня подозрение, что это школьная задача, так что реализации длинной арифметики тут не ждут. К тому же, "без использования массивов".

[Rsa97]

Антон Жилин, А мы на строках, с доступом по указателю :-)

Answer 2

[Арсений Ефремов]

Общая схема примерно такая:

(I)nput := [x0, y0, x1, y1, x2, y2 ... xn, yn]

(R)ational := (a, b)
Trunc(R) := R(a / НОД(a,b), b / НОД(a,b))
R1 + R2 := Trunc(a1*b2 + a2*b1, b1*b2)
R1 + R2 + R3 := (R1 + R2) + R3

Output := R(I[0],I[1]) + R(I[2],I[3]) + ... + R(I[2n-1],I[2n])

Comments

[Mercury13]

Без массивов!

[Арсений Ефремов]

Mercury13, для схемы не имеет значения. Пусть будет последовательность, а не массив. Логика не меняется.

Answer 3

[Mercury13]

Заводим структуру-сумматор. Изначально она 0/1. Что-то типа

typedef struct {
  int num, den;
} Fraction;

…

Fraction sum = { 0, 1 };

Дальше пишу псевдокодом, НОД и НОК разберись, как реализовать самому.

для каждой очередной дроби
  ввести(дробь)
  новыйЗнам = НОК(сумматор.знам, дробь.знам)
  множСумм = новыйЗнам / сумматор.знам
  множДробь = новыйЗнам / дробь.знам
  новыйЧисл = сумматор.числ × множСумм + дробь.числ × множДробь
  сокрНод = НОД(новыйЧисл, новыйЗнам)
  сумматор.числ = новыйЧисл/сокрНод
  сумматор.знам = новыйЗнам/сокрНод

Можно и оптимизировать, но тогда нужна хитрая разновидность алгоритма Евклида; в учебных целях не стоит.

И ещё. Одна из известных ошибок в написании НОК — произведение аргументов не влезает в свой тип, а НОК влезает. Поймёшь, как в такой ситуёвине избавиться от переполнения?