1. Anagrammit

Tee ohjelma Anagrammit.java, joka tarkistaa, ovatko kaksi sanaa anagrammeja. Sanat ovat anagrammeja, jos jokainen kirjain esiintyy niissä yhtä monta kertaa. Esimerkiksi sanat talo ja lato ovat anagrammeja. Voit olettaa, että sanat muodostuvat kirjaimista a–z.

Esimerkki 1

Anna 1. sana: talo
Anna 2. sana: lato
Annoit anagrammit.

Esimerkki 2

Anna 1. sana: talo
Anna 2. sana: altto
Et antanut anagrammeja.

2. Alkusummia

Tehtävänäsi on etsiä annetusta lukujonosta sellainen alkuosa jonka summa on haluttu. Ohjelmalle annetaan lukujono jonka jälkeen suoritetaan monta kyselyä.

• Toteuta luokka Etsin jonka konstruktorille Etsin(int[] luvut) annetaan taulukollinen positiivisia kokonaislukuja
• Toteuta metodi Etsin.etsi(int haluttuSumma) joka kutsulla etsi(x) palauttaa indeksin i konstruktorille annettuun taulukkoon luvut siten, että

  luvut[0] + luvut[1] + ... + luvut[i] = x

  Palauta -1 jos tällaista indeksiä ei löydy.

Tee ohjelmastasi salamannopea. Testit testaavat että 10 000 kyselyä 100 000 luvun taulukosta vie alle 50ms.

Huom! Testit eivät testaa pääohjelmaa (main) vaan suoraan luokkaa Etsin!

Vihje! binäärihaku

Esimerkki 1

Montako lukua?
3
Anna luvut:
1
2
3
Mikä summa?
1
Indeksi: 0
Mikä summa?
3
Indeksi: 1
Mikä summa?
6
Indeksi: 2
Mikä summa?
5
Indeksi: -1

Esimerkki 2

Montako lukua?
10
Anna luvut:

10
20
4
7
7
5
7
7
10
1
Mikä summa?
48
Indeksi: 4

3. Fibonaccin luvut

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 2) + F(n - 1), kun n > 1

• F(0) = 0
• F(1) = 1
• F(2) = 1
• F(3) = 2
• F(4) = 3
• F(5) = 5
• F(6) = 8
• F(7) = 13
• F(8) = 21
• F(9) = 34
• F(10) = 55

Esimerkki 1

n: 5
F(n): 5

Esimerkki 1

n: 9
F(n): 34

4. Puuttuva luku

Tee ohjelma PuuttuvaLuku.java, joka toimii seuraavasti: Käyttäjä antaa ensin ohjelmalle kokonaisluvun n ja sitten kaikki kokonaisluvut väliltä 1...n yhtä lukuun ottamatta. Ohjelman tehtävänä on selvittää, mikä on puuttuva luku. Voit olettaa, että käyttäjä antaa ainakin yhden luvun ja korkeintaan miljoona lukua. Tee ohjelmasta niin tehokas, että se käsittelee miljoona lukua muutamassa sekunnissa. Testit testaavat ajankäytön.

Esimerkki 1

Suurin luku? 5
Anna luvut:
3
1
5
4
Puuttuva luku: 2

Esimerkki 2

Suurin luku? 5
Anna luvut:
3
1
2
4
Puuttuva luku: 5

Vihje: Tehtävään on olemassa ratkaisualgoritmi, jonka aikavaativuus on O(n) ja tilavaativuus on O(1).

5. Suurin summa

Tee ohjelma SuurinSumma.java, joka selvittää suurimman peräkkäisten lukujen summan käyttäjän antamissa luvuissa. Ohjelma kysyy ensin, kuinka monta lukua käyttäjä antaa.

Tässä tehtävässä summaan täytyy kuulua ainakin yksi luku. Voit olettaa, että suurin summa on positiivinen.

Voit olettaa, että käyttäjä antaa ainakin yhden luvun ja korkeintaan miljoona lukua. Lisäksi voit olettaa, että jokainen luku on kokonaisluku väliltä -1000...1000, jolloin kaikki summat mahtuvat int-muuttujiin. Tee ohjelmasta niin tehokas, että se käsittelee miljoona lukua muutamassa sekunnissa. Huom! Ohjelmasi on oltava tehokas. Testit tarkastavat asian.

Esimerkki 1

Kuinka monta? 5
Anna luvut:
1
-2
5
2
-1
Suurin summa: 7

Esimerkki 2

Kuinka monta? 5
Anna luvut:
4
-2
5
2
-1
Suurin summa: 9

Esimerkki 3

Kuinka monta? 4
Anna luvut:
4
3
-5
6
Suurin summa: 8

Esimerkissä 1 suurin summa saadaan laskemalla yhteen luvut 5 ja 2. Esimerkissä 2 suurin summa saadaan laskemalla yhteen luvut 4, -2, 5 ja 2. Esimerkissä 3 suurin summa saadaan laskemalla kaikki luvut yhteen.

Vihje: Tehtävään on olemassa ratkaisualgoritmi, jonka aikavaativuus on O(n) ja tilavaativuus on O(1).