Autor Wątek: Rozpisywanie liczby na wszystkie mozliwe kombinacje skladnikow  (Przeczytany 4228 razy)

Offline _user

  • Użytkownik

# 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.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline SuperBoy

  • Użytkownik

# 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.

Offline _user

  • Użytkownik

# 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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

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

Offline _user

  • Użytkownik

# Kwiecień 22, 2015, 14:16:41
A moglbys w czystym C to napisac ? Chcialbym przyklad z czystego c, bylbym wdzieczny.
« Ostatnia zmiana: Kwiecień 22, 2015, 14:23:18 wysłana przez _user »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# 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. :)

Offline _user

  • Użytkownik

# 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.
« Ostatnia zmiana: Kwiecień 22, 2015, 16:53:29 wysłana przez _user »

Offline SuperBoy

  • Użytkownik

# 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.

Offline _user

  • Użytkownik

# 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

Offline Kos

  • Użytkownik
    • kos.gd

  • +6
# Kwiecień 22, 2015, 17:41:03
Cos ty, ucze sie dla siebie :)
(...)
wolalbym zeby to juz bylo zastapione i sprobowac i tak to ogarnac


Offline _user

  • Użytkownik

# Kwiecień 22, 2015, 17:54:12
@Kos - i wcale nie musisz.

Offline Xirdus

  • Moderator

# Kwiecień 22, 2015, 19:14:52
Może weź się za kurs C++ teraz? Najlepiej C++11, z nastawieniem na bibliotekę STL.

Offline _user

  • Użytkownik

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

Offline sheadovas

  • Użytkownik
    • Blog

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

Offline koirat

  • Użytkownik

# Kwiecień 22, 2015, 20:21:47
Ale za pomocą sita to robiliście pewnie faktoryzację.