Здравствуйте.
Решил создать новую тему, ибо мне кажется данную задачу можно решить разными способами, и акцент в данном случае не идёт на длинную арифметику. Проблема была в том, что мы хотели сократить знаменатель к единице. Если администрация считает что не стоит создавать новый топик, то не возражаю чтобы, его закрыли.
То что требуется я реализовал сегодня.
Вспомогательные моменты.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
struct Number
{
int num;
int num2;
int count;
int* multipliers;
};
struct Number* initializeNumber(int a)
{
struct Number* n = (struct Number*)malloc(sizeof(struct Number));
n->num = a;
n->num2 = a;
n->count = 0;
n->multipliers = NULL;
}
int viewNumber(struct Number* a)
{
printf("num= %i\n", a->num);
printf("num2= %i\n", a->num2);
printf("divisors:");
for (int i = 0; i < a->count; ++i)
{
printf("%i ", a->multipliers[i]);
}
printf("\n");
return 0;
}
//assume a->num > 1
int factorization(struct Number* a)
{
for (int i = 2; i<=a->num2; ++i)
{
if (a->num2%i == 0)
{
a->count += 1;
a->multipliers = (int*)realloc(a->multipliers, a->count*sizeof(int));
a->multipliers[a->count - 1] = i;
a->num2 /= i;
factorization(a);
break;
}
}
return 0;
}
Как работает factorization. Например на входе 150, находит первый делитель слева 2, дальше рекурсивный запуск 75, находим 3, дальше рекурсивный запус 25, находим 5, дальше рекурсивный запуск 5, находим 5, рекурсивный запуск на 1, приводит к завершению. Вместо 150 получаем массив 2 3 5 5 .
Возможно данную функцию можно реализовать лучше, буду рад предложениям.
Вы наверное догадались зачем нужна эта функция. Фиксируем элемент знаменателя, и пытаемся найти такой элемент числитель, что a%b==0,если такой элемент не найден, то фиксированный элемент знаменателя раскладываем на простейшие и расширяем массив знаменателя . Вместо 150 у нас появится 4 числа 2 3 5 5 . Ниже код
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
//Сочетания
char* la_combination(unsigned n, unsigned m)
{
m = (n - m > m) ? m : n-m;
int* up = (int*)malloc(sizeof(int)*m);//числитель
int* down = (int*)malloc(sizeof(int)*m);//знаменатель
for (int i = 1; i <= m; ++i)
{
*(up + m - i) = n - m + i;
*(down + m - i) = i;
}
#ifdef DEBUG
for (int i = 0; i < m; ++i)
printf("%i ", up[i]);
printf("\n");
for (int i = 0; i < m; ++i)
printf("%i ", down[i]);
printf("\n");
#endif
int len_down = m;
for (int i = 0; i < len_down; ++i)//1 проход по знаменателю, длина знаменателя меняется
{
if (down[i] != 1)
{
int j = 0;
for (j = 0; j < m; ++j)//проход по числителю
{
if (!(up[j] % down[i]))
{
up[j] /= down[i];
down[i] = 1;
break;
}
}
if (j == m && down[i]!=1) //если перебрали все элементы числителя, а фиксированный элемент знаменателя не сократили
{
struct Number* n = initializeNumber(down[i]);
factorization(n); //раскладываю число на множители
down[i] = 1;
len_down += n->count;
down = (int*)realloc(down, sizeof(int)*len_down);
for (int i = 0; i < n->count; ++i)
{
down[len_down - n->count + i] = n->multipliers[i];
}
free(n->multipliers);
free(n);
}
}
}
#ifdef DEBUG
for (int i = 0; i < m; ++i)
printf("%i ", up[i]);
printf("\n");
for (int i = 0; i < len_down; ++i)
printf("%i ", down[i]);
printf("\n");
#endif
char* res="1";
char* t = (char*)malloc(10);
for (int i = 0; i < m; ++i)
{
sprintf(t, "%d", up[i]);
res = la_multiplication(res, t);
}
free(t);
return res;
}
На функцию la_multiplication(res, t) можно не обращать внимание (но если нужна она реализована в соседнем топе), это сложение двух строк.
Мне интересно как вы бы решили аналогичную задачу, ну и возможно у кого-то есть замечания по рефакторингу кода, оптимизации алгоритмов, и конечно-же организации данных. (Может стоит создать статическую переменную под длину массива, и не создавать структуру, например)
PS
Вчера с трудом заснул и снились кошмары(из-за того что меня одолевали сомнения по тернарному оператору). Всё-таки не стоит использовать С++ только из-за расширенных возможностей тернарного оператора, сегодня изменил весь код в длинной арифметике на код Си.
