2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Проверка переполнения типа в рекурсии
Сообщение03.04.2008, 00:20 
Надо написать функцию для нахождения числа Стирлинга 2 рода(Комбинаторика)
Сама формула выглядит как S(m,n) = S(m-1, n-1) + n*S(m-1, n).

Вот так выглядит моя рекурсивная функция.
MAXANSWER = 2^32;
Код:
unsigned int S(unsigned int m,unsigned int n)
{
   unsigned int Answer = 0;
   unsigned int a, b, c;
   if (m == n)
      return 1;
   if (m > 0 && !n)
                return 0;
   if (!m && !n)
      return 1;
   if (n > m)
      return 0;
   if (!Error)
   {
      a = S(m - 1, n - 1);
      b = S(m - 1, n);
      if (b >= MAXANSWER / n)
      {
         Error = 1;
         return 0;
      }
      c = b * n;
      if (c >= MAXANSWER - a)
      {
         Error = 1;
         return 0;
      }
                Answer = a + c;
   }
   return Answer;
}


Как можно выполнить проверку переполнения a и b в этой функции?

Пользуйтесь тегом [code] // нг

 
 
 
 
Сообщение06.04.2008, 11:27 
Эээ, Вы вроде бы уже выполнили проверку на переполнение следующим кодом:
Код:
if (b >= MAXANSWER / n)
{
  Error = 1;
  return 0;
}
c = b * n;
if (c >= MAXANSWER - a)
{
  Error = 1;
  return 0;
}
Answer = a + c;

Что Вам еще нехватает?

Добавлено спустя 8 минут 47 секунд:

P.S. Мне ясно, что при переполнении у Вас некоторая внешняя переменная Error устанавливается в 1. Неясно только, зачем нужна проверка if (!Error), т.к. в момент провекри Error всегда 0.

 
 
 
 
Сообщение06.04.2008, 12:17 
Error - глобальная переменная, изначально равная 0, как я понимаю, когда наступит переполнение, она станет 1 и, чтобы не заходить в рекурсию, я поставил эту проверку..возможно, я ошибаюсь и она действительно лишняя..

Цитата:
Что Вам еще нехватает?

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

 
 
 
 
Сообщение06.04.2008, 12:25 
Для начала используйте вместо Вашего MAXANSWER именнованную константу UINT_MAX, определенную в limits.h. У меня подозрение, что проблема в 2^32 (естественно не укладывается в 32-битное беззнаковое целое).
Далее. Рекомендую для начала завести промежуточную переменную типа unsigned long long int, проводить с ней все вычисления, проверять ее на то, что она не больше UINT_MAX, и присваивать Вашим переменным ее значение в положительном случае.

Цитата:
Error - глобальная переменная, изначально равная 0, как я понимаю, когда наступит переполнение, она станет 1 и, чтобы не заходить в рекурсию, я поставил эту проверку..возможно, я ошибаюсь и она действительно лишняя..

Посмотрите внимательно - переполнение может произойти только тогда, когда все экземпляры рекурсивной ф-ии уже вызваны, и в каждом вызове проверка на Error уже прошла.

 
 
 
 
Сообщение06.04.2008, 23:55 
да, спасибо большое, по поводу Error и UINT_MAX поправил....но с переполнением осталась бага...до определенных чисел все нормально считает и проверяет переполнение, но когда a достаточно велико бага осталась(причем абсолютно для меня непонятная, ибо проверки действительно на первый взгляд есть) :oops:

 
 
 
 
Сообщение07.04.2008, 11:42 
kdm, Вы сделали так, как я советовал: применить в качестве хранилища промежуточных результатов вычислений unsigned long long int?

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

 
 
 
 
Сообщение07.04.2008, 16:22 
Дествительно, так оно и есть, переполняется стек....осталось это поправить :)

 
 
 
 
Сообщение08.04.2008, 09:20 
Цитата:
Дествительно, так оно и есть, переполняется стек....осталось это поправить

Успехов в поисках багов!

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

Вы посчитайте, как быстро она размножается ($2^n$), сколько памяти и процессорного времени на это тратится.

 
 
 
 
Сообщение08.04.2008, 09:57 
я тоже думал, что знаю :) спасибо

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group