Рейтинг:
2
Patrice T
Цитата:
Как найти число путей от источника до пункта назначения, которое складывается до заданной суммы k в 2d-матрице?
Это похоже на какую-то домашнюю работу, но ваше главное усилие-это вставить требование.
В чем же вопрос?
Цитата:
Используйте динамическое программирование, чтобы решить эту проблему.
Вам дается подсказка о том, как это сделать.
Мы не делаем вашу домашнюю работу, если вы хотите помочь, вам нужно показать свою работу и объяснить проблему.
Чтобы начать, вы можете начать с подхода грубой силы (пробуя каждый путь 1 на 1), а затем уточнить.
[Обновление]
Цитата:
В приведенном выше фрагменте кода он был успешно скомпилирован ,и выводимый вывод имеет более высокое значение, чем ожидалось
Как ваш код обрабатывает буквы, которые не являются "x" ?
[Обновление]
Похоже, ваш код никогда не выходит за пределы этой точки
int countpath(char a[][100], int i,int j,int val)
{
if (
(
(i == n-1) &&
j == (n-1)
)
&&
(
(a[n-1][n-1] == k) ||
(a[n-2][n-2] == k) ||
(a[n-1][n-2] == k) ||
(a[n-2][n-1] == k)
)
)
{
return 1;
}
else
return 0;
// code beyond this point is never executed
a[0][0] = 0;
if (
i = 0 &&
j < n-1 &&
a[i][j+1] != 'x'
)
return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');
if (
j = 0 &&
i < n-1 &&
a[i+1][j] != 'x'
)
return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');
if ( a[i][j] != 'x' )
return countpath(a, i+1,j+1, (a[i+1][j+1]+a[i+1][j]+a[i][j+1])-'0');
}
Похоже, вам стоит изучить отладчик.
Рейтинг:
1
Stefan_Lang
Ваша функция countpath показывает ряд проблем. Я укажу на пару очевидных для меня вещей и предложу вам исправить их, прежде чем продолжить - может быть, после этого вы сможете продолжить самостоятельно, иначе вы всегда можете вернуться сюда и спросить:
1. Ваш первый if заявление будет return значение (1 или 0) на обеих ветвях. Поэтому код после этого if-else блок никогда не будет выполнен. Я подозреваю, что случай else не всегда должен возвращать 0: вы, вероятно, упускаете еще один if?
2. Второй и третий if заявление содержит задания (i = 0 и j = 0 соответственно) . Вы хотели провести здесь сравнение?
3. это очень сложно: вы передаете матрицу a в функцию, определяя ее как имеющую 100 столбцов, хотя истинный размер (NxN), вероятно, намного меньше. С этим определением a[1][0] будет обращаться к адресу [a+100], который может находиться вне выделенного пространства памяти для матрицы a, если бы он был определен как 10x10 или меньше! Вы не ахоу свою вызывающую функцию, которая должна объявлять и выделять a. Если вы определили его как 100x100, независимо от N, это, вероятно, нормально. В противном случае вам потребуется, чтобы это исправить.
4. и менее очевидный: ваш код, по-видимому, проверяет, можете ли вы продолжить движение в определенном направлении, и если да, то вычислите количество путей для этого направления рекурсивно. Однако вы забываете, что после этой рекурсии вы также должны проверить и другие направления и добавить эти числа к общей сумме. Вместо этого вы немедленно возвращаетесь с номером, который вы получили, идя в этом направлении, игнорируя другие варианты. А это значит, что вы никогда не сможете найти больше одного пути...
Рейтинг:
1
OriginalGriff
Мы более чем готовы помочь тем, кто застрял, но это не значит, что мы здесь, чтобы сделать все это для вас! Мы не можем сделать всю работу, вам либо платят за это, либо это часть ваших оценок, и было бы совсем несправедливо, если бы мы сделали все это за вас.
Поэтому нам нужно, чтобы вы сделали работу, и мы поможем вам, когда вы застряли. Это не значит, что мы дадим вам пошаговое решение, которое вы можете сдать!
Начните с объяснения, где вы находитесь в данный момент и каков следующий шаг в этом процессе. Затем расскажите нам, что вы пытались сделать, чтобы этот следующий шаг сработал, и что произошло, когда вы это сделали.
Diaesh Antony
Я написал нижеприведенную часть функции ,но она не работает
инт countpath(символ[][100], int я,инт Дж,внутр вал)
{
если бы(((я == н-1) и усилитель; & J В == (Н-1) ) &&усилителя; ((а[п-1][Н-1] == К) || (а[п-2][п-2] == К) || (а[п-1][п-2] == К) || (а[п-2][Н-1] == к)))
{
возврат 1;
}
еще
возвращает 0;
a[0][0] = 0;
если(i = 0 & & amp; j < n-1 && a[i][j+1] != 'x')
return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');
если(j = 0 & & amp; i < n-1 && a[i+1][j] != 'x')
return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');
если(a[i][j] != 'x')
вернуться countpath(а, я+1,ю+1, (а[я+1][Дж+1]+а[я+1][Дж]+а[я][Дж+1])-'0');
}
Patrice T
Воспользуйся Улучшить вопрос чтобы обновить ваш вопрос.
Чтобы каждый мог обратить внимание на эту информацию.
OriginalGriff
"Это не работает" - одно из самых бесполезных описаний проблемы, которое мы получаем: оно абсолютно ничего не говорит нам о проблеме. Мы не знаем, получаете ли вы сообщение об ошибке, или неправильные данные, или даже что этот код успешно компилируется!
Помните, что мы не можем видеть ваш экран, получить доступ к вашему жесткому диску или прочитать ваши мысли - мы получаем только то, что вы печатаете для работы.
Итак, расскажите нам, что происходит, когда вы запускаете этот код, что вы ожидали, как вы проверили, что произошло. Помогите нам помочь вам!
Используйте виджет "улучшить вопрос", чтобы отредактировать свой вопрос и предоставить более подробную информацию.
Stefan_Lang
Эта функция всегда будет возвращать 1 или 0 и никогда не достигнет кода после вашего первого if ... еще...
Этот код явно не будет возвращать слишком высокое значение, поэтому это не тот код, о котором вы говорили изначально.
Кроме того, вы должны добавить пояснения по параметрам функций, особенно по назначению i и j. мы можем догадаться об этом по их использованию в вашем коде, но если они являются частью проблемы, мы можем ошибиться.
Пожалуйста, используйте кнопку [улучшить вопрос] под вашим вопросом, чтобы добавить реальный, полный код к вашему вопросу и объяснениям, чтобы все могли видеть, над чем вы работаете.
Diaesh Antony
В приведенном выше фрагменте кода он был успешно скомпилирован ,и выводимый вывод имеет более высокое значение, чем ожидалось
OriginalGriff
На нем написано "долгий день"...
Так... вы написали некоторый код, поместили некоторые данные, которые мы не получили в него, и если дали вам "более высокую ценность".
Это очень полезно. Немного, но это только начало.
Сначала вы отправились на прогулку и сломались в середине нигде. Вы позвонили в гараж, сказали, что он сломался, и положили трубку. Теперь вы ждете, когда гараж появится с нужными частями для вашего автомобиля, не зная, какая это машина, что с ней случилось, кто вы, или какое-либо представление о том, где она может быть.
Теперь вы пересмотрели его, и звонок пошел: "Гараж Джо, чем мы можем помочь?" - Он сломался. Это же "Фиат"."
Я подозреваю, что вы будете сидеть у дороги очень долго, прежде чем гараж прибудет с новым радиатором или шиной: они должны обыскать всю страну для вас, и угадайте, какая часть сломалась еще.
Мы такие же: корми нас дрянью, мы можем делать дрянью все.
Итак, расскажите нам, что вы сделали, чтобы получить результаты, что произошло, что вы сделали, чтобы выяснить, почему. Какие данные вы ему скормили? Как вы проверили правильность данных? Что показал вам отладчик, когда вы использовали его, чтобы посмотреть, что происходит? Какой путь через код и данные он прошел, когда вы его запустили?
Stefan_Lang
Я добавил этот блок кода к вашему вопросу и переформатировал его для удобства чтения. Я не добавлял и не удалял ничего, кроме пробелов.