Vzdialenosť vrcholov v strome – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Vzdialenosť vrcholov v strome – Java – Fórum – Programujte.comVzdialenosť vrcholov v strome – Java – Fórum – Programujte.com

 

Jozef010
Newbie
2. 5. 2017   #1
-
0
-

Zdravím,

potreboval by som pomôcť s týmto problémom:
Je daný počet uzlov stromu a číslo uzla, ktorý je koreň. Ďalej sú na vstupe neusporiadané dvojice vzájomne prepojených uzlov.

Pre každý uzol je treba vypísať najväčšiu možnú vzdialenosť medzi ľubovoľnými dvoma uzlami, ktoré ležia "nižšie", nanajvýš rovnako "vysoko" ako uzol, pre ktorý to zisťujeme.

Obrázok pomôže asi viac: (vpravo hore je príklad vstupu a výstupu).

K obrázku:

Připojen obrázek.

  1.  najväčšiu vzdialenosť  má 10 + 3 alebo 10 + 5 = 5
  2. 10 + 3; 10 + 5; 10 + 2 = 5
  3. 0 - nič nie je nižšie
  4. 10 + 8 = 8
  5. 0
  6. 1

Ako mám začať? (Napríklad ako dať dokopy tie dvojice uzlov.)

Ďakujem za odpovede, Jožo

Nahlásit jako SPAM
IP: 212.26.187.–
gna
~ Anonymní uživatel
1891 příspěvků
2. 5. 2017   #2
-
0
-

Pro každý uzel potřebuješ jeho vazby, takže třeba...

class Node
{
	List<Node> links = new ArrayList<Node>();
	
	public Node() {}
}

Pak je načteš a provážeš...

HashMap<Integer,Node> map = new HashMap<Integer,Node>();

while (sc.hasNext()) {
	int a = ...nextInt
	int b = ...nextInt

	Node nodeA = map.get(a);
	Node nodeB = map.get(b);
	
	if (nodeA == null) { nodeA = new Node(); map.put(a, nodeA); }
	if (nodeB == null) { nodeB = new Node(); map.put(b, nodeB); }
	
	nodeA.links.add(nodeB);
	nodeB.links.add(nodeA);
}
Nahlásit jako SPAM
IP: 213.211.51.–
gna
~ Anonymní uživatel
1891 příspěvků
2. 5. 2017   #3
-
0
-

Pak bych ty vazby ještě od rootu pročistil ať jsou jednosměrné. Další práce pak bude jednodušší.

Nahlásit jako SPAM
IP: 213.211.51.–
Jozef010
Newbie
4. 5. 2017   #4
-
0
-

Ďakujem, 
skúsil som to, ale vôbec neviem, čo sú čísla na výstupe. 

Připojen obrázek.

Neviem, čo robia Node a HashMap.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

class Program {
	public static void main(String[] args) {
		Scanner sc;
        sc=new Scanner(System.in);
        int pocet=sc.nextInt();
        int koren=sc.nextInt();
        
        class Node {
        	ArrayList<Node> links = new ArrayList<Node>();
        	public Node() {}
        }
        HashMap<Integer,Node> map = new HashMap<Integer,Node>();

        while (sc.hasNext()) {
        	int a = sc.nextInt();
        	int b = sc.nextInt();

        	Node nodeA = map.get(a);
        	Node nodeB = map.get(b);
        	
        	if (nodeA == null) { nodeA = new Node(); map.put(a, nodeA); }
        	if (nodeB == null) { nodeB = new Node(); map.put(b, nodeB); }
        	
        	nodeA.links.add(nodeB);
        	nodeB.links.add(nodeA);
        }
        
        sc.close();
	}
}
Nahlásit jako SPAM
IP: 212.26.187.–
gna
~ Anonymní uživatel
1891 příspěvků
4. 5. 2017   #5
-
0
-

Taky nevím, kde se tam ta čísla berou.

Nahlásit jako SPAM
IP: 213.211.51.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 69 hostů

Podobná vlákna

Google maps vzdialenosť — založil Anonym

Pomoc se strome — založil ragon

Lopta na strome — založil mephi

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý