Разложение числа на слагаемые - C (СИ) (77359)

Узнай цену своей работы

Формулировка задачи:

Не могу найти найти не рекурсивный алгоритм разложения числа на заданное кол-во слагаемых. Может у кого есть реализованный?
алгоритм есть, но вот с паскалем трудности возникают((
  procedure Next;
      begin
    {найти i: (i<L) and ( (X[i-1]>X[i]) or (i=1) )}
    X[i]:=X[i]+1;
    { L:= i + X[i+1]+...+X[L] - 1 }
    X[i+1]:=...:=X[L]:=1
      end;
Через L мы обозначили количество слагаемых в текущем    разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:
 
  program Razbieniya;
    type Razb=array [byte] of byte;
    var N,i,L:byte;
    X:Razb;
    procedure Next(var X:Razb;var L:byte);
      var i,j:byte;
      s:word;
    begin
      i:=L-1;s:=X[L];
      {поиск i}
      while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;
      inc(X[i]);
      L:=i+s-1;
      for j:=i+1 to L do X[j]:=1
    end;
  begin
    write('N=');readln(N);
    L:=N; for i:=1 to L do X[i]:=1;
    for i:=1 to L do write(X[i]);writeln;
    repeat
      Next(X,L);
      for i:=1 to L do write(X[i]);writeln
    until L=1
  end.

Решение задачи: «Разложение числа на слагаемые»

textual
Листинг программы
    static const int CacheN = 400;
    static const int CacheK = 50;
    static unsigned __int64 pCache[CacheN][CacheK];
 
unsigned __int64 PStep(int n, int k) {
    unsigned __int64 s;
    if (n<CacheN && k<CacheK) {
        s = pCache[n][k];
        if (s) return s;
    }
    int r = n - k;
    if ( k<r ) {
        s = 0;
        for (int m=1; m<=k; m++) s += PStep(r, m);
    } else {
        s = 1;
        for (int m=1; m<r; m++) s += PStep(r, m);
    }
    if (n<CacheN && k<CacheK) pCache[n][k] = s;
    return s;
}
 
unsigned __int64 P(int n, int k) {
    if ( n<0 || k<0 || n<k ) return 0;
    if ( n==k ) return 1;
    if ( k==0 ) return 0;
    unsigned __int64 res = PStep(n, k);
    return res;
}
 
int main() {
    unsigned __int64 s;
    int n, k;
    do {
        std::cin >> n >> k;
        s = P(n, k);
        std::cout << s << std::endl;
    } while (s);
    return 0;
}

Объяснение кода листинга программы

  1. В этом коде реализуется функция PStep, которая вычисляет некоторые значения, используя итеративный подход. Эта функция использует массив pCache, чтобы сохранить уже вычисленные значения. Если значение уже есть в массиве, оно возвращается, в противном случае оно вычисляется.
  2. Функция P использует функцию PStep для вычисления значений и возвращает результат.
  3. В функции main создается цикл, который считывает числа n и k с консоли и вызывает функцию P, чтобы вычислить значение s. Затем значение s выводится на консоль. Цикл продолжается до тех пор, пока s не станет равным нулю.
  4. В этом коде используется тип данных unsigned __int64, который представляет собой 64-битное беззнаковое целое число.
  5. Константы CacheN и CacheK определяют размер массива pCache.
  6. Массив pCache объявлен как статический член класса, поэтому его размер не может быть изменен во время выполнения программы.
  7. Код не содержит обработки ошибок или проверки на входные данные, которые могут привести к переполнению или другим проблемам.
  8. В этом коде не используются библиотеки или сторонние функции, все вычисления выполняются внутри функции main.
  9. Код не компилируется без предоставления определения функции PStep, которое должно быть добавлено в файл заголовочного кода.
  10. В этом коде не используются переменные, которые могут быть объявлены в других блоках кода, что означает, что любые переменные, объявленные внутри функций, будут уничтожены, когда они выйдут из области видимости.
  11. Функция main возвращает значение 0, чтобы указать, что программа успешно завершилась.
  12. Этот код не использует многопоточность или асинхронное программирование.
  13. В этом коде не используются константы или макросы, которые могут быть определены в других файлах или заголовочных файлах.
  14. В этом коде не используются функции ввода-вывода, такие как cin и cout, которые могут быть определены в других файлах или заголовочных файлах.
  15. В этом коде не используются функции, которые могут быть определены в других файлах или заголовочных файлах.
  16. В этом коде не используются структуры данных или классы, которые могут быть определены в других файлах или заголовочных файлах.
  17. В этом коде не используются указатели или ссылки, которые могут быть определены в других файлах или заголовочных файлах.
  18. В этом коде не используются переменные, которые могут быть определены в других файлах или заголовочных файлах.
  19. В этом коде не используются функции, которые могут быть определены в других файлах или заголовочных файлах.
  20. В этом коде не используются функции, которые могут быть определены в других файлах или заголовочных файлах.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.357 из 5
Похожие ответы