On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 01.07.14 17:18. Заголовок: Наименьшее общее кратное (the lowest common multiple) для набора целых чисел.


Одна фирма, которая объявила о вакансии программиста C++, прислала мне на днях тестовое задание.

Я категорически против выполнения всяких тестовых заданий, которые вам задают различные фирмы. Свое отношение к этому вопросу я высказал в разделе форума "C/C++. Общие вопросы по языку (general questions on C/C++)" в теме Cracking The Coding Interview. 150 Programming Interview. Questions and Solutions.

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

Сразу же скажу, что решение, которое я здесь покажу, вполне возможно не является оптимальным. На самом деле в программировании не требуется находить наилучший алгоритм. Разработка алгоритмов - это дело математиков, а математика, как известно, сложная и обширная область человеческих знаний. В программировании главное, чтобы программа была корректной, понятной и выполняла поставленную задачу с приемлемыми характеристиками.

Основная задача задания формулируется следующим образом.

Найти наименьшее общее кратное для некоторой целочисленной последовательности

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

Кто уже забыл школьную программу по математике, напомню, что наименьшее общее кратное двух целых чисел a и b является такое наименьшее целое число m, которое нацело делится как на a, так и на b.

Например, наименьшим общим кратным чисел a = 140 и b = 110 будет число m = 1540.

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

Например, числа a и b из предыдущего примера можно разложить на простые множители следующим образом:

a = 140 : 2 * 2 * 5 * 7
b = 110 : 2 * 5 * 11

В этих разложениях максимальное число повторений множителя 2 равно 2. Следовательно наименьшее общее кратное m вычисляется следующим образом:

2 * 2 * 5 * 7 * 11

и будет равно, как уже было выше сказано, 1540.

Так как найти наименьшее общее кратное для последовательности чисел?

Для этого удобно использовать стандартный контейнер std::map ключом которого будет простой множитель для всех чисел последовательности, а значением - максимальное повторение множителя в разложении каждого из чисел последовательности.

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

Вот как будет выглядеть программа.

 
#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 );

for ( unsigned int i = 2; i * i <= z; i++ )
{
size_t n = 0;
while ( z % i == 0 )
{
++n;
z /= i;
}
if ( n != 0 ) m[ i ] = std::max( m[ i ], n );
}

if ( 1 < z && !m[ z ] ) ++m[ z ];
};

std::for_each( std::begin( a ), std::end( a ), decomposition );

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 ),
std::not1( std::bind1st( std::modulus<unsigned long long>(),
lowest_commom_multiple ) ) )
);

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;
}


Результатом ее работы будет следующий вывод на экран консоли:

 
18 7 10 20 1 4 19 16 14 14 2 17 17 12 2 2 10 13 9 8
21162960 = 2^4 * 3^2 * 5^1 * 7^1 * 13^1 * 17^1 * 19^1


Если у вас есть собственные оригинальные решения этой задачи, то можете разместить их в этой теме.


Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 2 [только новые]





ссылка на сообщение  Отправлено: 02.07.14 20:37. Заголовок: Приведенный выше код..


Приведенный выше код нахождения наименьшего общего кратного содержит не бросающийся в глаза баг. Этот баг присутствует в отладочном предложении с 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 }



Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 04.07.14 17:29. Заголовок: Другой подход к реше..


Другой подход к решению задачи нахождения наименьшего общего кратного основывается на утверждении, что произведение двух целых положительных чисел равно произведению наибольшего общего делителя на наименьшее общее кратное. То есть для двух положительных целых чисел a и b имеет место равенство

 
a * b = НОД( a, b ) * НОК( a, b )


Исходя из этой формулы, можно воспользоваться стандартным алгоритмом std::accumulate для нахождения наименьшего общего кратного, не прибегая при этом к услугам стандартного контейнера std::map.

Вот как будет выглядеть запись вызова этого алгоритма для вывода на экран консоли наименьшего общего кратного для целочисленного массива a

 
std::cout << std::accumulate( std::begin( a ), std::end( a ), 0ull,
[]( unsigned long long acc, int x ) -> unsigned long long
{
unsigned long long y = abs( x );
if ( acc == 0 ) return y;
if ( y == 0 ) return acc;
unsigned long long product = acc * y;
while ( y )
{
unsigned long long tmp = acc % y;
acc = y;
y = tmp;
}

return ( product / acc );
} ) << std::endl;


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


Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 31
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет