Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/16: Рейтинг темы: голосов - 16, средняя оценка - 4.56
Agent_147
2 / 2 / 1
Регистрация: 10.04.2011
Сообщений: 35
#1

Найти количество инверсий в заданной перестановке

09.06.2011, 12:06. Просмотров 2977. Ответов 2
Метки нет (Все метки)

Дан целочисленный массив А размера N, являющийся перестановкой. Найти количество инверсий в данной перестановке, то есть таких пар элементов Ai и Aj , в которых большее число находится слева от меньшего: А] > А] при I < J.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2011, 12:06
Ответы с готовыми решениями:

Количество инверсий в массиве
Добрый день. Необходимо написать программу, которая выведет количество инверсий...

Определить количество инверсий в массиве
Определить количество инверсий в этом массиве X (т.е. таких пар элементов, в...

Определить количество инверсий в данной последовательности
Дана последовательность длинной до 20 целых чисел.Определить количество...

Определить количество инверсий в массиве (таких пар элементов, в которых большие числа находится слева)
определить количество инверсий в массиве х (т. е таких пар элементов, в которых...

В заданной строке найти количество подстрок, состоящих из цифр
в заданной строке найти количество подстрок состоящих из цифр

2
chessman1
165 / 94 / 23
Регистрация: 13.03.2011
Сообщений: 402
14.06.2011, 17:33 #2
Лучший ответ Сообщение было отмечено Agent_147 как решение

Решение

Цитата Сообщение от Agent_147 Посмотреть сообщение
Дан целочисленный массив А размера N, являющийся перестановкой. Найти количество инверсий в данной перестановке, то есть таких пар элементов Ai и Aj , в которых большее число находится слева от меньшего: А] > А] при I < J.
C#
1
2
3
4
5
6
int count = 0;
for(int i=0; i < N; i++) 
    if(A[i] > (A[i+1]) {
        Console.Write( i + " ");
        count = count + 1;
Console.Write(count);
0
raiyin
0 / 0 / 1
Регистрация: 20.03.2012
Сообщений: 1
23.03.2012, 22:55 #3
C#
1
2
3
4
5
6
7
8
9
10
11
long count = 0;
for (int i = 0; i < myArray.Count - 1; i++)
{
     for (int j = i + 1; j < myArray.Count; j++)
     {
          if (myArray[i] > myArray[j])
          {
                count++;
          }
     }
}
Данный алгоритм не оптимален. Имеет сложность O(n2), где n-длина массива. Из плюсов - простота реализации. Оптимальный алгоритм использует стратегию разделяй и властвуй и имеет сложность O(n*ln(n)).
Курс стэнфордского университета по алгоритмам https://www.coursera.org/algo/
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2012, 22:55

В заданной строке найти количество строк состоящих из цифр
в заданной строке найти количество строк состоящих из цифр

Найти количество строк, среднее арифметическое элементов которых меньше заданной величины
Здравствуйте, уважаемые форумчане. Возникла проблема при написании метода,...

Найти количество строк, среднее арифметическое элементов которых меньше заданной величины
Коэффициенты системы линейных уравнений заданы в виде прямоугольной матрицы. С...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru