Редактирование: Получение номера по объекту

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 66: Строка 66:
  
 
== Разбиение на слагаемые ==
 
== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.   
+
Рассмотрим алгоритм получения номера в лексикографическом порядке данного разбиение на слагаемые числа <tex>n</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически и будем строить его.   
  
 
*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
 
*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
Строка 74: Строка 74:
 
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.   
 
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.   
  
Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.  
+
Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> по убыванию <tex>j</tex>.  
  
Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>).  
+
Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex>, таких разбиений <tex>\mathtt{d[i - j][j]}</tex>, либо не содержать, таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>.  
  
 
Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:
 
Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:
Строка 87: Строка 87:
  
  
'''int''' part2num(part: '''list<int>'''):
+
  '''int''' part2num(part: '''list<int>'''):
  numOfPart = 0, last = 0, sum = 0
+
    numOfPart = 0
  '''for''' i = 1 '''to''' part.size
+
    '''for''' i = 1 '''to''' N  <font color=green>// <tex>N</tex> {{---}} число, которое было разбито на слагаемые </font>   
    '''for''' j = last '''to''' part[i] - 1           <font color=green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font>     
+
      '''for''' j = last '''to''' part[i] - 1 <font color=green>// перебираем все элементы, лексикографически меньше нашего, но больше или равны предыдущего</font>     
      numOfPart += d[N - sum - j][j]       <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
+
        numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
    sum += part[i]                         <font color=green>// увеличиваем уже поставленную сумму</font>
+
      sum += part[i] <font color=green>// увеличиваем уже поставленную сумму</font>
    last = part[i]                         <font color=green>// обновляем последний поставленный элемент </font>
+
      last = part[i] <font color=green>// обновляем последний поставленный элемент </font>
  '''return''' numOfPart                         <font color=green>// возвращаем ответ</font>
+
    '''return''' numOfPart <font color=green>// возвращаем ответ</font>
  
 
Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.
 
Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: