Zadanie 10 : Podział liczby
Łukasz Bańcarz
Informatyka I
Zaoczne magisterskie
Grupa A
Treść zadania:
Liczbę naturalną C można przedstawić jako sumę parami różnych liczb naturalnych. Skonstruuj algorytm wyczerpujący z nawrotami generujący wszystkie podziały podanej liczby naturalnej C.
Algorytm w pseudokodzie:
Podzial ( n, A[1..n] )
Stos.empty();
i <- 1
WHILE ( i < n) DO
IF ( SumaStosu() + A[i] < n )
Stos.push( A[i] );
i++;
ELSE IF ( SumaStosu() + A[i] > n ) i <- Stos.pop() + 1;
ELSE
Stos.push( A[i] );
WypiszStos();
i <- Stos.pop() + 1;
Implementacja w C#:
for (int i = 0; i < n; )
{
if (summVector(vector) + data[i] < n)
{
vector.Add(data[i]);
i++;
}
else if (summVector(vector) + data[i] > n)
{
i = vector[vector.Count - 1];
vector.RemoveAt(vector.Count - 1);
}
else
{
vector.Add(data[i]);
Console.WriteLine(print(vector));
i = vector[vector.Count - 1];
vector.RemoveAt(vector.Count - 1);
}
}
Listingi programu:
N = 11
N = 13
1. 1 + 2 + 3 + 5
1 + 2 + 3 + 7
2.
1 + 2 + 8
1 + 2 + 4 + 6
3.
1 + 3 + 7
1 + 2 + 10
4.
1 + 4 + 6
1 + 3 + 4 + 5
5. 1 + 10
1 + 3 + 9
6. 2 + 3 + 6
1 + 4 + 8
7.
2 + 4 + 5
1 + 5 + 7
8.
2 + 9
1 + 12
9.
3 + 8
2 + 3 + 8
10. 4 + 7
2 + 4 + 7
11. 5 + 6
2 + 5 + 6
12.
2 + 11
13.
3 + 4 + 6
14.
3 + 10
15.
4 + 9
16.
5 + 8
17.
6 + 7
18.
13
Krok po kroku:
Dla N = 5
Stan
i
Stos
WypiszStos
0
1
[ ]
1
2
[ 1 ]
2
3
[ 1 , 2 ]
3
3
[ 1 ]
4
4
[ 1 ,3 ]
5
4
[ 1 ]
6
5
[ 1 , 4 ]
1 + 4
7
5
[ 1 ]
8
2
[ ]
9
3
[ 2 ]
10
4
[ 2 , 3 ]
2 + 3
11
4
[ 2 ]
12
3
[ ]
13
4
[ 3 ]
14
4
[ ]
15
5
[ 4 ]
16
5
[ ]
17
6
[ 5 ]
5