Warsztat.GD

Programowanie => Szkółka => Wątek zaczęty przez: _user w Kwiecień 22, 2015, 13:03:51

Tytuł: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 13:03:51
Mam problem z zadaniem:
Napisz program, który rozpisuje daną liczbę na wszystkie możliwe kombinacje jej składników.
 
Przykład:
 
2 = 1+1
2 = 2
Chodzi o rozpisanie np
1+1+1
1+2
3

A dla 4:

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

tylko zeby z podana liczba to program robil.I nie mam pojecia jak to zrobic, jak to zaczac i wgl, prosilbym o jakas pomoc.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: SuperBoy w Kwiecień 22, 2015, 13:27:00
Wbrew pozorom to nie jest trywalny problem. Możesz spróbować zrobić to rekurencyjnie.
To znaczy:
 1 to 1,
 2 to 1 + 1
 3 to 1 + 2 a dla dwóch już potrafisz wypisać liczbe.
 4 to 1 + 3, ale tez 2 + 2, i 1 + 3.
Ogolnie petla n^2 i rekurencja. No i zapisuj wyniki gdzies. Tak zeby nie liczyc jakiejs liczby milion razy.
Poczytaj o programowaniu dynamicznym.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 14:04:35
Poczytam, ale narazie wolalbym jakis kawalek kodu z przykladem, nie za wiele wiem z twojego opisu nadal, wolalbym fragment kodu
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: Krzysiek K. w Kwiecień 22, 2015, 14:10:15
Cytuj
Wbrew pozorom to nie jest trywalny problem.
Nie taki też to szczególnie trudny problem:
(wrzuciłem też online: http://cpp.sh/7guo)
#include <stdio.h>
#include <vector>
using namespace std;

int number;
vector<int> components;

void add_components(int value,int max_comp)
{
    if(max_comp>value)
        max_comp = value;
    for(int i=1;i<=max_comp;i++)
        if(i==value)
        {
            printf("%d = %d",number,i);
            for(int j=(int)components.size()-1;j>=0;j--)
                printf(" + %d",components[j]);
            printf("\n");
        }
        else
        {
            components.push_back(i);
            add_components(value-i,i);
            components.pop_back();
        }
}

void print_components(int number)
{
    ::number = number;
    components.clear();
    add_components(number,number);
}

int main()
{
    print_components(7);
}
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 14:16:41
A moglbys w czystym C to napisac ? Chcialbym przyklad z czystego c, bylbym wdzieczny.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: Krzysiek K. w Kwiecień 22, 2015, 15:54:57
No to zastąp sobie std::vector globalną tablicą o stałym rozmiarze + licznik elementów, wywal operator :: i masz. :)
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 16:35:27
jaki licznik elementow ;c Nie wiem, nie wiem jak sie do tego zabrac, dobra tam.Znalazlem fajny kod ale jest zbyt dlugi i skomplikowany i go nie rozumiem ;/


    4programmers.net » Forum » Newbie » Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow

Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
«  1 2

    c

Odpowiedz
Nowy wątek
«  1 2
FakeAccount
dzisiaj, 14:03

    Rejestracja:
    2014-06-12 18:18
    Ostatnio:
    1 minuta temu
    Postów:
    277


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 ;)
on ma dysgooglie - nie czepiaj się :P - kaczus dzisiaj, 14:23
oj i chwala Bogu za ta moja przypadlosc ! :) - _user dzisiaj, 14:24

0
Głosuj na ten post

Udostępnij
Raportuj
Cytuj
_user
dzisiaj, 14:37

    Rejestracja:
    2015-03-13 21:56
    Ostatnio:
    42 minuty temu
    Postów:
    119


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);
}

dlatego wole twoj bo krotszy i moze go ogarne, tylko zamienilbys na c
tylko bez tych
            components.push_back(i);
            add_components(value-i,i);
            components.pop_back();
czy components.clear();

bo te tez nie wiem co to.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: SuperBoy w Kwiecień 22, 2015, 17:00:31
To jakas praca domowa, prawda? :)

Wejdź tutaj -> http://en.cppreference.com/w/ przeczytaj o tych funkcjach co napisałeś wyżej. Zrozumiesz co robią. To jest zastąpisz czymś innym.

Serio. Zamiast szukać tego w necie, strać 2h i zrozumiesz to, na oko musisz zastapic z 5 linijek. Pewnie mniej. Ten kod powyżej jest w 95% napisany w c.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 17:37:39
Czemu odrazu praca domowa ? :p Cos ty, ucze sie dla siebie :)
Wiem czytam o tych funkcjach i wgl, praktycznie skonczylem 1 kurs c ale nie wiem jak to zastapic, nie wiem nie wiem nie wiem, nie chce nic zastepowac, wolalbym zeby to juz bylo zastapione i sprobowac i tak to ogarnac, chociaz nawet jakby bylo w 100% w c nie wiem czy ogarne, przy samym zrozumeniu bd mial sporo roboty a tu jeszcze zastepowac cos, nie nie nie ;c
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: Kos w Kwiecień 22, 2015, 17:41:03
Cos ty, ucze sie dla siebie :)
(...)
wolalbym zeby to juz bylo zastapione i sprobowac i tak to ogarnac

(http://www.edugeek.net/attachments/forums/general-chat/28293d1421156196-help-ghosts-image.png)
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 17:54:12
@Kos - i wcale nie musisz.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: Xirdus w Kwiecień 22, 2015, 19:14:52
Może weź się za kurs C++ teraz? Najlepiej C++11, z nastawieniem na bibliotekę STL.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 20:09:12
Uczylem sie z kursu c++ troche ale zdecydowalem sie najpierw dobrze poznac c a potem ewentualnie c++ dokoncze kurs i sie poucze, chce tak bo uzywam systemu gnu z kernelem na bazie linuxa i tu duzo rzeczy jest napisanych w c, chociazby sam kernel :D, no i c jest dobre do programowania niskopoziomych spraw.

Wiecie, troche zastanowilem sie nad jednym przykladem z internetu, przeanalizowalem go solidnie i nawet ladnie zrozumialem, ale jednak nie wszystko do konca, wkleje tutaj ten kod i zakomentuje linijke ktorej nie rozumiem.
Kod: (c) [Zaznacz]
#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);
}
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: sheadovas w Kwiecień 22, 2015, 20:20:17
Swego czasu miałem coś podobnego na laborkach z programowania i my musieliśmy to zrobić za pomocą sita:

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;


class RozkladLiczby
{
public :
RozkladLiczby(int n) throw (string)
{
if (n < 2)
throw (string) " liczba spoza zakresu";

try {
sito = new int[n - 1];
}
catch (bad_alloc &b) {
throw (string) " za duza liczba. Nie udalo sie stworzyc sita!";
}

for (int i = 0; i < n - 1; i++)
sito[i] = 0;

for (int i = 0; i*i <= n; i++) {
if (sito[i] == 0) {
for (int j = (2*i+2); j < n - 1; j += i + 2) {
if (sito[j] == 0)
sito[j] = i + 2;
}
}
}
}

~RozkladLiczby()
{
delete[] sito;
//delete[] t;
}

int *czynnikiPierwsze(int m) throw (string)
{
if (m < 0)
throw (string) " liczba ujemna";

int *t;
int counter = 1;
int *tmp;

int sqr = log2(m);
tmp = new int[sqr];

for (int i = 0; i < sqr && m != 1; i++) {
if (sito[m - 2] == 0) {
tmp[i] = m;
m = 1;
}
else {
tmp[i] = sito[m - 2];
m /= sito[m - 2];
counter++;
}
}

t = new int[counter];
for (int i = 0; i < counter; i++) {
t[i] = tmp[i];
}

size = counter;

delete[]tmp;
return t;
}


public:
int size;

private:
int *sito;
//int *t;
};


int getMax(int argc, char* argv[])
{
int max = 0, next = 0;
for (int i = 1; i < argc; i++) {
try {
istringstream iss(argv[i]);
iss.exceptions(ios::failbit);
iss >> next;
}
catch (ios::failure e) {
continue;
}

if (next > max)
max = next;
}
return max;
}


int main(int argc, char* argv[])
{
int n = getMax(argc, argv);

RozkladLiczby *liczba;
try {
liczba = new RozkladLiczby(n);
}
catch (string str) {
cout << n << str << endl;
system("PAUSE");
return EXIT_FAILURE;
}

for (int j = 1; j < argc; j++) {
int m;
try {
istringstream iss(argv[j]);
iss.exceptions(ios::failbit);
iss >> m;
}
catch (ios::failure e) {
cout << argv[j] << " nie jest liczba" << endl;
continue;
}

int *t;
try {
t = liczba->czynnikiPierwsze(m);
}
catch (string s) {
cout << m << s << endl;
continue;
}

int counter = 1;
cout << m << " = ";

for (int i = 0; i < liczba->size; i++) {
cout << t[i];


if ((i < liczba->size - 1) && (t[i + 1] != t[i])){
cout << " * ";
continue;
}
else {
counter = 1;
while ((i < liczba->size - 1) && (t[i + 1] == t[i])){
counter++;
i++;
}
if ( counter > 1)
cout << "^" << counter;
}

if (i < liczba->size - 1)
cout << " * ";
}

cout << endl;
delete[] t;
}

system("PAUSE");
return EXIT_SUCCESS;
}
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: koirat w Kwiecień 22, 2015, 20:21:47
Ale za pomocą sita to robiliście pewnie faktoryzację.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 22, 2015, 20:28:16
spoko, ale prosze o odpowiedz na pytanie, jesli liczba podana do rozpisania bedzie 10 to przy drugim odwiedzeniu tej linijki "first = (level == 0) ? 1 : a[level-1]" ile doda ? 0,1,9,10 ? dokladniej opisalem to w poprzednim poscie moim w zakomentowanym kodzie.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: mawpa w Kwiecień 23, 2015, 00:13:36
Geez. Trochę samodzielnego myślenia nie zaszkodzi... Wystarczy przeanalizować, co program robi.

