привести дроби к общему знаменателю

@exploited · Регистрация: 25.08.2008

Author24 — интернет-сервис помощи студентам

Помогите, пожалуйста, с алгоритмом, а то завтра практику сдавать и последняя задача осталась(
1.даны дроби p1/q1, p2/q2 ... p/q, надо привести их к общему знаменателю и расположить в порядке возрастания

@FlyDeR · 25.08.2008, 17:56

самый просто способ привести к общему знаменателю - перемножить все q

@exploited · 25.08.2008, 18:03 **[ТС]**

это я, честно, говоря сам понял, но если будет десяток впринципе небольших дробей, там все равно ппц, какие числа получатся, так что надо бы к наименьшему, чтобы выглядело нормально

@Xentar · 25.08.2008, 18:08

Как вариант можешь выполнить это методом перебора

уууухххх машинку то загрузит !!!
от самого большого знаменателя до перемножения всех дробей....
а вообще есть алгоритм... только я его забыл за пять лет то

мы его в колледже еще проходили...

@exploited · 25.08.2008, 18:09 **[ТС]**

перебор это мазохизм какойто)) лан, может, кто вспомнит

@Lurker · 25.08.2008, 18:58

1)Делаешь (забыл как называется тип которые НЕупорядоченный набор однотипных данных, множество что-ли?) туда складываешь все простые числа.
потом раскладываешь знаменатели на простые числа(перемножение которых даст знаменатель)
смотришь простой множитель Х появлялся максимум n раз а Y m раз то общий знаменатель будет X^n*Y*m
всё понятно?

@exploited · 25.08.2008, 19:05 **[ТС]**

все, кажись, понял

Vovan-VE · 25.08.2008, 20:08

Там же через НОД че-то как-то. Эх, давно это было.

@Puporev · 25.08.2008, 21:08

Общий знаменатель это по сути наименишее общее кратное. Известно, что НОК=(А*B)/НОД.
На этом основании написана функция NOK.
Задачу делал быстро, немного сырая, хотя и работает. Дроби представил в виде записей, хотя можно и в двухмерном массиве a[1,i]-числитель, a[2,i]- знаменатель, в принципе одно и тоже. Ввод сделал рандомом, чтобы быстрее тестировать, можно переделать на ручной. Ну и красоту навести, если что не нравится.

Код

[FONT='Courier New CYR'][SIZE=3]uses crt;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]type drob=record[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']          ch:integer;//[/FONT][FONT='Courier New CYR']числитель[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']          zn:integer;/[/FONT][FONT='Courier New CYR']знаменатель[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]          end;[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']var a:array[1..100] of drob;//[/FONT][FONT='Courier New CYR']массив[/FONT][FONT='Courier New CYR']дробей[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']    nk:array[1..100] of integer;//[/FONT][FONT='Courier New CYR']массив[/FONT][FONT='Courier New CYR']НОКов[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']    ozn:integer;[/FONT][FONT='Courier New CYR'] //общий знаменатель[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]    n,i,j:integer;[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']    x:drob;[/FONT][FONT='Courier New CYR'] //буфер при сортировке[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]Function NOK(m,n:integer):integer;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]Function NOD(m,n:integer):integer;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]begin[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]while m<>n do[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]if m>n then m:=m-n else n:=n-m;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]NOD:=M;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]end;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]begin[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]NOK:=m*n div NOD(m,n);[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]end;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]begin[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]clrscr;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]randomize;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]write('n=');readln(n);[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]writeln('Ishodnyj massiv drobej:');[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]for i:=1 to n do[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]  begin[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']   a[i].ch:=random(10)-2;//[/FONT][FONT='Courier New CYR']числитель[/FONT][FONT='Courier New CYR']-[/FONT][FONT='Courier New CYR']любое[/FONT][FONT='Courier New CYR']целое[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']   a[i].zn:=random(20)+1;//[/FONT][FONT='Courier New CYR']знаменатель[/FONT][FONT='Courier New CYR'] >0[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]   write(a[i].ch,'/',a[i].zn,'  ');[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3] end;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]writeln;[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']nk[1]:=nok(a[1].zn,a[2].zn);//[/FONT][FONT='Courier New CYR']первый[/FONT][FONT='Courier New CYR']НОК[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]for i:=3 to n do[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']nk[i-1]:=nok(nk[i-2],a[i].zn);//[/FONT][FONT='Courier New CYR']остальные[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']ozn[/FONT][FONT='Courier New CYR']:=[/FONT][FONT='Courier New CYR']nk[/FONT][FONT='Courier New CYR'][[/FONT][FONT='Courier New CYR']n[/FONT][FONT='Courier New CYR']-1]; //последний – общий знаменатель[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]for i:=1 to n do[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']a[i].ch:=a[i].ch*(ozn div a[i].zn);//[/FONT][FONT='Courier New CYR']домножаем[/FONT][FONT='Courier New CYR']числители[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]for i:=1 to n-1 do[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]for j:=1 to n-1 do[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']if[/FONT][FONT='Courier New CYR']a[/FONT][FONT='Courier New CYR'][[/FONT][FONT='Courier New CYR']j[/FONT][FONT='Courier New CYR']].[/FONT][FONT='Courier New CYR']ch[/FONT][FONT='Courier New CYR']>[/FONT][FONT='Courier New CYR']a[/FONT][FONT='Courier New CYR'][[/FONT][FONT='Courier New CYR']j[/FONT][FONT='Courier New CYR']+1].[/FONT][FONT='Courier New CYR']ch[/FONT][FONT='Courier New CYR']then[/FONT][FONT='Courier New CYR'] //сортируем по возрастанию[/FONT][/SIZE]
[SIZE=3][FONT='Courier New CYR']begin[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]     x:=a[j];[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]     a[j]:=a[j+1];[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]     a[j+1]:=x;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]   end;[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]writeln('Ob. zn=',ozn);[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]writeln('Otsortirovannyj massiv drobej:');[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]for i:=1 to n do[/SIZE][/FONT]
[SIZE=3][FONT='Courier New CYR']write(a[i].ch div (ozn div a[i].zn),'/',a[i].zn,'  ');//[/FONT][FONT='Courier New CYR']числитель[/FONT][FONT='Courier New CYR']обратно[/FONT][FONT='Courier New CYR']делим[/FONT][/SIZE]
[FONT='Courier New CYR'][SIZE=3]readln[/SIZE][/FONT]
[FONT='Courier New CYR'][SIZE=3]end.[/SIZE][/FONT]

@sambuka · 21.05.2009, 12:37

а нельзя ли эту же задачку решить при условии что исходные и выходные данные должны храниться в файлах?

@exploited 0 / 0 / 0 Регистрация: 25.08.2008 Сообщений: 4
		1
	привести дроби к общему знаменателю 25.08.2008, 17:37. Показов 8157. Ответов 9 Метки нет (Все метки) Помогите, пожалуйста, с алгоритмом, а то завтра практику сдавать и последняя задача осталась( 1.даны дроби p1/q1, p2/q2 ... p/q, надо привести их к общему знаменателю и расположить в порядке возрастания 0

@FlyDeR 3 / 3 / 0 Регистрация: 07.08.2008 Сообщений: 32
	25.08.2008, 17:56	2
	самый просто способ привести к общему знаменателю - перемножить все q 0

@exploited 0 / 0 / 0 Регистрация: 25.08.2008 Сообщений: 4
	25.08.2008, 18:03 [ТС]	3
	это я, честно, говоря сам понял, но если будет десяток впринципе небольших дробей, там все равно ппц, какие числа получатся, так что надо бы к наименьшему, чтобы выглядело нормально 0

@Xentar Of Wolf and Man 999 / 198 / 5 Регистрация: 09.07.2008 Сообщений: 1,784
	25.08.2008, 18:08	4
	Как вариант можешь выполнить это методом перебора уууухххх машинку то загрузит !!! от самого большого знаменателя до перемножения всех дробей.... а вообще есть алгоритм... только я его забыл за пять лет то мы его в колледже еще проходили... 0

@exploited 0 / 0 / 0 Регистрация: 25.08.2008 Сообщений: 4
	25.08.2008, 18:09 [ТС]	5
	перебор это мазохизм какойто)) лан, может, кто вспомнит 0

@Lurker 6140 / 1898 / 14 Регистрация: 07.07.2008 Сообщений: 10,417
	25.08.2008, 18:58	6
	1)Делаешь (забыл как называется тип которые НЕупорядоченный набор однотипных данных, множество что-ли?) туда складываешь все простые числа. потом раскладываешь знаменатели на простые числа(перемножение которых даст знаменатель) смотришь простой множитель Х появлялся максимум n раз а Y m раз то общий знаменатель будет X^nYm всё понятно? 0

@exploited 0 / 0 / 0 Регистрация: 25.08.2008 Сообщений: 4
	25.08.2008, 19:05 [ТС]	7
	все, кажись, понял 0

Vovan-VE 13208 / 6596 / 1041 Регистрация: 10.01.2008 Сообщений: 15,069
	25.08.2008, 20:08	8
	Там же через НОД че-то как-то. Эх, давно это было. 0

@sambuka 0 / 0 / 0 Регистрация: 16.11.2008 Сообщений: 30
	21.05.2009, 12:37	10
	а нельзя ли эту же задачку решить при условии что исходные и выходные данные должны храниться в файлах? 0