Форум программистов, компьютерный форум CyberForum.ru

Вроде бы граф - C++

Восстановить пароль Регистрация
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.10.2011, 14:37     Вроде бы граф #1
Как делается эта задачка? Сделайте пожалуйста, кто может.. Спасибо !
Дан прямоугольник MxN. Найти все варианты как можно добраться из левого верхнего угла в правый нижний, если передвигаться можно только вниз и вправо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2011, 14:37     Вроде бы граф
Посмотрите здесь:

С++ вроде простые проги C++
C++ функции .. вроде как то коряво
C++ вроде все просто
C++ Вроде массивы
работа со строками (вроде) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.10.2011, 14:50     Вроде бы граф #2
На динамику задача.
Просто заполняете матрицу по следующему принципу:
В текущую клетку можно попасть сверху и слева, поэтому количество способов попасть в нее = matrix[i-1][j] + matrix[i][j -1](комбинаторное правило сложения). При этом нужно учесть выход за пределы матрицы + начальные значения. Ответом будет matrix[n-1][m-1], если нумерация с нуля.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.10.2011, 15:03     Вроде бы граф #3
Цитата Сообщение от diagon Посмотреть сообщение
На динамику задача.
Динамического программирования не вижу. Перебор поиском в глубину - вижу.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.10.2011, 15:05  [ТС]     Вроде бы граф #4
Цитата Сообщение от diagon Посмотреть сообщение
На динамику задача.
Просто заполняете матрицу по следующему принципу:
В текущую клетку можно попасть сверху и слева, поэтому количество способов попасть в нее = matrix[i-1][j] + matrix[i][j -1](комбинаторное правило сложения). При этом нужно учесть выход за пределы матрицы + начальные значения. Ответом будет matrix[n-1][m-1], если нумерация с нуля.
Можно поподробнее пожалуйста
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
13.10.2011, 15:06     Вроде бы граф #5
Цитата Сообщение от Deviaphan Посмотреть сообщение
Динамического программирования не вижу. Перебор поиском в глубину - вижу.
Да нет, это динамика и поиск писать не надо - 2 фора и сложение.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.10.2011, 15:09  [ТС]     Вроде бы граф #6
Объяснииитеее ) или приведите пример, пожалуйста )
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.10.2011, 15:16     Вроде бы граф #7
Цитата Сообщение от Dani Посмотреть сообщение
2 фора и сложение
Какое сложение? Зачем? Нужно найти все пути, а не просто их количество.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.10.2011, 15:18     Вроде бы граф #8
Цитата Сообщение от Montanaa Посмотреть сообщение
Объяснииитеее ) или приведите пример, пожалуйста )
Примерно так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    
    int ** matrix = new int * [n];
    for (int i = 0 ; i < n; ++i)
        matrix[i] = new int [m];
    
    matrix[0][0] = 1; // в первую клетку можно попасть одним способом - остаться в ней
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m ; ++j)
            if ( i != 0 || j != 0 )
                matrix[i][j] = ( i > 0 ? matrix[i - 1][j] : 0 ) + ( j > 0 ? matrix[i][j - 1] : 0 );
            
    std::cout << matrix[n - 1][m - 1] << std::endl;
        
    for (int i = 0; i < n; ++i)
        delete[] matrix[i];
    delete[] matrix;
}
Цитата Сообщение от Deviaphan Посмотреть сообщение
Нужно найти все пути, а не просто их количество.
Цитата Сообщение от Montanaa Посмотреть сообщение
Найти все варианты как можно добраться из левого верхнего угла в правый нижний, если передвигаться можно только вниз и вправо.
Как-то этого не ясно из формулировки задачи...
P.S. код выше считает количество
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.10.2011, 15:27  [ТС]     Вроде бы граф #9
Я думаю, чтобы найти все ПУТИ, т.е. координаты, нужен граф так и так.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.10.2011, 15:33     Вроде бы граф #10
Цитата Сообщение от diagon Посмотреть сообщение
Как-то этого не ясно из формулировки задачи...
Цитата Сообщение от Montanaa Посмотреть сообщение
Найти все варианты как можно добраться...
Уверен, что не понятно?
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.10.2011, 15:35  [ТС]     Вроде бы граф #11
Количество я и сам могу найти, а с графами работать не умею (
diagon
13.10.2011, 15:37
  #12

Не по теме:

Цитата Сообщение от Deviaphan Посмотреть сообщение
Уверен, что не понятно?
Уверен...
Вывести можно в виде матрицы, где путь закрашен (например), в виде последовательности координат, еще как-нибудь можно извратиться. Но в условии задачи этого не уточняется, следовательно вполне логичен вывод, что нужно просто вывести количество.

Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.10.2011, 15:44     Вроде бы граф #13
Цитата Сообщение от diagon Посмотреть сообщение
Вывести можно в виде матрицы
Вывести можно как угодно, но требуются ВСЕ пути. Как выводить не важно, важно, что ВСе и СКОЛЬНО это разные слова.)
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
18.10.2011, 16:06  [ТС]     Вроде бы граф #14
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    
    int ** matrix = new int * [n];
    for (int i = 0 ; i < n; ++i)
        matrix[i] = new int [m];
    
    matrix[0][0] = 1; // в первую клетку можно попасть одним способом - остаться в ней
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m ; ++j)
            if ( i != 0 || j != 0 )
                matrix[i][j] = ( i > 0 ? matrix[i - 1][j] : 0 ) + ( j > 0 ? matrix[i][j - 1] : 0 );
            
    std::cout << matrix[n - 1][m - 1] << std::endl;
        
    for (int i = 0; i < n; ++i)
        delete[] matrix[i];
    delete[] matrix;
}

Ребят, не могли бы вы изменить вот этот код, учитывая то, что можно ходить еще и по диагонали? Я не догоняю ( Спасибо огромное, заранее!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2011, 16:11     Вроде бы граф
Еще ссылки по теме:

Вроде простенькая C++
Проблемы с конструктором (вроде) C++
C++ Вроде переполнение, а вроде бы и нет

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.10.2011, 16:11     Вроде бы граф #15
Цитата Сообщение от Montanaa Посмотреть сообщение
Ребят, не могли бы вы изменить вот этот код, учитывая то, что можно ходить еще и по диагонали? Я не догоняю ( Спасибо огромное, заранее!
Здесь только количество находиться, но изменяется несложно =)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
int main()
{
        int n, m;
        std::cin >> n >> m;
        
        int ** matrix = new int * [n];
        for (int i = 0 ; i < n; ++i)
                matrix[i] = new int [m];
        
        matrix[0][0] = 1; // в первую клетку можно попасть одним способом - остаться в ней
        
        for (int i = 0; i < n; ++i)
                for (int j = 0; j < m ; ++j)
                        if ( i != 0 || j != 0 )
                                matrix[i][j] = ( i > 0 ? matrix[i - 1][j] : 0 ) + ( j > 0 ? matrix[i][j - 1] : 0 ) + ( i > 0 && j > 0 ? matrix[i - 1][j - 1] : 0 );
                        
        std::cout << matrix[n - 1][m - 1] << std::endl;
                
        for (int i = 0; i < n; ++i)
                delete[] matrix[i];
        delete[] matrix;
}
Yandex
Объявления
18.10.2011, 16:11     Вроде бы граф
Ответ Создать тему
Опции темы

Текущее время: 17:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru