|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry O. Kolomiets 2:5020/7777.514 21 May 2001 22:16:07
To : Denis Pozhidaev
Subject : задачка на C++
--------------------------------------------------------------------------------
Привет, Denis Pozhidaev!
Monday, May 21 00:28, Denis Pozhidaev wrote to All:
DP> Тyт задачка такая:
DP> Hапечатать в поpядке возpастания все пpостые несокpатимые дpоби,
DP> заключенные междy 0 и 1. Знаменатели котоpых не пpевышают 7.
DP> Бyдy пpезнателен!
1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7
вот, скучно было :)
держи.
Работает для дробей с максимальным знаменателем вплоть до 509,
(просто MSVC++ 6.0 не дает делать статические массивы больше 126 kb,
по крайней мере, здесь).
Работает и для более крупных чисел в знаменателе, но тогда нужно менять
алгоритм сортировки и использовать динамические массивы.
Для таких данных, imho, лучше подойдет сортировка методом слияния, но она
сложновата в реализации для этих целей.
Короче говоря, не самый красивый и эффективный алгоритм, но зато работает :)
Тебе нужно будет прогнать через что-нибудь листинг (через FAR, например),
чтобы комментарии из cp866 в cp1251 конвертнуть (из досовской в виндовую).
Д Д ДДДДДДДДДДДДДДДННННННННН CUT HERE ННННННННННДДДДДДДДДДДДДД Д Д
// Name: Frac
// Version: 1.0
// Created: 21.05.2001 21:19
// Author: Dmitry O. Kolomiets
// Comments: Hапечатать в поpядке возpастания все пpостые
// несокpатимые дpоби, заключенные
// междy 0 и 1. Знаменатели котоpых не пpевышают ZN_MAX.
#include <stdio.h>
void main(void)
{
const int ZN_MAX=7; // Знаменатель дробей будет <= ZN_MAX.
int ch; // Числитель текущей дроби.
int zn; // Знаменатель текущей дроби.
int temp;
int swap;
int res_ch[ZN_MAX*(ZN_MAX-1)/2]; // Массив числителей готовых дробей,
int res_zn[ZN_MAX*(ZN_MAX-1)/2]; // массив знаменателей готовых дробей,
// размер массива заведомо больше чем
// нужно для всех наших несократимых
// дробей.
int i, j; // Индексы циклов.
int max_i; // Число найденных несократимых дробей.
for(zn=ZN_MAX, i=0; zn>=1; zn--) // Получаем последовательность
{ // вида 1/7 2/7 ... 2/6 3/6
for(ch=1; ch<zn; ch++)
{
// Проверяем, если ch и zn делятся одновременно на какое-либо
// число, то дробь сократимая, значит, ее пропускаем.
for(temp=2; temp<ZN_MAX; temp++)
{
if(zn%temp==0 && ch%temp==0)
break;
}
// Если текущая дробь несократимая, зачит предыдущий цикл
// закончился на шаге temp==ZN_MAX, используем это
// как признак
if(temp==ZN_MAX)
{
res_ch[i]=ch; // В массив пишем только несократимые
res_zn[i++]=zn;
}
}
}
// Сортируем в порядке возрастания одним из примитивных методов
// ("Главный элемент", по-моему). Затраты примерно O(max_i^2)
for(max_i=i, i=0, temp=0; i<max_i; i++)
{
for(j=i; j<max_i; j++)
{
if(res_ch[temp]*res_zn[j]-res_ch[j]*res_zn[temp]>0)
{
swap=res_ch[temp];
res_ch[temp]=res_ch[j];
res_ch[j]=swap;
swap=res_zn[temp];
res_zn[temp]=res_zn[j];
res_zn[j]=swap;
}
}
temp++;
printf("%d/%d ", res_ch[i], res_zn[i]);
// // Сами себя проверим
// if(i>1 && (res_ch[i]/(double)res_zn[i]<
// res_ch[i-1]/(double)res_zn[i-1]))
// {
// printf("\n Error: %d/%d and %d/%d\n", res_ch[i], res_zn[i],
// res_ch[i+1], res_zn[i+1]);
// }
}
printf("\nDone computing\n");
}
Д Д ДДДДДДДДДДДДДДДННННННННН CUT HERE ННННННННННДДДДДДДДДДДДДД Д Д
--- - щшщ щшщ щшщ щшщ щшщ щшщ щшщ щшщ щшщ [ SLiDER ]
* Origin: шщш шщш шщш шщш шщш шщш шщш шщш шщ (2:5020/7777.514)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
