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 SubAihe on jo aika vanha, joten et voi enää vastata siihen.