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 09. 03. 2011 12:03
serazeni cisel
Ahoj, tento priklad by me docela zajimal jak by mel vypadat je tu nekdo kdo by mi to mohl vysvetlit jak to ma vypadat a hlavne proc to tak ma vypadat? A programovat neumim vubec tak jestli se najde nekdo kdo ma trpelivost mi to podrobne vysvetlil tak bych byl rad. dekuju
Dostanete pole 100 čísel z intervalu {0,…,9999}. Seřaďte je v lineárním čase, smíte alokovat maximálně 500 paměťových míst (integerů) + pár (max. 10) pomocných proměnných. ("Lineární čas" pro pevný počet prvků ve skutečnosti nedává smysl; myslím tím, že n=100 a smíte alokovat nejvýše 5*n prvků. Váš algoritmus by měl fungovat pro každé n, ten interval hodnot je vždy stejný.)
Offline
#3 09. 03. 2011 16:29
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: serazeni cisel
Predpokladam, ze to nemusite naprogramovat, akorat staci popsat algoritmus (jestli se pletu, tak me oprav). Pravdepodobne bude potreba neco jako Radix sort, podrobne napriklad tady. Zkusim to priblizne vysvetlit, nejsem moc trpelivy :-)
Budes to serazovat postupne nejdriv podle posledni cifry, pak podle predposledni a tak dale pro vsechny cifry.
Takze zacnes posledni cifrou - seradit to podle jedne cifry jde s linearni slozitosti, nejdriv spocitas, kolik je tam od kazde cislice na dane pozici cisel (asi proto 10 pomocnych promennych). Z toho pak zjistis, na jake pozici v poli budou po serazeni zacinat cisla s 0 naposlednim miste, s 1 na poslednim miste, s 2 na poslednim miste atd az do 9 (to ted budes mit ulozene v tech pomocnych). Pak akorat projdes cele to pole a budes kopirovat ty cisla do noveho pole. Podle toho jaka je cislice na posledni miste, tak na prislusne misto v novem poli ulozis to cislo (tu pozici mas v pomocne promenne) a promennou zvysis o 1.
Takhle to budes mit setridene podle posledni cifry, to udelas postupne pro vsechny cifry od posledni az po prvni, a bude to setridene.
Napriklad zjednodusene zadani:
4322,2424,2242,4243,3421,1241,1234,1212,4122
nejdriv posledni cifra (u dalsich nerozepisuju) :
1 - 2x - bude zacinat na pozici 0
2 - 4x - bude zacinat na pozici 2
3 - 1x - bude zacinat na pozici 6
4 - 2x - bude zacinat na pozici 7
takze po prvnim kopirovani (setrideni podle posledni cifry) bude pole vypadat:
3421,1241,4322,2242,1212,4122,4243,2424,1234
pak predposleni:
1212,3421,4322,4122,2424,1234,1241,2242,4243,
pak druha:
4122,1212,1234,1241,2242,4243,4322,3421,2424
pak prvni:
1212,1234,1241,2242,2424,3421,4122,4243,4322
Takze ted je to setridene.
Nemyslim si, ze jsem to dobre vysvetlil, tak se klidne ptej, a nebo si muzes najit vic o Radix sortu, Counting sortu a podobnych algoritmech - ty linearni tridici maji vsechny podobny princip (anebo to nejak sam vymyslet, za pomoci toho co jsem psal napriklad).
Offline