Проблема треугольника

Question

Я пытаюсь решить проблему Эйлера 18 -> http://projecteuler.net/index.php?section=problems&id=18

Я пытаюсь сделать это с помощью C ++ (я переучиваю это, и проблемы Эйлера делают для хорошего изучения / поиска материала)

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

Функция countNums используется для перехода вниз или по диагонали. Я проверил эту функцию так:

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;

И это работает (я также немного изменил функцию, чтобы она печатала все числа, через которые проходил)

Но я все еще не могу получить правильный результат. Это понижается и направо и все еще идет направо (соседние числа направо), понижается и продолжает понижаться (смежное число налево). Что я здесь делаю не так?

---

Аластер: это просто

long long unsigned countNums (короткий start_x, короткий start_y, короткий массив [] [15], короткий размер, bool goright, bool goright2);

start_x и start_y являются координатами массива массив является ссылкой на массив размер - это просто размер массива (это всегда 15) Goright должен знать, собираюсь ли я идти вниз и вправо или просто вниз goright2 должен знать, собираюсь ли я продолжать идти вниз или идти налево

Answer 1

Хорошо, так, во-первых, мне немного непонятно, как вы думаете, в чем проблема. Я не могу разобрать это второе последнее предложение ...

Во-вторых, вы можете переосмыслить свой дизайн здесь. Подумайте о функциях, которые выполняют одну отдельную задачу и не переплетаются с остальной частью приложения (т. Е. Читайте о «тесно связанных и слабо связанных»). Для меня большим предупреждением здесь является наличие чрезмерно общего имени функции countNums с длинным списком аргументов.

Я думаю, что если бы вы поделили проблему на более мелкие, более понятные куски, вы могли бы найти проблемы намного легче найти. Я знаю подход, который я выбрал бы здесь, но я предполагаю, что весь смысл упражнения заключается в том, чтобы помочь вам практиковать свои навыки программирования, поэтому я просто оставлю это на этом ...

Answer 2

Я решил эту проблему. Учитывая природу Project Euler, состоит в том, чтобы решить проблему самостоятельно («фотокопирование решенной кроссворда не означает, что вы решили ее») и что я не хочу испортить это для кого-то другого, все, что я могу сказать, что ваше решение выглядит слишком сложным.

Однако вы можете решить эту проблему, читая файл. Решите это таким образом, и задача № 69 будет легче!

Удачи!

Answer 3

Основная функция проверяет, что запись не равна нулю, но другая функция, которую она вызывает, не проверяет это, даже если она снова изменяет индекс. Я не знаю, я действительно не понимаю, что вы пытаетесь сделать.

Я вижу размер массива 15 для 15 элементов, будет ли индекс для объявления также начинаться с 0? Позвольте мне проверить на секунду. Просто убедитесь, что заявлено с размером, но доступ основан на 0. Хорошо.

Почему вы использовали вложенное для операторов одно место, а условие компоновки для оператора позже? Лучше проверить, что && не имеет более высокого приоритета, чем <. Группа 8 превосходит группу 13 здесь . Оператор инкремента не используется несколько раз в выражении, это хорошо.

Похоже, вы уже делали эту проблему раньше на другом языке, не могли бы вы также проследить это и найти место, в котором ваша новая программа впервые отличается?

Другие парни правы, вопрос сбивает с толку. Сначала я попытался бы решить эту проблему, купив построение подсекций в другой матрице, дающей наивысший балл, если пирамида начиналась в этой точке, и наращивал ее от нижнего ряда к верхнему.

Answer 4

Я немного смущен этой проблемой ..
Я бы начал с очистки вашего кода.

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

Теперь я читаю вопрос, и я не уверен, что он делает то, что вы хотите. Поскольку это не то, что вы хотите, я бы сначала предложил псевдокод ответ. Забудьте код .. Каков ответ в коде sudo.
Ох и ради любви всего святого. Не помещайте более одного инициализатора в цикл for. Я знаю, что меня это задело, но это грязно и действительно не нужно. Что-то, что вы могли бы рассмотреть, - это рекурсивная функция. Кажется, идеально подходит для этой проблемы.