У меня есть вопрос. Я пишу этот компаратор:Порядок сортировки на основе наибольшего общего деления
bool cmp(int a, int b)
{
return __gcd(a, b) > 1;
}
и, например:
, если у меня есть эти цифры:
2 5 6 7 8 12 15 19 20
мой код выводит:
20 15 12 8 6 2 5 7 19
это нормально ..
но, например:
1 2 3 4 5 6 7 8 9
мой код выхода
1 2 3 4 5 6 7 8 9
Как я могу это сделать?
эта последовательность должна быть что-то вроде этого:
9 6 3 (...)
Ваш компаратор не устанавливает strict weak ordering, поэтому результаты не определены.
Для правильного компаратора вы должны убедиться, что верно следующее:
cmp(a, a) == false - ваш компаратор не проходит тест на cmp(2, 2)
cmp(a, b) == true → cmp(b, a) == false - ваш компаратор не проходит тест на cmp(2, 4)
cmp(a, b) == true and cmp(b, c) == true → cmp(a, c) == true - ваш компаратор не сдал тест на cmp(2, 6) and cmp(6, 3)
Вы можете мне помочь? – JanKo
@JanKo Вам нужно снова подумать о своих критериях сортировки. Почему сортировка начинается с '9, 6, 3'? Почему бы не '8, 4, 2'? Почему бы не '3, 6, 9',' 6, 3, 9' или другие 3 комбинации? В каком порядке следует поместить номера '2, 4' после сортировки? Зачем? Вы увидите, что иметь общий делитель недостаточно, чтобы установить однозначный порядок, и вы будете вынуждены дать дополнительные критерии. –
истина безразлична, созданная последовательность, важно построить на gcd – JanKo
Предположительно вы используете 'std :: so rt'? Это не сработает. 'std :: sort' требует [* строгий слабый порядок *) (https://www.sgi.com/tech/stl/StrictWeakOrdering.html), что в основном означает, что он должен сортироваться как обычные числа. Например. '3 <4', поэтому'! (4 <3) '. Но 'gcd' является * коммутативным *' gcd (a, b) == gcd (b, a) '- он работает одинаково в любом случае, поэтому по этой причине (и другим) ваш' cmp' не может сделать смысл сортировки. Как бы то ни было, я не уверен, какого порядка вы пытаетесь достичь в любом случае. – BoBTFish
Итак, как я могу сортировать? – JanKo
Если честно, я не уверен, какого порядка вы пытаетесь достичь. Я не вижу, что имеет смысл, чтобы один элемент был «больше», чем другой, если у них нетривиальный gcd, когда оба будут «больше» друг друга. Это не ошибка программирования, это ошибка в математике. Подумайте о том, чего вы действительно хотите. Это действительно имеет смысл? – BoBTFish