Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow

Wlasnie skonczylem ostatnie cwiczenie z kursu, kod dziala tak jak chcialem, tylko nie jestem na 100% przekonany czy dokladnie o to chodzilo w zadaniu, dlatego chcialem to z wami skonsultowac : ) Tresc zadania i moj kod zamieszcze kolejno pod spodem:

Napisz program, który rozpisuje daną liczbę na wszystkie możliwe kombinacje jej składników.

Przykład:

2 = 1+1
2 = 2

#include<stdio.h>

int main(void){
int a;
scanf("%i", &a);
printf("dodawanie do uzyskania podanej liczby\n");
int i;
for(i=0;i<=a;++i){
  int w = a-i;
  printf("%i = %i + %i\n", a, i, w);
 }
 printf("odejmowanie do uzyskania podanej liczby\n");
 for(i=a;i>=0;--i){
   int s = a+i;
   printf("%i = %i - %i\n", a, s , i);
 }
 float x =  a;
 printf("mnozenie do uzyskania podanej liczby\n");
 for(i=1;i<=x;++i){
   float c = x/i;
   printf("%i = %f * %i\n", a, c , i);
 }
 printf("dzielenie do uzyskania podanej liczby\n");
 for(i=1;i<=a;++i){
   float v = a*i;
   printf("%i = %f / %i\n", a, v, i);
 }
 return 0;
}

Taki byl zamysl zadania czy niebardzo ?

dodanie znacznika <code class="cpp"> - @furious programming

Ani trochę. Chodziło tylko o dodwanie, ale o rozpisanie go na więcej niż 2 składniki. Na przykład dla 3 masz już

1+1+1
1+2
3

A dla 4 masz

1+1+1+1
1+1+2
2+2
3+1
4

Aha, no okej to zrobie drugi program tak jak mowisz, dzieki : ) ...Chociaz ten koncept wyglada na troche trudniejszy, moze jakas wskazowka jak zaczac to w kodzie ? Bo nie widzi mi sie zaden pomysl na razie.

Integer partitions

Ale jak zapisac te integer partitions w kodzie, jak ich uzyc.

A może najpierw sprawdź co to jest?

@_user nie ogarniam cie trochę. Albo chcesz sie czegoś nauczyć albo nie. Jak ci napiszemy jak zrobić to zadanie to nie nauczysz się niczego...

_user napisał(a):

Aha, no okej to zrobie drugi program tak jak mowisz, dzieki : ) ...Chociaz ten koncept wyglada na troche trudniejszy, moze jakas wskazowka jak zaczac to w kodzie ? Bo nie widzi mi sie zaden pomysl na razie.

Spróbuj użyć rekurencji.

Bylbym wdzieczny jak ktos moglby podac przyklad w kodzie c jak to zrobic.

Tutaj masz algorytm:

1. wejdz na google
2. wpisz cos w rodzaju "partycje liczb"
3. chyba trzeci link: http://www.impossible-technologies.eu/down/tl.pdf

a tak btw to nie widze zadnego sensu w ograniczaniu sie do polskich materialow, zwlaszcza w kontekscie programowania

Wiem co to te partycje, ale nie mam pojecia jak to umiescic i wykorzystac w kodzie, o to chodzi, dlatego chcialbym przyklad kodu.

Po wpisaniu odpowiedniej frazy w google w pierwszych 5 wynikach jest 5 przykaldowych kodow zrodlowych... Napisanie jednego z Twoich postow zajelo ci duzo wiecej czasu niz po prostu odpalenie tego nieszczesnego googla ;)

Dzieki Fake za rade, co prawda bez google ale wyszukalem fajny kod:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int first;
  int n;
  int level;
} Call;

void print(int n, int * a) {
  int i ;
  for (i = 0; i <= n; i++) {
    printf("%d", a[i]);
  }
  printf("\n");
}

void integerPartition(int n, int * a){
  int first;
  int i;
  int top = 0;
  int level = 0;
  Call * stack = (Call * ) malloc (sizeof(Call) * 1000);
  stack[0].first = -1;
  stack[0].n = n;
  stack[0].level = level;

  while (top >= 0){
    first = stack[top].first;
    n = stack[top].n;
    level = stack[top].level;

    if (n >= 1) {
      if (first == - 1) {
	a[level] = n;
	print(level, a);
	first = (level == 0) ? 1 : a[level-1];
	i = first;
      } else {
	i = first;
	i++;
      }
      if (i <= n / 2) {
	a[level] = i;
	stack[top].first = i;
	top++;
	stack[top].first = -1;
	stack[top].n = n - i;
	stack[top].level = level + 1;
      } else {
	top--;
      }
    } else {
      top --;
    }
  }
}

int main(){
  int n;
  scanf("%i", &n);
  int * a = (int * ) malloc(sizeof(int) * n);
  printf("\nThe integer partition for %d is :\n", n);
  integerPartition (n, a);
  return(0);
}

I chyba tyle, teraz tylko przeanalizuje go sobie dobrze i ok :)

@Edit
Nie jednak nie wystarczy... nic z tego nie rozumiem nie wiem co teraz, zbyt rozpisany kod, przydalby sie prostszy ;/

jakby ktos mogl wytlumaczyc ten kod byloby spoko

Troche sie zastanowilem nad przykladem i nawet sporo zrozumialem, ale mam problem z tylko jedna linijka, prosilbym o jej wytlumaczenie, linijka ktorej nie rozumiem zakomentowana ponizej:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int first;
  int n;
  int level;
} Call;

void print(int n, int * a) {
  int i ;
  for (i = 0; i <= n; i++) {
    printf("%d", a[i]);
  }
  printf("\n");
}

void integerPartition(int n, int * a){
  int first;
  int i;
  int top = 0;
  int level = 0;
  Call * stack = (Call * ) malloc (sizeof(Call) * 1000);
  stack[0].first = -1;
  stack[0].n = n;
  stack[0].level = level;

  while (top >= 0){
    first = stack[top].first;
    n = stack[top].n;
    level = stack[top].level;

    if (n >= 1) {
      if (first == - 1) {
        a[level] = n;
        print(level, a);
        first = (level == 0) ? 1 : a[level-1];   /* Tutaj mam problem, bo przy pierwszym wejsciu tutaj level==0 i przypisuje first wartosc 1(jesli sie myle to poprawcie) ale gdy drugi raz tu przychodzi program to level juz nie jest 0 tylko 1 i w tym momencie przypisuje wartosc a[level-1] do first, tak ? tylko co to za wartosc, 0,1,9 czy 10 ? ile to jest te a[level-1]. */
        i = first;
      } else {
        i = first;
        i++;
      }
      if (i <= n / 2) {
        a[level] = i;
        stack[top].first = i;
        top++;
        stack[top].first = -1;
        stack[top].n = n - i;
        stack[top].level = level + 1;
      } else {
        top--;
      }
    } else {
      top --;
    }
  }
}

int main(){
  int n;
  scanf("%i", &n);
  int * a = (int * ) malloc(sizeof(int) * n);
  printf("\nThe integer partition for %d is :\n", n);
  integerPartition (n, a);
  return(0);
}

a[level-1] to poprzedni poziom zlokalizowany w kontenerze a, jak mniemam.

proponuję, abyś na początku utworzył tablice o rozmiarze podanej liczby i wypełnił ją jedynkami. Spróbuj tak zaprojektować pętle, aby program dodawał do siebie liczby w komórkach znajdujących się obok siebie. Zastanów się jaki można zastosować warunek, aby swobodnie przechodził do dalszych indeksów, nie dodając jedynie liczb znajdujących się w dwóch pierwszych komórkach. Przykład z siódemką:

7 = 1, 1, 1, 1, 1, 1, 1
7 = 2, 1, 1, 1, 1, 1
7 = 2, 2, 1, 1, 1
7 = 2, 2, 2, 1
7 = 2, 2, 3
7 = 4, 3
7 = 7

Jeżeli chcesz również rozpatrzeć takie przypadki jak:

7 = 4, 2, 1
7 = 5, 2

to może warto zastanowić się nad kombinacjami bez powtórzeń.

zamiana znaczników <quote> na <code class="cpp"> - @furious programming

dzieki czarny ale juz mam kod, i ponawiam pytanie: "first = (level == 0) ? 1 : a[level-1]" <- jaka wartosc bedzie przekazana do first przy drugim wywolaniu tego jesli np podana liczba do rozpisania bedzie 10 ?

nie uważasz, że używasz narzędzi, których nie rozumiesz? Nie lepiej zrobić coś prościej, jednak zrozumiale? Nie wątpię, że rozwiązanie użyte w umieszczonym przez ciebie kodzie są o wiele bardziej eleganckie, od zaproponowanego ode mnie, jednak ja go chociaż potrafię wdrożyć "do życia"

Nie uwazasz ze marnujesz moj czas na czytanie tego ?? Zadalem pytanie a teraz marnuje czas czytajac cos co mi sie nie przyda, no czlowieku szanujmy sie....

pytanie nadal akutalne, jest na poprzedniej stronie w 2 ostatnich moich postach

Ta linijka, czyli:

first = (level == 0) ? 1 : a[level-1];

Może być zastąpiona takim kodem:

 if(level == 0)
   first = 1;
else
   first = a[level-1];

Jest to w tym wypadku skrócony zapis. Do zmiennej first przypisujesz wartość wyrażenia:

( (level == 0) ? 1 : a[level-1] ) 

W nawiasie warunek, jeżeli będzie prawdziwy to robisz to co zaraz za ? inaczej ( else ) robisz to co za :. To znaczy wyrażenie to przyjmie wartość odpowiednio 1 lub a[level-1].
Jest to tak zwany ternary operator - operator potrójny.
Ma on szersze zastosowanie, możesz poczytać.
http://en.wikipedia.org/wiki/%3F:#C.2B.2B
http://en.wikipedia.org/wiki/Ternary_operation
https://msdn.microsoft.com/en-us/library/e4213hs1(v=vs.71).aspx

Wiem co znaczy ten operator !!!! Ja sie pytam co tam wpisze bo nie wiem co znaczy [level-1] ! prosze o prosta odpowiedz -->> JAKA LICZBE WPISZE DO FIRST ZA DRUGIM RAZEM JESLI DANA PRZEZ UZYTKOWNIKA LICZBA TO 10 <<-- ??

@_user zachowuj sie bo będzie ban. Skasuj ten kradziony kod, bo jest słabej jakości i nieczytelny. Napisz WŁASNY i tyle. Serio. To nie jest trudny problem, tylko źle do tego podchodzisz. Tzn podchodzisz tak samo jak do wszystkich swoich innych problemów, tzn na zasadzie głowa potrzebna mi tylko do jedzenia, niech pomyślą za mnie inni!. Weź do ręki kartkę i ołówek a następnie wypisz wszystkie zbiory dające w sumie 10. Tzn

10
9+1
8+2
8+1+1
7+3
7+2+1
7+1+1+1

itd.
Jak już to zrobisz to zastanów sie w jaki sposób to zrobiłeś. Następnie ten sam sposób zapisz w kodzie programu. Voila.

mam problem z jedna linijka, prosilbym o jej wytlumaczenie, linijka ktorej nie rozumiem zakomentowana ponizej:

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
  int first;
  int n;
  int level;
} Call;
 
void print(int n, int * a) {
  int i ;
  for (i = 0; i <= n; i++) {
    printf("%d", a[i]);
  }
  printf("\n");
}
 
void integerPartition(int n, int * a){
  int first;
  int i;
  int top = 0;
  int level = 0;
  Call * stack = (Call * ) malloc (sizeof(Call) * 1000);
  stack[0].first = -1;
  stack[0].n = n;
  stack[0].level = level;
 
  while (top >= 0){
    first = stack[top].first;
    n = stack[top].n;
    level = stack[top].level;
 
    if (n >= 1) {
      if (first == - 1) {
        a[level] = n;
        print(level, a);
        first = (level == 0) ? 1 : a[level-1];   /* Przyjmijmy ze podana liczba do rozpisania skladnikow =10 ...  i Tutaj mam problem, bo przy pierwszym wejsciu tutaj level==0 i przypisuje first wartosc 1(jesli sie myle to poprawcie) ale gdy drugi raz tu przychodzi program to level juz nie jest 0 tylko 1 i w tym momencie przypisuje wartosc a[level-1] do first, tak ? tylko co to za wartosc, 0,1,9 czy 10 ? ile to jest te a[level-1]. ; jaka liczba bedzie przekazana do first przy drugim odwiedzeniu tej linijki*/
        i = first;
      } else {
        i = first;
        i++;
      }
      if (i <= n / 2) {
        a[level] = i;
        stack[top].first = i;
        top++;
        stack[top].first = -1;
        stack[top].n = n - i;
        stack[top].level = level + 1;
      } else {
        top--;
      }
    } else {
      top --;
    }
  }
}
 
