Fórum studentů MFF UK

od **hon2a** » 20. 1. 2010 17:19

Jeste jsem zapomnel obecne a osobni poznamky k predchozimu zadani.

Na reseni jsou stale tri hodiny, zacinaji se pocitat po skonceni dotazu po vysvetleni zadani. Internet se vypina jeste pred zadanim ulohy, je tedy pouze chvilka na stazeni testovacich vstupu, pripadne prednasek a jinych materialu. Pouzivat vlastni pocitac neni povoleno, stejne jako je zakazano chmatat na pocitac po skonceni prislusnych tri hodin.

Zadani mi prislo jednodussi nez nektera jina z tohoto fora, ktera jsem si zkusebne resil. Kod jsem mel napsany za ~2hod., pak jsem chvilku ladil triviality a pak pul hodiny to, ze jsem se upsal v implementaci prikazu negace, ktery byl pouzit pouze v poslednim testovacim vstupu. Kdybych si na to udelal unit test, tak bych skoro celou tu pulhodinu usetril... Prede mnou odchazeli asi 4 dalsi resitele, ale kolik lidi to udelalo celkove nevim.

Pro uspesne splneni bylo potreba jen vhodne si navrhnout datove struktury, umet jednoduchou praci s textem a naproste zaklady vicevlaknoveho programovani.

od **hon2a** » 20. 1. 2010 17:06

Interpret Assembleru

Program dostane kod v "assembleru" (netusim, nakolik se podoba skutecnemu assembleru, protoze jsem v nem nikdy nepsal) a ma ho provest. Kazdy radek kodu obsahuje jeden prikaz (a jeho parametry) navzajem oddelene libovolnym poctem mezer. Jako parametry dostane program nazev vstupniho souboru, pocet registru a velikost pameti. Tezistem ulohy je nacteni kodu do rozumne struktury a jeho spravne provadeni, ne nacitani vstupu a podobnych prkotin, takze je mozne vlozit vstupni argumenty, pripadne vstup, primo do kodu. Registry a pamet jsou proste misto na kupu integeru, "velikost pameti" je pocet cisel v ni, stejne jako u poctu registru.

Prikazy:

MOV kam co/odkud -- presune co/odkud kam
ADD kcemu co -- pricte co kcemu a da do kcemu
SUB odceho co -- odecte co odceho a da do odceho
DIV co cim -- celociselne vydeli co cim a da do co
MOD co cim -- da do co zbytek po deleni co cim
MUL co cim -- vynasobi co cim a da do co
NEG co -- da do co nulu, pokud je co rovne nule, jinak jednicku
PRINT co -- vytiskne co na konzoli
SEQ ridici_registr az_po -- sekvence (viz nize)
ENDSEQ -- konec sekvence
PAR ridici_registr az_po -- paralelni sekvence (viz nize)
ENDPAR -- konec paralelni sekvence

Promenne:

kam, co, odkud, cim, az_po mohou byt celociselne konstanty, adresy registru, adresy v pameti
kam, co mohou byt adresy registru, adresy v pameti

Typy promennych (format):

celociselna konstanta: 0, 42, -4
adresa registru: r0, r13
adresa v pameti: [0], [r0]

Sekvence:

0. i := 0, vysledek := 0
1. ridici_registr := i
2. provede sekvenci prikazu az do odpovidajiciho konce sekvence (vcetne vnorenych sekvenci atd.)
3. if (ridici_registr != 0) { vysledek := 1 }
4. i++
5. if (i > az_po) { goto 6. } else { goto 1. }
6. ridici_registr := vysledek, KONEC

Paralelni sekvence:

Podobna sekvenci, ale sekvence prikazu se provadi paralelne pro vsechny hodnoty ridici promenne (pro i od 0 do az_po vcetne se spusti samostatna vlakna). Kazdy paralelni beh ma vlastni kopii registru (tzn. po dobehnuti vsech paralelnich behu bude hodnota vsech registru krome ridiciho stejna jako pred probehnutim).

----------------------

Reseni:

Kód: Vybrat vše

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

namespace AssemblerParser
{
    class MyException : ApplicationException
    {
        protected string message;
        public new string Message { get { return this.message; } }

        public MyException(string s) : base()
        {
            this.message = s;
        }
    }

    enum AssemblerKeyword { END, MOV, ADD, SUB, DIV, MOD, MUL, NEG, PRINT, SEQ, PAR };

    class AssemblerCommand
    {
        public readonly AssemblerKeyword keyword;

        public AssemblerCommand(string keyword)
        {
            if (keyword == "MOV")
            {
                this.keyword = AssemblerKeyword.MOV;
            }
            else if (keyword == "ADD")
            {
                this.keyword = AssemblerKeyword.ADD;
            }
            else if (keyword == "SUB")
            {
                this.keyword = AssemblerKeyword.SUB;
            }
            else if (keyword == "DIV")
            {
                this.keyword = AssemblerKeyword.DIV;
            }
            else if (keyword == "MOD")
            {
                this.keyword = AssemblerKeyword.MOD;
            }
            else if (keyword == "MUL")
            {
                this.keyword = AssemblerKeyword.MUL;
            }
            else if (keyword == "NEG")
            {
                this.keyword = AssemblerKeyword.NEG;
            }
            else if (keyword == "PRINT")
            {
                this.keyword = AssemblerKeyword.PRINT;
            }
            else if (keyword == "SEQ")
            {
                this.keyword = AssemblerKeyword.SEQ;
            }
            else if (keyword == "ENDSEQ")
            {
                this.keyword = AssemblerKeyword.END;
            }
            else if (keyword == "PAR")
            {
                this.keyword = AssemblerKeyword.PAR;
            }
            else if (keyword == "ENDPAR")
            {
                this.keyword = AssemblerKeyword.END;
            }
        }
    }

    enum ParamType { Constant, Register, Index, RegisterIndex };

    class Param
    {
        public readonly ParamType type;
        public readonly int value;

        public Param(string s)
        {
            bool typeAssigned = false;
            if (s[0] == '[')
            {
                this.type = ParamType.Index;
                typeAssigned = true;
                s = s.Substring(1, s.Length - 2);
            }
            if (s[0] == 'r')
            {
                this.type = typeAssigned ? ParamType.RegisterIndex : ParamType.Register;
                s = s.Substring(1);
            }
            this.value = Int32.Parse(s);
        }

        public override string ToString()
        {
            switch (this.type)
            {
                case ParamType.RegisterIndex:
                    return "[r" + this.value + "]";
                case ParamType.Index:
                    return "[" + this.value + "]";
                case ParamType.Register:
                    return "r" + this.value;
                default:
                    return this.value.ToString();
            }
        }
    }

    class AssemblerLine
    {
        public readonly AssemblerCommand command;
        public AssemblerKeyword Keyword { get { return this.command.keyword; } }
        public readonly Param param1;
        public readonly Param param2;
        public AssemblerCode code;
        public bool IsSequence { get { return (this.Keyword == AssemblerKeyword.SEQ) || (this.Keyword == AssemblerKeyword.PAR); } }

        public AssemblerLine(string line)
        {
            string[] words = line.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            this.command = new AssemblerCommand(words[0]);
            switch (this.Keyword)
            {
                case AssemblerKeyword.MOV:
                case AssemblerKeyword.ADD:
                case AssemblerKeyword.SUB:
                case AssemblerKeyword.DIV:
                case AssemblerKeyword.MOD:
                case AssemblerKeyword.MUL:
                case AssemblerKeyword.SEQ:
                case AssemblerKeyword.PAR:
                    this.param1 = new Param(words[1]);
                    this.param2 = new Param(words[2]);
                    break;
                case AssemblerKeyword.NEG:
                case AssemblerKeyword.PRINT:
                    this.param1 = new Param(words[1]);
                    break;
                default:
                    break;
            }
        }

        public override string ToString()
        {
            switch (this.Keyword)
            {
                case AssemblerKeyword.MOV:
                case AssemblerKeyword.ADD:
                case AssemblerKeyword.SUB:
                case AssemblerKeyword.DIV:
                case AssemblerKeyword.MOD:
                case AssemblerKeyword.MUL:
                case AssemblerKeyword.SEQ:
                case AssemblerKeyword.PAR:
                    return this.Keyword.ToString() + " " + this.param1.ToString() + " " + this.param2.ToString();
                case AssemblerKeyword.NEG:
                case AssemblerKeyword.PRINT:
                    return this.Keyword.ToString() + " " + this.param1.ToString();
                default:
                    return "";
            }
        }
    }

    class AssemblerCode
    {
        public readonly List<AssemblerLine> code;

        protected AssemblerCode()
        {
            this.code = new List<AssemblerLine>();
        }

