Mensajes

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:

Código [Seleccionar] Expandir



#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;
}