Приведенный выше код нахождения
наименьшего общего кратного содержит не бросающийся в глаза баг. Этот баг присутствует в отладочном предложении с
assert.
Даже получив указание, где находится баг, не так легко сходу разобраться, в чем он заключается.
Дело в том, что код предназначен для нахождения
наименьшего общего кратного знаковых целых чисел. В функциональном объекте
decomposition эти числа переводятся в беззнаковые целые числа с помощью стандартной функции
abs. Поэтому в выражениях внутри определения этого функционального объекта, например, -2 превращается в 2. В то же время в предложении с
assert функция
abs не применяется к последовательности знаковых целых чисел. Поэтому в выражениях с беззнаковыми объектами внутреннее представление отрицательных чисел будет рассматриваться как некое положительное число. Так - 2,приведенное к типу
unsigned long long, будет интерпретироваться как 18446744073709551614.
Чтобы было более понятно, то, допустим, у нас есть последовательность целых следующего вида
{ -2, 3 }
Так как функциональный объект
decomposition использует функцию
abs, то
наименьшее общее кратное будет определяться для положительных чисел { 2, 3 }, и в итоге будет равно 6. Однако внутри предложения с
assert функция
abs не используется, а потому возникнет сообщение об ошибке. Действительно, если выполнить следующее предложение
std::cout << ( unsigned long long )6 % -2 << std::endl;
то результатом будет вывод на экран значение 6. так как
( unsigned long long )-2 больше чем
( unsigned long long )6.
Если бы это предложение было переписано следующим образом
std::cout << ( unsigned long long )6 % std::abs( -2 ) << std::endl;
то получился бы корректный результат 0.
Даже если вы не смогли уследить за ходом обсуждения причины бага, вам следует знать, что функциональный объект, используемый в предложении с
assert, не корректный, то есть не соответствует алгоритму, который использовался в вычислении
наименьшего общего кратного.
Поэтому эти эффектно вложенные друг в друга функциональные объекты, используемые в алгоритме
std::all_of в предложении с
assert
std::not1( std::bind1st( std::modulus<unsigned long long>(), lowest_commom_multiple ) )
придется заменить на менее эффектно выглядящее, но более корректное лямбда-выражение
[=]( int x )
{
return ( lowest_commom_multiple % abs( x ) == 0 );
} )
Еще одно замечание по программе. Программа совершенно игнорирует ситуацию, когда последовательность чисел состоит только из 1 и/или -1. Для таких последовательностей
наименьшее общее кратное будет равно 1. Следовательно такая возможность должна быть обработана кодом. Кроме того, если 1 попала в разложение
наименьшего общего кратного, в котором представлены и другие простые множители, то указание 1 в степени 1 при выводе на консоль в виде
1^1 будет лишним. Поэтому элемент
std::map с ключом равным 1 следует удалить. Он должен быть оставлен только в случае, когда он единственный в разложении
наименьшего общего кратного С учетом всего сказанного более корректный код программы будет выглядеть следующим образом
#include <iostream>
#include <map>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <ctime>
#include <cassert>
int main()
{
const size_t N = 20;
int a[N];
std::srand( ( unsigned ) std::time( 0 ) );
std::generate( std::begin( a ), std::end( a ),
[] { return ( std::rand() % N + 1 ); } );
for ( int x : a ) std::cout << x << ' ';
std::cout << std::endl;
std::map<unsigned int, size_t> m;
auto decomposition = [&m]( int x )
{
unsigned int z = std::abs( x );
if ( z == 1 )
{
m[z] = 1;
}
else
{
for ( unsigned int i = 2; i * i <= z; i++ )
{
size_t n = 0;
while ( z % i == 0 )
{
++n;
z /= i;
}
if ( n != 0 ) m = std::max( m, n );
}
if ( 1 < z && !m[z] ) ++m[z];
}
};
std::for_each( std::begin( a ), std::end( a ), decomposition );
if ( m.size() != 1 && m.find( 1 ) != m.end() ) m.erase( 1 );
auto multiply = []( unsigned long long acc,
std::pair<unsigned int, size_t> p ) ->unsigned long long
{
unsigned long long n = 1;
for ( size_t i = p.second; i != 0; --i ) n *= p.first;
return ( acc == 0 ? n : n * acc );
};
unsigned long long lowest_commom_multiple =
std::accumulate( m.begin(), m.end(), 0ull, multiply );
assert
(
std::all_of( std::begin( a ), std::end( a ),
[=]( int x )
{
return ( lowest_commom_multiple % std::abs( x ) == 0 );
} )
);
std::cout << lowest_commom_multiple << " =";
char c = ' ';
for ( const auto &p : m )
{
std::cout << c << ' ' << p.first << '^' << p.second << ' ';
c = '*';
}
std::cout << std::endl;
return 0;
}
Протестируйте ее самостоятельно, например, для таких последовательностей, как
{ 1, -1 }
{ -2, 3 }
{ 1, 2, 3 }
- участник сейчас на форуме
- участник вне форума