int main(){
  int n;
  scanf("%i", &n);
  int * a = (int * ) malloc(sizeof(int) * n);
  printf("\nThe integer partition for %d is :\n", n);
  integerPartition (n, a);
  return(0);

Szczerze to dziwię się, że ktokolwiek chce ci w ogóle odpisywać na takie chamskie posty, nie mówiąc już o udzielaniu pomocy. Opanuj się.

Napisales ze sie dziwisz ze ktos jeszcze odpisuje, a sam odpisales ? Logiki....

Jakie chamskie rzeczy ? Ja ? Ja pisze normalnie, tylko ze wejdzie taki jeden z drugim jak ty, sugeruje sie pozorami bo pozornie wyglada ze ja tu jestem chamski i w ten sposob tworzy sie na mnie nagonka, bo najpierw wszedl jeden gosciu z kompleksami to mu powiedzialem co mysle o jego zachowaniu, drugiemu to sie nie spodobalo i tak w kolko az doszlo do ciebie, a to ze ludzie wchodza i nie odpowiedza ci na pytanie... dobra no to mogli wgl nie wchodzic ale ktos wejdzie i ani ci nie odpowie a gada jakies bzdury nie w temacie, to jak sie moge do tego odniesc, tak jak na to zasluguja, to nie ja tu jestem chamski, tylko ty jestes powierzchowny.

@_user nikt nie ma ochoty ci odpisywać, bo zadajesz idiotyczne pytania, na które powinieneś sam znaleźć odpowiedź. Jeśli bardzo nie chcesz ruszyć głową i napisać tego kodu samodzielnie to odpal ten który masz pod debugerem i wykonuj krok po kroku. Będziesz wtedy widział kiedy i jakie wartości się pojawiają. Nikt tego za ciebie nie zrobi.

_user napisał(a):

Napisales ze sie dziwisz ze ktos jeszcze odpisuje, a sam odpisales ? Logiki....

Sajgonowi chodziło o to, że dziwi sie, że ktoś ci odpisuje w kontekscie tego beznadziejnego kawałka kodu, który bezmyslnie sobie zajwaniłeś. Używajać logiki, do której sie odwołujesz, można by sie tego po prostu domyślic ;)

Jak na mój gust to masz dwa wyjścia, jeśli chcesz sie tego nauczyć to schowaj swoją chorą dume do kieszeni i zrób to po ludzku jak Ci tutaj ludzie proponowali, albo przygotuj sobie 50zł+ i załóż watek w Ogloszeniach

dobra a wiec pomyslalem sobie tak:

first = (level == 0) ? 1 : a[level-1];

przy drugim okrazeniu level bedzie 1 czyli wykona sie : a[level-1] czyli level bedzie 0 czyli do first za drugim okrazeniem wpisze sie 1 ?

dodanie znacznika <code class="c"> - @furious programming

_user napisał(a):

dobra a wiec pomyslalem sobie tak:

first = (level == 0) ? 1 : a[level-1];

przy drugim okrazeniu level bedzie 1 czyli wykona sie : a[level-1] czyli level bedzie 0 czyli do first za drugim okrazeniem wpisze sie 1 ?

Tlumaczenie jakiejs konkretnej linijki bez kontekstu calego programu jest calkowicie debilne, ale skoro sie tak upierasz, prosze bardzo:

do zmiennej first bedzie wpisane "coś" w zależności od warunku level == 0. Jeśli warunek jest spełniony, zostanie wpisana wartość 1, jeśli nie jest warunek spełniony, zostanie wpisana wartość z tabeli a (czy czymkolwiek to a jest) spod indeksu level-1. Czyli jeśli level wynosi 1, to do first bedzie wpisane a[0], czyli to co siedzi w tablicy a pod indeksem 0, itd

Jaka chora dume ? co ma zadanie wspolnego z duma ? Musze dojsc do tego co robi tamta linijka kodu i tyle, z duma nie ma to nic wspolnego, samemu mi nie idzie tego ogarnac, moze na innym forum ktos pomoze

Zadanie nie ma nic wspolnego z chorą dumą, twoje podejście do rozwiązania zadania ma. Moglbyś zaczać od zrobienia researchu czym w ogóle sa te partycje liczb i jak powstaja, ale ci sie nie chce. Moglbys sobie po prostu na piechote rozpisac dla jakiegos malego n na kartce, ale nie, bo nie i juz, kilka osob ci powiedizalo ze sie zabierasz do tego od d**y strony, ale masz to gdzies i idziesz w zaparte - stad stwierdzenie o chorej dumie.

Mozesz tez poszukac rozwiazania na innym forum, ale watpie czy uda ci sie tego dokonac bez uzywania tego strasznego googla, przed ktorym sie bronisz od poczatku tego tematu

dodanie znacznika <code class="c"> - @furious programming