1

Тема: Рекурсія

Дана карта місцевості, розміром 10 на 10. Нулем визначені озера,
одиницею суша. Якщо клітинки, які заповнені нулями мають спільну сторони,
то це те саме озеро. Скільки озер на карті?
Допоможіть, будь ласка... Наперед дякую)

2

Re: Рекурсія

Які у вас ідеї? Чому в назві теми "рекурсія"?

Подякували: koala, FakiNyan2

3

Re: Рекурсія

Потрібно розв'язати цю задачу за допомогою рекурсії

4

Re: Рекурсія

Не знаю до чого там рекурсія, але воно вирішується отак

https://algs4.cs.princeton.edu/15uf/

5

Re: Рекурсія

Ну, якщо рекурсією - то шукайте всі нулі і заливайте двійками, трійками і т.д. Скільки чисел знадобиться - така відповідь.

6

Re: Рекурсія

0x9111A написав:

Які у вас ідеї? Чому в назві теми "рекурсія"?

Бо викладач так сказав

Подякували: FakiNyan, 0x9111A2

7

Re: Рекурсія

У гілці нічого про C/C++ немає, переношу в Алгоритми.

8

Re: Рекурсія

мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."

9

Re: Рекурсія

FakiNyan написав:

мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."

Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.

Подякували: Q-bart1

10

Re: Рекурсія

koala написав:
FakiNyan написав:

мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."

Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.

викладач, чому ви викрали акаунт пана koala???

Подякували: sensei1

11

Re: Рекурсія

Робочий код :

#include <stdio.h>
#include <stdlib.h>

struct Field {
    int Width;
    int Height;
    char **Array;
};

void freeField(Field *const);
Field *getCopy(Field const *const);
int getAreasCount(Field const *const, char const);
void recursiveFunction(Field const *const, int const, int const);

int main(int argc, char *const *const argv) {

    // Check arguments
    if(argc < 2) {
        char const *const program_name = argc > 0 ? argv[0] : "program.exe";
        printf(" Start program with file_name parameter.");
        printf(" For example :\r\n  %s \"%s\"", program_name, "file.txt");
        return 0x0;
    }

    // Open file
    FILE *file_ptr(nullptr);
    file_ptr = fopen(argv[1], "r");
    if(!file_ptr) {
        printf(" Cannot open file \"%s\".", argv[1]);
        return 0x1;
    }

    // Read file
    Field *field = (Field *)malloc(sizeof(Field));  // C style
    // Field *field(new Field());                   // C++ style
    if(!field) {
        printf(" Memory allocation failed.");
        return 0x2;
    }
    field->Width = 0;
    field->Height = 0;
    fscanf(file_ptr, "%i %i", &field->Width, &field->Height);
    if(field->Width < 1 || field->Height < 1) {
        printf(" Invalid field size ( %i x %i ).", field->Width, field->Height);
        return 0x3;
    }
    field->Array = (char **)malloc(field->Height * sizeof(char *));  // C style
    // field->Array = new char *[field->Height];                     // C++ style
    if(!field->Array) {
        printf(" Memory allocation failed.");
        return 0x4;
    }
    for(int row_i(0); row_i < field->Height; ++row_i) {
        char *field_row(field->Array[row_i] = (char *)malloc(field->Width * sizeof(char)));  // C style
        // char *field_row(field->Array[row_i] = new char[field->Width]);                    // C++ style
        if(!field_row) {
            printf(" Memory allocation failed.");
            return 0x5;
        }
        for(int col_i(0); col_i < field->Width; ++col_i) {
            int temp(0);
            fscanf(file_ptr, "%i,", &temp);
            field_row[col_i] = temp;
        }
    }

    // Close file
    fclose(file_ptr);

    // Print field
    printf("\r\n Size ( W x H ) : ( %i x %i )\r\n\n Field :\r\n", field->Width, field->Height);
    for(int row_i(0); row_i < field->Height; ++row_i) {
        char *field_row(field->Array[row_i]);
        for(int col_i(0); col_i < field->Width; ++col_i) {
            printf(" %i", field_row[col_i]);
        }
        printf("\r\n");
    }

    // Print result
    printf("\r\n Count of areas : %i\r\n ", getAreasCount(field, 0));

    freeField(field);
    return 0x0;
}

void freeField(Field *const field) {
    if(!field) return;
    if(field->Array) {
        for(int row_i(0); row_i < field->Height; ++row_i) {
            if(field->Array[row_i]) {
                free(field->Array[row_i]);        // C style
                // delete[] field->Array[row_i];  // C++ style
            }
        }
        free(field->Array);        // C style
        // delete[] field->Array;  // C++ style
    }
    field->Width = 0;
    field->Height = 0;
    free(field);      // C style
    // delete field;  // C++ style
}

Field *getCopy(Field const *const field) {
    if(!field) return (Field *)0;
    Field *copy((Field *)malloc(sizeof(Field)));  // C style
    // Field *copy(new Field());                  // C++ style
    if(!copy) return copy;
    copy->Width = field->Width;
    copy->Height = field->Height;
    copy->Array = (char **)malloc(copy->Height * sizeof(char *));  // C style
    // copy->Array = new char *[copy->Height];                     // C++ style
    if(!copy->Array) return copy;
    for(int row_i(0); row_i < field->Height; ++row_i) {
        char *field_row(field->Array[row_i]);
        char *copy_row(copy->Array[row_i] = (char *)malloc(copy->Width * sizeof(char)));  // C style
        // char *copy_row(copy->Array[row_i] = new char[copy->Width]);                    // C++ style
        if(!copy_row) continue;
        for(int col_i(0); col_i < field->Width; ++col_i) {
            copy_row[col_i] = field_row[col_i];
        }
    }
    return copy;
}

int getAreasCount(Field const *const field, char const searchValue) {
    int count(0);
    Field *copy(getCopy(field));
    for(int row_i(0); row_i < copy->Height; ++row_i) {
        char *copy_row(copy->Array[row_i]);
        if(!copy_row) continue;
        for(int col_i(0); col_i < copy->Width; ++col_i) {
            copy_row[col_i] = copy_row[col_i] == searchValue;
        }
    }
    for(int row_i(0); row_i < copy->Height; ++row_i) {
        char *copy_row(copy->Array[row_i]);
        if(!copy_row) continue;
        for(int col_i(0); col_i < copy->Width; ++col_i) {
            if(copy_row[col_i]) {
                recursiveFunction(copy, col_i, row_i);
                ++count;
            }
        }
    }
    freeField(copy);
    return count;
}

void recursiveFunction(Field const *const field, int const x, int const y) {
    if(x < 0 || x >= field->Width) return;
    if(y < 0 || y >= field->Height) return;
    if(!field->Array[y][x]) return;
    field->Array[y][x] = 0;
    recursiveFunction(field, x + 1, y);
    recursiveFunction(field, x, y - 1);
    recursiveFunction(field, x - 1, y);
    recursiveFunction(field, x, y + 1);
}

Приклад даних у файлі :

10 10

1,0,0,0,1,1,0,0,0,1,
0,1,0,1,0,0,1,0,1,0,
0,0,1,0,0,0,0,1,0,0,
0,1,0,1,0,0,1,0,1,0,
1,0,0,0,1,1,0,0,0,1,
1,0,0,0,1,1,0,0,0,1,
0,1,0,1,0,0,1,0,1,0,
0,0,1,0,0,0,0,1,0,0,
0,1,0,1,0,0,1,0,1,0,
1,0,0,0,1,1,0,0,0,1,

Приклад виклику програми в терміналі / в командному радку :

Program.exe "InputFile.txt"

Замість "Program" має бути ім'я скомпільованого exe файлу. "InputFile.txt" - ім'я файлу, який містить вхідні дані.

Тепер є сенс перенести тему назад (в C/C++).

Post's attachments

Recursive_MSVC_Solution.7z 11.74 kb, 371 downloads since 2018-04-12 

12

Re: Рекурсія

koala написав:
FakiNyan написав:

мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."

Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.

Так і роблю зазвичай

13 Востаннє редагувалося Alchimic (16.04.2018 18:19:06)

Re: Рекурсія

тра ля ля... тра ля ля. проходимся циклом по масиву. коли ноль запускаєм рекурсивну функцію затерання озера. плюс 1. і все поїхали дальше.

int a[10][10]={...};
int count=0;
del(int i,int j)
{
a[i][j]=1;
if(i>0) {if (a[i-1,j]==0) del(i-1,j);};
if(j>0) {if (a[i,j-1]==0) del(i,j-1);};
if(i<9) {if (a[i+1,j]==0) del(i+1,j);};
if(j<9) {if (a[i,j+1]==0) del(i,j+1);};
}

go(int i, int j)
{
if(a[i][j]==0)
{
count++;
del(i,j);
}
i++;
if (i>9)
{
i=0;
j++;
}
if(j<9)
go(i,j);
}
main(){
go(0,0);
}

Зразу кажу код на око... непротестований.