        public static AssemblerCode FromReader(TextReader r)
        {
            AssemblerCode ret = new AssemblerCode();
            string line;
            while ((line = r.ReadLine()) != null)
            {
                AssemblerLine codeLine = new AssemblerLine(line);
                if (codeLine.IsSequence)
                {
                    codeLine.code = AssemblerCode.FromReader(r);
                }
                if (codeLine.Keyword == AssemblerKeyword.END)
                {
                    break;
                }
                ret.code.Add(codeLine);
            }
            return ret;
        }

        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();
            foreach (AssemblerLine line in this.code)
            {
                builder.AppendLine(line.ToString());
                if (line.IsSequence)
                {
                    builder.Append(line.code.ToString());
                    builder.AppendLine("END");
                }
            }
            return builder.ToString();
        }
    }

    enum LocationType { Register, MemorySlot };

    class Location
    {
        public readonly LocationType type;
        public readonly int index;

        public Location(LocationType type, int index)
        {
            this.type = type;
            this.index = index;
        }
    }

    class Assembler
    {
        protected int[] registers;
        protected int[] memory;

        public Assembler(int registerCount, int[] memory)
        {
            this.registers = new int[registerCount];
            this.memory = memory;
        }

        public Assembler(Assembler parent)
        {
            this.registers = new int[parent.registers.Length];
            this.memory = parent.memory;
            Array.Copy(parent.registers, this.registers, this.registers.Length);
        }

        protected int GetValue(Param param)
        {
            if (param.type == ParamType.Constant)
            {
                return param.value;
            }
            return this.GetValue(this.GetLocation(param));
            /*
            switch (param.type)
            {
                case ParamType.RegisterIndex:
                    return this.memory[this.registers[param.value]];
                case ParamType.Register:
                    return this.registers[param.value];
                case ParamType.Index:
                    return this.memory[param.value];
                default:
                    return param.value;
            }
            */
        }

        protected int GetValue(Location location)
        {
            switch (location.type)
            {
                case LocationType.Register:
                    return this.registers[location.index];
                default:
                    return this.memory[location.index];
            }
        }

        protected Location GetLocation(Param param)
        {
            switch (param.type)
            {
                case ParamType.RegisterIndex:
                    return new Location(LocationType.MemorySlot, this.registers[param.value]);
                case ParamType.Register:
                    return new Location(LocationType.Register, param.value);
                case ParamType.Index:
                    return new Location(LocationType.MemorySlot, param.value);
                default:
                    return null;
            }
        }

        protected void Set(Location location, int value)
        {
            switch (location.type)
            {
                case LocationType.MemorySlot:
                    this.SetMemory(location.index, value);
                    break;
                case LocationType.Register:
                    this.SetRegister(location.index, value);
                    break;
            }
        }

        protected void SetRegister(int index, int value)
        {
            if (index >= this.registers.Length)
            {
                throw new MyException("Index out of bounds (registers). Try adding more registers.");
            }
            this.registers[index] = value;
        }

        protected void SetMemory(int index, int value)
        {
            if (index >= this.memory.Length)
            {
                throw new MyException("Index out of bounds (memory). Try adding more memory.");
            }
            this.memory[index] = value;
        }

        public bool Eval(AssemblerCode code)
        {
            return this.Eval(code, null);
        }

        public bool Eval(AssemblerCode code, Location watchedIndex)
        {
            foreach (AssemblerLine line in code.code)
            {
                switch (line.Keyword)
                {
                    case AssemblerKeyword.MOV:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.ADD:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) + this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.SUB:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) - this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.DIV:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) / this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.MOD:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) % this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.MUL:
                        this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) * this.GetValue(line.param2));
                        break;
                    case AssemblerKeyword.SEQ:
                        bool alwaysZero = true;
                        for (int i = 0; i <= this.GetValue(line.param2); ++i)
                        {
                            this.Set(this.GetLocation(line.param1), i);
                            this.Eval(line.code);
                            if (this.GetValue(line.param1) != 0)
                            {
                                alwaysZero = false;
                            }
                        }
                        this.Set(this.GetLocation(line.param1), alwaysZero ? 0 : 1);
                        break;
                    case AssemblerKeyword.PAR:
                        int param2 = this.GetValue(line.param2);
                        int retVal = 0;
                        if (param2 >= 0)
                        {
                            int iterations = param2 + 1;
                            Thread[] threads = new Thread[iterations];
                            AssemblerWorker[] workers = new AssemblerWorker[iterations];
                            for (int i = 0; i < iterations; ++i)
                            {
                                this.Set(this.GetLocation(line.param1), i);
                                Assembler assembler = new Assembler(this);
                                workers[i] = new AssemblerWorker(assembler, line.code, this.GetLocation(line.param1));
                                threads[i] = new Thread(workers[i].Start);
                                threads[i].Start();
                            }
                            foreach (Thread thread in threads)
                            {
                                thread.Join();
                            }
                            foreach (AssemblerWorker worker in workers)
                            {
                                if (worker.errorMessage != null)
                                {
                                    throw new MyException(worker.errorMessage);
                                }
                                if (worker.result)
                                {
                                    retVal = 1;
                                }
                            }
                        }
                        this.Set(this.GetLocation(line.param1), retVal);
                        break;
                    case AssemblerKeyword.NEG:
                        this.Set(this.GetLocation(line.param1), (this.GetValue(line.param1) == 0) ? 1 : 0);
                        break;
                    case AssemblerKeyword.PRINT:
                        Console.WriteLine(this.GetValue(line.param1));
                        break;
                    default:
                        break;
                }
            }
            bool ret = false;
            if (watchedIndex != null)
            {
                if (this.GetValue(watchedIndex) != 0)
                {
                    ret = true;
                }
            }
            return ret;
        }
    }

    class AssemblerWorker
    {
        protected Assembler assembler;
        protected AssemblerCode code;
        protected Location watchedRegister;
        public bool finished;
        public string errorMessage;
        public bool result;

        public AssemblerWorker(Assembler assembler, AssemblerCode code, Location watchedRegister)
        {
            this.assembler = assembler;
            this.code = code;
            this.watchedRegister = watchedRegister;
            this.finished = false;
            this.errorMessage = null;
        }

        public void Start()
        {
            try
            {
                this.result = this.assembler.Eval(this.code, watchedRegister);
            }
            catch (MyException e)
            {
                this.errorMessage = e.Message;
            }
            this.finished = true;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            string inputFilePath = "in8.txt";
            int registerCount = 20;
            int memorySize = 1000;

            TextReader r = new StreamReader(inputFilePath);
            AssemblerCode code = AssemblerCode.FromReader(r);
            r.Close();

            int[] memory = new int[memorySize];
            Assembler assembler = new Assembler(registerCount, memory);
            try
            {
                assembler.Eval(code);
            }
            catch (MyException e)
            {
                Console.WriteLine(e.Message);
            }

            //Console.WriteLine(code.ToString());
            Console.ReadLine();
        }
    }
}

-------------------------

Testovaci vstupy:

1) vystup: cisla od 0 do 100 a jednicka

Kód: Vybrat vše

SEQ r0 100
  PRINT r0
ENDSEQ
PRINT r0

2) vystup: cisla od 0 do 100 a nula

Kód: Vybrat vše

SEQ r0 100
  PRINT r0
  MOV r0 0
ENDSEQ
PRINT r0

3) vystup: cisla od 0 do 100 v nahodnem poradi a jednicka

Kód: Vybrat vše

PAR r0 100
  PRINT r0
ENDPAR
PRINT r0

4) vystup: cisla od 0 do 100 v nahodnem poradi a nula

Kód: Vybrat vše

PAR r0 100
  PRINT r0
  MOV r0 0
ENDPAR
PRINT r0

5) vystup: nasobky sedmi od 0 do 700

Kód: Vybrat vše

MOV r1 7
PAR r0 100
  MOV [r0] r0
  MUL [r0] r1
ENDPAR
SEQ r0 100
  PRINT [r0]
ENDSEQ

6) vystup: 1

Kód: Vybrat vše

MOV r1 121
PAR r0 r1
  MUL r0 r0
  SUB r0 r1
  NEG r0
ENDPAR
PRINT r0

7) vystup: 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55

Kód: Vybrat vše

PAR r0 10
  MOV [r0] 0
  SEQ r1 r0
    ADD [r0] r1
  ENDSEQ
ENDPAR
SEQ r0 10
  PRINT [r0]
ENDSEQ

8) vystup: dvojice cisel (x_i, y_i) pro i od 0 do 20, kde x_i == i a y_i ma hodnotu 0 pokud x_i neni prvocislo a 1, pokud je

Kód: Vybrat vše

PAR r0 20
  MOV r2 r0
  SUB r2 3
  PAR r1 r2
    ADD r1 2
    ADD r2 3
    MOD r2 r1
    MOV r1 r2
    NEG r1
  ENDPAR
  MOV [r0] r1
  NEG [r0]
ENDPAR
SEQ r0 20
  PRINT r0
  PRINT [r0]
ENDSEQ

od **vladoyak** » 9. 4. 2008 23:46

9. 4. 2008
Ahoj, po dlhom case opat jeden zapoctovy test. Prisiel sam Mgr. Jezek a dal priklad, ktory tu uz je popisany, konkr. ten s logikou (nacitanie suboru, vypis tych ohodnoteni kedy je vyraz pravdivy a prevod do DNF). Dokonca nam rozdal popis prikladu zo samotneho fora

Robil som to takto: zadany vyraz som ulozil do stromu (v uzloch logicke operatory, v listoch premenne), pomocou neho som urcil pravdive ohodnotenia a ziskal prvy pozadovany subor. Prevod do DNF je uz potom hracka.

Zacali sme 17:20, povodny deadline bol 21:30!! Prvy clovek odovzdaval tesne po tomto termine, ja okolo tristvrte. Dalej neviem, tvrdnut v skole o desiatej vecer tiez nie je ta najkrajsia predstava

Prajem vela stastia dalsim odvazlivcom

od **mgrafi** » 14. 2. 2008 17:59

