Разложение числа на слагаемые [рекурсия]

@BIOINFprf · Регистрация: 30.10.2016

Студворк — интернет-сервис помощи студентам

Привет!

Пишу программу разложения числа на слогаемые, но опять хочу попросить помощи - не проходит два последних теста по лимиту времени. А у меня нет даже идеи, что можно исправить.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
program rekursivnoje_razlozenije;
 
uses sysutils, crt;
 
var
  n: integer;
  c: array[1..100] of integer;
  print: boolean;
 
const
diapazon:set of byte=[1..40];
 
procedure find(num,k,len: integer);
const sign: array[boolean] of char = ('+', ' ');
var
  i: integer;
begin
  if num=0 then begin
    print := true;
    for i := 1 to pred(len) do
      if not (c[i] in diapazon) then print := false;
 
    if print then begin
    for i:=len-1 downto 1 do write(c[i], sign[i = 1]);
    writeln;
    end;
  end
  else begin
    for i:=1 to k do
      if num-i>=0 then begin
        c[len]:=i;
        find(num-i,i,len+1);
      end;
  end;
end;
begin
clrscr;
  read(n);
  if (n <= 40) then 
  find(n,n,1)
  else 
end.

Добавлено через 1 минуту
Заранее спасибо за помощь.

@IlushaMax · 14.12.2016, 20:53

По условию дано, что максимальное n=40 я правильно понял?

@BIOINFprf · 14.12.2016, 22:54 **[ТС]**

Да, именно так.
По условию дается число от 1 до 40 с последующим его разложением.
Программа работает правильно. Проходит большую часть тестов, а по другим тестам превышены лимиты времени. Совсем не знаю, что нужно изменить (или, может, совсем все переделывать?) или добавить.

@IlushaMax · 15.12.2016, 18:13

Я не сильно углублялся в твой код, но могу предложить свое решение.
Этот код вычисляет сколько способов разложения. Изменить его не сложно, добавив вывод с плюсами(вроде можно сделать без массивов, а сразу выводить слагаемое, которое вычислили)

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var k:longword;
procedure rec(n,pred:byte);
var i:byte;
begin
  inc(k);
  for i:=pred+1 to (((N div 2)-1)+N mod 2) do
  begin
    rec(n-i,i);
  end;
end;
var n:byte;
begin
  k:=0;
  readln(n);
  rec(n,0);
  writeln(k);
end.

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@IlushaMax 0 / 0 / 4 Регистрация: 09.04.2016 Сообщений: 128
	14.12.2016, 20:53
	По условию дано, что максимальное n=40 я правильно понял? 0

@BIOINFprf 1 / 1 / 1 Регистрация: 30.10.2016 Сообщений: 35
	14.12.2016, 22:54 [ТС]
	Да, именно так. По условию дается число от 1 до 40 с последующим его разложением. Программа работает правильно. Проходит большую часть тестов, а по другим тестам превышены лимиты времени. Совсем не знаю, что нужно изменить (или, может, совсем все переделывать?) или добавить. 0