Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha2-2010 [2010/10/19 00:08]
redtop created
+++ courses:a4m33pal:uloha2-2010 [2025/01/03 18:28] (aktuální)
@@ Řádek 3: / Řádek 3: @@
 Počítačová síť
-[[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/cviceni/uloha2_pripojeni_popis.pdf|Provizorní zadání]]
+[[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=pocitacova_sit|Zadání]]
+Limit: 2s
 Jak na to:
+  - Načíst vstup a uložit do listu hran. Je potřeba dávat pozor na to, že A->B je to stejné jako B->A. Mohou se tam také vyskytnout duplicitní nabídky, takže zachovat jenom tu s menší cenou
+  - Seřadit hrany podle ceny, pokud jsou ceny stejné tak podle čísla první budovy
+  - Inicializovat struktury na UNION-FIND - dvě pole:
+    * "pole bossů" - index je číslo budovy a obsah je kdo je boss budovy, na začátku je každý svůj boss
+    * "pole hloubek" - index je číslo budovy a obsah její hloubka, na začátku je hloubka 0
+  - Procházet možné hrany od těch s nejmenších cenou a postupně je přidávat dokud jich nebude (počet budov-počet připojení k netu)
+  - Nesmím ale přidat hranu, která by vytvořila cyklus - máme funkci můžuPřidatHranu(hrana), kterou řeší UNION-FIND:
+    * pokud obě budovy z hrany mají stejného bosse, vzniknul by cyklus a vracím false
+    * pokud obě budovy z hrany mají různého bosse, vracím true a přidávám hranu do dvou polí takto:
+      * pokud hloubka bosse první budovy < hloubka bosse druhé budovy => boss první budovy je boss druhé budovy
+      * pokud hloubka bosse první budovy > hloubka bosse druhé budovy => boss druhé budovy je boss první budovy
+      * pokud hloubka bosse první budovy == hloubka bosse druhé budovy => boss druhé budovy je boss první budovy && zvyšuju hloubku u bosse první budovy o 1
+  - Najít budovy, kam zavést interfernet, to už je easy:
+    * Projdu pole bossů a uložím si tolik různých bossů, kolik mám zavést internetů
+  - Všechno vypsat
+====== Hledání koster a UNION-FIND ======
+Mnohem lépe vysvětlené než na přednáškách včetně praktických ukázek pseudokódu:{{:courses:a4m33pal:kostry.pdf|Hledání minimální kostry a UNION-FIND problém}}
+====== Generátor grafů ======
+Přidávám svůj generátor grafů pro tuhle úlohu. Snad někomu pomůže. Pro opravdu velké grafy je nutné krapet přepsat a flushovat více String Buildery
+public class MatrixGenerator {
+    public static void main(String[] args) {
+        if(args.length!=4){
+            System.out.println("Run the program with [nodes] [connections] [edges] [full/random/noconn] params.");
+            return;
+        }
+        final int NODES = Integer.parseInt(args[0]);
+        final int CONNECTIONS = Integer.parseInt(args[1]);
+        final int EDGES = Integer.parseInt(args[2]);
+        final String type = args[3];
+        if("full".equals(type.toLowerCase())){
+            makeFullGraph(NODES,CONNECTIONS);
+        }else if("random".equals(type.toLowerCase())){
+            makeRandomGraph(NODES, CONNECTIONS,EDGES);
+        }else{
+            makeNotConnectableFullGraph(NODES,CONNECTIONS);
+        }
+    }
+    public static void makeRandomGraph(int NODES,int CONNECTIONS, int EDGES){
+        StringBuilder sb = new StringBuilder();
+        final boolean random = true;
+        sb.append(NODES);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for(int i = 0 ; i<= EDGES ; i++){
+            int x = (int)(1+((Math.random()*NODES)%(NODES-1)));
+            int y = (int)(1+((Math.random()*NODES)%(NODES-1)));
+            if(x == y){
+                i--;
+                continue;
+            }
+            sb.append(x);
+            sb.append(" ");
+            sb.append(y);
+            sb.append(" ");
+            sb.append(getWeight(random));
+            sb.append("\n");
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static void makeNotConnectableFullGraph(int NODES,int CONNECTIONS) {
+        final boolean random = true;
+        StringBuilder sb = new StringBuilder();
+        sb.append(NODES+CONNECTIONS+1);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for (int i = 1; i <= NODES; i++) {
+            for (int y = 1; y <= NODES; y++) {
+                if (i != y) {
+                    sb.append(y);
+                    sb.append(" ");
+                    sb.append(i);
+                    sb.append(" ");
+                    sb.append(getWeight(random));
+                    sb.append("\n");
+                }
+            }
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static void makeFullGraph(int NODES,int CONNECTIONS) {
+        final boolean random = true;
+        StringBuilder sb = new StringBuilder();
+        sb.append(NODES);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for (int i = 1; i <= NODES; i++) {
+            for (int y = 1; y <= NODES; y++) {
+                if (i != y) {
+                    sb.append(y);
+                    sb.append(" ");
+                    sb.append(i);
+                    sb.append(" ");
+                    sb.append(getWeight(random));
+                    sb.append("\n");
+                }
+            }
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static int getWeight(boolean random) {
+        if (random) {
+            return (int) (Math.random() * 99 + 1);
+        } else {
+            return 10;
+        }
+    }
+}
+====== Diskuze ======
 ~~DISCUSSION~~

courses/a4m33pal/uloha2-2010.1287439688.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru