Дефиниција
За Н низ не-негативних целих бројева [1 .. н], ако ја <ј, и [и]> [ј], назвао ([и] [ј]) низ у обрнутом пару.
На пример, низ (3,1,4,5,2) на наличју постоји (3,1), (3,2), (4,2), (5,2), укупно четири.
Број решавање проблема на реверсу
Опис проблема
С обзиром на низ, наћи низ садржи број обрнутог права.
Методе решавањаМетод Један: најпримитивнији начин, користећи двоструку петље пописивање. Време Сложеност алгоритма је О (н ^ 2).
Ц код је следећи:
цоунт_инверсион инт (инт *, инт н)
{
инт бројац = 0;
инт и, ј;
фор (и = 0; и <н, и )
за (ј = и 1; ј <н ј )
ако је (а [и]> [ј])
цоунт ;
повратак рачунати;
}
Пасцал код је како следи:
вар И, Ј, К, Н: лонгинт;
: арраи [1. .. 1000000] од лонгинт;
почети
реадлн (н);
фор и: = 1 до н читам ([и]);
К: = 0;
фор и: = 1 до н-1 до
за ј: = и 1 до н уради
ако [и]> [Ј] онда инц (К);
врителн (К);
|