Programozás‎ > ‎Feladatok‎ > ‎Partíció probléma‎ > ‎

Megoldás

Algoritmus

Levonunk egy lehetséges első tagot az összegből, majd a megmaradó részre rekurzív meghívjuk az eljárást. Az összeg tagjait a globális tag tömbben tároljuk, figyelve arra, hogy a tagok monoton növekvő sorozatot alkossanak. (Ezzel garantáljuk, hogy minden megoldást egyszer kapunk meg.) Kezdetben tag[0]=1.

Pszeudokód



Particio(n, szint)
  Ha n = 0 akkor
    Ki: tag[1], tag[2], ..., tag[szint]
  Különben
    Ciklus i := tag[szint]-től n-ig
      tag[szint + 1] := i
      Particio(n - i, szint + 1)
     Ciklus vége
  Elágazás vége
Eljárás vége

Megoldások

Comments