Información completa y detallada sobre la división de enteros

La teoría de la división de enteros estudia principalmente las propiedades de varios tipos de funciones de división y sus interrelaciones. Ya en la Edad Media se investigaban problemas especiales de división de números enteros. En la década de 1840, L. Euler propuso utilizar el método de la función generativa (o método formal de series de potencias) para estudiar la división de enteros, lo que demostró muchos teoremas importantes y sentó las bases teóricas para la división de enteros. La introducción del método del círculo en la teoría analítica de números desarrolló aún más la teoría de la división de enteros. La división de enteros está estrechamente relacionada con las funciones modulares y tiene importantes aplicaciones en matemáticas combinatorias, teoría de grupos, teoría de probabilidades, estadística matemática y física de partículas. Introducción básica Nombre chino: División de enteros Nombre extranjero: División de enteros, Partición Materia: Matemáticas Aplicación: Estudiar las propiedades y las interrelaciones de varias funciones divididas Propuesto por: Leonhard Euler Figuras relevantes: G.H Hardy, Principio de Srinivasa Ramanujan, clasificación, ejemplos, estimación de números divididos , prueba del teorema de estimación de números divididos, propiedades de números divididos, propiedad uno, propiedad dos, propiedad tres, método de cálculo de números divididos, recurrencia Método de inferencia, método de programación dinámica, método de función generadora, método de números pentagonales, principio El problema de división de enteros es antiguo y muy problema interesante. La llamada división de números enteros se refiere a expresar un número entero positivo como la suma de varios números enteros positivos. Clasificación Dependiendo de si se considera el orden de las partes divididas, podemos dividir el problema de división de enteros en división ordenada (composición) y división desordenada (partición). La diferencia entre ambos es la siguiente: En la división ordenada, se considera el orden entre las sumas de las partes divididas. Supongamos que las diferentes clasificaciones entre , se registran como esquemas diferentes, que se denominan k divisiones ordenadas de n. Por ejemplo, las 2 divisiones ordenadas de 3 son: 3 = 1 + 2 = 2 + 1. Podemos modelar este problema como un problema de "partición" en permutación y combinación, es decir, si n bolas indistinguibles se dividen en r partes y cada parte tiene al menos una bola, es necesario insertar r-1 particiones entre las bolas. Hay n-1 espacios entre ellos, por lo que el número total de opciones es C(n-1,r-1). En una división desordenada, no se considera el orden en que se suman. Generalmente se supone que lo llamamos división k desordenada de n. Por ejemplo, la división k desordenada de 3 es: 3 = 1 + 2. Esta división puede entenderse como dividir n bolas indistinguibles en r partes y cada parte tiene al menos una bola. Generalmente, el número de divisiones desordenadas está representado por p (n), luego p (2) = 1, p (3) = 2, p (4) = 4. En general, la división de enteros se refiere a la división desordenada de números enteros. Ejemplo Ejemplo 1 Hay una pesa de 1 gramo, 2 gramos, 3 gramos y 4 gramos. ¿Cuántas pesas se pueden pesar? ¿De cuántas maneras podemos pesar cada pesa? Este problema puede verse como el número de divisiones donde n se divide en la suma de 1, 2, 3 y 4 sin permitir la repetición. La función principal se usa para calcular de la siguiente manera: Significa que hay dos formas de pesar 4. gramos, que son 1+3 y 2+2, y así sucesivamente, si supera los 10 gramos no se puede pesar. Ejemplo 2 Divide 14 entre la suma de dos números naturales y maximiza el producto de estos dos números naturales. ¿Cómo se debe dividir? Análisis y solución no consideran el orden de la suma, divide 14 en la suma de dos números naturales, quedan 1+13, 2+12, 3+11, 4+10, 5+9, 6+8, 7+7 ** *Siete métodos. Después del cálculo, es fácil saber que cuando 14 se divide entre 7+7, el producto máximo es 7×7=49. Ejemplo 3 ¿Cómo dividir 15 entre la suma de dos números naturales y maximizar el producto de estos dos números naturales? El análisis y la solución no consideran el orden de la suma. 15 se puede dividir en la suma de dos números naturales de la siguiente forma: 1+14, 2+13, 3+12, 4+11, 5+10, 6+9. , 7+ 8. Obviamente, cuando 15 se divide entre 7+8, el producto máximo es 7×8=56. Nota: Se puede ver en los dos ejemplos anteriores que cuando un número natural se divide por la suma de dos números naturales, si el número natural es un número par 2m, cuando se divide en m + m, hay un producto máximo m×m=m2; si el número natural es El número impar 2m+1, cuando se divide en m+(m+1), tiene el producto máximo m×(m+1). Ejemplo 4 ¿Cómo dividir 14 entre la suma de tres números naturales y maximizar el producto de estos tres números naturales? Análisis y solución Obviamente, sólo haciendo la diferencia entre los números divididos lo más pequeña posible (como 0 o 1) el producto obtenido puede ser el mayor.

No es difícil pensar que cuando 14 se divide en 4+5+5, el producto máximo es 4×5×5=100. Estimación de números divididos Históricamente, se han realizado muchos estudios sobre la división de enteros, incluido G.E Hardy de la Universidad de Cambridge en el Reino Unido y los académicos indios Ramanujan y Hardy encontraron un valor asintótico relevante a través de su propia investigación. Un entero positivo n se divide en la suma de varios enteros positivos. Los diferentes números divididos están representados por p (n). La función principal de {p (n)} es: Entonces el número dividido se puede estimar como: número dividido. La prueba del teorema de estimación se basa en la serie de MacRolin: Entonces: Y como así, así, pero así, dejemos que la curva y = lnx sea convexa hacia arriba, por lo que la recta tangente de la curva y = lnx en (1,0) es y = x- 1, es decir, para encontrar el valor mínimo: Sea su derivada de primer orden, la solución de la ecuación es y debido a la derivada de segundo orden de y, el valor mínimo de y es Entonces la propiedad del número dividido propiedad entera n se divide en el número más grande es el número de divisiones de k, y el número de divisiones de la suma n dividida en k números es el mismo. Propiedad 2: El número de divisiones de un número entero n en sumas de como máximo m números es igual al número de divisiones de n en sumas de no más de m números. Propiedad 3: El número de divisiones de la suma de varios números impares que son diferentes entre sí es el mismo que el número de divisiones de n en la imagen de Ferrers del yugo autosexual. Método de cálculo de números divididos La división de enteros se puede calcular mediante la fórmula asintótica. A medida que N se vuelve infinito, el valor estimado de la división de enteros se acerca al valor real. En los tiempos modernos, también se pueden utilizar métodos informáticos para resolverlo. Aquí, presentamos principalmente 4 métodos de cálculo. El método recursivo considera las siguientes situaciones según la relación entre n y m: (1) Cuando n = 1, no importa cuál sea el valor de m (m>0), solo hay una división, a saber, {1} ( 2) Cuando m = 1, no importa cuál sea el valor (n>0), solo hay una división, a saber, {1,1,....1,1,1} (3) Cuando n = m, según la división, si n está incluido se puede dividir en dos situaciones: (a) Cuando n está incluido en la división, solo hay uno, a saber, {n} (b) Cuando n no está incluido en la división, el También es seguro que el número más grande en la división es menor que n, es decir, todas las (n-1) particiones de n, por lo tanto, f(n,n) = 1 + f(n, n - 1). (4) Cuando n m, dependiendo de si m está incluido en la división, se puede dividir; en dos situaciones: (a) El caso incluido en la partición, es decir, {m,{x1,x2,x3,...,xi}}, donde la suma de {x1,x2,x3,...,xi} es n-m, posiblemente aparezca m nuevamente, por lo que es una división m de (n-m), por lo que el número de tales divisiones es f(n-m,m; (b) Si m no está incluido en la división, todos los valores en la la división es menor que m, es decir, (m-1) división, el número es f(n,m-1; por lo tanto, f(n,m)=f(n-m,m)+f(n,m-1 ). Con base en las situaciones anteriores, podemos ver Resulta que la conclusión anterior tiene las características de una definición recursiva, entre las cuales (1) y (2) pertenecen a condiciones de regresión, (3) y (4) pertenecen a casos especiales. , y el caso (5) es un caso general y pertenece al método recursivo, cuya esencia El problema se resuelve principalmente reduciendo n o m para lograr condiciones de regresión.

La fórmula recursiva detallada se describe a continuación: Código fuente de referencia #include?#define?MYDATA?long?longconst?MYDATA?MOD?=?1000000007;#define?MAXNUM?100005¿Número más alto de veces?Método recursivo para resolver división de enteros sin signo? long?GetPartitionCount(int?n,?int?max){if?(n?==?1?||?max?==?1)return?1;if?(n?

El código fuente de referencia es el siguiente: #include?#define?MYDATA?long?longconst?MYDATA?MOD?=?1000000007;#define?MAXNUM?1005Tiempos máximos?unsigned?long?ww[MAXNUM?*?11 ][MAXNUM ?*?11];unsigned?long?dynamic_GetPartitionCount(int?n,?int?max);usando?namespace?std;int?main(int?argc,?char?**argv){int?n ;int? m;unsigned?long?count;mientras?(1){cin?>>?n;cout?<

Código fuente de referencia: #include?#include?#include?using?namespace?std;#define?MYDATA?long?longconst?MYDATA?MOD?=?1000000007;const ?int?N?=?100005;int?c1[N],?c2[N];int?main(int?argc,?char**?argv){int?n,?i,?j,?k ; mientras?(cin?>>?n){si?(n?==?0)?break;para?(i?=?0;?i?<=?n;?i++){c1[i] ? =?1;c2[i]?=?0;}para?(i?=?2;?i?<=?n;?i++){para?(j?=?0;?j?<= ? n;?j++)para?(k?=?0;?k?+?j?<=?n;?k?+=?i)c2[k?+?j]?=?(c2[k ? +?j]?+?c1[j])?%?MOD;para?(j?=?0;?j?<=?n;?j++){c1[j]?=?c2[j] ; c2[j]?=?0;}}cout?<

En , los coeficientes en el lado derecho de la ecuación son todos 0. Comparando los coeficientes en ambos lados de la ecuación, podemos obtener la fórmula recursiva de la función de división: Entonces, a través de la fórmula recursiva anterior, podemos calcular rápidamente el número de planes de división de enteros.

Código de referencia: #include?using?namespace?std;#define?MYDATA?long?longconst?MYDATA?MOD?=?1000000007;#define?AMS?100005MYDATA?pp[AMS];MYDATA?asist[2? *?AMS];void?myinit(){for?(int?i?=?0;?i?>?n;cout?<