Encuentra el mínimo de la función.
PS
dónde y $$ f(x,y)=|ax-by+c|$.
Las preguntas aquí y aquí son similares, pero son en casos en que$a,b,c \in \mathbb N$ están delimitados. Tomando las derivadas parciales, etc. no ayuda ¿Hay una manera de hacerlo de manera eficiente (para un programa de computadora)?
Respuestas
¿Demasiados anuncios?
user30382
Puntos
48
El valor positivo más pequeño que toma$ax-by$ es$\gcd(a,b)$. La búsqueda de$x_0$ y$y_0$ para la cual$ax-by$ es mínimo se puede hacer con el algoritmo de Euclides. Luego tome un múltiplo apropiado de$x_0$ y$y_0$ para acercarse lo más posible a$c$, es decir, multiplique ambos por$\tfrac{c}{\gcd(a,b)}$ redondeado al número entero más cercano.
Mutasim Mim
Puntos
66
Dejar $(a,b)=d$. Tenga en cuenta que para todos los$k\in \mathbb Z$, hay$x,y\in \mathbb Z$ tal que$ax-by=kd$. Además, para todos los$x,y\in \mathbb Z$,$ax-by$ tiene la forma$kd$, para algunos$k\in \mathbb Z$. Por lo tanto, el valor mínimo de$|ax-by+c|$ es el mismo que el valor mínimo de los números del formulario$|kd+c|$. Es obvio que este valor mínimo es$c$$(\mod gcd(a,b)).$
