Плиииизззз... с помощью рекурсии Дано натуральное число N. Требуется получить и вывести...

Question

Плиииизззз... с помощью рекурсии Дано натуральное число N. Требуется получить и вывести на экран все возможные различные способы представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсив-ной процедуры.
Пример:
Введите натуральное число:
4
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2

Comments

сложная

---

если понимаешь рекурсию, то нет

---

а вообще эта задача на олимпиаде встречалась

---

сейчас увидишь, как все просто)

---

рекурсия сама по себе штука не простая

Answer 1

//PascalABC.NET 3.1 сборка 1200
procedure Decomposition(depth, previous, rest: integer; a: string);
begin
  if rest < 0 then
    exit;
 
  if (rest = 0) and a.Contains('+') then begin
    Println(a);
    exit;
  end;
 
  for var i := previous to rest do
    Decomposition(depth + 1, i, rest - i,
      (a = '') ? i.ToString() : a + ' + ' + i.ToString());
end;

begin
  Decomposition(1, 1, ReadInteger('n ='), '');
end.

Comments

спасибо, попробую

---

на то она и школа чтоб учили и помогали

---

тогда прям на уроке говоришь что нужна была одна функция, ее не учили, полез в гуголь искать и нашел, может она не правильная, подскажите как надо

---

в школе

---

и где это не прокатит?

---

ну

---

какую команду вы знаете чтоб преобразовывала число в строку?

---

поэтому она не прокатит

---

какую команду вы знаете чтоб преобразовывала число в строку?

---

нечта

Answer 2

Var
  n: integer;
  a: array[1..100] of integer;
procedure gen(pos, prev, sum: integer);
var i: integer;
begin
  if sum > 0 then
  for i := prev to sum do
  begin
    a[pos] := i;
    gen(pos + 1, i, sum - i);
  end
  else if a[1] < n then
  begin
    write(a[1]);
    for i := 2 to pos - 1 do write(' + ', a[i]);
    writeln;
  end;
end;
begin
  read(n);
  gen(1, 1, n);
end.

Comments

Можно и без массива, но это намного сложнее, да и вообще будет работать дольше

---

мне вот и надо без массива, это обязательное условие

---

program ex1;
var n,t: integer;
procedure A(p, v, s: integer);
var i: integer;
begin
if s > 0 then
for i := v to s do
begin
t := i;
A(p + 1, i, s - t);
end
else if t < n then
begin
write(t);
for i := 2 to p - 1 do
write(' + ', t);
writeln;
end;
end;
begin
read(n);
A(1, 1, n);
end.

---

что изменить, чтобы считала правильно

---

Надо, чтобы без массива была

---

я не говорю, что это плохо)

---

много условий это фильтры и удобочитаемость, так что не надо говорить что это плохо

---

procedure gen(depth, previous, number: integer; a: string);
begin
if number < 0 then
exit;

if (number = 0) and a.Contains('+') then begin
Println(a);
exit;
end;

for var i := previous to number do
gen(depth + 1, i, number - i,
(a = '') ? i.ToString() : a + ' + ' + i.ToString());
end;

begin
var n := ReadInteger;
gen(1, 1, n, '');
end.

---

или даже так var a := true ? 1 : 0;

---

тернарник есть: writeln(true ? 1 : 0)