Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562

Ошибки: Неуместная рекурсия при вычислении миноров

26.09.2014, 13:30. Показов 2915. Ответов 45
Метки нет (Все метки)

Неуместная рекурсия.
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
double det(dpuble *a, int n)
{
 double ***minors;
 double result;
 int m;
 int i;
 int j;
 if (n==2)
 {
   return (a[0][0]*a[1][1]-a[1][0]*a[0][1];
 }
 minors=new double**[n];
 for (result=0.0, m=0; m<n; ++m)
 {
  minors[m]=new double*[n-1];
  for (i=0, i<(n-1); i++)
  {
   minors[m][i]=new double[n-1];
   for (j=0, j<(n-1); j++)
   {
    if (i<m)
    {
     minors[m][i][j]=a[i][j+1];
    }
    else
    {
     minors[m][i][j]=a[i-1][j+1];
    }
   }
   if (i%2==0)
   {
    result+=det(minors[m], n-1);
   }
   else
   {
    result-=det(minors[m], n-1);
   }
   delete [] minors[m][i];
  }
  delete [] minors[m];
 }
 delete [] minors;
 return result;
}
void kramer(double **a, int n, double *b, double *x)
{
 double **ax;
 double d;
 double dx;
 int i;
 int j;
 int k;
 d=det(a, n);
 ax=new double*[n];
 for (i=0; i<n; ++i)
 {
  ax=new double [n];  
  for (j=0; j<n; ++j)
  {
   ax[j]=new double [n];  
   for (k=0; k<n; ++k)
   {
    if (i==j)
    {
     ax[j][k]=b[k];
    }
    else
    {
     ax[j][k]=a[j][k];
    }
   }
   dx=det(ax,n);
   x[i]=dx/d;
  }
  for (j=0; j<n; ++j)
  {  
   delete [] ax[j];
  }
 }
 delete [] ax;
}
Ошибка заключается в перерасходе памяти из-за того, что при каждом рекурсивном вызове выделяется память для минора. Хуже всего, если этот программный текст перевести с использованием статических массивов на язык вроде паскаля, где тип массива - полноценный тип и если этим типом декларировать неизменяемый параметр подпрограммы, то он передаётся по значению, а не по указателю. Тогда возможно расходование на миноры дефицитнейшей памяти - стека, причём, ещё и в сочетании с резервированием массивов максимального размера, что увеличивает сам расход памяти. Рекурсию использовать надо, но ровно в двух случаях:
1. Если для решения задачи вообще не получается составить не рекурсивный алгоритм.
2. Если рекурсивны сами обрабатываемые данные (пример тому - работа с деревьями).
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.09.2014, 13:30
Ответы с готовыми решениями:

Ошибки при вычислении
Что я опять не так делаю? :wall: В методичке тоже самое написано и все вычислено а у меня не хочет. Файл - в студию!!!

Ошибки при вычислении функции
Нужно нарисовать график функции, но все время возникают следующие ошибки: 200, 215 и 217. uses crt,graph; var ...

Ошибки при вычислении выражения
Помогите почему не работает #include&lt;conio.h&gt; #include&lt;math.h&gt; #include&lt;stdio.h&gt; int main() { float i,ch,n,S,f,eps; ...

45
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:06  [ТС]
Цитата Сообщение от aLarman Посмотреть сообщение
стоп поправлюсь, точнее не без нее, а без ьессмысленнго расхода памяти на миноры, их же можно использовать оригинальные(т.е брать данные из исходной матрицы)
Нельзя. Из матрицы при каждом вызове вычёркивается одна строка и один столбец, при вызове из экземпляра, уже обрабатывающего минор, вычёркивается ещё одна строка и один столбец и так далее. Где хранить информацию о том, что и где вычеркнуто? А ведь по всему этому безобразию надо ещё умудриться пройти в цикле. Поэтому здесь только избавляться от рекурсии вообще, например, менять Крамера на Гаусса.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:09
Цитата Сообщение от taras atavin Посмотреть сообщение
Где хранить информацию о том, что и где вычеркнуто?
а передать индекс вычеркнутой строки и столбка не вариант чтоле
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:13  [ТС]
Да и определители можно ведь считать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double det(double **a, int n)
{
 int i;
 int j;
 int k;
 double r;
 for (i=0; i<n; ++i)
 {
   for (j=i+1; j<n; ++j)
   {
    for (k=i+1; k<n; ++k)
    {
     a[j][k]-=a[i][k]*a[j][i]/a[i][i];
    }
    a[j][i]=0.0;  
   }
 }
 for (r=1.0, i=0; i<n; ++i)
 {
  r*=a[i][i];
 }
 return r;
}
.

Добавлено через 34 секунды
Цитата Сообщение от aLarman Посмотреть сообщение
а передать индекс вычеркнутой строки и столбка не вариант чтоле
Один индекс? Или тысячу? Ранее вычеркнутые не возвращаются.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:15
Цитата Сообщение от taras atavin Посмотреть сообщение
Один индекс? Или тысячу?
передать вектор вычеркнутых индексов хД

Добавлено через 49 секунд
Цитата Сообщение от taras atavin Посмотреть сообщение
Да и определители можно ведь считать так:
так зачем же тогда использовать рекурсию
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:15  [ТС]
Цитата Сообщение от aLarman Посмотреть сообщение
так тут без нее и можно обойтись так то
Обойтись без неё можно даже в тех случаях, когда она уместна. Но так делать тоже не надо.

Добавлено через 43 секунды
Цитата Сообщение от aLarman Посмотреть сообщение
передать вектор вычеркнутых индексов хД
Эйси. А как потом его наложить на матрицу?
0
26.09.2014, 17:16

Не по теме:

а зачем нужна дорога, если через нее нельзя перевести бабку

0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:16  [ТС]
Цитата Сообщение от aLarman Посмотреть сообщение
так зачем же тогда использовать рекурсию
Здесь её и не надо использовать.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:16
Цитата Сообщение от taras atavin Посмотреть сообщение
А как потом его наложить на матрицу?
зачем накладывать, просто столбцы и строки с такими индексами не использовать в расчете
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:17  [ТС]
Цитата Сообщение от aLarman Посмотреть сообщение
зачем накладывать, просто столбцы и строки с такими индексами не использовать в расчете
Как?
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:20
тогда проще будет сет, короч
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 0; //blabla)
{
if(IndexSet.find(i) != IndexSet.end())
{
continue;
}
for(int j = 0; //blabla)
{
if(IndexSet.find(j) != IndexSet.end())
{
continue;
}
}
}
как нить так
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:22  [ТС]
Я на дипломе допустил именно эту ошибку. В результате порядок матрицы решабельной системы ограничился шестью, на семи происходило переполнение стека и сообщение стек ойвелоу. Заменил Крамера Гауссом и на той же машине смог решить систему с матрицей трёхсотого порядка. Проект был на object pascal, для всех матриц, в том числе миноров, юзались статические массивы. Нашёл за несколько минут тестирования библиотеки, подцепив её к специальному тестовому проектику. После тестов подцепил её к основному проекту.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:30
а дык, сосчитайте сколько будет вызовов для матрицы в 7 строк и столбцов
7*6*5*4*3
почти факториал размерности, есесна оверфлоу будет

Добавлено через 2 минуты
есесна если у тебя рекурсия порождает такое кол-во вызовов будет беда, лучше макимум 2 вызова делать, а то что больше уже слишком быстро растет от глубины рекурсии
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 17:54  [ТС]
Цитата Сообщение от aLarman Посмотреть сообщение
а дык, сосчитайте сколько будет вызовов для матрицы в 7 строк и столбцов
7*6*5*4*3
почти факториал размерности, есесна оверфлоу будет
Нерекурсивная подпрограмма вызывалась один раз и только для одной матрицы.

Добавлено через 9 минут
Цитата Сообщение от aLarman Посмотреть сообщение
есесна если у тебя рекурсия порождает такое кол-во вызовов будет беда, лучше макимум 2 вызова делать, а то что больше уже слишком быстро растет от глубины рекурсии
Скорость роста не отменяет самого недостатка, просто иногда приходится на этот расход памяти всё таки идти, чтоб не сделать ещё хуже, а иногда нет.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TDir *Search(TDir *Dir, std::string &Name)
{
 TDir *p;
 TDir *t;
 if (Dir->Name==Name)
 {
  return Dir;
 }
 if (Dir->ChildrenCount>0)
 {
  for (p=Dir->Children+Dir->ChildrenCount-1; p>=Dir->Children; --p)
  {
   t=Search(p, Name);
   if (t!=NULL)
   {
    return t;
   }
  }
 }
 return NULL;
}
, зависимость количества вызовов от количества уровней может быть ещё хуже, но здесь рекурсия уместнее. Отличие же именно в том, что здесь обрабатывается дерево, а поддерево есть часть дерева, которое само является деревом.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 17:57
Цитата Сообщение от taras atavin Посмотреть сообщение
но здесь рекурсия уместнее.
речь все таки об уместности рекурсии или что?
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 18:03  [ТС]
Речь о том, что прежде чем применять рекурсию, следует подумать, действительно ли она нужна именно в этом случае. Если уместна, то ни в коем случае нельзя искусственно от неё избавляться. Юзайте рекурсию. Нет - юзайте не рекурсивные алгоритмы.

Добавлено через 3 минуты
Бывает, что два алгоритма решения одной и той же задачи/подзадачи не имеют значимых преимуществ перед друг другом и выбирать один из них можно произвольно. Но если один алгоритм рекурсивен, а другой нет, то такая ситуация уже не возможна и выбор должен быть обоснован.
0
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
26.09.2014, 18:06
ну логично же, что ,если каждый вызов рекурсии требует перекопирования части матрицы, то лучше отказаться от нее(от рекурсии)
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 18:12  [ТС]
Это только пример. Рекурсивный факториал тоже не так хорош как кажется, хотя там зависимость линейная. Пока память избыточна, можно юзать
C++
1
2
3
4
5
6
7
8
unsigned long int f(unsigned short int n)
{
 if (x==0)
 {
  return 1;
 }
 return f(n-1)*n;
}
. А если память и так уже достаточно израсходована? Мало ли на каком уровне вложения вызовов потребуется факториал и сколько при этом будет физической памяти. Калькулятор на настольном компе - не единственная возможность вызова фактриала. Лучше сразу сделать явно-циклический вариант, а не ждать, что не хватит ровно шестнадцати байт.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38207 / 21140 / 4311
Регистрация: 12.02.2012
Сообщений: 34,752
Записей в блоге: 14
26.09.2014, 18:27
taras atavin, Ваш код ужасен!!! Вот рекурсивная программа расчета определителя:

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
int *minor (int *A, int n, int k)
{
    int sz,i,j,jj,ii,pf,pt;
    int *m;
    sz=n-1;
    m=new int[sz*sz];
    ii=-1;
    for (i=0; i<n; i++)
        if (i != k) 
        {
            ii++;
            for (j=1; j<n; j++)
            {
                jj=j-1;
                pf=index(n,j,i);
                pt=index(n-1,jj,ii);
                m[pt]=A[pf];
            }
        }
    return m;
}
        
int Det (int *A,int n)
{
    int i,s,p,z;
    int *mi;
 
    if (n == 2)
        return A[0]*A[3]-A[1]*A[2];
    else
    {
        s=0;
        p=1;
        for (i=0; i<n; i++)
        {
            z=A[index(n,0,i)];
            mi=minor(A,n,i);           // строим минор
            s+=p*z*Det(mi,(n-1)); // учитываем
            p=-p;                        // удаляем
            delete mi;
        }
        return s;
    }
}
Разумеется, вычислять определители нужно методом Гаусса...
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
26.09.2014, 18:29  [ТС]
Цитата Сообщение от Catstail Посмотреть сообщение
taras atavin, Ваш код ужасен!!! Вот рекурсивная программа расчета определителя:
Ничего подобного. Если матрица 2x2 то в ней не может быть индексов от 0 до 3.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38207 / 21140 / 4311
Регистрация: 12.02.2012
Сообщений: 34,752
Записей в блоге: 14
26.09.2014, 18:33
Цитата Сообщение от taras atavin Посмотреть сообщение
Ничего подобного. Если матрица 2x2 то в ней не может быть индексов от 0 до 3.
- торопишься... Ты приглядись - у меня не используются двумерные массивы (двумерные массивы мапируются на одномерные).

Добавлено через 1 минуту
Да, не включил в код функцию мапирования:

C++
1
2
3
4
int index(int n, int i, int j)
{
    return n*i+j;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.09.2014, 18:33

Ошибки при вычислении в double
При выполнении самых простых операций над числами происходит непонятно что. double k = 14.02 - 14; // k = 0.019999999999999574 ...

Ошибки при вычислении интегралов
Здравствуйте! Решаю следующую задачу по тер вер.: есть совместная плотность случайных величин f(x,y): f(x,y)=a*m*exp(-(a*x+m*y)) в...

Ошибки при вычислении выражения
Народ, я в затупке, что я не так делаю вот код Public Class Form1 Private Sub Button1_Click(ByVal sender As System.Object,...

Найти ошибку(ошибки) при вычислении суммы
функция y=\frac{\left( {S}^{3}+0.01n\right)}{S+3} s=m\sum_{k=1}^{20}\frac{1}{{k}^{2}} Написал следующее. Где-то должна быть...

При вычислении функции arccos и преобразовании её в arctg возникают ошибки.
Надо вычислить. #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; #define sqr(t) ((t) * (t)) #define sqrt(t) ((t) / (t)) ...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
alhaos 10.06.2026
Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .
[golang] Состояние гонки (race condition)
alhaos 10.06.2026
Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .
Взрослые отношения, и почему они не получаются
kumehtar 09.06.2026
Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .
[golang] Worker Pool
alhaos 09.06.2026
Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline
alhaos 08.06.2026
Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .
Свет внутри себя
kumehtar 07.06.2026
Пусть это будет здесь lIs4oanZS9Y
Программа для com-порта
Uhbif79 05.06.2026
Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[
anaschu 01.06.2026
Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru