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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
#1

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

13.10.2011, 14:37. Просмотров 670. Ответов 14
Метки нет (Все метки)

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

Вроде переполнение, а вроде бы и нет - C++
День добрый! Интересует, почему си не дает мне сделать следующую штуку. int a = 4999998848; cout << a*2 << endl; По...

Вроде простенькая - C++
Задача Данно 3 массива.Найти элементы которые есть в 1 массиве и нет в 2 и 3. мой код int mas1={1,3,6,5,7,2}; int...

Вроде массивы - C++
Написать программу, использующую функцию. Для каждого из заданных целочисленных массивов X, Y, Z вычислить произведение элементов кратных...

вроде все просто - C++
#include "stdafx.h" #include <iostream> #include <ctime> using namespace std; int main() { int mas, a; srand...

работа со строками (вроде) - C++
ребята, не для себя прошу, правда. помочь надо девушке а я бессилен в данном случае надо программу написать вот задание: выяснить,...

С++ вроде простые проги - C++
Привет Всем народ очень нужна помощь до четверга написать вот такие программы могу только на паскале а вот на С++ не могу( 3 проги ...

Проблемы с конструктором (вроде) - C++
Недавно перешёл с С на С++. Есть класс Notebook который использует определённый мной список имён. list.h: //List.h template...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1927 / 1193 / 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++
1286 / 1220 / 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
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 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++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.10.2011, 15:16     Вроде бы граф #7
Цитата Сообщение от Dani Посмотреть сообщение
2 фора и сложение
Какое сложение? Зачем? Нужно найти все пути, а не просто их количество.
diagon
Higher
1927 / 1193 / 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++
1286 / 1220 / 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++
1286 / 1220 / 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++
Добрый день. Как и говорилось в заголовке, почему то, не работает банальный поиск в бинарном файле: void search (FILE *f,char* k) { ...

Задача вроде как на мощность... - C++
Задача Дед в К1 разов сильнее бабки,бабка в К2 разов сильнее внучки,внучка в К3 разов сильнее Жучки,Жучка в К4 разов сильнее кошки,кошка...

вроде метод монте карло - C++
распишите пожалуйста что делает это программа?? int i,a,b,n,k,c,d,e,f; double s1,s,x,y,z; int _tmain(int argc, _TCHAR* argv) { ...


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1927 / 1193 / 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     Вроде бы граф
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru