С++: произведение с переполнением...
Задача состояла в проверке того, сколько сомножителей можно взять в некотором произведении, пока не наступит переполнение (при вычислении с заданным целочисленным типом данных). Например, факториал от какого максимального значения аргумента можно вычислить в типе данных 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-байтовых длинных целых).
08.11.2013, 18:39 [8764 просмотра]