Деление дробей. - C++

@dmital · Регистрация: 18.02.2011

Задача: вывести в порядке возрастания все правильные несократимые дроби со знаменателем, не превосходящим n.
Сам код:

C++

#include <iostream>
#include <string>
using namespace std;
using std::string;
int main() {
int n,i,num,numi;
float last=0,min;
string temp;
cin>>n;
const int r=n-1;
int a[r];
for(i=1; i<=r ;i++)
 a[i]=1;
while (last<(r/(r+1))) {
min=1;
for (i=1; i<=r; i++) 
if (((a[i]/(i+1))<min)&&((a[i]/(i+1))> last))  {
min=(a[i]/(i+1));
numi=i;
temp=a[i]+"/"+(i+1);
}
last=min;
cout<<temp;
a[numi]++;
}
return 0;
}

Как должно работать: Создается массив из n-1 чисел, причем число a[i] представляет дробь a[i]/(i+1). Первоначально все числа равны единице. last - последняя выведенная дробь, сначала это значение равно нулю. До тех пор, пока не выведена дробь (n-1)/n, проходим весь массив, и выбираем минимальную из дробей вида a[i]/(i+1), запоминаем ее номер, и записываем в строку temp. После окончания цикла выводим дробь и увеличиваем на 1 a[i].
Проблема в том, что нужно как-то изменить процедуру деления, чтобы в результате деления двух целых чисел получалось дробное число, а не ноль, но я не знаю, как это сделать.

@co6ak · 11.08.2011, 11:24

int ни когда не будет дробным.
можно результирующую переменную сделать, допустим, double.

@dmital · 11.08.2011, 11:35 **[ТС]**

Каким образом это сделать?
Я пробовал вот так, но не помогло, так как при делении все равно ноль получается.

C++

#include <iostream>
#include <string>
using namespace std;
using std::string;
int main() {
int n,i,num,numi;
float last=0,min;
string temp;
cin>>n;
const int r=n-1;
int a[r];
for(i=1; i<=r ;i++)
 a[i]=1;
while (last<(r/(r+1))) {
min=1;
for (i=1; i<=r; i++) {
double z=a[i]/(i+1);
if ((z<min)&&(z>last))  {
min=(a[i]/(i+1));
numi=i;
temp=a[i]+"/"+(i+1);
}
}
last=min;
cout<<temp;
a[numi]++;
}
return 0;
}

@Dani · 11.08.2011, 11:42

Я бы делал так: создал структуру дроби с числителем и знаменателем. Далее написал функцию поиска НОДа, искал его для каждой дроби - если он не равен 1 тогда дробь сократимая и делаем с ней что надо, иначе дробь несократимая. Потом массив из дробей отсортировал так: приводил к общему знаменателю как НОК (заменатель1*знаменатель 2 / нод(знаменатель1,знаменатель2) и сравнивал.

@~~IrineK~~ · 11.08.2011, 11:42

Задача предполагает обязательный поиск НОД числителя и знаменателя. Если НОД>1, дробь сократима.

@dmital · 11.08.2011, 11:51 **[ТС]**

Сообщение от Dani

Я бы делал так: создал структуру дроби с числителем и знаменателем. Далее написал функцию поиска НОДа, искал его для каждой дроби - если он не равен 1 тогда дробь сократимая и делаем с ней что надо, иначе дробь несократимая. Потом массив из дробей отсортировал так: приводил к общему знаменателю как НОК (заменатель1*знаменатель 2 / нод(знаменатель1,знаменатель2) и сравнивал.

Спасибо, но остается проблема с делением. Если нужно найти значение a/b, где а и b - целые, то что нужно сделать, чтобы результат оказался нецелого типа?

@~~IrineK~~ · 11.08.2011, 11:54

C++

#include <iostream>
using namespace std;
 
int NOD(int x, int y)
{   if (y == 0) return x;
    return NOD(y, x % y);
}
 
int main()
{   int denominator, i;
    
    cout<<"Denominatior N = ";
    cin>>denominator;
 
    for(i=0;i<denominator;i++)
        if(NOD(i,denominator)==1) cout<<i<<"/"<<denominator<<" "; 
 
    cin.sync();cin.get();
    return 0;
}

@Dani · 11.08.2011, 11:56

Сообщение от dmital

Спасибо, но остается проблема с делением. Если нужно найти значение a/b, где а и b - целые, то что нужно сделать, чтобы результат оказался нецелого типа?

Так?

C++

1	float b=(float)a/b;

@dmital · 11.08.2011, 11:59 **[ТС]**

IrineK, Dani, благодарю за советы, дальше, наверное, разберусь сам.

@~~IrineK~~ · 11.08.2011, 12:02

Задача решена. "Дальше" - некуда ))

@diagon · 11.08.2011, 12:14

В ряд Фарея разложить можно.

@mac_alleb · 17.08.2011, 08:18

Уважаемый(ая) IrineK может быть с точки зрения математики задача и решена (хотя я и в этом
сомневаюсь

), а вот с точки зрения программирования - нет. Я думаю здесь подойдет полный перебор
деления чисел с критерием: если есть остаток - значит дробь несократима. Видимо основная задача -
деление двух целых больших чисел. Подскажите, насколько большое n

. Берусь сделать на Tasm 5.0
за пару-тройку дней

. Писать прогу?

@Puporev · 17.08.2011, 08:45

Сообщение от mac_alleb

если есть остаток - значит дробь несократима.

Это не так, по условию все дроби правильные, у всех есть только остаток и нет целой части.

@mac_alleb · 19.08.2011, 22:18

Сделал бинарное сложение и вычитание, а также часть деления для 248-битных чисел. Наверное,
в будующем, для полноты картины, потребуется еще и умножение

, но на все это потребуется отличное
от 0 время

, а то я устал за последнее время

.

@co6ak Кошковед 514 / 502 / 30 Регистрация: 12.04.2010 Сообщений: 1,392
	11.08.2011, 11:24	#2
	int ни когда не будет дробным. можно результирующую переменную сделать, допустим, double. 0

@Dani 1393 / 637 / 57 Регистрация: 11.08.2011 Сообщений: 2,295 Записей в блоге: 2 Завершенные тесты: 1
	11.08.2011, 11:42	#4
	Я бы делал так: создал структуру дроби с числителем и знаменателем. Далее написал функцию поиска НОДа, искал его для каждой дроби - если он не равен 1 тогда дробь сократимая и делаем с ней что надо, иначе дробь несократимая. Потом массив из дробей отсортировал так: приводил к общему знаменателю как НОК (заменатель1*знаменатель 2 / нод(знаменатель1,знаменатель2) и сравнивал. 2

@~~IrineK~~ Заблокирован
	11.08.2011, 11:42	#5
	Задача предполагает обязательный поиск НОД числителя и знаменателя. Если НОД>1, дробь сократима. 1

@dmital 1 / 1 / 0 Регистрация: 18.02.2011 Сообщений: 20
	11.08.2011, 11:51 [ТС]	#6
	Сообщение от Dani Я бы делал так: создал структуру дроби с числителем и знаменателем. Далее написал функцию поиска НОДа, искал его для каждой дроби - если он не равен 1 тогда дробь сократимая и делаем с ней что надо, иначе дробь несократимая. Потом массив из дробей отсортировал так: приводил к общему знаменателю как НОК (заменатель1*знаменатель 2 / нод(знаменатель1,знаменатель2) и сравнивал. Спасибо, но остается проблема с делением. Если нужно найти значение a/b, где а и b - целые, то что нужно сделать, чтобы результат оказался нецелого типа? 0

@dmital 1 / 1 / 0 Регистрация: 18.02.2011 Сообщений: 20
	11.08.2011, 11:59 [ТС]	#9
	IrineK, Dani, благодарю за советы, дальше, наверное, разберусь сам. 0

@~~IrineK~~ Заблокирован
	11.08.2011, 12:02	#10
	Задача решена. "Дальше" - некуда )) 0

@diagon Higher 1934 / 1200 / 49 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	11.08.2011, 12:14	#11
	В ряд Фарея разложить можно. 0

@mac_alleb 7 / 7 / 0 Регистрация: 05.08.2011 Сообщений: 54
	17.08.2011, 08:18	#12
	Уважаемый(ая) IrineK может быть с точки зрения математики задача и решена (хотя я и в этом сомневаюсь ), а вот с точки зрения программирования - нет. Я думаю здесь подойдет полный перебор деления чисел с критерием: если есть остаток - значит дробь несократима. Видимо основная задача - деление двух целых больших чисел. Подскажите, насколько большое n . Берусь сделать на Tasm 5.0 за пару-тройку дней . Писать прогу? 0

@Puporev Модератор 53461 / 41261 / 14416 Регистрация: 18.05.2008 Сообщений: 96,392
	17.08.2011, 08:45	#13
	Сообщение от mac_alleb если есть остаток - значит дробь несократима. Это не так, по условию все дроби правильные, у всех есть только остаток и нет целой части. 0

@mac_alleb 7 / 7 / 0 Регистрация: 05.08.2011 Сообщений: 54
	19.08.2011, 22:18	#14
	Сделал бинарное сложение и вычитание, а также часть деления для 248-битных чисел. Наверное, в будующем, для полноты картины, потребуется еще и умножение , но на все это потребуется отличное от 0 время , а то я устал за последнее время . 0

Опции темы

С++ для начинающих

Деление дробей. - C++