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
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Hashovací tabulka s lineárním sondováním (TOTO TÉMA JE VYŘEŠENÉ)
#1 22. 03. 2021 16:59
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: 4891
- Reputace: 105
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?
"Máte úhel beta." "No to nemám."
Offline
#3 22. 03. 2021 19:49
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: 4891
- Reputace: 105
Re: Hashovací tabulka s lineárním sondováním
↑ vek2:
A pak ten prvek umístí, když je pole obsazeno?
"Máte úhel beta." "No to nemám."
Offline
#5 23. 03. 2021 07:04
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: 4891
- Reputace: 105
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.
"Máte úhel beta." "No to nemám."
Offline
#7 23. 03. 2021 21:43
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: 4891
- Reputace: 105
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é).
"Máte úhel beta." "No to nemám."
Offline
#10 24. 03. 2021 10:43
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
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Hashovací tabulka s lineárním sondováním (TOTO TÉMA JE VYŘEŠENÉ)