Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 22. 03. 2021 16:59

vek2
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

Hashovací tabulka s lineárním sondováním

Úloha zasahuje napůl do matematiky, napůl do informatiky. Jedná se o otázku z roku 2018, přijímačky na FI MUNI.

Uvažujme hašovací tabulku s lineárním sondováním (linear probing) a hašovací funkcí h(x) = (5*x +3) mod 7. Začínáme s prázdnou hašovací tabulkou. V jakém pořadí musíme do tabulky vložit hodnoty
1, 2, 5, 7, 9, 12 tak, aby obsah výsledné tabulky byl následující: 2, 12, 1, 5, 7, prázdná položka, 9?

A) 2, 9, 12, 5, 1, 7
*B) 9, 2, 12, 1, 5, 7 [SPRÁVNĚ]
C) 2, 9, 5, 12, 1, 7
D) 9, 2, 12, 5, 1, 7
E) 9, 2, 5, 12, 1, 7

Když mám nabídnuté odpovědi, v tomto případě i tu správnou, začínám dosazováním. Právě proto, že nevím jak na to, dosazuji za h(x) i x, a to 2 nebo 9 (tj. začínám s prvními hodnotami). Zbytek mi ale vychází 6. Jdu na to úplně špatně?

Offline

  • (téma jako vyřešené označil(a) vek2)

#2 22. 03. 2021 18:30

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Hashovací tabulka s lineárním sondováním

↑ vek2:
Ahoj. A jak funguje ta hashovací tabulka s lineárním sondováním?


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#3 22. 03. 2021 19:49

vek2
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

Re: Hashovací tabulka s lineárním sondováním

↑ check_drummer:

Ahoj, představ si jednorozměrnou tabulku (pole rozdělení na několik částí), do kterých musíš podle haše rozřadit určené hodnoty, ale může se stát, že se v jednom políčku sejdou dvě hodnoty (teda spíš je tam jedna, ale další se tam taky hodí), lineární sondování ti pro tu hodnotu hledá další volné místo. Jestli to takhle dává smysl.

Jak ti to tady vysvětluju, tak už asi vím kde je chyba...zbytek z "výpočtu" není v tomto případě výsledek, ale index, tedy pořadí v poli (hashovací tabulce)...jdu to zkusit

Offline

 

#4 22. 03. 2021 23:23

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Hashovací tabulka s lineárním sondováním

↑ vek2:
A pak ten prvek umístí, když je pole obsazeno?


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#5 23. 03. 2021 07:04

vek2
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

Re: Hashovací tabulka s lineárním sondováním

↑ check_drummer:

Právě že umístí až když najde další prázdný políčko. Už jsem na to přišla, jen si nejsem jistá, jestli ta 7 v hašovací funkci určuje i počet polí (0-6 tj. 7), ale nejspíš ano.

Offline

 

#6 23. 03. 2021 17:42

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Hashovací tabulka s lineárním sondováním

↑ vek2:
Asi nezbývá než to prozkoušet a vylučovat nesprávné možnosti. Ta 7 za mod v hašovací funkci označuje zbytek po dělení 7.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#7 23. 03. 2021 21:43

vek2
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

Re: Hashovací tabulka s lineárním sondováním

↑ check_drummer:

Nakonec jsem nemusela nic z výsledků dosazovat a vím, že modulo je zbytek, ale v tomhle případě nejspíš určuje i počet těch políček, protože i ten je důležitý.
Postupně jsem všechna čísla dosadila do rovnice, zbytek představoval index (tj. pozici v poli) pro to číslo ...a vychází to.

Offline

 

#8 23. 03. 2021 22:12

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Hashovací tabulka s lineárním sondováním

↑ vek2:
Je to počet položek, protože v zadání obsahuje výsledná tabulka 7 polí (jedno je prázdné).


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#9 23. 03. 2021 22:20

vek2
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

Re: Hashovací tabulka s lineárním sondováním

Vidíš, to jsem přehlídla. Viděla jsem podobný příklad a tam taky sedělo modulo a počet polí, tak mě to zmátlo.

Offline

 

#10 24. 03. 2021 10:43

Stýv
Vrchní cenzor
Příspěvky: 5592
Reputace:   214 
Web
 

Re: Hashovací tabulka s lineárním sondováním

↑ vek2: Samozřejmě není třeba mít žádné nabízené možnosti. A samozřejmě ten modul (teda jestli se to tak jmenuje, prostě ta sedmička) musí být rovna velikosti tabulky. Jinak by ti buď něco mohlo padnout vedle, nebo by naopak na konci vždy byla prázná místa.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson