Keskustelu: Ohjelmointikysymykset: Java: Java...jeesaisko joku...

Kouluun pitäisi seuraavanlainen Java harjoitus.

***********************
KOMBINAATIOT
Kuinka monta yhden, kahden, kolmen, neljän ja viiden kirjaimen erilaista kombinaatiota on mahdollista tehdä syötetystä 1 - 5 kirjainta sisältävästä merkkijonosta? Tee ohjelma, joka laskee vastauksen ja tulostaa kombinaatiot pituusjärjestyksessä. Käyttäjä voi jatkaa merkkijonojen syöttämistä haluamansa määrän.
***********************

Olen yrittänyt ratkoa ongelmaa, mutten ole tullu hullua hurkaammaksi, joten ajattelin kysästä jospa Kuhan jengiltä heruisi vinkkejä tehtävään. Kuinkahan tuota kannattaisi lähteä ratkomaan....

Kiitos etukäteen mahdollisista vinkeistä...!!!

Käy paperin ja kynän kanssa läpi pari yksinkertaisinta tapausta, ja mieti, minkä säännön perusteella yhdistelmät muodostuvat. Tämän jälkeen tutustu Javan tapaan käsitellä merkkijonoja ja yritä laatia ohjelma löytämäsi säännön perusteella. Vai oliko ongelma siinä, että et ymmärrä tehtäväksiantoa?

periaatteessa ymmärrän tehtävän annon ja funtsin tossa voisikohan taulukko ja kertomaa jotenkin hyödyntää tehtävän suorituksessa... danke!

lainaus:

ajattelin kysästä jospa Kuhan jengiltä heruisi vinkkejä

Hehehe, sitä se copypastaaminen teettää ;-)

joo =D huomasin ittekin....heti kun laitoin... Copy&paste rulettaa silti...LOL!

Kummallinen silti toi tehtävän anto...

jos nyt Ollenkaan ymmärsin mitä tässä haetaan niin... ihan näin hatusta, eikös se kombinaatioiden määrä ole 'n!'
(eli kolmella = 3 * 2 * 1 = 6, neljällä 4 * 3 * 2 * 1 = 24 jne)

ja tuonhan laskee helposti näin...

int maara( int pituus ) {
  // noniin, pitihän tätä muokata ennen ku oli toimivaa koodia.
  // väsymys ja vitutus näkyy...
  return (pituus > 1) ? pituus * maara(pituus-1) : 1;
}

ja kolmen kirjaimen yhdistelmäthän ovat seuraavat.

a b c
a c b
b a c
b c a
c a b
c b a

tuon tekee samalla tavalla kuin totuustaulukot, ei muuta kuin algoritmia väsäämään... pitipä ihan oman pään rauhottamisen vuoksi varmistaa tuo. eli neljän kirjaimen yhdistelmät alla. rupes algoritmintynkäkin päässä jo kypsymään...

a b c d
a b d c
a c b d
a c d b
a d b c
a d c b

b a c d
b a d c
b c a d
b c d a
b d a c
b d c a

c a b d
c a d c
c b a d
c b d a
c d a b
c d b a

d a b c
d a c d
d b a c
d b c a
d c a b
d c b a

NiCK. Tuo on permutaatio eli kertoma. Permutaatio ilmoittaa, miten monella tavalla voidaan järjestää jonoksi, mutta ei ota huomioon perättäisiä merkkejä. Kombinaatio on eri asia. Kunhan pääsen kotiin, niin tarkastan kominaation matematiikan kirjasta.

En tiedä, tietääkö opettajasi tarkalleen mitä tarkoitetaan kombinaatiolla. Tässä tapauksessa tehtävänannossa saattaa olla väärä termi, eli sanaa kombinaatio on käytetty väärin.

Kuitenkin:
kombinaation kaava on tämä:
(n yli k) = n!/(k!*(n-k)!)

