Python-сообщество

chigiwar86 · Фев. 11, 2016 22:23:41

Мой код не проходит один из тестов, уже несколько часов пытаюсь понять, почему.

Задача:
В комьютерной науке и дискретной математике, инверсия - это пара позиций последовательности, где элементы на этих позициях выпадают из естественного порядка. Таким образом, если мы используем порядок по возрастанию для группы чисел, то инверсия получается, когда более крупные цифры стоят перед меньшим значением в последовательности.

Проверим такой пример последовательности: (1, 2, 5, 3, 4, 7, 6) и мы можем видеть здесь три инверсии
- 5 и 3; - 5 и 4; - 7 и 6.

Вам дана последовательность уникальных чисел и вы должны подсчитать число инверсий в этой последовательности.

Входные данные: Последовательность как кортеж целых чисел.

Выходные данные: Количество инверсий.

Примеры:

count_inversion((1, 2, 5, 3, 4, 7, 6)) == 3
count_inversion((0, 1, 2, 3)) == 0

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

Предусловия:

2 < len(sequence) < 200
len(sequence) == len(set(sequence))
all(-100 < x < 100 for x in sequence)

Мое решение:

def count_inversion(sequence):
    i=0
    rep = 0
    while i<len(sequence):
        n = i + 1
        try:
            if sequence[i] > sequence[n]:                
                while sequence[i]>sequence[n]:
                    rep += 1
                    n += 1
                    
                    if n>=len(sequence):
                        break
                        
        except:
            pass
        i += 1
	return rep

Неправильно решение при

sequence =(5,12,-85,-92,-32,-8,1,-34,-55,-74,-44,-63,84,8,65,54,71,90,-81,98,-17,82,-45,-72,37,26,91,97,64,-62,-24,-70,42,56,-67,0,-78,-87,-57,-56,67,-2,11,-16,7,13,-1,-46,-54,16,-4,-14,63,-15,-48,-66,36,46,75,85,-79,-83,-52,73,49,-3,88,-10,60,-21,-75,38,44,2,-89,-65,-96,-22,-76,-31,-58,55,58,14,-47,20,80,-60,93,62,-71,24,45,-64,94,29,-94,-36,57,-23,6,51,15,-5,-53,25,-41,-97,89,-59,66,87,-19,-38,-27,-86,-9,40,18,-93,30,-20,81,34,3,92,77,-25,-49,74,-51,17,41)

Функция возвращает 515, а должна 4181

Куда копать?

P.S Python3

Отредактировано chigiwar86 (Фев. 11, 2016 22:24:24)

py.user.next · Фев. 12, 2016 01:48:02

chigiwar86
Мое решение:

Должно быть
1 1 1 1 1 0 => 5
1 1 1 1 0 0 => 8
1 1 1 0 1 0 => 7

chigiwar86 · Фев. 12, 2016 02:02:46

py.user.next
Должно быть
1 1 1 1 1 0 => 5
1 1 1 1 0 0 => 8
1 1 1 0 1 0 => 7

Что?

Отредактировано chigiwar86 (Фев. 12, 2016 02:03:20)

py.user.next · Фев. 12, 2016 02:49:48

Вот твоё решение

>>> def count_inversion(sequence):
...     i=0
...     rep = 0
...     while i<len(sequence):
...         n = i + 1
...         try:
...             if sequence[i] > sequence[n]:
...                 while sequence[i]>sequence[n]:
...                     rep += 1
...                     n += 1
...                     if n>=len(sequence):
...                         break
...         except:
...             pass
...         i += 1
...         return rep
... 
>>> count_inversion([1, 1, 1, 1, 1, 0])
0
>>>

должно возвращать 5.

Отредактировано py.user.next (Фев. 12, 2016 02:50:27)

shaptmos · Фев. 12, 2016 16:15:15

Куда копать?

в сторону правильного алгоритама

Проверим такой пример последовательности: (1, 2, 5, 3, 4, 7, 6) и мы можем видеть здесь три инверсии
- 5 и 3; - 5 и 4; - 7 и 6.

в примере же показано, что инверсия не только для двух соседних значений бывает. допустим, если следовать твоему алгоритму при i == 3 пропускается инверсия 5 и 3.

chigiwar86 · Фев. 12, 2016 16:22:41

спасибо, уже разобрался

Отредактировано chigiwar86 (Фев. 12, 2016 16:22:50)

Python-сообщество

Уведомления

#1 Фев. 11, 2016 22:23:41

Задача с chekio на инверсию

#2 Фев. 12, 2016 01:48:02

Задача с chekio на инверсию

#3 Фев. 12, 2016 02:02:46

Задача с chekio на инверсию

#4 Фев. 12, 2016 02:49:48

Задача с chekio на инверсию

#5 Фев. 12, 2016 16:15:15

Задача с chekio на инверсию

#6 Фев. 12, 2016 16:22:41

Задача с chekio на инверсию

Board footer