1_5.hs

{--
Задача 1-5*	
Одеров Роман, 545 гр.
--}


{- Раскладываем в порядке убывания первого слагаемого.

	f(s, e, n, c) - вспомогательная функция
	s - с какого слагаемого хотим начать раскладывать
	e - максимальное слагаемое, которое может быть первым в разложении n. 
		(Этот параметр, в принципе, лишний, т.к. может быть вычислен из n по ходу выполнения)
	n - "начальное число", раскладываемое на слагаемые
	c - счетчик количества разложений
-}

nseq n = f 1 (div (n-1) 2) n 1	{-- s = 1,
									e = (n-1)/2), т.к. очевидно, что первое слагаемое может быть равно максимум (n-1)/2,
												чтобы удовлетворять свойству возрастания последовательности разложения
									n = n,
									c = 1, учитываем сразу тривиальное разложение.
								--}
								
f s e n c = if s>e 	-- если первое слагаемое больше половины числа, то это разложение уже не будет возрастающим, 
					-- следовательно, не считается (+0)
			then c+0
			else
				
				if s<e
				then f (s+1) e n (c + f (s+1) (div (n-s-1) 2) (n-s) 1) 
													{-если все ОК с первым слагаемым, то идем дальше и раскладываем 
													остаток от исходного числа (n-start), начиная со след.слагаемого (start+1), 
													и считаем, сколькими способами получится сделать это.
													В итоге, прибавим к имеющимся разложениям.-}
				
				else c+1 -- если s==e, то, очевидно, +1 к количеству разложений, 
						 -- т.к. дошли до макс. допустимого первого слагаемого больше из текущего n мы выжаить не сможем