×

Opmerking

Vandaag heeft zich een storing bij HCC!net voorgedaan waardoor de mail niet kon worden opgehaald en er ook niet kon worden ingelogd op de web-mail. Op dit moment zijn wij nog bezig met het verhelpen van de storing, maar kan de mailserver wel weer worden bereikt en worden ingelogd.
  1. Johan Volkers
  2. Programmeren
  3. zaterdag 15 februari 2020
Programmeeropgave.
Waar hij vandaan komt weet ik niet meer.
Ik heb zelf niet direct een oplossing
Bijlagen
Geaccepteerd antwoord
Geaccepteerd antwoord In Afwachting Moderatie
Hint
In de Bilt werden logaritmen op grondtal 2 genoemd; realiseer je dat 2log(1000000) = 10 (bijna).


Beetje weinig. 2log(1000000) = bijna 24
  1. meer dan een maand geleden
  2. Programmeren
  3. # Permalink
Reacties (11)
Geaccepteerd antwoord In Afwachting Moderatie
In De Bilt werd de volgende oplossing genoemd:

for i = 1 to 1000000
do
lees de hele input file
om te controleren of i erin voorkomt
if antwoord = 'nee'
then
print i
fi
done

Verbeterde versie:

maak een hulp bestand met de getallen 1 t/m 1000000 in records van vaste lengte.
open de input en het hulp bestand
while getal = read( input)
do
seek record getal in het hulp bestand
en vervang het getal door NUL bytes
done
sluit de bestanden
filter alle NUL bytes uit het hulp bestand (bijv. met het 'tr' commando)
je houdt dan alle getallen over die niet in de input voorkomen.

Hint
In de Bilt werden logaritmen op grondtal 2 genoemd; realiseer je dat 2log(1000000) = 10 (bijna).
  1. meer dan een maand geleden
  2. Programmeren
  3. # 1
Geaccepteerd antwoord In Afwachting Moderatie
Via deze link bestanden opgave vindt je een zip-file met het inputbestand (met 1.000.001 - 80 getallen) en de 80 getallen die er niet in staan
  1. meer dan een maand geleden
  2. Programmeren
  3. # 2
Geaccepteerd antwoord In Afwachting Moderatie
Sorry. 2log(1000000) = 20, natuurlijk.
  1. meer dan een maand geleden
  2. Programmeren
  3. # 3
Geaccepteerd antwoord In Afwachting Moderatie
Nog een suggestie, die ik maar QuickCheck zal noemen:

Loop het invoerbestand af en schrijf de getallen naar twee hulpbestanden, zodanig dat de getallen kleiner dan het gemiddelde (500.000) in het ene bestand komen en de rest in het andere. Tel ondertussen het aantal elementen in elk deel. Als een van de hulpbestanden het maximale aantal elementen heeft, verwijder dat dan.

Roep de procedure recursief aan op de overblijvende hulpbestanden met het berekende minimum en maximum als parameter (als minimum en maximum gelijk zijn ben je klaar). Als je een hulpbestand overhoudt met 0 elementen, dan print je alle getallen tussen het minimum en maximum en verwijdert dat bestand.

Dit is geen sorteren, maar het effekt is het zelfde.
  1. meer dan een maand geleden
  2. Programmeren
  3. # 4
Geaccepteerd antwoord In Afwachting Moderatie
Een soort quicksort, maar dan op disk. Zal best wel werken.
  1. meer dan een maand geleden
  2. Programmeren
  3. # 5
Geaccepteerd antwoord In Afwachting Moderatie
Ik denk meer de volgende kant op:
- lees het bestand in, 10 getallen per keer
- sorteer ze en schrijf afwisselend een reeks van 10 weg op bestand A en bestand B
- lees vervolgens bestand A en B in en voeg de reeksen van 10 samen tot reeksen van 20 en schrijf die afwisselend weg op bestand C en D
- voeg op de zelfde manier C en D samen op E en F met reeksen van 40
- herhaal dit totdat je 1 reeks krijgt
- dan is het bestand gesorteerd en kun je vrij gemakkelijk de ontbrekende getallen bepalen
Aangezien in iedere run de grootte van de reeksen verdubbelt en het aantal halveert ben je in 20 runs door het sorteerprocess heen
Knuth spendeert in TAOCP hoofdstuk 5.4 aan external sorting
  1. meer dan een maand geleden
  2. Programmeren
  3. # 6
Geaccepteerd antwoord In Afwachting Moderatie
Ik heb ondertussen achterhaald waar het oorspronkelijke probleem vandaan komt en ik heb ook mijn toenmalige oplossing achterhaald.
Die werkt vrij snel (< 3 seconden) maar schrijft wel 1730 tijdelijke bestanden weg....
En dat op een echte harddisk (dwz geen SSD).
Mijn oplossing destijds was ongeveer die van Dan the Man
- verdeel het oorspronkelijke bestand in twee bestanden
- bestand 1: alles in de range 1..500000
- bestand 2: alles in de range 500.001 -- 1.000.000
Verwerk (via recursie) vervolgens de twee bestanden.
Omdat ik weet hoeveel regels in de bestanden terecht komen kan ik het verwerken van bestanden die net zoveel regels bevatten als de range groot is skippen. Dat levert plm. 800 bestanden op die niet verder verwerkt hoeven te worden.
Dit kan omdat duplicaten niet voorkomen.

Het oorspronkelijke probleem komt uit het boek van Jon Bentley (Programming Pearls (1999) --nog steeds een aanrader en het is ondertussen op internet) te vinden.
  1. meer dan een maand geleden
  2. Programmeren
  3. # 7
Geaccepteerd antwoord In Afwachting Moderatie
Het testbestand wijkt af van de specificatie van het probleem: het bevat zowel de getallen 0 als 1000000:-(
  1. meer dan een maand geleden
  2. Programmeren
  3. # 8
Geaccepteerd antwoord In Afwachting Moderatie
Het probleem is als 'opgelost' gemarkeerd; hierbij een poging om een oplossing te vinden.... Om te beginnen verander ik het probleem maar zodat het draait om getallen van 6 cijfers (000.000 tot en met 999.999) -- zie mijn vorige opmerking.

Dan verzon ik iets wat je kunt doen met een array van 10 gehele getallen en dat het bestand regel voor regel inlezen, eventuele voorloopnullen aanbrengen en tellen hoe vaak je de cijfers 0 t/m 9 aantrof. Noem het cijfer dat het minste voorkwam c.

De volgende doorgang splits lees je het invoerbestand weer in en schrijft de getallen naar een zevental hulpbestanden: het eerste bestand ontvangt de getallen waar op de eerste positie een c voorkomt,... en het zesde bestand de getallen met dat cijfer op de zesde positie; het zevende bestand krijgt de getallen waar dat cijfer helemaal niet in voorkomt. Sommige getallen komen inderdaad in meerdere bestanden.

In de derde stap kijk je hoe groot de hulpbestanden zijn (zonder ze te lezen), vergeleken met het aantal dat ze zouden hebben als alle getallen van 000.000 t/m 999.999 in de invoer voorkwamen. Als dat aantal gelijk is, kun je het hulpbestand verwijderen, anders moet je het recursief verder doorzoeken.

De recursie is de vierde stap: daarbij gebruik je een array van 1 bits (booleans, flags) die initieel 0 zijn, waarin je het c-e element op 1 zet. De eerste stap wijzigen we zodanig dat cijfers waarvoor het bitmasker een 1 bevat moeten worden overgeslagen. Als alle bits in het masker op 1 staan moet de recursie stoppen. We hebben nog een extra parameter die initieel ook 000.000 is, maar waarvan je het i-e cijfer vervangt door een c. Als de recursie klaar is, zit je met een leeg hulpbestand en druk je die parameter af, die een ontbrekend getal moet zijn.

Na de recursieve aanroep moet je nog de hulpbestanden verwijderen.

Discussie: als je alle bestanden twee keer doorleest hoef je minder hulpbestanden te maken dan wanneer je gewoon bij het eerste cijfer begint. In dat geval hoef je elk bestand maar één keer door te lezen. Wat is efficiënter?
  1. 3 weken geleden
  2. Programmeren
  3. # 9
Geaccepteerd antwoord In Afwachting Moderatie
Hierbij de hierboven aangeduide "oplossing" in de vorm van Java code. Het is niet de meest snelle, maar gebruikt inderdaad een array van 10 integers (en een array met de namen van de tijdelijke bestanden). Om een nette uitvoer te krijgen moet je de getallen sorteren en duplicaten verwijderen.
Bijlagen
  1. 5 dagen geleden
  2. Programmeren
  3. # 10
  • Pagina :
  • 1


Er zijn nog geen reacties op dit bericht.
Reageer als een van de eersten op dit bericht!
Nog geen HCC-gebruikersaccount aangemaakt? Klik dan hier.

Inloggen