Recorrido del diccionario en lenguaje c
Ayuda, informe en lenguaje C del factor de descomposición | Aún quedan 14 días y 3 horas hasta el final del problema. Preguntado por: Cloud Guardian | Puntos de recompensa: 30 | Vistas: 40 veces.
Dado un entero positivo A, es necesario descomponerlo en el producto de varios enteros positivos, es decir, a = a1 * a2 * a3 *...* an y 1
La salida debe ser un número entero positivo que indique el número de descomposición que cumple con los requisitos.
Por ejemplo, hay cuatro representaciones suplementarias de 20:
Solo explica mis pensamientos claramente~ ~
Gracias
Debería Cabe señalar que está hablando de "factorización" (el contenido del aprendizaje de matemáticas en la escuela primaria) en lugar de "factorización" para los talentos de la escuela secundaria (esta última es mucho más difícil de implementar en una computadora). Por supuesto, la "factorización" no incluye el caso en el que sólo hay un factor.
Para esta pregunta, debe ser una pregunta de competencia para estudiantes de secundaria. No es necesario construir una biblioteca de números primos.
Existen al menos dos formas de pensar. 1. Genere varias descomposiciones una por una según el orden del diccionario, como la descomposición de 20 en el orden del diccionario: (2, 2, 5), (2, 10), (4, 5), (20), y genere cada descomposición en este orden. La otra es generar una clase una por una según el número de factores de descomposición, y cada clase se genera una por una en orden del diccionario. Por ejemplo, para 20, un factor tiene un caso, (20) dos factores tienen dos casos: (2, 10) y (4, 5) tres factores tienen el caso (2, 2, 5); Los casos tienen cuatro o más factores.
Para ahorrar espacio, primero estime el límite superior del número de factores que no sea demasiado grande. La forma más sencilla es encontrar el factor primo más pequeño de un entero dado A (que se puede suponer que es un entero positivo), sea b1, de modo que n = [log _ b1 (A)] (el logaritmo de A con b 1 ya que la base se redondea. Este último se expresa como n = (en lenguaje C.
Si desea ser preciso para ahorrar espacio (especialmente cuando A es grande, esto es necesario), primero puede encuentre el número de todos los factores primos (incluida la repetición) para determinar el número máximo de factores después de la descomposición, no es complicado, puede determinar n = a
m = (int) (sqrt (. D; )) 1, n=0, c = 2;
mientras (m gt; c)
{ si (D c = = 0)
{ n;
printf("d",c);
D = D/c;
if (D==1)romper;
p>
else printf(",",c);
m = (int)(sqrt(D)) 1;
}
else c;
if (m lt; = c) { n; printf ("D", D }
}
<); p>printf( ")\nEl número de factores primos de un número entero es d.\n",n);Analicemos cómo usar la primera idea para dar todas las descomposiciones de A (el cartel puede considerar el segundo por sí mismo. La idea y la dificultad son las mismas; pero el primer método puede reducir algunos cálculos repetidos sin aumentar la sobrecarga de espacio.
Dado que a se puede descomponer en el producto directo de n factores como máximo. , se utilizan dos matrices. Representa cada factor y el rango de valores aproximado de cada factor. Utilice A[n] para representar cada factor y B[n] para representar el rango de cada factor. descomponerse excepto por un factor en al menos dos factores, A[1]*A[2], donde A[1]
Hasta que un cierto k haga A[k]* A[k]》. : E[k] hace A 【k 1】= E【k】.
De esta forma se obtiene un patrón de descomposición: a = a[1]* a[2]*...* a[k]* a[k 1].
Al retroceder, deje que A[k] se agregue solo. Si E[k-1] A[k]== 0, se obtiene otro método de descomposición. Cuando se hayan atravesado todos los casos de A [k], realice la autoadición de A [k-1] para atravesar nuevamente.
Hasta que A[1] haya atravesado todas las situaciones.
El programa transversal solo necesita modificar el programa anterior para encontrar el número de factores primos.
Los programas factibles son los siguientes:
# include ltstdio.h gt
# include ltmalloc.h gt
# include ltmath .h gt
Main()
{ int a, b, c, n, F, F1, D, num, I, I, m
printf("\nEste programa obtendrá el número de factorizaciones sin clasificar de un entero determinado. Ingrese un entero positivo mayor que 1. \nEntrada numérica: ");
scanf ("d", ampa);
if (a lt; 2)
{ printf (\n Entrada error. \n ");
devuelve 0;
}
printf("\nEl número primo del entero d dado. Los factores son los siguientes: \n \t(", a);
d = a;
m = (int) (sqrt (D)) 1, n = 0, c = 2;
mientras (m gt; c)
{ si (D c = = 0)
{ n;
printf ("d ",c);
D = D/c;
if (D==1) romper;
si no printf("," , c) ;
m = (int) (sqrt (D)) 1;
}
else c
if (m lt; ; = c) { n; printf ("D", D); break; }
}
printf()\nEl número de factores primos de un número entero es d. \n",n);
if (n==1)
{ printf("\nEl número entero que ingresó es un número primo. Factorización sin clasificar El número es 1. \ n ");
Devuelve 1;
}
a = (int *) malloc (tamaño de (int) * n 1 );
if (A == NULL)
{ printf (\nError. Espacio de memoria insuficiente.\n ");
Devuelve 0;
}
b = (int *) malloc (tamaño de (int) * n 1
if (B == NULL)
{ printf(\nError); . Espacio de memoria insuficiente. \ n ");
Devuelve 0;
}
e = (int *) malloc (sizeof (int) * n 1);
if(E==NULL)
{ printf(\nError. Espacio de memoria insuficiente.
\n ");
Devuelve 0;
}
e【0】= A, A【0】= 2, A【1】= 1 , num = 0;
b[1]=(int)(sqrt(E[0])) 1;
I = 1;
mientras (I gt; 0 amp lt=n)
{ F=0, F 1 = 0;
//printf("\n I = d, B[I ]= d, E【I-1】= d, A【I-1】= d.", I, B【I], E【I-1】, A【I-1】);
//if (I gt; n) { printf ("\n Error. I = d gtn = d.\n", I, n); return -1; I]; a[I] lt; b[I]; a[I] )
{//printf ("\n A[I] = d, ", A[I]) ;
if (E[I-1] A[I]== 0)
{ //printf ("Válido.);
E[ I] = E[I-1]/A[I]; F, f 1;
si (E[I] lt; A[I]* A[I] amp; ampf 1 = = 0) //E【Yo】! =1
{ printf("\nFactorización válida: d=",A);
if(I gt;0) printf("d",A[ 1]);
if (I gt; 1) for (I = 2; I lt I; i) printf ("* d", A
printf ("* d", E[I]);
num;
f = 0;
}
else / /F1! = 0 | I 1]= A[I]-1; i; romper;}
}//finalizar si (E[I-1] A[I]= = 0)
//else printf ("No válido);
} //Finalizar bucle I
if (F = = 0. ampf 1 = = 0) //E [ I-1 】No es divisible por todos los posibles A[I]
{ printf ("\nFactorización válida: d=",A);
if (I gt; 1)
{ printf("d*",A【1】);
for(I = 2;iltI;i) printf("d*",A 【I】);
}
printf("d",E【I-1】);
num, I-;
}
}// while(I gt; 0)
printf("\nEl número de factorización sin clasificar del entero dado es d.\n", num);
Gratis (A);
Gratis (B);
Gratis (E);
Devolución 1;
}
Compilado por gcc, cuando se ingresa 20, el resultado es el siguiente:
Este programa obtendrá el número de factorizaciones sin clasificar de un número entero determinado. Ingrese un número entero positivo mayor que 1. .
Ingreso numérico: 20
Los factores primos del entero dado 20 son los siguientes:
(2, 2, 5)
Entero El número de factores primos es 3.
Una factorización válida: 20=2*2*5
Una factorización válida: 20=2*10
Un factor válido Descomposición de fórmulas: 20=4 *5
Una factorización válida: 20=20
El número de factorización desordenada del entero dado es 4.
Cuando se ingresa 36, el resultado es el siguiente.
Este programa obtendrá el número de factorizaciones sin ordenar de un número entero dado. Introduzca un número entero positivo mayor que 1.
Ingreso numérico: 36
Los factores primos del entero dado 36 son los siguientes:
(2, 2, 3, 3)
El número de factores primos de un número entero es 4.
Una factorización válida: 36=2*2*3*3
Una factorización válida: 36=2*2*9
Una factorización válida: 36 =2*3*6
Una factorización válida: 36=2*18
Una factorización válida: 36=3 *3*4
Una factorización válida : 36=3*12
Una factorización válida: 36=4*9
Una factorización válida Factorización de: 36=6*6
Una factorización válida : 36=36
El número de factorización desordenada del entero dado es 9.