1 / 1 / 0
Регистрация: 30.04.2019
Сообщений: 89
1

Рекурсивная функция

09.05.2019, 12:32. Показов 556. Ответов 5
Метки нет (Все метки)

Здравствуйте!

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

Мое решение: рекурсия, однако с технической стороны что-то не так. Прошу посмотреть код функции и дать комментарий:

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
25
26
27
28
29
30
31
32
33
34
35
36
37
bool isLegal(int i, int j)
{
    return (i<n && i>=0 && j<m && j>=0);
}
 
void spread(int i, int j, int table[n][m], int count)
{
 
    if (count == n*m)
    {
        return;
    }
    else
    {
    int move[] = {0, 1, -1}; 
        for (int k=0; k<3; k++)
        {
            int new_j = j + move[k];
            if (isLegal(i, new_j) && table[i][new_j] != 1)
            {
                table[i][new_j] = 1;
                count++;
                spread(i, new_j, table, count);
            }
        }
        for (int k=0; k<3; k++)
        {
            int new_i = i + move[k];
            if (isLegal(new_i, j) && table[new_i][j] != 1)
            {
                table[new_i][j] = 1;
                count++;
                spread(new_i, j, table, count);
            }
        }
    }
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.05.2019, 12:32
Ответы с готовыми решениями:

Рекурсивная функция
Для заданного одномерного массива B из N элементов найти произведение множителей, вычисляемых по...

Рекурсивная функция
...помогите пожалуйста сделать задачки... ...

Рекурсивная функция
Походу что-то с массивами не то, когда ввожу слишком большое число (15+), то выбивает ошибку с...

Рекурсивная функция
Как быть? Мне надо вызывать рекурсивную функцию очень много раз,вплоть до того что вылетает...

5
3653 / 2990 / 828
Регистрация: 25.03.2012
Сообщений: 11,028
Записей в блоге: 1
09.05.2019, 13:07 2
constantin_01, рекурсия это поиск в глубину, т.е. берём шаг вправо и из него рекурсивно тоже шаг вправо и.т.д. в глубину рекурсии вправо по самые помидоры.

тебе больше подходит очередь - поиск в ширину.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
кладём в очередь начальную точку
while(очередь не пуста)
    достаём из начала очереди опорную точку
            for (int k=0; k<4; k++)
        {
            int new_x = x + move_x[k];//+   0, 1, 0, -1
            int new_y = y + move_y[k];//+  1, 0, -1, 0
            if (isLegal(new_x , new_y ) && table[new_x ][new_y ] != 1)
            {
                table[new_x ][new_y ] = 1;
                count++;
                кладём в конец очереди (new_x , new_y )
            }
        }
0
5233 / 2887 / 1208
Регистрация: 07.02.2019
Сообщений: 7,284
09.05.2019, 13:12 3
constantin_01,
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>
 
template<int n, int m>
void spread(int i, int j, int(&table)[n][m], int& count)
{
    if (i < n && j < m && !table[i][j])
    {
        ++table[i][j];
        ++count;
    }
    else return;
    spread(i + 1, j, table, count);
    spread(i - 1, j, table, count);
    spread(i, j + 1, table, count);
    spread(i, j - 1, table, count);
}
 
int main()
{
    int table[5][6]{};
    int cnt{};
    spread(3, 3, table, cnt);
    std::cout << cnt;
}
0
3653 / 2990 / 828
Регистрация: 25.03.2012
Сообщений: 11,028
Записей в блоге: 1
09.05.2019, 13:15 4
zayats80888, и в чём отличие от автора? Всё так же в глубину, а не в ширину, только красивей написано.
1
5233 / 2887 / 1208
Регистрация: 07.02.2019
Сообщений: 7,284
09.05.2019, 13:16 5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
и в чём отличие от автора?
если честно, я его код не смотрел, только сигнатуру функции скопировал
0
3653 / 2990 / 828
Регистрация: 25.03.2012
Сообщений: 11,028
Записей в блоге: 1
09.05.2019, 13:24 6
вот! недавно писал в теме про лабиринт Лабиринт: определить и вывести на экран самое короткое расстояние от входа к выходу
аналог с цифрами на поле.
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <fstream> 
#include <iostream> 
#include <string>
#include <queue>
using namespace std;
int main() {
    vector<string> world;
    struct xy { int x, y; } start;
    {
        ifstream in("input.txt");
        string line;
        while (getline(in, line))
            world.push_back(line);
    }
    for (int y = 0; y < world.size(); ++y)
        for (int x = 0; x < world[y].size(); ++x)
            if (world[y][x] == 'A')
                start = { x, y };
    queue<xy> tasks[2];
    int src = 0, dst = 1, distance = 0;
    tasks[src].push(start);
    const xy dir[] = { {1,0}, {0, -1}, {-1, 0}, {0, 1} };
    while (!tasks[src].empty())
    {
        while (!tasks[src].empty())
        {
            for (int i = 0; i < 4; ++i)
            {
                int x = tasks[src].front().x + dir[i].x;
                int y = tasks[src].front().y + dir[i].y;
                try {
                    if (world.at(y).at(x) == '0') {
                        world[y][x] = '1';
                        tasks[dst].push({ x, y });
                    }
                }
                catch (out_of_range& ex) {}
            }
            tasks[src].pop();
        }
        swap(src, dst);
        ++distance;
    }
    cout << distance << endl;
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.05.2019, 13:24
Помогаю со студенческими работами здесь

Рекурсивная функция
Добрый день. Мне необходимо составить рекурсивную и нерекурсивную функцию для следующей задачи:...

Рекурсивная функция
Расскажите пожалуйста про рекурсивную функцию, как она задаётся и всё что с ней связанно. (можно с...

Рекурсивная функция
Пожалуйста как сделать рекурсию функции my_ln? int main() { setlocale(LC_ALL,...

Рекурсивная функция C++
Сосчитать f(y)=3y+5, yk - входное данное.


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru