Консультация онлайн # 202976

Раздел: Информатика
Автор вопроса: Мария (Посетитель)
Дата: 08.06.2022, 17:12 Консультация неактивна
Поступило ответов: 0
Здравствуйте! Прошу помощи в следующем вопросе: как правильно установить счетчик внутри рекурсивной функции? Вот, например, код сортировки Хоара с рекурсивной функцией, в котором мне нужно посчитать количество сравнений и количество пересылок.Для этого я добавила переменные w и w1 в качестве счетчиков. Но так как функция в итоге вызывает сама себя несколько раз, вместо суммы выводятся промежуточные значения переменных. Как это можно обойти? Спасибо!

Ответов еще не поступило.

Мини-форум консультации # 202976

CradleA

Мастер-Эксперт

ID: 325460

326463

= общий =    08.06.2022, 18:08
К примеру добавить к счетчику модификатор Static. Но не забыть счетчики обнулить когда выходите из рекурсии.
=====
to live is to die
Мария

Посетитель

ID: 405671

326464

= общий =    08.06.2022, 19:17

К примеру добавить к счетчику модификатор Static


Т.е. достаточно будет обозначить w и w1 как static int?

Но не забыть счетчики обнулить когда выходите из рекурсии.


С этим моментом у меня проблема. Как можно определить этот момент выхода из рекурсии, чтобы можно было их обнулить?
Алексеев Владимир Николаевич

Мастер-Эксперт

ID: 259041

326465

= общий =    09.06.2022, 04:11
Я больше люблю простенький прог-язык VBScript Ссылка (его код после написания / правки сразу готов к работе, ПрогСреда и компиляторы не нужны…). Но принцип подсчёта кол-ва итераций или времени выполнения прог-блока - одинаков во всех языках.
Примеры: Чтоб подсчитать кол-во вызовов какой-то рекурсивной функции (например функци Сравнений funCompare ), я перед первым вызовом создаю и обнуляю счётчик вызовов:
nCompar := 0

В блоке функции funCompare оператор nCompar ++ инкрементирует счётчик. По окончании всех вызовов остаётся лишь зачитать nCompar-значение, выведенное на экран пользователя. Никаких заморочек типа "определить этот момент выхода из рекурсии" не требуется.

Иногда бывает нужно подсчитать кол-во циклов вызова рекурсивной функции, когда эта функция вызывает сама себя заранее-непредсказуемое число раз. Живой пример из практи: Мне надо составить файлы-списки моих 12 корне-папок с их под-папками для Бэкапа (резервное копирование важных файлов на случай их ошибочного удаления или смерти ГлавЖёстДиска). Понятно, что каждая подпапка содержит вложенные подпапки, и будут вложенные рекурси-вызовы. Для попутного подсчёта файлов в корнепапках я в начале скрипта создаю и обнуляю 2 счётчика: nRoot и nAll .

В процессе работы рекурси-функции оба счётчика инкрементируются. Но по окончании обработки каждой из 12 корне-папки на экран выводится и сразу обнуляется переменная nRoot (кол-во файлов в отдельной корне-папке), а по окончании работы скрипта я читаю nAll-значение - итоговое кол-во файлов.
Обратите внимание: имена моих переменных состоят не из одной буквы, а уникальны для всего скрипт-кода и ещё имеют смысл (Root - корень, All - все, n - числовое кол-во). Это позволяет мигом находить ПрогПоиском все вхождения имени переменной в очень большой код и легко понимать свой забытый код спустя много лет, если потребуется правка.
CradleA

Мастер-Эксперт

ID: 325460

326466

= общий =    09.06.2022, 10:20
static int w = 0;
static int w1 = 0;
это сделает переменную одну и туже во всех рекурсивных функциях

в самом конце функции перед } сделать w = 0; w1 = 0;

И должно отработать все.
=====
to live is to die
Мария

Посетитель

ID: 405671

326467

= общий =    09.06.2022, 10:51
Благодарю за ответ и пояснения! Пока работаю над внедрением
Мария

Посетитель

ID: 405671

326468

= общий =    09.06.2022, 10:52
В таком случае static int w = 0; и static int w1 = 0; объявляются как глобальные переменные или внутри функции?
CradleA

Мастер-Эксперт

ID: 325460

326469

= общий =    09.06.2022, 11:29
объявляются внутри функции и они становятся для данной функции статичными, т.е. помещаются в отдельную область памяти и для всех вызовов этой функции становятся видимыми из этой области памяти, а не выделяются при вызове функции.
=====
to live is to die
Мария

Посетитель

ID: 405671

326470

= общий =    09.06.2022, 13:04
Исправила, и кажется,стало лучше, чем было, но выдает в итоге все те же промежуточные результаты


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

void qsort(int *mas, int size) {
//Указатели в начало и в конец массива
static int w;
static int w1;
int i = 0;
int j = size - 1;
//Центральный элемент массива
int mid = mas[size / 2];
//Делим массив
do {
//Пробегаем элементы, ищем те, которые нужно перекинуть в другую часть
//В левой части массива пропускаем(оставляем на месте) элементы, которые меньше центрального
while(mas[i] < mid) {
i++; w++;
}
//В правой части пропускаем элементы, которые больше центрального
while(mas[j] > mid) {
j--; w++;
}
//Меняем элементы местами
if (i <= j) {
int tmp = mas[i];
mas[i] = mas[j];
mas[j] = tmp;
i++;
j--;
w++;
w1 += 3;
}
} while (i <= j);
//Рекурсивные вызовы
if(j > 0) {
//"Левый кусок"
qsort(mas, j + 1);
w++;
}
if (i < size) {
//"Правый кусок"
qsort(&mas[i], size - i);
w++;
}
printf("C = %d , M = %d \n", w, w1);
w = 0;
w1 = 0;
}
int main ()
{ printf("Quick Sorting:\n");
int cp3[8] = {2,45,7869,34,564,2,1};
qsort(cp3, 8); // вызов функции сортировки
for (int i = 0; i<8; i++)
printf("%d ", cp3[i]);
printf("\n");
}

-----
Прикрепленные файлы:

CradleA

Мастер-Эксперт

ID: 325460

326471

= общий =    09.06.2022, 14:30
https://prog-cpp.ru/sort-fast/ - может это поможет? похоже надо передавать границы сортировки в рекурсивную функцию.
https://forkettle.ru/vidioteka/programmirovanie-i-set/algoritmy-i-struktury-dannykh/108-sortirovka-i-poisk-dlya-chajnikov/1010-metod-khoara-bystraya-sortirovka-quick-sort
https://ru.stackoverflow.com/questions/812048/%D0%9F%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F-%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%A5%D0%BE%D0%B0%D1%80%D0%B0
=====
to live is to die
Мария

Посетитель

ID: 405671

326473

= общий =    09.06.2022, 14:57
Спасибо, буду искать подсказки на этих ресурсах. Еще раз спасибо за уделенное время!
Алексеев Владимир Николаевич

Мастер-Эксперт

ID: 259041

326482

= общий =    10.06.2022, 08:55
Учитесь по Школьному принципу "От простого к сложному". Вам трудно, потому что Вы пытаетесь распутать сразу Б клубок : Счётчик, Рекурсию и сортировку Хоара.
Напишите сначала простенькую прогу со счётчиком вызовов простейшей Функции. Без массивов и сортировок. Убедитесь, что счётчик работает адекватно.

Затем добавьте рекурсию в свою функцию. Рекурсию надо ограничить (глубиной вложений или кол-вом циклов), чтобы Ваша прога не зациклилась. Если не будет получаться, сообщите, я вышлю Вам свой скрипт для примера.
Мария

Посетитель

ID: 405671

326491

= общий =    12.06.2022, 09:13
Спасибо!
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.