БлогNot. С++: произведение с переполнением...

С++: произведение с переполнением...

Задача состояла в проверке того, сколько сомножителей можно взять в некотором произведении, пока не наступит переполнение (при вычислении с заданным целочисленным типом данных). Например, факториал от какого максимального значения аргумента можно вычислить в типе данных long int или unsigned long int.

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

long int i=1,p=1;
for (;;i++) {
 p*=i;
 if (p<0) break;
}
//ответ = i-1

или уменьшение произведения p по отношению к его предыдущему значению p1

unsigned long int p=1,p1=0,i=1;
for (;;i++) {
 p*=i;
 if (p<p1) break;
 p1=p;
}

может оказаться опасным - вдруг произведение растёт настолько быстро, что при умножении очередное значение p "перепрыгнет" через область ограничений? Например, вместо ожидаемого из-за переполнения отрицательного числа получится снова положительное?

Возможно, более правильной идеей будет следующая - в цикле считать произведение p и при этом контролировать его на переполнение, деля текущее произведение на последний сомножитель и проверяя, равно ли частное предыдущему сохранённому значению произведения p0.

На пример факториала код может выглядеть так:

unsigned long int nf() {
 unsigned long int p=1,p0=1,i=1;
 for (;;i++) {
  p*=i; //или накопление другого произведения
  if ((p/i)!=p0) return i; //или деление не на i, а на последний сомножитель
  p0=p;
 }
}

Код работает только "в целых числах", узкое место - (p/i)!=p0 - ведь деление целых значений в C/C++ всегда даёт тоже целое значение, то есть, 5/2==2.

Кстати, для факториала ответ всего-навсего 13 (при 4-байтовых длинных целых).


теги: c++ алгоритм

08.11.2013, 18:39; рейтинг: 7877