Um Expanded Number é a representação computacional de um número real expandido em suas somas multiplicadas por dez elevado a suas respectivas ordens.
(p0)[m0 o0] -> ... -> (pi)[mi oi] -> ... -> (pn)[mn on] -> λ
Onde pi é a i-ésima parte, mi é o i-ésimo módulo e oi é a i-ésima ordem de um Expanded Number.
Uma parte é formada pelo seu módulo e a sua ordem.
-
Se 123 é um número real. Então, pode ser escrito como: 123 = 1x102 + 2x101 + 3x100 Dessa forma, na representação Expanded Number será: (p0)[3 0] -> (p1)[2 1] -> (p2)[1 2] -> λ
-
Se 10023 é um número real. Então, pode ser escrito como: 10023 = 1x104 + 2x101 + 3x100 Dessa forma, na representação Expanded Number será: (p0)[3 0] -> (p1)[2 1] -> (p2)[1 4] -> λ
-
Se 100,23 é um número real. Então, pode ser escrito como: 100,23 = 1x104 + 2x10-1 + 3x10-2 Dessa forma, na representação Expanded Number será: (p0)[3 -2] -> (p1)[2 -1] -> (p2)[1 4] -> λ
Normaliza um Expanded Number.
Exemplos de Expanded Number não normalizado:
- (p0)[18 0] -> (p1)[3 1] -> λ
- (p0)[123 0] -> (p1)[47 1] -> λ
Exemplos acima normalizado:
- (p0)[8 0] -> (p1)[4 1] -> λ
- (p0)[3 0] -> (p1)[9 1] -> (p2)[5 2] -> λ
Em código, o equivalente será:
Expanded_Number *normalize_expanded_number(Expanded_Number *number) {
Expanded_Number *tmp = create_expanded_number();
Expanded_Number_Part *current = number->head;
unsigned int current_module;
int current_order;
while (current) {
current_module = current->module;
current_order = current->order;
while (current_module > 0){
append_expanded_number_part(
tmp,
current_module % 10,
current_order
);
current_module /= 10;
current_order++;
}
current = current->next;
}
Expanded_Number *result = create_expanded_number();
current = tmp->head;
while (current) {
if (
is_empty_expanded_number(result) ||
result->tail->order != current->order
) {
append_expanded_number_part(
result,
current->module,
current->order
);
current = current->next;
continue;
}
if (result->tail->order == current->order) {
result->tail->module += current->module;
}
current = current->next;
}
destroy_expanded_number(tmp);
if (!is_normalized_expanded_number(result)) {
return normalize_expanded_number(result);
}
return result;
}
Seja a = (p0)[2 0] -> (p1)[7 2] -> λ
Seja b = (p0)[4 0] -> (p1)[3 1] -> λ
Então, a soma a + b será:
a + b = (p0)[6 0] -> (p1)[3 1] -> (p2)[7 2] -> λ
Em código, o equivalente será:
Expanded_Number *sum_expanded_number(Expanded_Number *a, Expanded_Number *b) {
Expanded_Number *tmp = create_expanded_number();
Expanded_Number_Part *current_a = a->head;
Expanded_Number_Part *current_b = b->head;
while (current_a || current_b) {
if (current_a) {
append_expanded_number_part(
tmp,
current_a->module,
current_a->order
);
current_a = current_a->next;
}
if (current_b) {
append_expanded_number_part(
tmp,
current_b->module,
current_b->order
);
current_b = current_b->next;
}
}
Expanded_Number *result = normalize_expanded_number(tmp);
destroy_expanded_number(tmp);
return result;
}
Seja a = (p0)[2 0] -> λ
Seja b = (p0)[3 0] -> (p1)[3 1] -> λ
Então, a multiplicação a * b será:
a * b = (p0)[6 0] -> (p1)[6 1] -> λ
Expanded_Number *multiply_by_expanded_number_part(Expanded_Number *number, Expanded_Number_Part *part) {
Expanded_Number *tmp = create_expanded_number();
Expanded_Number_Part *current = number->head;
while (current) {
append_expanded_number_part(
tmp,
current->module * part->module,
current->order + part->order
);
current = current->next;
}
Expanded_Number *result = normalize_expanded_number(tmp);
destroy_expanded_number(tmp);
return result;
}
Expanded_Number *multiply_expanded_number(Expanded_Number *a, Expanded_Number *b) {
Expanded_Number *result = multiply_by_expanded_number_part(b, a->head);
Expanded_Number *previous_result;
Expanded_Number *tmp;
Expanded_Number_Part *current = a->head->next;
while (current) {
previous_result = result;
tmp = multiply_by_expanded_number_part(b, current);
result = sum_expanded_number(previous_result, tmp);
destroy_expanded_number(previous_result);
destroy_expanded_number(tmp);
current = current->next;
}
return result;
}
#include "../headers/expanded_number.h"
Expanded_Number *factorial_expanded_number(Expanded_Number *number) {
Expanded_Number *result = create_expanded_number();
append_expanded_number_part(result, 1, 0);
if (is_empty_expanded_number(number)) {
return result;
}
Expanded_Number *previous_result;
Expanded_Number *increment = create_expanded_number();
append_expanded_number_part(increment, 1, 0);
Expanded_Number *current = create_expanded_number();
append_expanded_number_part(current, 1, 0);
Expanded_Number *previous_current;
while (!is_equal_expanded_number(number, current)) {
previous_result = result;
previous_current = current;
current = sum_expanded_number(previous_current, increment);
result = multiply_expanded_number(previous_result, current);
destroy_expanded_number(previous_result);
destroy_expanded_number(previous_current);
}
return result;
}
int main() {
Expanded_Number *number = create_from_int(100);
Expanded_Number *factorial = factorial_expanded_number(number);
describe_expanded_number(factorial);
print_expanded_number(factorial);
return 1;
}
Nesse exemplo, é calculado o fatorial de 100.
Compilando o arquivo
make
Executando
make run_factorial
Limpar o diretório de build
make clean