Ewentualnie zrobić prymitywny debugging, czyli dodać printf.
first = (level == 0) ? 1 : a[level-1];
printf("first = %d\n", first);
Za każdym razem zobaczysz, ile masz w first.

Skąd się biorą te wartości, można wywnioskować symulując wykonanie programu. Jeśli masz z tym trudności, rozpisz sobie na kartce kilka obiegów tego while'a, linijka po linijce. Z początku chciałem to zrobić tutaj, ale nie będę Ci psuł zabawy ;)
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 23, 2015, 02:06:51
nie wiem ile ma first ;c
Prosze wiec o powiedzenie mi :
first = (level == 0) ? 1 : a[level-1];

jesli podam 10 jako dana liczbe do rozpisania to ile ta linia da mi w drugim okrazeniu do first ?
Nie wiem ile to jest ten [level-1] to bedzie ten level0 z wartoscia 10 ? To chyba najlatwiejsze pytanie jakie zadalem w temacie, prosze juz tylko o odpowiedz na nie, i bede usadysfakcjonowany :)
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 23, 2015, 12:25:54
Okej, ogarnalem co wpisuje do first, w drugim okrazeniu wpisuje tam 1 :) takze nie mam wiecej pytan.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: topik92 w Kwiecień 23, 2015, 13:44:14
Możesz rozłożyć liczbę na tablice liczb z których da się ją z sumować dla 4 = {1 1 1 1 2 2 3 4}
for(int i=1; i<=szukanaLiczba;i++) // kolejne liczby od 1 do
    for(int j=0; j < szukanaLiczba / i ;i++)
//@up liczba wystapien kazdej liczby  dla 4 jeden raz dla 3 jeden raz, dla 2 dwa razy ect.
{
//zapisujesz elemnty w tablicy
}
Problem sprowadza się do z sumawania  i sprawdzenia każdej możliwej kombinacji.
Możesz spróbować zrobić to tak:
 tworzysz tablice o długości  takiej samej jak twoja pomocnicza wypłenioną  zerami  {0 0 0 0   0 0 0 0 } która bedzie reprezentować kolejne liczby  binarne od {0 0 0 0   0 0 0 0 } do { 1 1 1 1  1 1 1 1} Iteracyjnie zwiększasz ją ciągle o 1 i za  co iteracje sumujesz te wyrazy tablicy głównej którym opowiada 1 w pomocniczej.
Problem gdybys odpowiednio poifował to to mógł byś bardzo ograniczyć liczbe obliczeń.
Żeby nie zżerać tak duzo pamieci można zrobić taki myk że indeks tablicy + 1 oznacza wartość a liczba w nim w pisana ilośc elemntów, a w tablicy zamiast kolejnych liczb binarnych generować  liczby z zakresu 0-1 0-1 0-2 0-4.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 23, 2015, 13:51:13
@topik92 - to zbyt skomplikowane nic z tego nie rozumiem, ale nie wazne ziomus, juz ogarnalem tamta linijke w tym kodzie co znalazlem, rozumiem kod mniej wiecej wiec zadanie uwazam za wykonane :)
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: topik92 w Kwiecień 23, 2015, 14:34:16
W implementacji to są 2 pętle for by zrobić tablice z liczbami od 1-x, i jedna pętla for do sumowania i sprawdzania i funkcja zamieniająca liczby 10 na binarne która można zrobić na 1 pętli for.

@down dał bym Ci plusa ale się nie da :c
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: Xender w Kwiecień 23, 2015, 17:04:09
2 pentle
;_;

Włącz w przeglądarce sprawdzanie pisowni i nie grzesz więcej... :P
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: voytech w Kwiecień 23, 2015, 17:58:00
nie wiem ile ma first ;c
Prosze wiec o powiedzenie mi :
first = (level == 0) ? 1 : a[level-1];

jesli podam 10 jako dana liczbe do rozpisania to ile ta linia da mi w drugim okrazeniu do first ?
Nie wiem ile to jest ten [level-1] to bedzie ten level0 z wartoscia 10 ? To chyba najlatwiejsze pytanie jakie zadalem w temacie, prosze juz tylko o odpowiedz na nie, i bede usadysfakcjonowany :)

może się mylę ale wydaje mi się że nie rozumiesz działania operatora "?:"

Kod: (c) [Zaznacz]
first = (level == 0) ? 1 : a[level-1];
to jest skrócona forma zapisu:

Kod: (c) [Zaznacz]
if (level==0) {
    first = 1;
} else {
    first = a[level-1];
}
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: _user w Kwiecień 23, 2015, 18:09:08
... Dzialanie operatora rozumiem, nie wiedzialem co za wartosc jest w - a[level-1] , tylko tego, ale juz to przeanalizowalem i doszedlem do wniosku ze to bedzie w drugim okrazeniu 1, takze spoczko.
Tytuł: Odp: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow
Wiadomość wysłana przez: voytech w Kwiecień 23, 2015, 18:40:50
pewnie w którymś okrążeniu level==0 wtedy odczyt z a[-1] staje się niebezpieczny i dlatego jest ten warunek