14. 2.2007
Ani dnes Mgr. Jezek "nesklamal". Naprogramovat sme mali "Bison", teda program, ktory zo vstupu nacita LR(0) gramatiku a na vystup da popis stavoveho automatu, ktory robi semanticku analyzu, t.j. popisy stavov a prechodovej funkcie.
Jednym z testovacich vstupov bol Mlaskal.y (absolventi Principov prekladacov vedia, o com hovorim

)
Bolo nas tam 9 a po 5 hodinach kodenia to dokoncene nemal nikto! Viacerym nam to ako-tak chodilo, no nikomu sa do "bodky a do pismena" nezhodovali vystupy s tymi referencnymi.
Postup: Nechce sa mi to moc rozpisovat, malo sa to robit cez "bodkovu" ("teckovu") notaciu => tranzitivny uzaver prepisovacich pravidiel daneho stavu, zostavenie prechodovej funkcie cez symboly za bodkou a pripadna redukcia automatu. Viz Yaghobove slajdy http://ulita.ms.mff.cuni.cz/pub/predn/p ... -saatr.ppt

+Info: Par terminov by sa este malo objavit v priebehu semestra a potom aj v letnom skuskovom.

od **Medved** » 11. 2. 2008 17:24

11.2.2008

Myslim, ze stejne jako minule (asi proto, ze ho tady nikdo nenapsal).

Na vstupu jsou dva parametry
1) "Vstup.pripona"
2) "Vystup_bez_pripony"

Vasim ukolem je nacist vstupni soubor a vygenerovat dva soubory vystupni: "Vystup_bez_pripony.eval" a "Vystup_bez_pripony.result".

Ve vstupnim souboru je vyraz, ktery ma jeden z nasledujicich tvaru:
( V1 op V2 ) - kde V1, V2 jsou vyrazy a op z {&,|,<->,->}
! V3 - kde V3 je vyraz
xy - neboli promenna, to je posloupnost pismen a cislic nezacinajici cislici

Z cehoz tedy mimojine vyplyva, ze treba ! ! ! xy je vyraz, ale ( xy ) neni vyraz. Oddelene je to presne jak pisu, tzn. kazdy atom mezerama z obou stran, vstup je na jednom radku.
Pocet promennych ve vstupnim souboru muze byt vetsi, nez 32, ale je mensi, nez 64.

Dale byly definovany logicke operace & (konjunkce), | (disjunkce), -> (implikace), <-> (ekvivalence) a ! (negace) a jejich pravdivostni tabulky (to tady psat nehodlam).

Ukolem je nacist vstupni soubor a vyhodnotit je pro vsechny mozne kombinace promennych ze Z_2^n, kde n je pocet tech promennych a do souboru "Vystup_bez_pripony.eval" vypsat jen ty kombinace, kde je ohodnoceni pravdive. Kazdou kombinaci na jeden radek. Dulezite bylo poradi vyhodnocovani, promenne si seradite podle jejich prvniho vyskytu ve vstupnim souboru a pak jedete takhle
a b e c d
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
...
1 1 1 1 1
Proste, kdyz si to vezmete jako cislo ze Z_2, tak porad pricitate jednicku. Na prvnim radku toho souboru jsou vypsany promenne, tak jak je mate serazeny.

Priklad: kdyz ve vstupnim souboru je ( a -> ( b | c ) )
Tak na vystupu bude
0 0 0
0 0 1
0 1 0
0 1 1
1 0 1
1 1 0
1 1 1
Tedy skoro vse

Druha cast toho ukolu je vygenerovat soubor "Vystup_bez_pripony.result", kde je disjunktivni normalni forma (DNF). To udelate tak, ze zpracujete kazdy radek souboru "Vystup_bez_pripony.eval" a vygenerujete vyrazy (budu znacit A,B,C,...), ktere spojite disjunkci.

Takze neco jako: A | B | C | D | E
Vyraz musi byt spravne uzavorkovany, asociovano vzdy zprava, takze ve skutecnosti to bude: ( A | ( B | ( C | ( D | E ) ) ) )

Kazde velke pismeno reprezentuje jeden radek souboru "Vystup_bez_pripony.eval" a vypada takhle
( a & b & c & d & e ) kde a-e jsou jednotlive promenne. Takhle by to bylo pro ohodnoceni 1 1 1 1 1, kdyz by nekde byla 0, tak tam bude negace, takze 1 0 1 0 1 bude ( a & ! b & c & ! d & e ) a opet uzavorkovane asociativne zprava, takze ( a & ( ! b & ( c & ( ! d & e ) ) ) )

Uzavorkovani je dulezite, protoze jako kontrola se porovnavaji vase vysledky s tim, co si pan Jezek s sebou prinesl. A tak jak je to nadefinovano jsou vystupy jednoznacne. Uzavorkovani pro me bylo nejvetsi peklo, cele jsem to mel asi za hodku a pul a dalsi 2 hodiny jsem ladil zavorky a stejne mi to nakonci nefungovalo uplne, jak melo.

Testovalo se to i na dost velkych datech a taky na tom, ze to co vygenerujete je logicky vyraz, takze se to na nej da znova pustit a vylezt musi uplne to stejne. Proto se to muselo vypsat opet na jeden radek a oddelene ze vsech stran mezerama.

Jeste nas pan Jezek varoval, abychom nepouzivali sve znalosti z logiky, ze s tim nema dobre zkusenosti

Uspesnost nevim, ale spis to lidi vzdavali sami...rekl bych, ze tak pulka dala.

od **MrCooper** » 5. 2. 2008 11:16

graham realyze píše:Celkove zatim asi jedno z nejlehcich zadani (muj subjektivni dojem).

Souhlasim, miny byly pouze pracne. Hodne mi pomohlo http://dsrg.mff.cuni.cz/~jezek/HousenkaSimple.zip , zejmena nacitani klaves, jejich zpracovani a to, ze goto se bat nemam

od **Polik** » 4. 2. 2008 22:25

Tedy lepší termín než dnes odpoledne jsem si vybrat nemohl... ale C#.NET mne potěšil, měl třídu na regexpy

Passed. Kdyžtak můžu vyhrabat jakéstakés řešení.

od **Joe** » 4. 2. 2008 21:56

Zadani odpoledniho terminu vypadalo asi nejak nasledovne:
Naprogramovat jednoduchy SQL server. Na vstupu bylo jmeno vstupniho souboru s sql prikazem a jmeno vystupniho souboru (tedy program se spoustel napr. nejak takhle: "server.exe query1.q outputfile.txt"). SQL prikaz obsavoval cast SELECT, FROM a mohl a nemusel obsahovat cast WHERE. Cast WHERE mohla obsahovat dva typy omezeni:
a) sloupec = 'hodnota'
b) tabulka1.sloupec = tabulka2.sloupec
Soubor s dotazem vypadal napr. takhle:

Kód: Vybrat vše

SELECT e.FirstName & e.LastName & o.OrderDate & c.ContactName & c.CompanyName FROM o = Orders & e = Employees & c = Customers WHERE o.EmployeeID = e.EmployeeID & o.CustomerID = c.CustomerID

K dispozici byly dale soubory s daty jednotlivych tabulek - Employees, Customers ... Ty obsahovaly na zacatku vycet dvojic <typ, nazev sloupce> tabulky a pak data tabulky oddelene strednikem. Nejak takhle:

Kód: Vybrat vše

Columns:
string Address
DateTime BirthDate
string City
PRIMARY_KEY int EmployeeID
string FirstName
string LastName
int? ReportsTo
string Title
Data:
507 - 20th Ave. E.<br />Apt. 2A;8.12.1948 0:00:00;Seattle;1;Nancy;Davolio;2;Sales Representative
908 W. Capital Way;19.2.1952 0:00:00;Tacoma;2;Andrew;Fuller;NULL;Vice President, Sales
722 Moss Bay Blvd.;30.8.1963 0:00:00;Kirkland;3;Janet;Leverling;2;Sales Representative
4110 Old Redmond Rd.;19.9.1937 0:00:00;Redmond;4;Margaret;Peacock;2;Sales Representative
14 Garrett Hill;4.3.1955 0:00:00;London;5;Steven;Buchanan;2;Sales Manager
Coventry House<br />Miner Rd.;2.7.1963 0:00:00;London;6;Michael;Suyama;5;Sales Representative
Edgeham Hollow<br />Winchester Way;29.5.1960 0:00:00;London;7;Robert;King;5;Sales Representative
4726 - 11th Ave. N.E.;9.1.1958 0:00:00;Seattle;8;Laura;Callahan;2;Inside Sales Coordinator
7 Houndstooth Rd.;27.1.1966 0:00:00;London;9;Anne;Dodsworth;5;Sales Representative

Otaznik za typem znamena, ze dany sloupec muze met hodnotu NULL. Vystupem pak mel byt vyhodnoceny SQL vyraz. Mel vypadat napr. asi nejak takhle:

Kód: Vybrat vše

