прикреплённый файл:2012-11-23.slagaemye.py к странице LecturesVMSH/Python/2012-11-23

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Напечатать на экране все различные представления числа n в виде суммы натуральных чисел. Перестановка слагаемых нового способа не дает 
   5 '''
   6 
   7 def razlR(N, Seq=[]):
   8     '''Рекурсивная функция.
   9     N — число, Seq — накопленные слагаемые'''
  10     if N:                               # Можно добавить ещё слагаемых
  11         # Чтобы не получилось перестановок, соблюдаем упорядоченность слагаемых
  12         Min=len(Seq) and Seq[-1] or 1   # Минимально допустимое значение слагаемого
  13         for i in xrange(Min,N+1):
  14             razl(N-i,Seq+[i])
  15     else:
  16         if len(Seq)>1: print Seq
  17 
  18 def razlN(N):
  19     '''Нерекурсивная функция с сохранением состояния'''
  20     N, Seq, = N-1, [1]
  21     State = [(N,Seq[:])]                # Состояние
  22     while State:
  23         if Seq[-1]<=N:
  24             State.append((N,Seq[:]))    # Запомним состояние
  25             Seq.append(Seq[-1])
  26             N-=Seq[-1]
  27             continue
  28         else:
  29             if not N:                   # Сумма готова
  30                 if len(Seq)>1:          # Слагаемых больше одного
  31                     print Seq
  32                 N, Seq = State.pop()    # Вспомним предыдущее состояние
  33             Seq[-1]+=1
  34             N-=1
  35 
  36 
  37 def razlNE(n):
  38     '''Нерекурсивная функция с вычислением состояния'''
  39     N, Seq, = n-1, [1]
  40     while Seq[0]<n:
  41         if Seq[-1]<=N:
  42             Seq.append(Seq[-1])
  43             N-=Seq[-1]
  44             continue
  45         else:
  46             if not N:                   # Сумма готова
  47                 if len(Seq)>1:          # Слагаемых больше одного
  48                     print Seq
  49                 N += Seq.pop()          # Вспомним прошлое состояние
  50             Seq[-1]+=1
  51             N-=1
  52 
  53 
  54 n=input("Введите число: ")
  55 
  56 razlNE(n)