Создать отдельный стек для функции

@kravam · Регистрация: 04.06.2008

Author24 — интернет-сервис помощи студентам

необходимо. Мне надо вызывать рекурсивную функцию; при этом происходит переполнение стека, мне бы хотелось бы это контролировать.
g++ не поддерживает обработку SEH- исключений, отловить переполнение стека, как, впрочем и другие я не могу. Программа падает просто и всё.
вызов рекурсивной функции в отдельном потоке с созданным и, как следствие, контролируемым стеком (билиотека pthread) рассамтриваю только в качестве ПОСЛЕДНЕГО варианта.

Спасибо, кто откликнется

Добавлено через 48 минут
Только что в отладчике OllyDbg исполоьзовал такой приём: выделял объём памяти и вручную менял регистр ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек.
Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь.

@~~Сыроежка~~ · 29.11.2011, 23:08

kravam,

Ваша идея крайне опасная и в принципе некорректная! Не надо делать все через одно заднее место. Надо просто рекурсивную функцию заменить на нерекурсивную и не морочить ни себе, ни другим голову!

@kravam · 29.11.2011, 23:23 **[ТС]**

Там комбинаторика, её не заменить. Другое дело, что глубина рекурсии невысока, поэтому вряд ли стек переполнится. Но! Это "вряд ли" применимо к безошибочному коду. А если я по ошибке (а в процессе написания прог я тыщу раз ошибочно создавал бесконечную рекурсию) запущу эту рекурсивную функцию, то стек переполнится, а программа прсто рухнет и я не буду знать, что программа рухнула из-за переполнения стека. g++ с SEH вообще никак, то есть абсолютно.

Поэтому пока я прогу отлаживаю мне и нужно это как индикатор, то что идея рисковая я и сам знаю. Предложите другую.

Только не предлагайте ме заменять рекурсию чем-нибудь другим...
И чё не корректного, да?

@alex_x_x · 30.11.2011, 00:39

Сообщение от kravam

Там комбинаторика, её не заменить.

не вычисление факториалов, сочетаний, надеюсь?

Сообщение от kravam

ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек.
Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь.

вообще-то стек так и работает
вы просто рискуете его разрушить

@kravam · 30.11.2011, 01:11 **[ТС]**

Почему не сочетаний? Как раз-таки сочетаний из m по n без возврата
И завязывайте уже намёками говорить. Полуфразы-полудиалоги у вас. Я знаю как стек работает и докладаю, что если нормально программу скропать- если нормально, подчёркиваю, вы же об этом риске говорите?- риска вообще нет никакого. При штатном тык скыть стеке и то риск больший потому что прога выкинет необрабатываеющееся исключение, я говорил уже. В моём же случае предполагается в самой рекурсивной функции подсчёт памяти, которую она занимает с момента тык скыть начала цепочки и если чё просто сигнализирование: не та, дескать, память.

Другое дело, что её можно и не скропать нормально-то, можно вообще никак не скропать. Так это второй вопрос. Так-то я прочёл у вас: ты рискуешь не написать программу. Ну да, есть такое.

Короче: очень информативное сообщение у вас получилось.

Вот дядька примерно то же самое делает.
http://www.rsdn.ru/article/baseserv/stack.xml

@alex_x_x · 30.11.2011, 13:26

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

Добавлено через 40 минут
я ж понимаю вот это нужно

C

#include <math.h>
#include <stdio.h>
 
static int round_value(double value)
{
   return (int)floor (value + 0.5); 
}
 
unsigned c_n_k (unsigned n, unsigned k)
{
   double val = 1.;
   unsigned i;
 
   for (i=1;i<=k;++i)
   {
      val *= 1. * (n - k + i) / i;
   }
 
   return (unsigned)round_value (val);
}
 
int main()
{
   unsigned n = 12, k = 6;
   printf ("(%u, %u) = %u", n, k, c_n_k(n, k));
   return 0;
}

@Nameless One · 30.11.2011, 13:51

Как вариант, переписать на хвостовую рекурсию (если это возможно), плюс компилировать с ключем -03, и (возможно), gcc соптимизирует хвостовые вызовы (тему не читал). Вообще, любую рекурсивную функцию можно переписать на цикл, и это будет правильно в случае С/С++ (это же вам не хацкель какой-нибудь)

@kravam · 30.11.2011, 14:16 **[ТС]**

Сдаётся мне, что этот код неправильный, он что делает?

@alex_x_x · 30.11.2011, 14:22

kravam, считает сочетание из n по k
на каких входных данных неправильно?

