Date post: | 21-Aug-2015 |
Category: |
Documents |
Upload: | victor-aravena |
View: | 278 times |
Download: | 1 times |
Factorial Again!
ACM ICPC 2013 – Latin American Regional
Víctor Aravena, Mónica Díaz, Bastian Barrientos
Universidad de la Frontera
Descripción de Problema
• Mathew, un estudiante de primer año de ingeniería, está desarrollando una notación posicional original para representar números enteros. Lo llamó \ Un método Curious "(ACM por sus siglas). La notación ACM utiliza los mismos números que la notación decimal, es decir, del 0 al 9. Para convertir un número A de ACM a la notación decimal debe agregar términos k, donde k es el número de dígitos de A (en la notación ACM). El valor del i-th término, correspondiente al i-th ai dígitos, contando de derecha a izquierda, es ai * i!. Por ejemplo 719ACM es equivalente a 5310, desde el 7 * 3! + 1 * 2! + 9 * 1! = 5310. Mathew acaba de comenzar el estudio de la teoría de números, y probablemente no sabe qué propiedades de un sistema de numeración debe tener, pero por el momento sólo está interesado en conversión de un número de ACM a decimal. ¿Puedes ayudarle?
Especificación de entrada
• Cada caso de prueba se administra en una sola línea que contiene una cadena no vacía de un máximo de 5 dígitos, lo que representa un número en notación ACM. La cadena no tiene ceros a la izquierda. El último caso de prueba es seguida por una línea que contiene un cero.
Especificación de salida
• Para cada caso de prueba emitir una sola línea que contiene la representación decimal del número correspondiente de ACM.
Formula de un factorial (n!)
Importante un factorial de n se define como la multiplicación acumulada de valores consecutivos desde 1 al número N. Es decir
n!= 1 x 2 x 3 x 4 x …x (n-1) x n.
Por ejemplo.
El factorial de 5 seria 1 x 2 x 3 x 4 x 5 = 120
Desarrollo del Problema
• Analizando nuestro problema, si el número ingresado es 719 el número resultante se calcula de la siguiente forma:7(tercera posición) + 1 (segunda posición) + 9 (primera posición)
7x3! + 1x2! + 9x1!
7x(3x2x1) + 1x(2x1) + 9 x(1)
7x(6) + 1x(2) + 9x(1)
42 + 2 + 9
Salida 53.
Desarrollo del Problema
• Algoritmo– Paso 1 => preguntamos el número y asignamos el número – Paso 2 => Si el número es cero finalizo– Paso 3 => Si es distinto a cero
• Paso 3.1 => calculo el largo del número• Paso 3.2 => Itero desde el primer elemento hasta el ultimo
– 3.2.1 Tomo el valor de la posición– 3.2.2 Convierto a entero– 3.2.3 Lo multiplico con el factorial (largo – posición)– 3.2.4 Lo incorporo a una variable que contiene la suma
• Paso 3.3 => Entrego el resultado• Paso 3.4 => Vuelvo al primer paso 1.
Estructura de Código
• Es importante recordar la estructura de los códigos– Paso 1 => declarar las librerías y espacio de trabajo– Paso 2 => construir las funciones, en este caso una función que
calcula el factorial– Paso 3 => Iniciar el método principal (int main)– Paso 4 => Declarar e iniciar las variables a utilizar– Paso 5 => Realizar la captura de los datos– Paso 6 => Procesar– Paso 7 => Entregar información
Estructura de Código
– Paso 1 => declarar las librerías y espacio de trabajo
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<cstdlib>
#include<string.h>
using namespace std;
Estructura de Código
– Paso 2 => construir las funciones, en este caso una función que calcula el factorial
int factorial(int N){
int multiplicacion = 1;
for(int contador = 1;contador <=N;contador++){
multiplicacion = multiplicacion * contador;
}
return multiplicacion;
}
Estructura de Código
– Paso 3 => Iniciar el método principal (int main)
int main(){
……
}
– Paso 4 => Declarar e iniciar las variables a utilizar
char a[100];
int limite, posicionFactorial, suma;
Estructura de Código– Paso 5 => Realizar la captura de los datos
cin.getline(a, 100, '\n');– Paso 6 => Procesar
cin.getline(a, 100, '\n');
string largo = ""+string(a);
limite = largo.length();
posicionFactorial = limite;
suma = 0;
for(int i=0;i<limite;i++){
suma = suma + (a[i]-'0')*factorial(posicionFactorial);
posicionFactorial = posicionFactorial - 1;
}
Estructura de Código– Paso 7 => Entregar información
printf("%d\n", suma);
– Paso adicional => Generamos un proceso do-while para validar si el número a procesar es distinto de cero
do{
….
}while(atoi(a)!=0);
Estructura de Código
– Para verificar el entendimiento del problema vamos a solicitar unas pequeñas modificaciones al código. Favor tratar de sacar cada uno de los puntos en un nuevo código (archivo .cpp):
• Invertir la forma de obtener el factorial, es decir:– 719 sería 7x factorial 1 + 1 factorial de 2 + 9 factorial de 3
• En vez de sumar poder restar, es decir – 719 sería 7x factorial 3 + 1 factorial de 2 + 9 factorial de 1