Columns:
string ContactName
string CompanyName
Data:
Maria Anders;Alfreds Futterkiste;
Ana Trujillo;Ana Trujillo Emparedados y helados;
Antonio Moreno;Antonio Moreno Taquer├¡a;
Thomas Hardy;Around the Horn;
Christina Berglund;Berglunds snabbk├╢p;
Hanna Moos;Blauer See Delikatessen;
Fr├⌐d├⌐rique Citeaux;Blondesddsl pere et fils;
Mart├¡n Sommer;B├│lido Comidas preparadas;
Laurence Lebihan;Bon app';
Elizabeth Lincoln;Bottom-Dollar Markets;
Victoria Ashworth;B's Beverages;
Patricio Simpson;Cactus Comidas para llevar;
Francisco Chang;Centro comercial Moctezuma;
Pedro Afonso;Com├⌐rcio Mineiro;
Elizabeth Brown;Consolidated Holdings;
Sven Ottlieb;Drachenblut Delikatessen;
Janine Labrune;Du monde entier;
Ann Devon;Eastern Connection;
Roland Mendel;Ernst Handel;
Aria Cruz;Familia Arquibaldo;
Diego Roel;FISSA Fabrica Inter. Salchichas S.A.;
Martine Ranc├⌐;Folies gourmandes;
Maria Larsson;Folk och f├ñ HB;
Peter Franken;Frankenversand;
Carine Schmitt;France restauration;

Bylo toho zase hodne na psani, hlavne pri joinovani tabulek. Kdyz jsem odchazel (asi 1,5 hod po puvodne planovanem terminu), tak to tam jeste nikdo nemel, tak by me docela zajimalo, kolik lidi to vlastne nakonec dalo. Hodne zdaru!

od **Tom** » 4. 2. 2008 18:56

graham realyze píše:Tak zadani pro 4. 2. dopoledni termin bylo "konzolove hledani min".

Pry ze solitaire uz byl, tak ted je na rade tohle. Ze zacatku jsem valil oci, protoze ten clovek popsal dve tabule ruznymi pravidly a podobne (chtel, abychom pouzivai ruzne barvy pro ruzne stavy policek, pak tam mohla byt na policku vlajecka nebo otaznicek, kdyz se zmacklo F1, melo se docasne odkryt vsechno, kdyz se zmacklo X, fungovalo to jako soucasne zmacknuti L i P tlacitka mysi ve wokenich minach (odkryti vic policek najednou) atd.)

Ale zas tak tezky to nebylo. Teda respektive myslenkove skoro vubec, jen to bylo docela pracne.

Celkove zatim asi jedno z nejlehcich zadani (muj subjektivni dojem).

Zdravim.

Co se týče mě, největší problém byl zjistit, jak to vlatně na té konzoli udělat (Ježek nám napsal nějaké funkce, které by se nám mohli hodit. Většinu jsem použil. K zadání bych chtěl ještě doplnit, že program se volal:

Kód: Vybrat vše

MojeMiny.exe sirka_tabulky vyska_tabulky celkovy_pocet_min

Pro představu přidávám svůj zdroják. Upozorňuji, že kdybych to dělal doma, tak by to mělo tak poloviční velikost (dělané metodou Ctrl+C, Ctrl+V). Na nějaké private, public atd., na to se tu nehraje, takže tak vypadá i můj zdroják.

od **graham realyze** » 4. 2. 2008 14:43

Tak zadani pro 4. 2. dopoledni termin bylo "konzolove hledani min".

Pry ze solitaire uz byl, tak ted je na rade tohle. Ze zacatku jsem valil oci, protoze ten clovek popsal dve tabule ruznymi pravidly a podobne (chtel, abychom pouzivai ruzne barvy pro ruzne stavy policek, pak tam mohla byt na policku vlajecka nebo otaznicek, kdyz se zmacklo F1, melo se docasne odkryt vsechno, kdyz se zmacklo X, fungovalo to jako soucasne zmacknuti L i P tlacitka mysi ve wokenich minach (odkryti vic policek najednou) atd.)

Ale zas tak tezky to nebylo. Teda respektive myslenkove skoro vubec, jen to bylo docela pracne.

Celkove zatim asi jedno z nejlehcich zadani (muj subjektivni dojem).

od **Petr-H** » 31. 1. 2008 11:34

Návštěvník píše:Diky za zdrojak, mas tam sikovne resene ty komentare(kodove) a resit ty chyby v kodu pomoci vyjimek me nenapadlo ;[

Můj názor je, že pokud je v zadání těchto zápočtových příkladů požadováno ošetřování chyb, tak se počítá s řešením pomocí vyjímek, minimálně proto aby si zadávající ověřil že je umíme používat (a taky proto že je to obecně jednodušší přístup)

od **Návštěvník** » 31. 1. 2008 00:06

myslim zes to dal jako jediny.(pokud se nemilim)
jsem si to trochu protach i prez cas a stejnak mi chybelo 5 minutek na odladeni, hloupej preklep mel jsem : list<int>.Remove(int index) , ale me bejt list<int>.RemoveAt(int index), njn to je tim jak v tom clovek nepise a tim casovyp presem. Ale nato ze jsem si VS2005 nainstaloval 26.1 a slaidy stah 28.1 tak bych si to stejnak nezaslouzil dat ;]

Diky za zdrojak, mas tam sikovne resene ty komentare(kodove) a resit ty chyby v kodu pomoci vyjimek me nenapadlo ;[

Ale jinak celkem prijemne stravene dopoledn ;]]]

od **gASK** » 30. 1. 2008 18:33

Odpoledním zadáním byl interpret BASICu.

Zadání:

Kód: Vybrat vše

Naprogramovat interpret BASICu.

Načte zdroják ze souboru a vykonává. Vykonává se od řádku s nejmenším číslem, končí se při příkazem END nebo pokud jsem dorazil na poslední řádek.

Každý řádek musí začínat číslem (může být odtabulátorován atd), přirozené.
Řádky mohou být zpřeházené! Pořadí vykonávání určuje číslo na začátku řádku, ne pořadí v souboru!

Komentáře jsou uvozené ', mohou být kdekoliv (samostatný řádek, za příkazem).

Proměnné jsou řetězce znaků nezačínajícíc a

Příkazy:
PRINT "string" - string NEOBSAHUJE mezery
PRINT 10
PRINT a2
INPUT a2 - načte číslo ze vstupu
SET a2 = 5 - přiřadí do a2, může se přiřazovat proměnná nebo hodnota
LET a2 = b2 + 5 - přiřadí do proměnné výsledek operac +, -, *, / mezi dvěma proměnnými / čísly
GOTO 1050 - skočí na řádek 1050
GOSUB 1020 - totéž, rozdíl viz níže
RETURN - skočí na řádek, odkud byl vykonán poslední příkaz GOSUB
FOR i = 1 TO b2 - for cyklus, proměnné se mohou "menit za běhu"
NEXT - konec for cyklu, neboli skok zpět na nejbližší předchozí FOR a inkrementace
IF a < 2 THEN GOTO 10 - pokud je splněna podmínka, jde na řádek specifikovaný na konci, podmínka obsahuje dvě proměnné / čísla a operátory <, >, <=, >=, <>, =
END - ukončí program

+ošetřit chyby syntaxe, ošetřit že nesmí být RETURN uvnitř FOR cyklu, nesmí být RETURN nebo NEXT bez FOR cyklul nebo GOSUB, řádky nezačínající číslem, neexistující příkazy, ...

Můj "ne přílíš pěkný" zdroják je přiložen, stejně jako testy.

BASIC.txt: Zdrojovy kod; (14.25 KiB) Staženo 421 x

BASICtests.zip: Testy; (2.25 KiB) Staženo 324 x

Času bylo dost (3 a něco hodiny), úspěšnost nevím, já odešel hodinu před koncem jako první.

od a » 30. 1. 2008 15:55

úspěšnost moc velká nebyla, z těch co přišli určitě nepřekročila polovinu, z druhé strany bych řek, že to dohromady udělali tak 3-4 lidi, kdyžtak mě opravte

od **Xerxes** » 30. 1. 2008 13:25

Dnes 30. ledna 2008 v 10:00 byl tento úkol:

Ve vstupním souboru máme zadaný vážený orientovaný graf formou vrhol:soused1,vaha1;soused2,vaha2;... na každém řádku. Úkolem bylo pěkně vypsat jeho matici sousednosti tak, aby byly vrcholy v jedné slabě souvislé komponentě u sebe, komponenty byly seřazené podle velikosti a vrcholy v rámci komponenty podle součtu vah hran, které do nich vedou.

V přílohách je upřesněné zadání a dva vzorové vstupy, které jsme si před odpojením internetu stáhli ze stránek zadávajícího (pan Poch). Dále je ještě přiloženo moje řešení (šité horkou jehlou, upozorňuju) a výstup, který vygenerovalo z prvního grafu. Výstup druhého grafu má 6 GB a v labu se generoval pět minut, takže ho sem nedám

. Stejně ho jenom zajímalo, zda to na něm seběhlo a nespadlo.

Pan Poch detailně kontroloval výstup na prvním grafu i kód (v rámci možností).

Odcházel jsem jako první cca hodinu a tři čtvrtě od začátku měření tříhodinového limitu, takže úspěšnost druhých neznám. Možná někdo doplní.

zadani.txt: Upřesněné zadání; (1.3 KiB) Staženo 390 x

graph.txt: První graf (malý); (582 bajtů) Staženo 350 x

biggraph.txt: Druhý graf (velký); (679.98 KiB) Staženo 435 x

reseni.txt: Moje řešení; (5.03 KiB) Staženo 393 x

vystup.txt: Můj výstup na prvním grafu; (7.77 KiB) Staženo 375 x

Fórum studentů MFF UK

NPRG035 Jazyk C# a platforma .NET

Odeslat odpověď

Rozšířit náhled Přehled tématu: NPRG035 Jazyk C# a platforma .NET

Ad.: Zapoctovy test 19.1.2010

Zapoctovy test 19.1.2010

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET

Re: NPRG035 Jazyk C# a platforma .NET