Seuraa 
Viestejä950

Onpas vaikea ohjelmointitehtävä: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=junar . Brute forcella sain selvitettyä 5 ekaa tapausta. Mikä on tehokas tapa loppuihin neljään?

Kommentit (11)

Käyttäjä17244
Seuraa 
Viestejä180

Sorry, en viitsi zippiä ottaa ja siivoilla siitä malvaree pois. Heitä matriisi tänne 6 - 10 tehtävistä. Vaihtamisen heuristiikka lienee jotain että vaihda ekasta vektorin puolikkaasta isoimman ja toisesta puolikkaasta pienimmän paikka. Tehtävässä on hyötyä jos pienempi luku on ennen isompaa. Tehtävässä on hyötyä myös järjestyksestä ylipäänsä, eli kannattaa vaihtaa sellaisten lukujen paikka mikä lisää vektorin järjestystä eniten. Se miten tuon järjestyksen hyvyyden määrittää onkin kysymys, ekana tulee mieleen niiden lukuparien määrä jotka ovat oikeassa järjestyksessä, silloinhan kierrokset minimoitunee? Eli brutella optimoimaan järjestyksessä olevien lukuparien määrä eri vaihtocomboilla?

Mihin mun vanha tili hävis?

Eusa
Seuraa 
Viestejä17412

Tehtävässä ei taideta suoraan ilmaista, että junan lähtöpaikka (asema) on ennalta määrätty, vaikka renkaasta onkin kyse. Muutenhan esimerkissä voisi tehdä ekan vaihtovariantin, lähteä 1:n kohdalta ja selvitä yhdellä kierroksella.

Suurilla lukumäärillä voisi toimia, että vaihdetaan väärässä järjestyksessä olevat mahdollisimman paljon toisistaan eroavat mahdollisimman etäällä toisistaan sijaitsevat luvut...

Enpä minäkään nyt zippiä lataile.

Hienorakennevakio vapausasteista: (1+2¹+3²+5³+1/2¹*3²/5³)⁻¹ = 137,036⁻¹

Sisältö jatkuu mainoksen alla
Sisältö jatkuu mainoksen alla
pöhl
Seuraa 
Viestejä950

Joo. Ei taida kannattaa ladata zippiä. Käytännössä on siis annettu luku n ja luvut 1,...,n jossain järjestyksessä. Sitten tehdään vaihto ja kerätään luvut numerojärjestyksessä. Millainen algoritmi toimii, kun n on noin 100000. Jos ei uskalla ladata zippiä, niin voi vaikka generoida lukujen 1,2,...,100000 satunnaispermutaation ja kokeilla, kunka nopeasti numerot saa kerättyä.

Eusa
Seuraa 
Viestejä17412

pöhl kirjoitti:
Joo. Ei taida kannattaa ladata zippiä. Käytännössä on siis annettu luku n ja luvut 1,...,n jossain järjestyksessä. Sitten tehdään vaihto ja kerätään luvut numerojärjestyksessä. Millainen algoritmi toimii, kun n on noin 100000. Jos ei uskalla ladata zippiä, niin voi vaikka generoida lukujen 1,2,...,100000 satunnaispermutaation ja kokeilla, kunka nopeasti numerot saa kerättyä.

Mennään yhden kerran luvut läpi ja kerätään peräkkäisten lukujen jononpätkien katkeamisten määrä:

- esim. löytyy 1...2... seuraavaksi odotetaan tulisiko 3 ennen 4:ää, mutta tuleekin 4, lisätään laskuria

- palataan kohtaan, josta löytyi 2 ja odotetaan lukua 5...

- jos 5 löytyykin ennen 4:ää, taas katkesi ja lisätään laskuria

- palataan kohtaan, josta löytyi 2 ja odotetaan lukua 6...

- oletetaan, että 6 löytyy vasta 5:n jälkeen, jolloin jatketaan odottamalla 7 ja pelätään 8... :) jne

Järjestysten katkeamien määrä on tarvittavien kierrosten määrä.

Hienorakennevakio vapausasteista: (1+2¹+3²+5³+1/2¹*3²/5³)⁻¹ = 137,036⁻¹

Eusa
Seuraa 
Viestejä17412

Eusa kirjoitti:
pöhl kirjoitti:
Joo. Ei taida kannattaa ladata zippiä. Käytännössä on siis annettu luku n ja luvut 1,...,n jossain järjestyksessä. Sitten tehdään vaihto ja kerätään luvut numerojärjestyksessä. Millainen algoritmi toimii, kun n on noin 100000. Jos ei uskalla ladata zippiä, niin voi vaikka generoida lukujen 1,2,...,100000 satunnaispermutaation ja kokeilla, kunka nopeasti numerot saa kerättyä.

Mennään yhden kerran luvut läpi ja kerätään peräkkäisten lukujen jononpätkien katkeamisten määrä:

- esim. löytyy 1...2... seuraavaksi odotetaan tulisiko 3 ennen 4:ää, mutta tuleekin 4, lisätään laskuria

- palataan kohtaan, josta löytyi 2 ja odotetaan lukua 5...

- jos 5 löytyykin ennen 4:ää, taas katkesi ja lisätään laskuria

