Здравствуйте. Пытаюсь вывести алгоритм для задачи разбиения натурального числа на максимальное кол-во различных слагаемых. Надо найти само k и вывести слагаемые. Сам перелопатил кучу литературы по комбинаторике, дошёл только до такого: n = 2+3+4+etc + (остаток до n, если число уже есть-убираем его из суммы и увеличиваем на единицу с конца число элементов=остатку.) Т.е. если n=22, то 22 = 2+3+4+5+6+2 = 2+3+4+6+7
Совершенный затык в том, как его реализовать. Пока делал что-то в таком духе:
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int[] s= new int[0];
int i=0;
int sum = 0;
if(sum<x){
sum+=i++;
s[i]+=s[i++];
System.out.println(s[i]);
}else{
s[i]+=s[i--];
System.out.println(s[i]);
}
}
Но это, очевидно, неверно. Посоветуйсте, пожалуйста, как можно реализовать именно добавление единиц?
n(n+1)/2
формулу используйте. Вам надо найти обратное. Думаю квадратное уравнение решить реально.{1,2,3,4...,k-1, S - k(k-1)/2}