Тема: Рекурсія
Дана карта місцевості, розміром 10 на 10. Нулем визначені озера,
одиницею суша. Якщо клітинки, які заповнені нулями мають спільну сторони,
то це те саме озеро. Скільки озер на карті?
Допоможіть, будь ласка... Наперед дякую)
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Дана карта місцевості, розміром 10 на 10. Нулем визначені озера,
одиницею суша. Якщо клітинки, які заповнені нулями мають спільну сторони,
то це те саме озеро. Скільки озер на карті?
Допоможіть, будь ласка... Наперед дякую)
Не знаю до чого там рекурсія, але воно вирішується отак
Ну, якщо рекурсією - то шукайте всі нулі і заливайте двійками, трійками і т.д. Скільки чисел знадобиться - така відповідь.
мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."
мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."
Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.
FakiNyan написав:мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."
Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.
викладач, чому ви викрали акаунт пана koala???
Робочий код :
#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++).
FakiNyan написав:мабуть, викладач думає так - "ок, мені треба перевірити, чи учні знають, що таке рекурсія, і можуть це використати в своєму коді". А потім бере будь-яке завдання і перед ним пише "Рекурсія."
Ризикну припустити, що викладач якраз все сказав і написав. Але студенту було ліньки записувати - ну не самому ж потім робити, хай хтось на форумі зробить.
Так і роблю зазвичай
тра ля ля... тра ля ля. проходимся циклом по масиву. коли ноль запускаєм рекурсивну функцію затерання озера. плюс 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);
}
Зразу кажу код на око... непротестований.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися