Un programa C para encontrar todas las factoraciones utilizando una tabla hash -- amp codereview Relacionados El problema

A C program to find all factorions using a hash table


0
vote

problema

Español

El objetivo de este programa es encontrar todo Factorions , que son números iguales a la Suma de los factoriales de sus dígitos.

Estoy buscando sugerencias sobre cómo mejorar el desempeño de este Código, así como el asesoramiento estilístico.

  #include <stdio.h> #include <stdlib.h> #define base 10 //We are working in base 10 #define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits. //If it has d digits, it must satisfy the inequality 10^{d-1} < n <= 9!d, which isn't satisfied above d = 8 #define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10  //Function prototype void create_hash_table(int[]); void get_fact_digit_sum(int[],int[]); void display_answers(int[]);  int main() {     int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -> n!      create_hash_table(hash_table_fact);      get_fact_digit_sum(answers,hash_table_fact);      display_answers(answers);      return 0; }  void create_hash_table(int hash_table_fact[]) {            int i = 1, fact = 1;     hash_table_fact[0] = 1; //0! = 1      for(i = 1; i < base; i++)     {         fact = fact*i;         hash_table_fact[i] = fact;     } }  void get_fact_digit_sum(int answers[], int hash_table_fact[]) {     int answerCount = 0, i = 1, temp, sum;      //Combing through the search space to search for factorions     for(i = 1; i <= upper_bound; i++)     {         temp = i;         sum = 0;         //Getting the sum of the factorials of the digits         while(temp != 0)         {             sum = sum + hash_table_fact[ (temp%base) ];             temp = temp/base;         }         if(sum == i)         {             answers[answerCount++] = i;         }     }      //Placing a 0 at the end to mark the end of the array     answers[answerCount] = 0; }  void display_answers(int answers[]) {     int i;      for(i = 0; answers[i] != 0; i++)     {         printf("%d ",answers[i]);     } }   
Original en ingles

The objective of this program is to find all factorions, which are numbers equal to the sum of the factorials of their digits.

I am seeking suggestions on how to improve the performance of this code, as well as stylistic advice.

#include <stdio.h> #include <stdlib.h> #define base 10 //We are working in base 10 #define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits. //If it has d digits, it must satisfy the inequality 10^{d-1} < n <= 9!d, which isn't satisfied above d = 8 #define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10  //Function prototype void create_hash_table(int[]); void get_fact_digit_sum(int[],int[]); void display_answers(int[]);  int main() {     int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -> n!      create_hash_table(hash_table_fact);      get_fact_digit_sum(answers,hash_table_fact);      display_answers(answers);      return 0; }  void create_hash_table(int hash_table_fact[]) {            int i = 1, fact = 1;     hash_table_fact[0] = 1; //0! = 1      for(i = 1; i < base; i++)     {         fact = fact*i;         hash_table_fact[i] = fact;     } }  void get_fact_digit_sum(int answers[], int hash_table_fact[]) {     int answerCount = 0, i = 1, temp, sum;      //Combing through the search space to search for factorions     for(i = 1; i <= upper_bound; i++)     {         temp = i;         sum = 0;         //Getting the sum of the factorials of the digits         while(temp != 0)         {             sum = sum + hash_table_fact[ (temp%base) ];             temp = temp/base;         }         if(sum == i)         {             answers[answerCount++] = i;         }     }      //Placing a 0 at the end to mark the end of the array     answers[answerCount] = 0; }  void display_answers(int answers[]) {     int i;      for(i = 0; answers[i] != 0; i++)     {         printf("%d\t",answers[i]);     } } 
  
     
     

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

Puede usar la suma anterior para calcular la siguiente

Su bucle principal calcula la suma de factoriales de los dígitos desde cero para cada número, pero está desechando mucho trabajo de número a número. Piense en dos números consecutivos, tales como:

  1234: sum = 1! + 2! + 3! + 4! 1235: sum = 1! + 2! + 3! + 5!   

Puede ver que para 1235 , solo difiere de 1234 por el último dígito, para que pueda calcular su suma más rápidamente si realiza esto:

  sum = previousSum + 5! - 4!   

Si el último dígito se envuelve desde 9 a 0 , tiene que hacer lo mismo con el siguiente dígito a la izquierda:

  1239: sum = 1! + 2! + 3! + 9! 1240: sum = 1! + 2! + 4! + 0!  sum  = previousSum; sum += 0! - 9! // Ones digit sum += 4! - 3! // Tens digit   

Si alcanza un nuevo poder de 10, debe hacer algo un poco diferente:

   99: sum =      9! + 9! 100: sum = 1! + 0! + 0!  sum  = previousSum; sum += 0! - 9! // Ones digit sum += 0! - 9! // Tens digit sum += 1!      // Hundreds digit (note: do not subtract 0!)   

Reescribe de muestra