Tuo huutomerkki on kertoma. Luvun 4 kertoma on 4*3*2*1=24
Kannattaa siis koodata oma funktionsa sille, joten lauseke voisi olla vaikka:

kertoma(n)/(kertoma(k)*kertoma(n-k))

Kombinaatio on äärellisen n-alkioisen joukon k-alkioisten osajoukkojen (k-kombinaatioiden) lukumäärä.

Esimerkki:
Kuinka monella tavalla 10:stä voidaan valita 2?
Tällöin mahdollisuuksia on (10 yli 2) eli 10!/(2!*8!)=45

Juu sehän se oli (kertoma siis :)
On nuo termit jääny vuosien mittaan vähän pölyn peittoon... Laskutapaa tarvitaan edelleen joten sen muistin...

Ja sen funktiohan oli tuossa yllä, tosin vähän puutteellinen eka rivi (funktiomääritelmä puuttuu)

public static int kertoma( int n ) {
   return (n > 1) ? n * kertoma(n-1) : 1;
}

No selitin sen lähinnä algoritmitasolla. Tuo on muuten häntärekursiivinen tapa toteuttaa kertoma...

Pistin ratkaisun kombinaatioiden generoinnista koodivinkkiosastolle. Ratkeaa parhaiten rekursiolla.

Tässä koko ratkaisi koodi VB.net:llä tehtynä. Form1:llä on button1 ja textbox1 jolla vertical scroll ja multiline asetettu päälle.

Tulostaa tämän:

Combinations 1 out of 5
1
2
3
4
5
Combinations 2 out of 5
12
13
14
15
23
24
25
34
35
45
Combinations 3 out of 5
123
124
125
134
135
145
234
235
245
345
Combinations 4 out of 5
1234
1235
1245
1345
2345
Combinations 5 out of 5
12345

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
       '
       ' test Combins
       '
       Dim level As Long
       Dim elem As Long
       Dim n As Long
       Dim m As Long
       Dim j As Long
       Dim k As Long
       Dim A(,) As Long = New Long(1000, 10) {}
       m = 5
       TextBox1.Text = ""
       For n = 1 To 5
           level = 0
           elem = 0
           Combins(n, m, level, elem, A)
           'print
           TextBox1.Text = TextBox1.Text + "Combinations " & Format(n) & " out of " & Format(m) & Chr(13) & Chr(10)
           For j = 1 To elem
               For k = 1 To n
                   TextBox1.Text = TextBox1.Text & Format(A(j, k))
               Next
               TextBox1.Text = TextBox1.Text & Chr(13) & Chr(10)
           Next
       Next n

   End Sub

   Public Sub Combins(ByVal n As Long, ByVal m As Long, ByVal level As Long, ByRef elem As Long, ByRef A(,) As Long)
       ' n out of m combinations to array A(,)
       Dim illeg As Boolean
       Dim counter As Long
       Dim k As Long
       Dim j As Long
       Dim i As Long
       level = level + 1
       If level > n Then
           ' is it a new combination
           illeg = False
           For k = 1 To elem
               counter = 0
               For j = 1 To n
                   For i = 1 To n
                       If A(elem + 1, i) = A(k, j) Then counter = counter + 1
                   Next i
               Next j
               If counter = n Then illeg = True 'combination already exists
           Next k
           If Not illeg Then
               ' so add it
               elem = elem + 1
               'remember values from previoius levels
               For j = 1 To level - 1
                   A(elem + 1, j) = A(elem, j)
               Next j
           End If
           Exit Sub 'return up one level
       Else
           For k = 1 To m
               A(elem + 1, level) = k
               If level > 1 Then
                   'check if the number is already used
                   illeg = False
                   For j = 1 To level - 1
                       If A(elem + 1, level) = A(elem + 1, j) Then illeg = True
                   Next j
               End If
               'if not used add it and call myself
               If Not illeg Then Combins(n, m, level, elem, A)
           Next k
       End If
   End Sub