 |
Coders' city
Nasza pasja to programowanie!
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
AndrzejekK
Gość
|
 Wysłany: Nie Lis 25, 2007 2:43 pm Temat postu: Algorytm na 'partition' liczby naturalnej |
  |
|
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: 3195
Skąd: Toruń
|
| Wysłany: Nie Lis 25, 2007 8:21 pm Temat postu: |
|
|
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 |
_________________
Windows XP SP3 + VB 6.0 SP6 / Vista Home Basic SP2+ VB 6.0 SP6 / Vista Home Basic SP2+Microsoft VB 2008 EE + Framework 3.5
Proszę nie pisać do mnie prywatnych wiadomości w sprawach programowania , od tego jest forum. |
|
| Powrót do góry |
|
|
AndrzejekK
Gość
|
| Wysłany: Nie Lis 25, 2007 10:45 pm Temat postu: |
|
|
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: 326
|
| Wysłany: Nie Lis 25, 2007 11:57 pm Temat postu: |
|
|
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 |
|
|
Taeril
Dołączył: 20 Cze 2005
Posty: 959
|
| Wysłany: Pon Lis 26, 2007 12:02 am Temat postu: |
|
|
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;
}
|
Nie wiem jak to działa ale zadaje się działać - ja tylko zamieniłem pseudokod na C++
_________________
T.
People love discussing things that don't matter, because it's so easy to have opinion about those things. - Bjarne Stroustrup |
|
| Powrót do góry |
|
|
Mgr.Dobrowolski
Dołączył: 18 Cze 2006
Posty: 326
|
| Wysłany: Czw Lis 29, 2007 10:13 am Temat postu: |
|
|
| 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 |
|
|
|
|
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.24038 sekund, zapytan = 10
|
Pomoc
Szukaj
Użytkownicy
Grupy
Rejestracja
Profil
Zaloguj się, by sprawdzić wiadomości
