Autor
|
Tema: Ayuda. (Leído 3,172 veces)
|
Jonhy_xc
Desconectado
Mensajes: 2
|
|
Ayuda.
« en: 22 Febrero 2019, 19:22 pm » |
|
Hola,
Necesitaría ayuda con un "problema" que consiste en calcular la distancia mínima de un número hasta el 1 en la espitar de Ulam. Solo te darían un número y la espiral de Ulam es infinita.
Se puede comprobar que los dígitos (comenzando por el 1) están dispuestos siguiendo un patrón en espiral de dentro hacia afuera.
17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23 --> ...
Se nos pide calcular la distancia más corta (distancia manhattan) de un número entero n hasta el 1. Para calcular esta distancia sólo se permiten movimientos hacia arriba, abajo, izquierda y derecha.
Un ejemplo sería: La distancia según este cálculo del 7 al 1 es 2.
Muchas gracias de antemano.
|
|
« Última modificación: 25 Febrero 2019, 15:00 pm por Jonhy_xc »
|
En línea
|
|
|
|
CalgaryCorpus
|
Tiene cara de ser la parte entera de la mitad de la raiz cuadrada del numero.
|
|
« Última modificación: 23 Febrero 2019, 19:52 pm por CalgaryCorpus »
|
En línea
|
|
|
|
MAFUS
Desconectado
Mensajes: 1.603
|
No, 3 tiene distancia 2. Debe ser otra cosa.
|
|
|
En línea
|
|
|
|
K-YreX
|
Tenía la intuición de que no parece un problema que se resuelva con una única fórmula. Por lo que intenté ir sacando relaciones a ver si llegaba a algo... Empecé encontrando algunas recurrencias que al final resultaron ser más sencillas. Mi planteamiento era el siguiente: - La espiral podemos verla como si fueran anillos concéntricos (el 1 es el anillo 0).
- El máximo valor del anillo n es (2*n+1)*(2*n+1) y se encuentra en la esquina inferior derecha de su anillo correspondiente.
El problema es que no tengo demasiado tiempo y como me parece un problema entretenido dejo aquí mis avances por si alguien quiere continuar con ello y que no se quede abandonado. (Tengo algunas recurrencias más por si le interesan a alguien... aunque creo que no son demasiado importantes). Luego he visto que por ahí se me iba a complicar mucho la cosa así que he pensado que se puede hacer una matriz donde dibujar la espiral calculando antes el número de anillos necesarios para que la espiral contenga el número que desea buscar el usuario. De ahí he sacado que: - El orden de la matriz que contiene n anillos es (2*n-1).
Me parece que la forma más sencilla es esta segunda (aunque sea un poco limitada). crear matriz con la forma de la espiral valor_actual := valor introducido por el usuario mientras valor_actual != 1 comparar con arriba, abajo, izquierda, derecha (cuidado con los limites) valor_actual := menor de los 4 valores anteriores distancia++
Cuando tenga tiempo intentaré acabarlo
|
|
|
En línea
|
cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
|
|
|
Loretz
Desconectado
Mensajes: 117
|
Debe haber por ahí alguna fórmula genial, de esas del tipo (a+b)^2 que nos deje a todos con la boca abierta, pero andando a pie, siguiendo la descripción más pedestre posible, mi algoritmo es este: #include <iostream> #include <cmath> #include <array>
int main() { // el primer círculo empieza en 2 y termina en 9 // el segundo empieza en 10 y termina en 25 // el tercero ... de 26 a 49 ...
// Claramente, cada círculo empieza donde termina el anterior y // terminan en 9 (3*3) o en 25 (5*5) o en 49 (7*7) ... [los cuadrados del número de elementos de sus lados]
// También, cada círculo tiene elementos que están más próximos al centro y están ubicados en cruz:
// Se ve que en la rama de la derecha de esa cruz están: // el 2 (primer círculo), // el 11 (su número de círculo + los elementos del círculo anterior = 2 + 9), // el 28 (su número de círculo + los elementos del círculo anterior = 3 + 25). // y lo mismo para los siguientes...
// Mirando también en las otras direcciones, // el primer círculo tiene en esa cruz al 2, que es por donde empieza, // y en las otras ramas al 4 (o sea, el 2 + su número de elementos por lado = 4), // tiene también al 6 (4 + su número de elementos por lado = 6) // y al 8 (6 + su número de elementos por lado -1 == 8). // Así que para el primer círculo esa cruz está formada por el 2, 4, 6, 8.
// Lo mismo para los otros círculos: // el segundo círculo tiene al 11, 15, 19 y 23.
// Cada círculo va a tener 4 números sobre la cruz: // el primero que está en el brazo horizontal de la derecha // y los otros tres distando entre sí la cantidad de elementos en cada lado.
// Bueno, eso es todo.
// Para calcular la distancia al centro de un número cualquiera habrá que calcular // la distancia a la rama más próxima de la cruz y sumar su número de círculo.
// Por ejemplo: dado un númeo cualquiera:
int n; std::cout << "numero: "; std::cin >> n;
// Se puede determinar a qué círculo pertenece: int c = 0; for (int i = 1; ; i += 2, ++c) { // 1, 3, 5, 7, ... if (i*i >= n) { break; } } std::cout << n << " pertenece al circulo " << c << '\n';
// Este círculo tiene 4 números sobre la cruz central: std::array<int, 4> cruz;
// El primero (rama de la derecha) es: cruz[0] = c + (2 * c - 1)*(2 * c - 1); // su número de círculo más los elementos del círculo anterior
// y los otros tres van a ser: for (int i = 1; i < 4; ++i) { cruz[i] = cruz[i - 1] + c * 2; // número anterior en la cruz + cantidad de elementos del lado }
std::cout << "los elementos de la cruz son: "; for (const auto& i : cruz) { std::cout << i << " "; } std::cout << '\n';
// Ahora, la distancia al centro de este número es: // la distancia al elemento de la cruz más cercano + su número de círculo:
int dist_cruz = 1000; // absurdamente grande for (int i = 0; i < 4; ++i) { if(abs(cruz[i] - n) < dist_cruz) { dist_cruz = abs(cruz[i] - n); } } int distancia = dist_cruz + c;
std::cout << "distancia al centro = " << distancia << '\n'; }
|
|
|
En línea
|
|
|
|
Jonhy_xc
Desconectado
Mensajes: 2
|
Debe haber por ahí alguna fórmula genial, de esas del tipo (a+b)^2 que nos deje a todos con la boca abierta, pero andando a pie, siguiendo la descripción más pedestre posible, mi algoritmo es este: #include <iostream> #include <cmath> #include <array>
int main() { // el primer círculo empieza en 2 y termina en 9 // el segundo empieza en 10 y termina en 25 // el tercero ... de 26 a 49 ...
// Claramente, cada círculo empieza donde termina el anterior y // terminan en 9 (3*3) o en 25 (5*5) o en 49 (7*7) ... [los cuadrados del número de elementos de sus lados]
// También, cada círculo tiene elementos que están más próximos al centro y están ubicados en cruz:
// Se ve que en la rama de la derecha de esa cruz están: // el 2 (primer círculo), // el 11 (su número de círculo + los elementos del círculo anterior = 2 + 9), // el 28 (su número de círculo + los elementos del círculo anterior = 3 + 25). // y lo mismo para los siguientes...
// Mirando también en las otras direcciones, // el primer círculo tiene en esa cruz al 2, que es por donde empieza, // y en las otras ramas al 4 (o sea, el 2 + su número de elementos por lado = 4), // tiene también al 6 (4 + su número de elementos por lado = 6) // y al 8 (6 + su número de elementos por lado -1 == 8). // Así que para el primer círculo esa cruz está formada por el 2, 4, 6, 8.
// Lo mismo para los otros círculos: // el segundo círculo tiene al 11, 15, 19 y 23.
// Cada círculo va a tener 4 números sobre la cruz: // el primero que está en el brazo horizontal de la derecha // y los otros tres distando entre sí la cantidad de elementos en cada lado.
// Bueno, eso es todo.
// Para calcular la distancia al centro de un número cualquiera habrá que calcular // la distancia a la rama más próxima de la cruz y sumar su número de círculo.
// Por ejemplo: dado un númeo cualquiera:
int n; std::cout << "numero: "; std::cin >> n;
// Se puede determinar a qué círculo pertenece: int c = 0; for (int i = 1; ; i += 2, ++c) { // 1, 3, 5, 7, ... if (i*i >= n) { break; } } std::cout << n << " pertenece al circulo " << c << '\n';
// Este círculo tiene 4 números sobre la cruz central: std::array<int, 4> cruz;
// El primero (rama de la derecha) es: cruz[0] = c + (2 * c - 1)*(2 * c - 1); // su número de círculo más los elementos del círculo anterior
// y los otros tres van a ser: for (int i = 1; i < 4; ++i) { cruz[i] = cruz[i - 1] + c * 2; // número anterior en la cruz + cantidad de elementos del lado }
std::cout << "los elementos de la cruz son: "; for (const auto& i : cruz) { std::cout << i << " "; } std::cout << '\n';
// Ahora, la distancia al centro de este número es: // la distancia al elemento de la cruz más cercano + su número de círculo:
int dist_cruz = 1000; // absurdamente grande for (int i = 0; i < 4; ++i) { if(abs(cruz[i] - n) < dist_cruz) { dist_cruz = abs(cruz[i] - n); } } int distancia = dist_cruz + c;
std::cout << "distancia al centro = " << distancia << '\n'; } Muchísimas gracias!!
|
|
|
En línea
|
|
|
|
Serapis
|
Tiene cara de ser la parte entera de la mitad de la raiz cuadrada del numero.
Más o menos es así... puede sumar o restar 1 según el caso, es decir según lo que dice si para 7 distancia es 2, para 1 distancia es 1, entonces debe sumarse 1... Está mal dibujado, los cuadrados pares son las diganoles de las esquinas a la izquierda arriba y los cuadrados impares son las diagonales de la esquina abajo a la derecha... d0 = int(int(sqr(n))/2) +1 Ahora bien, precisa algún ajuste pués difiere... yo toda la vida lo he visto dibujado empezando con el 0, así los cuadrados pares son diagonales al 0, y los cuadrados impares diagonales al 1... ...por otro lado como es la distancia Manhattan lo que se pide y no la euclidiana, no basta con una simple fórmula, pero para los cuadrados (las 4 diagnales) es esta: d1 = int(sqr(n)) +1 ...y el resto de casos debe resolverse con pequeños ajustes... conociendo los valores al este, oeste, norte y sur (según cada caso) entre el cuadrado menor que encaja y el siquiente que cubre al número pedido. Dicho de otro modo, hay que calcular de qué cuadrado queda más cerca de 'n', para saber porque lado queda afectado (vertical/horizontal al centro) hasta el que tiene que llegar, entonces la fórmula general sería... Desde ese punto 'p' al N,E,S,O (N=norte, E=este, etc...) el valor es: Si queda más cerca del cuadrado mayor que 'n': d2 = (d0 + (n-p))Si queda más cerca del cuadrado menor que 'n': d2 = (d0 + (p-n))Nótese que igual que d1 es la distancia para las diagonales d0, los es para los valores en N,E,S,O... Así que dejo a tu esfuerzo calcuar 'p'... que con logaritmo 2 resulta fácil calcular...
|
|
« Última modificación: 24 Febrero 2019, 20:54 pm por NEBIRE »
|
En línea
|
|
|
|
Alfil
Desconectado
Mensajes: 1
|
|
Re: Ayuda.
« Respuesta #7 en: 27 Febrero 2019, 11:04 am » |
|
Para los números impares cuya raíz cuadrada es entera, como puede ser 9, 25, 49, ... da un resultado inesperado. La solución a la que yo he llegado: #include <iostream> #include <cmath>
using namespace std;
int main(){ int n; cout << "Numero: "; cin >> n;
int indice = 0; // indice mínimo necesario de la matriz for( int i = 1; i * i <= n; i += 2 ) { indice++; }
// almacena los 4 puntos cardinales de 1 respecto a n int cardinales[4];
// primer punto cardinal cardinales[0] = indice + (2 * indice - 1) * (2 * indice - 1);
// resto de puntos cardinales for( int i = 1; i < 4; i++ ){ cardinales[i] = cardinales[i - 1] + indice * 2; }
// distancia al mayor cardinal menor que n int distancia = abs(cardinales[0] - n); for( int i = 1; i < 4; i++ ) { if( abs(cardinales[i] - n) < distancia ) distancia = abs(cardinales[i] - n); }
int manhatan = distancia + indice;
float raiz = sqrt(n); int raiz_entera = (int)raiz;
// Si n es impar y su raiz cuadrada es entera if( (n % 2 != 0) && (raiz == raiz_entera) ) manhatan = manhatan - 2;
cout << "\nDistancia Manhatan al #1: " << manhatan << endl;
return 0; }
|
|
|
En línea
|
|
|
|
MAFUS
Desconectado
Mensajes: 1.603
|
|
Re: Ayuda.
« Respuesta #8 en: 27 Febrero 2019, 14:57 pm » |
|
¿Y qué tal una autocompletado? Cuando se crea la espiral se usa la técnica de ver qué número es menor de los adyacentes. De igual forma se introduce otro número, por tanto es una tupla, que sumará en una unidad el número de pasos. El 1 tienen 0 pasos. Por tanto El 2, cuyo número más bajo cercano será el 1 tendrá 0+1 pasos. El 3, cuyo número más bajo cercano será el 2 tendrá que 1+1 pasos. El 4, cuyo número más bajo cercano será el 1 tendrá 0+1 pasos. ... El 11, cuyo número más bajo cercano será el 2 tendrá 1+1 pasos. Etc.
Creo que un número de tamaño máximo MAX_INT será rápido de calcular.
|
|
« Última modificación: 27 Febrero 2019, 15:23 pm por MAFUS »
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
[Ayuda] Necesito ayuda para crear un buen video uso AF y Flash.
Diseño Gráfico
|
XXXXXX
|
1
|
5,498
|
11 Noviembre 2009, 00:17 am
por Sub_Cero
|
|
|
Ayuda por davor ayuda os ruego ayuda XD (SOLUCIONADO)
Hardware
|
XxRekcahlExX
|
6
|
10,567
|
24 Mayo 2010, 00:56 am
por Aprendiz-Oscuro
|
|
|
AYUDA -.- ahora no entro más en 4chan (tengo una duda, ayuda por favor)
Foro Libre
|
Draklit
|
6
|
8,750
|
15 Octubre 2010, 03:14 am
por Draklit
|
|
|
[PYTHON][AYUDA][ERROR] Necesito ayuda para instalar PyGTK 2 en windows 7
Scripting
|
Noxware
|
2
|
7,600
|
20 Septiembre 2014, 00:05 am
por Noxware
|
|
|
[AYUDA] Ayuda para poner en modo monitor mi tarjeta de red! Kali LInux
GNU/Linux
|
Santi__
|
1
|
8,966
|
12 Noviembre 2016, 18:25 pm
por Will21
|
|