@kravam · 30.11.2011, 14:23 **[ТС]**

Я там не уточнил, поэтому щас все уточнения: я так понимаю, он работает без возврата и без учёта порядка?

@alex_x_x · 30.11.2011, 14:27

Сообщение от kravam

Я там не уточнил, поэтому щас все уточнения: я так понимаю, он работает без возврата и без учёта порядка?

поточнее
здесь реализовано почленное деление множителей факториалов в числителе и знаменателе
это самый простой и довольно точный способ сосчитать сочетание

@kravam · 30.11.2011, 14:30 **[ТС]**

Не ну как поточнее? Вот поточнее: как найти число сочетаний из m по n без возврата и без учёта порядка?
А вы мне даёте "почленное деление множителей факториала"

Если это одно и тоже, так и скажете: одно и то же. Если нет, тогда этот пример не уместен.

@alex_x_x · 30.11.2011, 15:22

Сообщение от kravam

без возврата и без учёта порядка?

объясните что это значит

@kravam · 30.11.2011, 15:58 **[ТС]**

Дурака включаем?

@Nameless One · 30.11.2011, 16:01

Сообщение от kravam

Дурака включаем?

почему же? Мне вон тоже непонятно. Просвети нас, о Мудрейший

@kravam · 30.11.2011, 16:10 **[ТС]**

Ага. Вон оно чё. Понятно всё с вами.
Вот если есть в корзине 5 шаров пронумерованных от 0 до 4-х и мы вытаскиваем 3 раза по одному шару и записываем каждый номер на бумажку и шар назад в корзину не возвращаем, т это без возврата называется.
Nameless One, вы этого не знали? ну-ну...

Так, и если мы так проделаем несколько раз подряд и смотрим на наборы номеров каждый раз которые получились. И видим, что однажды мы вытащили три шара в таком порядке 0, 2, 3, а другой раз в порядке 0, 3, 2, и услаливаемся, что эти наборы (ну или множества, кому как угодно) равные то это называется без учёта порядка.
Nameless One, этого вы не знали?

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

@Nameless One · 30.11.2011, 16:23

Сообщение от kravam

Вот если есть в корзине 5 шаров пронумерованных от 0 до 4-х и мы вытаскиваем 3 раза по одному шару и записываем каждый номер на бумажку и шар назад в корзину не возвращаем, т это без возврата называется.
Nameless One, вы этого не знали? ну-ну...

это называется сочетаниями без повторений

Сообщение от kravam

Так, и если мы так проделаем несколько раз подряд и смотрим на наборы номеров каждый раз которые получились. И видим, что однажды мы вытащили три шара в таком порядке 0, 2, 3, а другой раз в порядке 0, 3, 2, и услаливаемся, что эти наборы (ну или множества, кому как угодно) равные то это называется без учёта порядка.
Nameless One, этого вы не знали?

"сочетания", в которых учитывается порядок, называются размещениями

мораль: следует пользоваться общепринятой терминологией, чтобы тебя понимали окружающие. А если такой терминологии нет, то нужно уточнять приводимые понятия, чтобы не возникало неопределенности.

Сообщение от kravam

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

остается только догадываться, почему человек, который вроде бы не первый день на форуме, позволяет себе в ответ на вполне невинный вопрос откровенное хамство. Причем по отношению к человеку, который проявил интерес к его проблеме и даже предложил вариант ее решения

@Nameless One · 30.11.2011, 16:44

Сообщение от kravam

Сдаётся мне, что этот код неправильный, он что делает?

сдается мне (судя по последним уточнениям), что этот код делает как раз то, что тебе нужно

@kravam · 30.11.2011, 16:51 **[ТС]**

гы... А вот тут, например, другие определения. И в частности расматриваемый вариант, о котором идёт речь, называется именно сочетанием и именно без возврата (ах, да, без возвращения) и именно без учёта порядка.

Но дело не в названиях, как вы понимаете. Просто вы поняли о чём речь и тот парень понял и переспрашивает. Ну, Бог вам судья.

Добавлено через 1 минуту

Сообщение от Nameless One

сдается мне (судя по последним уточнениям), что этот код делает как раз то, что тебе нужно

Это зависит от предназначения кода. Я пока не услышал его предназначения.

@Nameless One · 30.11.2011, 16:58

Сообщение от kravam

А вот тут, например, другие определения

там такие определения, а в лекциях/учебниках, по которым я учился в вузе - другие. В той же Википедии, например, именно используются именно те термины, которые привел я. Лично я, когда увидел "возврат", подумал о возврате именно в контексте программирования (т.е. возврат из функции и т.п.), и это меня порядком смутило

Сообщение от kravam

Это зависит от предназначения кода. Я пока не услышал его предназначения.

он делает именно то, что у тебя по ссылке описано в теореме 3. Кстати, это прекрасно видно из самого кода

Добавлено через 1 минуту

Сообщение от kravam

А вот тут, например, другие определения

да, посмотри теорему 2 по твоей ссылке, там как раз и увидишь число размещений

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	30.11.2011, 16:23	17
	Сообщение от kravam Вот если есть в корзине 5 шаров пронумерованных от 0 до 4-х и мы вытаскиваем 3 раза по одному шару и записываем каждый номер на бумажку и шар назад в корзину не возвращаем, т это без возврата называется. Nameless One, вы этого не знали? ну-ну... это называется сочетаниями без повторений Сообщение от kravam Так, и если мы так проделаем несколько раз подряд и смотрим на наборы номеров каждый раз которые получились. И видим, что однажды мы вытащили три шара в таком порядке 0, 2, 3, а другой раз в порядке 0, 3, 2, и услаливаемся, что эти наборы (ну или множества, кому как угодно) равные то это называется без учёта порядка. Nameless One, этого вы не знали? "сочетания", в которых учитывается порядок, называются размещениями мораль: следует пользоваться общепринятой терминологией, чтобы тебя понимали окружающие. А если такой терминологии нет, то нужно уточнять приводимые понятия, чтобы не возникало неопределенности. Сообщение от kravam Остаётся только догадываться, почему такой уважаемый человек позволяет себе мелкое ёрничанье. остается только догадываться, почему человек, который вроде бы не первый день на форуме, позволяет себе в ответ на вполне невинный вопрос откровенное хамство. Причем по отношению к человеку, который проявил интерес к его проблеме и даже предложил вариант ее решения 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	30.11.2011, 16:44	18
	Сообщение от kravam Сдаётся мне, что этот код неправильный, он что делает? сдается мне (судя по последним уточнениям), что этот код делает как раз то, что тебе нужно 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 16:51 [ТС]	19
	гы... А вот тут, например, другие определения. И в частности расматриваемый вариант, о котором идёт речь, называется именно сочетанием и именно без возврата (ах, да, без возвращения) и именно без учёта порядка. Но дело не в названиях, как вы понимаете. Просто вы поняли о чём речь и тот парень понял и переспрашивает. Ну, Бог вам судья. Добавлено через 1 минуту Сообщение от Nameless One сдается мне (судя по последним уточнениям), что этот код делает как раз то, что тебе нужно Это зависит от предназначения кода. Я пока не услышал его предназначения. 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
		1
	Создать отдельный стек для функции 29.11.2011, 22:26. Показов 3542. Ответов 44 Метки нет (Все метки) необходимо. Мне надо вызывать рекурсивную функцию; при этом происходит переполнение стека, мне бы хотелось бы это контролировать. g++ не поддерживает обработку SEH- исключений, отловить переполнение стека, как, впрочем и другие я не могу. Программа падает просто и всё. вызов рекурсивной функции в отдельном потоке с созданным и, как следствие, контролируемым стеком (билиотека pthread) рассамтриваю только в качестве ПОСЛЕДНЕГО варианта. Спасибо, кто откликнется Добавлено через 48 минут Только что в отладчике OllyDbg исполоьзовал такой приём: выделял объём памяти и вручную менял регистр ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек. Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь. 0

@~~Сыроежка~~ Заблокирован
	29.11.2011, 23:08	2
	kravam, Ваша идея крайне опасная и в принципе некорректная! Не надо делать все через одно заднее место. Надо просто рекурсивную функцию заменить на нерекурсивную и не морочить ни себе, ни другим голову! 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	29.11.2011, 23:23 [ТС]	3
	Там комбинаторика, её не заменить. Другое дело, что глубина рекурсии невысока, поэтому вряд ли стек переполнится. Но! Это "вряд ли" применимо к безошибочному коду. А если я по ошибке (а в процессе написания прог я тыщу раз ошибочно создавал бесконечную рекурсию) запущу эту рекурсивную функцию, то стек переполнится, а программа прсто рухнет и я не буду знать, что программа рухнула из-за переполнения стека. g++ с SEH вообще никак, то есть абсолютно. Поэтому пока я прогу отлаживаю мне и нужно это как индикатор, то что идея рисковая я и сам знаю. Предложите другую. Только не предлагайте ме заменять рекурсию чем-нибудь другим... И чё не корректного, да? 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	30.11.2011, 00:39	4
	Сообщение от kravam Там комбинаторика, её не заменить. не вычисление факториалов, сочетаний, надеюсь? Сообщение от kravam ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек. Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь. вообще-то стек так и работает вы просто рискуете его разрушить 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 01:11 [ТС]	5
	Почему не сочетаний? Как раз-таки сочетаний из m по n без возврата И завязывайте уже намёками говорить. Полуфразы-полудиалоги у вас. Я знаю как стек работает и докладаю, что если нормально программу скропать- если нормально, подчёркиваю, вы же об этом риске говорите?- риска вообще нет никакого. При штатном тык скыть стеке и то риск больший потому что прога выкинет необрабатываеющееся исключение, я говорил уже. В моём же случае предполагается в самой рекурсивной функции подсчёт памяти, которую она занимает с момента тык скыть начала цепочки и если чё просто сигнализирование: не та, дескать, память. Другое дело, что её можно и не скропать нормально-то, можно вообще никак не скропать. Так это второй вопрос. Так-то я прочёл у вас: ты рискуешь не написать программу. Ну да, есть такое. Короче: очень информативное сообщение у вас получилось. Вот дядька примерно то же самое делает. http://www.rsdn.ru/article/baseserv/stack.xml 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	30.11.2011, 13:51	7
	Как вариант, переписать на хвостовую рекурсию (если это возможно), плюс компилировать с ключем -03, и (возможно), gcc соптимизирует хвостовые вызовы (тему не читал). Вообще, любую рекурсивную функцию можно переписать на цикл, и это будет правильно в случае С/С++ (это же вам не хацкель какой-нибудь) 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 14:16 [ТС]	8
	Сдаётся мне, что этот код неправильный, он что делает? 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	30.11.2011, 14:22	9
	kravam, считает сочетание из n по k на каких входных данных неправильно? 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 14:23 [ТС]	10
	Я там не уточнил, поэтому щас все уточнения: я так понимаю, он работает без возврата и без учёта порядка? 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	30.11.2011, 14:27	11
	Сообщение от kravam Я там не уточнил, поэтому щас все уточнения: я так понимаю, он работает без возврата и без учёта порядка? поточнее здесь реализовано почленное деление множителей факториалов в числителе и знаменателе это самый простой и довольно точный способ сосчитать сочетание 0

	30.11.2011, 16:58

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 14:30 [ТС]	12
	Не ну как поточнее? Вот поточнее: как найти число сочетаний из m по n без возврата и без учёта порядка? А вы мне даёте "почленное деление множителей факториала" Если это одно и тоже, так и скажете: одно и то же. Если нет, тогда этот пример не уместен. 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	30.11.2011, 15:22	13
	Сообщение от kravam без возврата и без учёта порядка? объясните что это значит 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 15:58 [ТС]	14
	Дурака включаем? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	30.11.2011, 16:01	15
	Сообщение от kravam Дурака включаем? почему же? Мне вон тоже непонятно. Просвети нас, о Мудрейший 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	30.11.2011, 16:10 [ТС]	16
	Ага. Вон оно чё. Понятно всё с вами. Вот если есть в корзине 5 шаров пронумерованных от 0 до 4-х и мы вытаскиваем 3 раза по одному шару и записываем каждый номер на бумажку и шар назад в корзину не возвращаем, т это без возврата называется. Nameless One, вы этого не знали? ну-ну... Так, и если мы так проделаем несколько раз подряд и смотрим на наборы номеров каждый раз которые получились. И видим, что однажды мы вытащили три шара в таком порядке 0, 2, 3, а другой раз в порядке 0, 3, 2, и услаливаемся, что эти наборы (ну или множества, кому как угодно) равные то это называется без учёта порядка. Nameless One, этого вы не знали? Остаётся только догадываться, почему такой уважаемый человек позволяет себе мелкое ёрничанье. 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	30.11.2011, 16:58	20
	Сообщение от kravam А вот тут, например, другие определения там такие определения, а в лекциях/учебниках, по которым я учился в вузе - другие. В той же Википедии, например, именно используются именно те термины, которые привел я. Лично я, когда увидел "возврат", подумал о возврате именно в контексте программирования (т.е. возврат из функции и т.п.), и это меня порядком смутило Сообщение от kravam Это зависит от предназначения кода. Я пока не услышал его предназначения. он делает именно то, что у тебя по ссылке описано в теореме 3. Кстати, это прекрасно видно из самого кода Добавлено через 1 минуту Сообщение от kravam А вот тут, например, другие определения да, посмотри теорему 2 по твоей ссылке, там как раз и увидишь число размещений 0