Оптимизация (поиск количества всех способов разложения числа на нечетные слагаемые)

@CasualNoob · Регистрация: 09.10.2016

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

Приветствую. Задание звучит следующим образом.

Кликните здесь для просмотра всего текста

Задано целое положительное число n. Требуется найти число способов представить его в виде суммы нечетных слагаемых. При этом разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми.
Например, число 6 можно представить следующими способами: 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 3, 3 + 3, 1 + 5.
То есть при n = 6 программа должна выдать 4.
Ограничение для числа n: 1 ≤ n ≤ 1000.

Реализовал я это как-то так.

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
var
   n      : longint;
   res    : longint;
 
procedure proc(n, min : longint);
var
   k, j   : longint;
 
begin
 
     k := min + 2;
 
     while k <= n do
     begin
 
          j := n;
          while(j >= k) do
          begin
               j := j - k;
               proc(j, k);
               res := res + 1;
          end;
 
          k := k + 2;
 
     end;
 
end;
 
begin
 
     read(n);
 
     res := 1;
     proc(n, 1);
     writeln(res);
 
end.

Небольшие пояснения по поводу этого.

Кликните здесь для просмотра всего текста

Чтобы было более понятно, приведу в качестве примера вариант с входным числом n = 8.
Возьмем в качестве первого варианта разложения 1+1+1+1+1+1+1+1 (res изначально равна 1, поэтому он не учитывается в самом алгоритме).
1) Далее начнем добавлять тройки вместо единиц: 1+1+1+1+1+3.
2) Сразу же после замены рекурсивно все повторяем с оставшимися единицами с учетом того, чтобы они были заменены на сумму чисел, не меньших и не равных 3, чтобы впоследствии не было повторов, то есть получаем следующий вариант разложения: 5+3. Так как единиц больше нет, возвращаемся к первому вхождению в процедуру.
3) Продолжаем добавлять тройки вместо единиц: 1+1+3+3. Троек больше вставить нельзя, поэтому переходим к пятеркам и повторяем все то же самое: 1+1+1+5. А потом к 7: 1+7.
Итого получается шесть вариантов.

Система проверки на 15 примерах из 50 выдает превышение по ограничению по времени, остальные тесты проходят нормально. Конкретные примеры и ограничения по времени неизвестны.

Помогите, пожалуйста, оптимизировать алгоритм, если здесь это можно сделать. Я, если честно, не вижу, где здесь есть какая-то избыточность или что-то в этом роде.

@Ромаха · 12.12.2016, 02:07

Сообщение от CasualNoob

Я, если честно, не вижу, где здесь есть какая-то избыточность или что-то в этом роде.

Вот она.

Code
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
43
44
var
   n      : longint;
   res    : longint;
   a      : array [1..1000, 1..1000] of integer;
procedure proc(n, min : longint);
var
   k, j   : longint;
 
begin
     Inc(a[n, min]);
     k := min + 2;
 
     while k <= n do
     begin
 
          j := n;
          while(j >= k) do
          begin
               j := j - k;
               proc(j, k);
               res := res + 1;
          end;
 
          k := k + 2;
 
     end;
 
end;
 
var i, j : Integer;
 
begin
 
     read(n);
 
     res := 1;
     proc(n, 1);
     writeln(res);
     for i := 1 to n do begin
        for j := 1 to n do Write(a[i, j], ' ');
        writeln
     end
 
end.

Добавлено через 5 часов 22 минуты
Ээ. Надеюсь, что все понятно, но все-таки - то что тебе нужно называется ленивая динамика. Нужно просто хранить ответы для предыдуших proc(n, min) и если такая процедура уже вызывалась - просто возьмем ответ, что уже был насчитан. Воот. Удачи

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта 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. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .