|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 23 May 2001 05:45:44
To : Denis Pozhidaev
Subject : Re: задачка на C++
--------------------------------------------------------------------------------
Привет! "Denis Pozhidaev" <Denis.Pozhidaev@p100.f80.n5005.z2.fidonet.org>
сообщил(а) нам:
Кстати, собственно программа:
#include <stdio.h>
// Поиск наибольшего обшего делителя
int nod(int Val_1, int Val_2){
if(Val_1<Val_2){
int Tmp=Val_1; Val_1=Val_2; Val_2=Tmp;
}
while(Val_2!=0){
int Tmp=Val_1%Val_2; Val_1=Val_2; Val_2=Tmp;
}
return Val_1;
}
// Генерация общего знаменателя дробей от 1/2 до 1/Max_Znam
int Ob_Znam(int Max_Znam){
int Tmp_Znam = 1;
for(int Cur_Znam=2; Cur_Znam<=Max_Znam; Cur_Znam++){
Tmp_Znam*=Cur_Znam/nod(Tmp_Znam, Cur_Znam);
}
return Tmp_Znam;
}
// Генерация списка дробей для знаменателей от 2 до Max_Znam
void Out_List(int Max_Znam){
int Cur_Znam = Ob_Znam(Max_Znam); // 420
int Min_Chis = Cur_Znam/Max_Znam; // 60
int Max_Chis = Cur_Znam-Min_Chis; // 360
for(int Cur_Chis=Min_Chis; Cur_Chis<=Max_Chis; Cur_Chis++){
int Tmp_Nod = nod(Cur_Znam, Cur_Chis);
if(Tmp_Nod>=Min_Chis){
printf("%0d/%0d\n", Cur_Chis/Tmp_Nod, Cur_Znam/Tmp_Nod);
}
}
}
int main(void){
Out_List(7);
}
Главное отличие от предложенного ранее алгоритма в том, что для уменьшения
кол-ва вычислений выдача на печать производится не по значению знаменателя,
а по значению HОД(числитель, знаменатель). А т.к.
Min_Chis/Cur_Znam==1/Max_Znam (т.е. в нашем случае - 1/7), то для любого HОД
>= Min_Chis знаменатель <= Max_Znam.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
