Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Algorytm na 'partition' liczby naturalnej



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
AndrzejekK
Gość





PostWysłany: Nie Lis 25, 2007 2:43 pm  OP    Temat postu: Algorytm na 'partition' liczby naturalnej Odpowiedz z cytatem Pisownia

Hejka!!
Na zajęcia z programowania mam zrobić program przedstwiający wszystkie unikalne sumy liczb naturalnych dające wynik równy podanej przez usera liczby np.:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

W języku angielskim nazywa się to 'partition of an intger number'
Czy ktoś już coś takiego pisał?? PLIZZZ pomocy!!

Z góry THX za podpowiedzi!:)
Powrót do góry
samolot



Dołączył: 26 Sty 2006
Posty: 8055
Skąd: Toruń

PostWysłany: Nie Lis 25, 2007 8:21 pm      Temat postu: Odpowiedz z cytatem Pisownia

Pogrzebałem troche w internecie i wstawiając hasło 'partition of an intger number' znalazłem to:
http://home.att.net/~numericana/answer/numbers.htm#partitions
Z tej strony skopiowałem ten kod do zdarzenia przycisku i go trochę przerobiłem:
Kod:
Private Sub plcAlgorytm_Click()
Dim m As Long, I As Long, u As Long, K As Long, J As Long

'm = InputBox("Wprowadx liczbę", "Witaj!", , 7400, 3500)'
For m = 1 To 100
   ReDim a(m), p(m)
  
   For I = 0 To m:
       p(I) = 1:
   Next I

  For u = 2 To m
       For I = 0 To m:
          a(I) = p(I):
          p(I) = 0:
       Next I
      
       For J = 0 To m Step u
           For K = J To m
              p(K) = p(K) + a(K - J)
           Next K
       Next J
      
  Next u

   If txtWynik.Text = "" Then
      txtWynik.Text = txtWynik.Text & "p(" & Str(m) & ")= " & Str(p(m))
   End If

   If txtWynik.Text <> "" Then
       txtWynik.Text = txtWynik.Text & vbNewLine & "p(" & Str(m) & ")= " & Str(p(m))
   End If
  
Next m

End Sub

Ten kod znajduje ilość kombinacji tych sum. Fragment wyniku z pola tekstowego:
Cytat:
p( 1)= 1
p( 1)= 1
p( 2)= 2
p( 3)= 3
p( 4)= 5
p( 5)= 7
p( 6)= 11
p( 7)= 15
p( 8)= 22
p( 9)= 30
p( 10)= 42
p( 11)= 56
p( 12)= 77
p( 13)= 101
p( 14)= 135
p( 15)= 176
....
p( 100)= 190569292

Te wyniki są zgodne z podanymi na stronie http://home.att.net/~numericana/data/partition.htm
Nie mam jednak pomysłu jak zrobić wykaz w takiej formie jak podałeś(dla p( 4)= 5 ):
Cytat:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

_________________
Nie zadawaj bezcelowych pytań / Windows 8.1 / Windows 10 / VB2008 / VB 2010 / VB 2012 / Pisz poprawnie
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email
AndrzejekK
Gość





PostWysłany: Nie Lis 25, 2007 10:45 pm      Temat postu: Odpowiedz z cytatem Pisownia

Hej:)
Szacunek Samolocie za włożoną dla mnie pracę. Jednak ja mam za zadanie napisać w C++ program przedstawiający wszystkie możliwe sumy. Sam nasz Doktór powiedział, że będzie to spory program z dużą ilością tzw. stosów.

Mimo wszystko Samolocie Wielkie Dzięks za wysiłek.
pozdrawiam i życzę sukcesów w programowaniu!!:D
Powrót do góry
Mgr.Dobrowolski



Dołączył: 18 Cze 2006
Posty: 503

PostWysłany: Nie Lis 25, 2007 11:57 pm      Temat postu: Odpowiedz z cytatem Pisownia

Znalazłem w sieci rekurencyjne rozwiązanie w kilkunastu linijkach.
Mogę podesłać gotowca, ale warto pobawić się samemu.
[/code]
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email Numer GG Tlen
Taeril



Dołączył: 20 Cze 2005
Posty: 1249

PostWysłany: Pon Lis 26, 2007 12:02 am      Temat postu: Odpowiedz z cytatem Pisownia

Google zapytane o algorithm partition of an intger number podało m.in. jakiś pliczek pdf z opisem algorytmu.
Zaimplementowałem to sobie:
Kod:
#include <iostream>
#include <sstream>

using std::cin;
using std::cout;
using std::endl;

void p(unsigned int n) {
    unsigned int m = 1;
    unsigned int h = 1;
    unsigned int r = 0;
    unsigned int t = 0;

    unsigned int *x = new unsigned int[n+1];
    
    for(unsigned int i=0; i<=n; ++i) {
        x[i] = 1;
    }

    x[1] = n;
    cout << x[1] << endl;

    while( x[1] != 1 ) {
        if( x[h] == 2  ) {
            m = m + 1;
            x[h] = 1;
            h = h - 1;
        } else {
            r = x[h] - 1;
            t = m - h + 1;
            x[h] = r;
            while( t >= r ) {
                h = h + 1;
                x[h] = r;
                t = t - r;
            }
            if( t == 0  ) {
                m = h;
            } else {
                m = h + 1;
                if( t > 1  ) {
                    h = h + 1;
                    x[h] = t;
                }
            }
        }

        for(unsigned int i=1; i<m; ++i) {
            cout << x[i] << " + ";
        }
        cout << x[m] << endl;
    }

    delete [] x;
}

int main(int argc, char** argv) {
    unsigned int k;
    if( argc > 1 ) {
        std::stringstream ss;
        ss << argv[1];
        ss >> k;
    } else {
        cout << "k = ";
        cin >> k;
    }
    p(k);

    return 0;
}
tyle, że brzydko, bo nie używa x[0] (chyba), nie sprawdza czy udało się przydzielić pamięć itp

Nie wiem jak to działa ale zadaje się działać - ja tylko zamieniłem pseudokod na C++

_________________
T.

"Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems." - Jamie Zawinski
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Mgr.Dobrowolski



Dołączył: 18 Cze 2006
Posty: 503

PostWysłany: Czw Lis 29, 2007 10:13 am      Temat postu: Odpowiedz z cytatem Pisownia

Kod:
#define MAX 100;

int  n,k;
int  p[MAX];

int min( int x, int y) {
    if (x<y) return x;
    return y;
}

void PrintIt(int t) {
    int i;
    for(i=1; i<=t; i++) printf("%d ", p[i]);
    printf("\n");
}

void P (int n, int k, int t) {
    int j;
    p[t] = k;
    if (n==k) PrintIt(t);
    for (j=min(k,n-k); j>=1; j--) P(n-k,j,t+1);
}

void main() {
    printf("Enter n,k: ");
    scanf("%d %d", &n ,&k );
      P( n,k,1 );
      /* NOTE: The call P( 2*n, n, 0 ) will produce all partitions of n. */
}

Zgrabne, prawda?
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email Numer GG Tlen
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.02486 sekund, zapytan = 12
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |