Crowdly
Додати до Chrome
Algoritmid ja andmestruktuurid (LTAT.03.005)
Шукаєте відповіді та рішення тестів для Algoritmid ja andmestruktuurid (LTAT.03.005)? Перегляньте нашу велику колекцію перевірених відповідей для Algoritmid ja andmestruktuurid (LTAT.03.005) в moodle.ut.ee.
Отримайте миттєвий доступ до точних відповідей та детальних пояснень для питань вашого курсу. Наша платформа, створена спільнотою, допомагає студентам досягати успіху!
Ülesandeks on kontrollida etteantud positiivse täisarvu jaoks, kas ta on 2 aste. Vaatleme järgmist algoritmi selle ülesande lahendamiseks. Kui arv on paarisarv, siis jagatakse ta 2-ga ja korratakse sama tegevust tulemuseks saadud arvuga. Kui nii tehes jäädakse lõpuks pidama arvul 1, siis tagastatakse „tõene”, vastasel korral aga tagastatakse „väär”. Milline on selle algoritmi halvima juhu keerukushinnang kujul Θ(f(n)), kus n on argumendiks saadud arvu numbrite arv kahendsüsteemis? Eeldada, et kõik jagamised on keerukusega Θ(1).
// <![CDATA[ var ulObj = new Object(); ulObj.tn = "n(n+1)"; document.write(tookiirus(ulObj)); // ]]>
Algoritmi töökiiruse sõltuvust sisendi suurusest väljendab funktsioon T(n) = n(n+1). Millistesse keerukusklassidesse see kuulub?
Vali kõik sobivad vastused.
Definitsioon. Olgu f ja g naturaalarvuliste argumentidega funktsioonid. Siis f on O(g), kui leiduvad c > 0 ja N > 0 nii, et |f(n)| < c|g(n)| iga n > N korral.
Olgu
- f(n) = 3n2 + 12n - 2
- g(n) = n
Kas nende funktsioonide puhul kehtib lause „f on O(g)”?
Vali kõik sobivad variandid.
Definitsioon. Olgu f ja g naturaalarvuliste argumentidega funktsioonid. Siis f on O(g), kui leiduvad c > 0 ja N > 0 nii, et |f(n)| < c|g(n)| iga n > N korral.
Olgu
- f(n) = 5n + 5
- g(n) = n
Kas nende funktsioonide puhul kehtib lause „f on O(g)”?
Vali kõik sobivad variandid.
Vaatleme algoritmi, mis liidab sisendiks saadud naturaalarvu n iseendale ja väljastab tulemuse. Milline on selle algoritmi keerukus kujul Θ(f(n)), eeldusel et arvud esitatakse tavakujul (st kümnendsüsteemis) ja liitmine toimub vastavalt tavaalgoritmile?
// <![CDATA[ var sone, ulObj; sone = rekursioon_soned[Math.floor(Math.random()*rekursioon_soned.length)]; ulObj = new Object(); ulObj.arg = "\"" + sone + "\""; ulObj.funktsioon = tag1(); document.write(mis_ekraanil(ulObj)); // ]]>
Mille prindib järgmine funktsioon sisendil "INFORMATSIOON"?
def tag(sõne):
if len(sõne) == 0:
return
print(sõne[0], end=' ')
tag(sõne[1:])
Mis keerukusega on järgnev algoritm?
def seljakott(a, k):
if len(a) == 0 or k <= 0:
return []
a0 = [a[0]] + seljakott(a[1:], k-a[0])
a1 = seljakott(a[1:], k)
s0 = sum(a0)
s1 = sum(a1)
if s0 > k or s1 > s0:
return a1
return a0
Meil on arvuti, millega võtab 10 miljoni elemendilise järjendi sorteerimine pistemeetodiga aega keskmiselt 512000 sekundit. Umbes mitu sekundit võtab aega 100 tuhande elemendilise järjendi sorteerimine sama meetodiga samal arvutil?
// <![CDATA[ var ulObj = new Object(); ulObj.question = "On teada, et järgnev programm väljastab Maria arvutil 6-tähelise sisendi kõik permutatsioonid 1 sekundiga. Mitu sekundit kulub samal programmil aega 10-tähelise sisendi puhul eeldusel, et Maria laseb programmil töötada samal arvutil?" ; ulObj.code_function = permutations_of_word; document.write(question_with_code(ulObj)); // ]]> On teada, et järgnev programm väljastab Maria arvutil 6-tähelise sisendi kõik permutatsioonid 1 sekundiga. Mitu sekundit kulub samal programmil aega 10-tähelise sisendi puhul eeldusel, et Maria laseb programmil töötada samal arvutil?
def permutatsioon(sõne, perm=""):
if len(sõne) == 0:
print(perm)
else:
for i in range(len(sõne)):
permutatsioon(sõne[:i] + sõne[i+1:], perm + sõne[i])
// <![CDATA[ var ulObj = new Object(); ulObj.question = "Oma arvutil leidis Mikk alljärgneval programmi töötada lastes kõigi 20-kohaliste bittvektorite arvu 10 sekundiga. Mitu sekundit kulub Mikul, et samas arvutis sama programmiga leida kõigi 24-kohaliste bittvektorite arv?"; ulObj.code_function = bit_vector; document.write(question_with_code(ulObj)); // ]]> Oma arvutil leidis Mikk alljärgneval programmi töötada lastes kõigi 20-kohaliste bittvektorite arvu 10 sekundiga. Mitu sekundit kulub Mikul, et samas arvutis sama programmiga leida kõigi 24-kohaliste bittvektorite arv?
def bittvektorite_generaator(n, vektor = ""):
if len(vektor) == n:
return 1
return bittvektorite_generaator(n, vektor + "0") + bittvektorite_generaator(n, vektor + "1")