Termlərə Parçalanma#2390

Termlərə Parçalanma (Həll təhlili)

Qoy $n = x_{1} + x_{2} + ... + x_{k}$ n = x_1 + x_2 + ... + x_k — $n$ sayını natural toplananlar şəklində təsviri olsun. Məsələ şərtindən götürsək, təsvirin hər hansı bir yığıcıları bu bərabərsizliyə uyğun olmalıdır:

x_{1} \geq x_{2} \geq ... \geq x_{k}

x_1 \ge x_2 \ge ... \ge x_k

Birinci yığıcı $x_{1}$ x_1 1-dən $n$ -ə qədər olan qiymətləri ala bilər, və hər bir növbəti $x_{i} (2 \leq i \leq k)$ x_i~(2 \le i \le k) — $x_{i - 1}$ x_{i-1}-dən böyük olmayan qiymətlər ala bilər.

Təsvirlərin yaradılma prosedurlarının rekursiv mahiyyəti belədir: əgər $n$ sayının təsvirində birinci yığıcı olaraq $x_{1} (x_{1} \leq n)$ x_1~(x_1 \le n) seçilibsə, onda növbəti yığıcı $n - x_{1}$ n - x_1 sayının yaradılmasıdır ki, bu da $x_{1}$ x_1-dən böyük olmayan yığıcıları ehtiva edir.

Alqoritmin tətbiqi

Arraydə $x$ , $n$ sayını əks etdirən yığıcıları yaradacağıq.

int x[50];

f funksiyası $n$ sayını təsvir edən yığıcıları generasiya edir və üç arqument alır:

$p os$ — $x$ arrayindəki cari mövqe;
$ma x$ — maksimum icazəli yığıcı dəyəri ki, bu da $p os$ mövqeyində yerləşə bilər;
$n$ — parçalanması lazım olan cari sayı.

void f(int pos, int max, int n)
{

Əgər $n$ dəyəri sıfıra bərabər olarsa, bu, təsvirin tamamlandığı və cari $x$ arrayi növbəti təsviri təmsil etdiyi deməkdir. Bu halda arrayi çıxış olaraq veririk.

  if (n == 0)
  {
    for (int i = 0; i < pos; i++) 
      printf("%d ", x[i]);
    printf("\n");
    return;
  }

C++

$x$ arrayində $p os$ mövqeyində 1-dən $min (ma x, n)$ min(max, n)-ə qədər olan hər hansı bir ədəd yerləşə bilər.

  for (int i = 1; i <= min(max, n); i++)
  {
    x[pos] = i;
    f(pos + 1, i, n - i);
  }
}

Proqramın əsas hissəsi. Giriş olaraq $n$ dəyərini oxuyur və həmin sayın bütün mümkün təsvirlərini generasiya edən funksiyanı işə salırıq.

scanf("%d",&n);
f(0,n,n);