Usando esta idea, su función se convierte en esto:

  void get_fact_digit_sum(int answers[], int hash_table_fact[]) {     int answerCount = 0;     int sum         = 1;      // Combing through the search space to search for factorions     for (int i = 1; i <= upper_bound; i++) {         int temp = i;          while (1) {             int digit = temp % base;             if (digit == 0) {                 sum += hash_table_fact[0] - hash_table_fact[base-1];                 temp /= base;                 if (temp == 1) {                     // Special case: reached new digit.                     sum += hash_table_fact[1];                     break;                 }             } else {                 sum += hash_table_fact[digit] - hash_table_fact[digit-1];                 break;             }         }         if (sum == i) {             answers[answerCount++] = i;         }     }      // Placing a 0 at the end to mark the end of the array     answers[answerCount] = 0; }   

La nueva forma en que corrió 4x más rápido que la forma antigua para el límite superior dado. Si extiendes el límite superior a 100 millones (aunque no hay respuestas que sean altas), la nueva forma se ejecuta 8 veces más rápido que el camino anterior.

 

You can use the previous sum to compute the next one

Your main loop computes the sum of factorials of digits from scratch for each number, but you are throwing away a lot of work from number to number. Think about two consecutive numbers, such as:

1234: sum = 1! + 2! + 3! + 4! 1235: sum = 1! + 2! + 3! + 5! 

You can see that for 1235, it only differs from 1234 by the last digit, so you can compute its sum more quickly if you do this:

sum = previousSum + 5! - 4! 

If the last digit wraps around from 9 to 0, you have to do the same thing with the next digit on the left:

1239: sum = 1! + 2! + 3! + 9! 1240: sum = 1! + 2! + 4! + 0!  sum  = previousSum; sum += 0! - 9! // Ones digit sum += 4! - 3! // Tens digit 

If you reach a new power of 10, you need to do something a little different:

 99: sum =      9! + 9! 100: sum = 1! + 0! + 0!  sum  = previousSum; sum += 0! - 9! // Ones digit sum += 0! - 9! // Tens digit sum += 1!      // Hundreds digit (note: do not subtract 0!) 

Sample rewrite

Using this idea, your function becomes this:

void get_fact_digit_sum(int answers[], int hash_table_fact[]) {     int answerCount = 0;     int sum         = 1;      // Combing through the search space to search for factorions     for (int i = 1; i <= upper_bound; i++) {         int temp = i;          while (1) {             int digit = temp % base;             if (digit == 0) {                 sum += hash_table_fact[0] - hash_table_fact[base-1];                 temp /= base;                 if (temp == 1) {                     // Special case: reached new digit.                     sum += hash_table_fact[1];                     break;                 }             } else {                 sum += hash_table_fact[digit] - hash_table_fact[digit-1];                 break;             }         }         if (sum == i) {             answers[answerCount++] = i;         }     }      // Placing a 0 at the end to mark the end of the array     answers[answerCount] = 0; } 

The new way ran 4x faster than the old way for the given upper bound. If you extend the upper bound to 100 million (even though there are no answers that high), the new way runs 8x faster than the old way.

 
 
         
         

Relacionados problema

12  Codificación de árbol binario  ( Binary tree encoding ) 
Implementé una solución a este desafío de codificación en el código de golf. Tengo experiencia decente con C / C ++, pero ha sido un tiempo desde que los us...

4  C Socket Parte-1  ( C socket part 1 ) 
En mis intentos en curso de convertirse en un mejor escritor de blog, tengo algunos códigos más que necesitan revisar. Fuente completa: https://github.com/...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

14  Representación de OpenGL ACTUPTAR  ( Opengl instanced rendering ) 
Tengo una configuración de representación muy básica de OpenGL ANDRANCT, que está compilando y funcionando, sin embargo, es super lento, y aunque pasé días de...

4  Juego de Runas: Versión 3  ( Game of runes version 3 ) 
He escrito una versión muy revisada y desarrollada de la juego de runas . Los cambios principales se enumeran: Convertir runas para usar maldiciones. ag...

2  Función para borrar un carácter en una cadena  ( Function to erase a character in a string ) 
void chrrem (char arr[], size_t len, size_t pos) { memmove(arr + pos, arr + (pos + 1), (len - pos) + 1); } Se supone que es simplemente rápido. Borra...

6  Palindrome más largo en una matriz  ( Longest palindrome in an array ) 
Soy nuevo en la programación, y creo que este código podría mejorarse. ¿Alguna sugerencia? 'done'0 ...

38  Sundoku Solver en C  ( Sudoku solver in c ) 
Tuve este código que miente, así que pensé que sometería esto como mi primer intento de una Fin de semana: desafío . Preferiría si las revisiones contenían s...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...

2  Mejora de la función que compara dos cadenas  ( Improving function that compares two strings ) 
Estoy aprendiendo C y he hecho esta función muy simple para comparar dos cuerdas. Me gustaría saber cómo se puede mejorar: int match(char* string1, char* s...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos