Problema del triángulo

Question

Estoy tratando de resolver el problema 18 de Euler - > http://projecteuler.net/index.php?section=problems < !> amp; id = 18

Estoy tratando de hacer esto con c ++ (lo estoy volviendo a aprender y los problemas de euler son un buen material de aprendizaje / búsqueda)

#include <iostream>

using namespace std;

long long unsigned countNums(short,short,short array[][15],short,bool,bool);

int main(int argc,char **argv) {

    long long unsigned max = 0;
    long long unsigned sum;


    short piramide[][15] = {{75,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                            {95,64,0,0,0,0,0,0,0,0,0,0,0,0,0},
                            {17,47,82,0,0,0,0,0,0,0,0,0,0,0,0},
                            {18,35,87,10,0,0,0,0,0,0,0,0,0,0,0},
                            {20,4,82,47,65,0,0,0,0,0,0,0,0,0,0},
                            {19,1,23,75,3,34,0,0,0,0,0,0,0,0,0},
                            {88,2,77,73,7,63,67,0,0,0,0,0,0,0,0},
                            {99,65,4 ,28,6,16,70,92,0,0,0,0,0,0,0},
                            {41,41,26,56,83,40,80,70,33,0,0,0,0,0,0},
                            {41,48,72,33,47,32,37,16,94,29,0,0,0,0,0},
                            {53,71,44,65,25,43,91,52,97,51,14,0,0,0,0},
                            {70,11,33,28,77,73,17,78,39,68,17,57,0,0,0},
                            {91,71,52,38,17,14,91,43,58,50,27,29,48,0,0},
                            {63,66,4,68,89,53,67,30,73,16,69,87,40,31,0},
                            {4,62,98,27,23,9,70,98,73,93,38,53,60,4,23}};

    for (short i = 0;i<15;i++) {
        for (short m=0;m<15;m++) {
            if (piramide[i][m] == 0)
                break;
            sum = countNums(i,m,piramide,15,true,true);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,true,false);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,false,true);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,false,false);
            if (sum > max)
               max = sum;

        }

    }
    cout << max;
    return 0;
}


long long unsigned countNums(short start_x,short start_y,short array[][15],short size, bool goright,bool goright2) {
    long long unsigned currentSum;

    currentSum = array[start_x][start_y];

    if (goright) { //go right
        if ((start_x + 1) < size)
            start_x++;
        if ((start_y + 1) < size)
            start_y++;
    }
    else //go down
        if ((start_x + 1) < size)
            start_x++;

    if (goright2) { //still going right
        for (short i = start_x, m = start_y;i< size && m < size;i++,m++) {
            currentSum += array[i][m];         
        }
    }
    else { //still going down
        for (short i = start_x;i<size;i++) {
            currentSum += array[i][start_y];            
        }
    }

    return currentSum;
}

La función countNums se usa para bajar o diagonalmente. He probado esta función así:

short a = 0;
short b = 0;
cout << countNums(a,b,piramide,15,true,true) << endl;
cout << countNums(a,b,piramide,15,true,false) << endl;
cout << countNums(a,b,piramide,15,false,true) << endl;
cout << countNums(a,b,piramide,15,false,false) << endl;
return 0;

Y funciona (también cambié un poco la función para que imprima cada número que estaba pasando)

Pero todavía no obtengo el resultado correcto. Esto baja y hacia la derecha y sigue hacia la derecha (números adyacentes a la derecha), baja y sigue bajando (número adyacente a la izquierda). ¿Qué estoy haciendo mal aquí, alguien?

---

Alastair: es simple

long long unsigned countNums (short start_x, short start_y, short array [] [15], short size, bool goright, bool goright2);

start_x y start_y son las coordenadas de la matriz matriz es la referencia a la matriz el tamaño es solo el tamaño de la matriz (siempre es 15) goright es saber si voy a bajar y bajar o simplemente bajar goright2 es saber si voy a seguir bajando o hacia la izquierda

Answer 1

Ok, en primer lugar, no estoy muy claro en cuanto a cuál crees que es el problema. No puedo analizar esa penúltima oración en absoluto ...

En segundo lugar, es posible que desee repensar su diseño aquí. Piense en las funciones que realizan una única tarea discreta y que no están entrelazadas con el resto de la aplicación (es decir, leer en & Quot; estrechamente acoplado y ligado libremente & Quot;). Para mí, una gran advertencia aquí es la presencia de un nombre de función demasiado genérico countNums con una larga lista de argumentos.

Creo que si dividiera el problema en trozos más pequeños y más fáciles de comprender, podría encontrar los problemas mucho más fáciles de encontrar. Sé el enfoque que tomaría aquí, pero supongo que el objetivo del ejercicio es ayudarlo a practicar sus habilidades de programación, así que lo dejaré así ...

Answer 2

He resuelto este problema. Dada la naturaleza del Proyecto Euler, es resolver el problema por su cuenta (& "; Fotocopiar un crucigrama resuelto no significa que lo haya resuelto &";) Y que no quiero arruinar esto para alguien De lo contrario, todo lo que puedo decir es que su solución parece demasiado compleja.

Sin embargo, puede resolver este problema mientras lee el archivo. ¡Resuélvelo de esta manera y el problema # 69 será muy fácil!

¡Buena suerte!

Answer 3

Estoy un poco confundido por el problema ..
Empezaría limpiando tu código.

long long unsigned countNums(short x,
                             short y,
                             short array[][15],
                             short size, 
                             bool goright,
                             bool goright2) 
{
    long long unsigned currentSum;
    currentSum = array[x][y];

    if ((x + 1) < size)    x++; //this happened in both your if cases

    if (goright && ((y + 1) < size)      y++; 

    if (goright2)
    { 
        for (;x< size && y< size;x++,y++)
            currentSum += array[x][y];         

    }
    else 
    {
        for (;x<size;x++) 
            currentSum += array[x][y];            
    }
    return currentSum;
 }

Ahora leo la pregunta y no estoy seguro de que esté haciendo lo que quieres. Dado que esto no es lo que quieres, te sugeriría primero psudocódigo de la respuesta. Olvida el código. ¿Cuál es la respuesta en el código sudo?
Ah, y por amor a todo lo que es santo. No ponga más de un inicializador en el bucle for. Sé que voy a ser criticado por eso, pero es desordenado y realmente no es necesario. Algo que podría considerar es una función recusiva. Parece ideal para este problema.

Answer 4

La función principal verifica que una entrada no sea cero, pero la otra función que llama no verifica eso aunque cambie el índice nuevamente. No sé, realmente no entiendo lo que estás tratando de hacer.

Veo el tamaño de matriz 15 para 15 elementos, ¿el índice para la declaración también comenzaría en 0? Déjame comprobar por un segundo. Solo asegurándome, declarado con tamaño pero accedido en base a 0. Bueno.

¿Por qué usó una declaración anidada para un lugar pero una condición compilada para la declaración más adelante? Mejor verifique que el && no tenga mayor precedencia que el <. El grupo 8 supera al grupo 13 aquí . El operador de incremento no se usa varias veces en una declaración, eso es bueno.

Parece que ya ha solucionado este problema anteriormente en otro idioma, ¿podría hacer un seguimiento de eso también y encontrar el lugar donde su nuevo programa es diferente?

Los otros chicos tienen razón, la pregunta es confusa. Primero trataría de resolver el problema comprando acumulando subpuntos en otra matriz dando el puntaje más alto si la pirámide comenzó en ese punto y construyéndolo desde la fila inferior hasta la parte superior.