[C] Kombinacje

[Akiva]

Witam.
Mam do zrobienia projekt: "Kombinacje. Należy napisać program który dla dowolnej liczby naturalnej n wypisuje wszystkie możliwe kombinacje (kolejność nie gra roli) takich liczb naturalnych, których suma daje liczbę oraz ilość tych kombinacji. np. n=3, 2+1, 1+1+1. " Zrobiłam trochę,ale chyba utknęłam w martwym punkcie i nie wiem co dalej.

Kod: Zaznacz cały

#include <stdio.h>
#include <conio.h>

void wyswietl(int * tablica, int ilosc, int kolejna_kombinacja)
{
printf("
%d - ", kolejna_kombinacja);
for (int i = 1; i <= ilosc; i++)
{
  printf("%d,", tablica[i - 1]);
}
}

int main()
{
int biezaca_kolumna, kolumna,liczba, poziom, i,j,k,suma,ilosc_elementow;
bool taka_sama, wszystkie_poziomy=0;
printf("Podaj liczbe calkowita: ");
scanf_s("%d", &liczba);
int * tablica, *tablica_temp;
tablica = new int[liczba];
tablica_temp = new int[liczba];
int ilosc_kombinacji = 0;
for (i = 1; i <= liczba; i++)
{
  tablica[i - 1] = 1;
}
ilosc_kombinacji++;
wyswietl(tablica, liczba, ilosc_kombinacji);
if (liczba <= 0)
{
  printf("Liczba musi byc wieksza od zera");
}
else
{
  biezaca_kolumna = 1;
  while (wszystkie_poziomy)
  {

  }
  /*	for (poziom = 2; poziom <= liczba; poziom++)
  {
  for (kolumna = 1; kolumna <= liczba; kolumna++)
  {
    if (kolumna == 1)
    {
    tablica[kolumna - 1] = poziom;
    }
    else
    {
    for (j = 1;j <= poziom;j++)
    {
      taka_sama = true;

      tablica[kolumna - 1] = j;
      for (k = 1;k <= liczba;k++)
      {
      if (tablica[k - 1] != tablica_temp[k - 1])
      {
        taka_sama = false;
      }
      }
      if (taka_sama==false)
      {
      suma = 0;
      for (k = 1;k <= liczba;k++)
      {
        suma = suma + tablica[k - 1];
        if (suma == liczba)
        {
        ilosc_kombinacji++;
        wyswietl(tablica, k, ilosc_kombinacji);
        }
      }

      for (k = 1;k <= liczba;k++)
        tablica_temp[k - 1] = tablica[k - 1];
      }
    }
    }
  }
  for (kolumna = 2;kolumna <= liczba;kolumna++)
    tablica[kolumna - 1] = 1;
  }
  */
}
ilosc_kombinacji++;

_getch();
return 0;
}

[dvrx47]

Prosta rekurencja:
na stosie przechowywane są liczby do wypisania
stack_id określa górę stosu (miejsce do zapisywania)

Kod: Zaznacz cały

#include <stdio.h>

#define min(a,b) (((a)<(b))?(a):(b))
#define MAX_STACK_SIZE 1000

int STACK[MAX_STACK_SIZE];


void print_combinations(int max, int sum, int stack_id);
void print_stack(int stack_end);


int main(){
	int n;
	scanf("%d", &n);
	print_combinations(n, n, 0);
	return 0;
}


void print_combinations(int max, int sum, int stack_id){
	if (sum == 0) { 
		print_stack(stack_id);
		return;
	}

	for(int i = min(sum,max); i > 0; --i){
		STACK[stack_id] = i;
		print_combinations(i, sum-i, stack_id + 1);
	}
}

void print_stack(int stack_end){
	printf("%d ", STACK[0]);
	for (int i=1; i<stack_end; ++i)
		printf("+ %d ", STACK[i]);
	printf("
");
}