Oletetaan, että erään valtion postilaitoksessa on pääjohtajan paikka haettavana. Oletetaan lisäksi, että sinä olet hakijoiden joukossa ja olet juuri saapunut työpaikkahaastatteluun. Sinulle annetaan seuraavanlainen tehtävä:
Postimaksu olkoon aina 1-70€, riippuen lähetyksen painosta (senteillä ei nyt pelata).
Muodostettava seitsemän eriarvoista postimerkkiä, joista valitsemalla yhden, kahden tai kolmen merkin yhdistelmällä voidaan maksaa kaikki eri postimaksut (siis 70 kpl).
(esim. jos merkit ovat 1€,2€,3€,8€,15€,24€ ja 54€:n arvoiset, niin niistä ei voi muodostaa vaikkapa 68 euron postimaksua millään yhden, kahden tai kolmen merkin yhdistelmällä)
Veikkanpa, että näillä oletuksilla työsi roskakuskin apulaisen osa-aikaisena lomittajana jatkuu edelleen.
Postimaksu olkoon aina 1-70€, riippuen lähetyksen painosta (senteillä ei nyt pelata).
Muodostettava seitsemän eriarvoista postimerkkiä, joista valitsemalla yhden, kahden tai kolmen merkin yhdistelmällä voidaan maksaa kaikki eri postimaksut (siis 70 kpl).
(esim. jos merkit ovat 1€,2€,3€,8€,15€,24€ ja 54€:n arvoiset, niin niistä ei voi muodostaa vaikkapa 68 euron postimaksua millään yhden, kahden tai kolmen merkin yhdistelmällä)
Veikkanpa, että näillä oletuksilla työsi roskakuskin apulaisen osa-aikaisena lomittajana jatkuu edelleen.
Vastaukset 16
Vanhimmat
jos ossaa vähänkää 2-luku järjestelmää tajuaa heti että luvut ovat 1 2 4 8 16 32 64
Et pysty muodostamaan esim. 31 euron postimaksua.
Jatka vain apupojan hommia.
unohin tuon että saa käyttää vain kolmea merkkiä
Onkohan tehtävässä kompa?
3-Stohrin luvut alkavat: 1, 2, 4, 8, 15, 22, 29.
http://www.research.att.com/~njas/sequences/A026474
Nyt näistä saadaan korkeintaan summaksi 15 22 19=37 19=56.
kompaa ja vain yksi ratkaisu on olemassa.
postimerkkiä saa käyttää useammin kuin kerran. Esim 3*1€=3€. Tuossa mainitsemassasi ketjussa ilmeisesti kaikkien kolmen luvun oltava eri lukuja.
1, 3, 4, 9, 12, 23, 26.
sinne aukkoja. taitaa 37 olla pienin.
En kyllä tajua tehtävää. Ensiksi sanottiin, että "Muodostettava seitsemän eriarvoista postimerkkiä, joista valitsemalla yhden, kahden tai kolmen merkin yhdistelmällä voidaan maksaa kaikki eri postimaksut (siis 70 kpl). " Myöhemmin "Samanarvoista postimerkkiä saa käyttää useammin kuin kerran." Eikö nämä ole keskenään ristiriitaiset lauseet?
Miten ne ovat mielestäsi ristiriitaiset? Jos voit valita seitsemästä merkistä 1, 2 tai 3 merkin yhdistelmät, niin miten se on ristiriidassa sen kanssa, että yhden merkin voi valita 0-3 kertaa?
Sinulla on käytössäsi seitsemää (ei seitsemän) erilaista postimerkkiä.
Lisäksi ensimmäinen on selvä. Tästä voi päätellä seuraavan tarvittavan ja sitten vähän kokeilua ja sen jälkeen päättelemällä(omaa ajatusta, ei välttämättä noin kannata).
En tiedä kuinka vaikeaa on ohjelmoinnin avulla ratkaista.
Näin lähelle pääsin pikaisesti kirjoitetulla leveyshaulla:
58 listasta [1, 3, 8, 12, 18, 22, 49]
59 listasta [1, 3, 8, 12, 18, 19, 32]
60 listasta [1, 3, 8, 12, 18, 34, 38]
61 listasta [1, 3, 8, 12, 14, 33, 43]
64 listasta [1, 3, 8, 12, 20, 26, 30]
67 listasta [1, 3, 8, 12, 21, 22, 37]
68 listasta [1, 3, 8, 9, 20, 24, 38]
69 listasta [1, 3, 8, 9, 22, 28, 32]
Luku on suurin kolmisumma, minkä joukosta saa. Olen siis vain yhden vaivaisen luvun päässä.
Ohjelmani suoritus ei taida loppua ihan heti. Sen sijaan se voi löytää tapauksen 70 ja tulostaa sen, jos käy hyvä tuuri...
Saapa nähdä miten iltapäivä tässä kuluu. Raportoin tuloksesta, jahka saan sen. Ehkä hakua voisi optimoida jotenkin? Tämä on hauskaa pohtimista, kiitos tehtävästä.
Tässä vielä summat:
1 == 1
2 == 1 1
3 == 3
4 == 3 1
5 == 3 1 1
6 == 3 3
7 == 3 3 1
8 == 8
9 == 9
10 == 9 1
11 == 9 1 1
12 == 9 3
13 == 9 3 1
14 == 8 3 3
15 == 9 3 3
16 == 8 8
17 == 9 8
18 == 9 9
19 == 9 9 1
20 == 9 8 3
21 == 9 9 3
22 == 22
23 == 22 1
24 == 22 1 1
25 == 22 3
26 == 22 3 1
27 == 9 9 9
28 == 28
29 == 28 1
30 == 28 1 1
31 == 28 3
32 == 32
33 == 32 1
34 == 32 1 1
35 == 32 3
36 == 32 3 1
37 == 28 9
38 == 32 3 3
39 == 28 8 3
40 == 32 8
41 == 32 9
42 == 32 9 1
43 == 32 8 3
44 == 32 9 3
45 == 28 9 8
46 == 28 9 9
47 == 22 22 3
48 == 32 8 8
49 == 32 9 8
50 == 32 9 9
51 == 28 22 1
52 == 22 22 8
53 == 28 22 3
54 == 32 22
55 == 32 22 1
56 == 28 28
57 == 32 22 3
58 == 28 22 8
59 == 28 28 3
60 == 32 28
61 == 32 28 1
62 == 32 22 8
63 == 32 28 3
64 == 32 32
65 == 32 32 1
66 == 22 22 22
67 == 32 32 3
68 == 32 28 8
69 == 32 28 9
Anteeksi moka (jalka suussa tai näppiksellä), kyseessä ei tietenkään ole naivi leveyshaku, vaan best-first-tyylinen haku. Pienemmät listat järjestetään sen mukaan, kuinka ison luvun niillä enintään saa ja siitä jatketaan.
Tietokoneen aika on halpaa. Pitää vielä miettiä, miten ratkaisun saisi elegantimmin.
70 listasta [1, 4, 5, 15, 18, 27, 34]
1 == 1
2 == 1 1
3 == 1 1 1
4 == 4
5 == 5
6 == 5 1
7 == 5 1 1
8 == 4 4
9 == 5 4
10 == 5 5
11 == 5 5 1
12 == 4 4 4
13 == 5 4 4
14 == 5 5 4
15 == 15
16 == 15 1
17 == 15 1 1
18 == 18
19 == 18 1
20 == 18 1 1
21 == 15 5 1
22 == 18 4
23 == 18 5
24 == 18 5 1
25 == 15 5 5
26 == 18 4 4
27 == 27
28 == 27 1
29 == 27 1 1
30 == 15 15
31 == 27 4
32 == 27 5
33 == 27 5 1
34 == 34
35 == 34 1
36 == 34 1 1
37 == 27 5 5
38 == 34 4
39 == 34 5
40 == 34 5 1
41 == 18 18 5
42 == 34 4 4
43 == 34 5 4
44 == 34 5 5
45 == 27 18
46 == 27 18 1
47 == 27 15 5
48 == 18 15 15
49 == 34 15
50 == 34 15 1
51 == 18 18 15
52 == 34 18
53 == 34 18 1
54 == 34 15 5
55 == 27 27 1
56 == 34 18 4
57 == 34 18 5
58 == 27 27 4
59 == 27 27 5
60 == 27 18 15
61 == 34 27
62 == 34 27 1
63 == 27 18 18
64 == 34 15 15
65 == 34 27 4
66 == 34 27 5
67 == 34 18 15
68 == 34 34
69 == 34 34 1
70 == 34 18 18
mielenkiinnosta, hyvää jatkoa!
roskakuski mielestäsi jotenkin halveksittava ammatti?