[Pytanie/VB.Net] Przekształcanie sumy na czynniki

[JachuPL]

Cześć. Piszę program, którego zadaniem będzie odwrócić proces sumowania. Do programu wpisuję sobie liczbę parzystą wygenerowaną innym programem. Wiedząc, że wprowadzoną liczbę mogę uzyskać tylko na jeden sposób, chciałbym aby program przedstawił mi ten sposób. Kiepsko mi idzie tłumaczenie, więc może to po prostu zaprezentuję.

 

1. W tablicy mam liczby 2^n+1, gdzie n przyjmuje wartości nieujemne od 0 do 15. Czyli mam coś takiego:

2

4

8

16

32

...

 

2. Wpisuję liczbę do programu. Załóżmy, ze będzie to 48. Dla nas wiadome jest, że jest to suma 16 i 32.

 

3. Program sprawdza, które z liczb z tablicy po zsumowaniu dają tę liczbę i podaje te liczby.

 

 

Da się coś takiego napisać? Z góry dzięki za odpowiedź i pozdrawiam

[Gość]

Module Module1

 

Sub Main()

Const SZUKANA_LICZBA As Integer = 48

Dim liczby As New List(Of Integer)

For i As Integer = 0 To 15

liczby.Add(Math.Pow(2, i + 1))

Next

Dim kombinacje As New Dictionary(Of Integer, Integer)

For Each i As Integer In liczby

For Each y As Integer In liczby

If i + y = SZUKANA_LICZBA Then

kombinacje.Add(i, y)

End If

Next

Next

For Each kombinacja In kombinacje

Console.WriteLine("{0} + {1} = {2}", kombinacja.Key, kombinacja.Value, SZUKANA_LICZBA)

Next

Console.ReadKey()

End Sub

 

End Module

[JachuPL]

a co w przypadku, gdy nie wiadomo ile liczb wchodzi w skład sumy i zakładamy, że każda liczba używana była tylko raz? (np. w skład 131070 (największa możliwa suma z elementów tablicy) wchodzi 16 czynników)

[JachuPL]

odświeżam

[Sopelek997]

http://pl.wikipedia.org/wiki/Problem_wydawania_reszty

 

Dla twojego przykłady wystarczy algorytm zachłanny. Lekko przyrobisz i będzie działał zgodnie z twoimi założeniami.

[Gość]

Nawet przepisałem Ci algorytm zachłanny na VB

im k As Integer = 13

Dim liczby() As Integer = {1, 2, 5}

Dim x As Integer = 0

While (k > 0)

Dim n As Integer = 0

For i As Integer = 0 To liczby.Length - 1

If liczby(i) <= k And liczby(i) > n Then n = liczby(i)

Next

k -= n

x += 1

End While

Console.WriteLine(x)

Console.ReadKey()

[JachuPL]

algorytm w 100% spełnia moje oczekiwania i jest zgodny z moimi założeniami. Serdeczne dzięki panowie, leci po 5 gwiazdek. Temat zgłaszam do zamknięcia.