- palataan kohtaan, josta löytyi 2 ja odotetaan lukua 6...

- oletetaan, että 6 löytyy vasta 5:n jälkeen, jolloin jatketaan odottamalla 7 ja pelätään 8... :) jne

Järjestysten katkeamien määrä on tarvittavien kierrosten määrä.

Aina, kun katkeaa, pitää aloittaa tutkiminen ekasta mihinkään jonoon kuulumattomasta tietty... Tuleehan siinä askelia, mutta kuitenkin aika kiivaasti vähenee algoritmin edetessä. Indeksitaulukkoja smartisti hyödyntämällä voi varmasti optimoida...

Hienorakennevakio vapausasteista: (1+2¹+3²+5³+1/2¹*3²/5³)⁻¹ = 137,036⁻¹

pöhl
Seuraa 
Viestejä950

Eusa][quote=pöhl kirjoitti:
Järjestysten katkeamien määrä on tarvittavien kierrosten määrä.

Joo. Tämän minäkin huomasin. Pitäisi vaan keksiä nopea tapa laskea, montako kahden luvun vaihtoa alkuperäiseen jonoon voidaan tehdä, jotta kierroksia olisi minimimäärä.

pöhl
Seuraa 
Viestejä950

Hmm. Dilworthin lauseen mukaan minimihajotelmia nouseviin osajonoihin on yhtä monta kuin maksimaalisen nousevan osajonon alkioiden lukumäärä. Eli tämän mukaan vaihtotapojen lukumäärä on helppo laskea. Sitten pitää  vaan selvittää mikä on se minimimäärä kierroksia, joilla luvut tulee kerättyä. Toistaiseksi ei ole tullut mieleen muuta kuin brute force.

pöhl
Seuraa 
Viestejä950

Tein tällaisen yritelmän. Ei taida ratkaista kaikissa tapauksissa optimaalisesti. Varoitus: Lataa tuon tiedoston. Jos olet huolissasi tietoturvasta, älä aja ohjelmaa. Algoritmi etsii satunnaispermutaatioilla optimaalisinta vaihtotapaa. Alussa lasketaan tapojen lukumäärä. Jotain nopeampaa pitäisi keksiä.

import requests
from zipfile import ZipFile
import random

# Minimal descending sequence.
def mds(lines):
m = 0
n = len(lines)
lds = [1] * n
for i in range(n):
for j in range(i):
if lines[i] < lines[j] and lds[i] < lds[j] + 1:
lds[i] = lds[j] + 1
for i in range(n):
if m < lds[i]:
m = lds[i]
return m

def clean_tables(lines):
for i in range(1, len(lines)):
lines[i] = int(lines[i][:-1])
lines.pop(0)
return lines

def computerounds(lines):
roundnumber = 1
for i in range(1, len(lines)):
if lines.index(i) > lines.index(i + 1):
roundnumber += 1
return roundnumber

def get_lines_from_file(filenumber):
with open('/home/user/Downloads/junar' + str(filenumber) + '.in') as f:
lines = f.readlines()
lines = clean_tables(lines)
return lines

if __name__ == '__main__':
url = "https://www.ohjelmointiputka.net/tiedostot/junar.zip"
r = requests.get(url)
with ZipFile('/home/user/Downloads/junar.zip', 'r') as zipObj:
# Extract all the contents of zip file in different directory
zipObj.extractall("/home/user/Downloads/")
lines = get_lines_from_file(9)
print(lines)
nolines = len(lines)
print(nolines)
lkm = mds(lines)
print(lkm)
minimal = None
for k in range(10000):
i = random.randrange(len(lines))
j = random.randrange(len(lines))
if i != j:
lines[i], lines[j] = lines[j], lines[i]
temp = computerounds(lines)
if minimal == None or minimal > temp:
minimal = temp
print(nolines, minimal, lkm)
lines[i], lines[j] = lines[j], lines[i]
print(minimal)
1 / 0

Eusa
Seuraa 
Viestejä17412

pöhl kirjoitti:
Ei tämä nyt niin helppoa ole. Esimerkiksi ensimmäisessä kohdassa luvut ovat

10
6
1
4
10
7
2
3
9
5
8

Tuossa on 10 kaksi kertaa, mutta eka kymppi huomiotta näyttäisi 9 ja 4 vaihdettuna menevän kolmella poiminnalla...

Olisiko sellaisessa taktiikassa mieltä, että muodostetaan pisin mahdollinen yhden poiminnan sarja ja toiseksi vaihdokkaaksi loppuja parhaiten järjestävä...?

Hienorakennevakio vapausasteista: (1+2¹+3²+5³+1/2¹*3²/5³)⁻¹ = 137,036⁻¹

pöhl
Seuraa 
Viestejä950

Eusa kirjoitti:
Tuossa on 10 kaksi kertaa

Tehtävänantohan oli: Tiedostoissa ensimmäisellä rivillä on numerotaulujen määrä ja seuraavilla riveillä kunkin taulun numero järjestyksessä vasemmalta oikealle.

Suosituimmat

Uusimmat

Sisältö jatkuu mainoksen alla

Uusimmat

Suosituimmat