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
Zdravím vás,
Rád bych se s vámi podělil o jeden oříšek, se kterým si nevím rady:
Spočtěte všechny symboly v řetězci a vypište je
Pro upřesnění tedy jde o toto:
Hello, world.
"H"=1
"e"=1
"l"=3
"o"=2
"," = 1
" "=1
"w"=1
"r"=1
"d"=1
"."=1
Máte nějaké nápady? Nejsem v algoritmizaci ještě úplně zběhlý, proto mi tato úloha už dělá menší problémy a vždycky se v tom zamotám.
Za všechny rady a postřehy moc děkuji
Offline
No třeba takto:
for(int i = 0; i < strlen(AnalyzovanyText); i++) { switch(AnalyzovanyText[i]) { case 'a': NumOf_a++; break; case 'b': NumOf_b++; break; case 'c': NumOf_c++; break; // atd... pro vsechny mozne znaky } }
Je to samozřejmě hloupý způsob psaní kódu, protože tam budeš muset ručně vypsat všechny písmena co existují.
Elegantněji by to šlo udělat přes "hodnotu znaku":
int CetnostZnaku[256]; for(int i = 0; i < strlen(AnalyzovanyText); i++) { CetnostZnaku[((int)AnalyzovanyText[i])]++; }
Offline
↑ MichalAld:
děkuji za radu. Mohl by jsi to zkusit napsat trochu víc obecně abych to pochopil? V Cčku(pokud je toto psané v Cčku) jem ještě nedělal, tento program píšu v MATLABu
Offline
↑ mirekjiranek:
Ahoj, má MATLAB něco jako asociativní pole, tj. možnost indexovat pole řetězcem? Pak to bude ještě snadnější.
Offline
ano, má klasické pole, které můžeš nadimenzovat na velikost, kterou potřebuješ a naplnit jej nulama pro začátek
Offline
↑ mirekjiranek:
Takže nemá asociativní pole.
V jednoduchosti: 8bitová ASCII tabulka má 256 položek, v rozsahu 0-255.
Takže je potřeba jej incializovat na velikost 256 a nastavit do nuly každý index.
Potom každý index přesně odpovída indexu položky v ASCII tabulce
např. array[65], bude představovat písmeno 'A', protože ascii hodnota písmena 'A' je 65.
jak napsat kód máš nahoře. Ale slovy postupuješ tak.
1) pro každý znak v řetezci musíš získat jeho ascii hodnotu, a tuto hodnotu získaš po indexovaní pole
např. 'H' = 72,
2) potom zvýšíš hodnotu na indexu o 1
array[72] = array[72] + 1
3) potom výsledek vypisuješ tak, že přes každou položku v poli, pokud neni nulová, tak výpíšeš hodnotu, ktera se tam vyskytuje a zaroveň převedeš číslo, kterým indexuješ tabulku na znak a ten taky vypíšeš
např. print(72 --> 'H', " : " , array[72]) //output H : 1
Offline
Jsem celkem překvapen, co všechno se podařilo vymyslet. Šel bych na to takto:
1. Podívám se na první prvek, někam si ho uložím, vymažu ho z řetězce a nastavím počitadlo na 1.
2. Projdu celý řetězec znak po znaku, když narazím na stejný znak, inkrementuji počítadlo a daný znak z řetězce vymažu.
3. Když jsem na konci řetězce, vypíšu ten uložený znak a hodnotu počitadla.
4. Pokud řetězec není prázdný, jdu na krok 1.
Takto není potřeba vůbec přemýšlet o ASCII tabulce a jak ji indexovat, ukládat počet znaků, které v řetězci vůbec nejsou, nebo dokonce předpokládat, jaké znaky tam jsou a kolik jich je. Pokud si nemohu dovolit řetězec při práci zničit, mohu pracovat s kopií. Pokud je kromě výpisu třeba si ten výsledek nějak uložit, záleží na konkrétním jazyce, co mám k dispozici.
Netvrdím, že je to jediná možnost.
Offline
:-) Ten Lukášův algoritmus je fakt zajímavej.
Vůbec třeba nechápu, k čemu je tam potřeba odmazávat započítané znaky. A zároveň konstatuji, že ve většině prostředí (nevím jak je na tom Matlab) to bude fyzicky obnášet opakované kopírování řetězce, opakovanou alokaci paměti, nejčastěji obojí. S takovým přístupem se pak nelze divit, že nový Open Office nezvládne na 4jádrovém procesoru s několika GHz a několika GB RAM v rozumném čase zobrazit graf z tabulky 1000x10, zatímco před mnoha lety to dokázal v pohodě i z řádově větší tabulky na jednojádru se čtvrt GB RAM.
Rozumné je prostě inkrementovat index.
Offline
No jo, protože "smazání znaku z řetězce" většinou nejde jednoduše provést. Zpravidla to znamená vyrobení nového řetězce překopírováním částí toho původního.
Můžeme si také znak nahradit nějakým předem zvoleným znakem, ale tím si to zase zkomplikujeme, protože řetězec může obsahovat i tenhle znak.
Stýv napsal(a):
↑ LukasM: Opravdu existuje mnoho způsobů, jak to udělat, ale procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)
A to je samozřejmě taky pravda, on ten řetězec nemusí mít jen pět či dvacet znaků. Může mít taky 100Gb, takže ho musíme načítat z disku, když to namísto jedenkrát budeme muset udělat 200x, tak to asi moc super nebude. A to ještě máme kliku, že znaků je jen pár desítek.
Pokud to ovšem budeme dělat nad jinou "abecedou" (třeba 32 bitovými instrukcemi), mohlo by to trvat o dost déle...jako třeba i několik let...
Pak také existuje možnost, že ten řetězec nebude uložený nikde, že to bude stream (bude nám to chodit postupně třeba po ethernetové síti) a musíme si s tím nějak poradit.
Offline
Ale určitě lze vymyslet ještě i zajímavější algoritmy. Jako třeba si ten řetězec nejprve setřídit, a pak aplikovat algoritmus na bázi toho Lukášova (kterému bak bude stačit jen jeden průchod a nebudou se muset žádné znaky mazat, prostě při každé změně zobrazíme, kolik kroků jsme napočítali a jaké to bylo písmeno, a resetujeme čítač...).
Offline
Nepřeháníte to trochu? Tazatel je naprostý začátečník, který chce "nějaký nápad", tedy nezná ŽÁDNÝ způsob, jak to udělat. Tak jsem vzal to nejjednodušší co mně napadlo a to jsem ještě zjednodušil, aby se to kolegovi programovalo co nejsnadněji. Že je to v nějakém slova smyslu optimální jsem nikde netvrdil, kdyby se tazatel chytil, sám bych na některé ty problémy upozornil. Navíc že místo mazání mohu znak přepsat nějakým vybraným znakem a tím se vyhnout realokacím řetězce, to si snad není zas takový problém domyslet (MichalAld to zvládl, v C++ se nabízí např. znak '\0'). Nicméně, když už jsem byl takto pranýřován, budu také adresněji reagovat.
Stýv napsal(a):
procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)
To je sice super, ale stejně tak dobře bych mohl říct, že tvořit si kvůli krátkému řetězci pole součtů o 256 prvcích je prasárna, a ne slušná práce s pamětí. Nemluvě o tom, že v zadání není nic o tom, že jde o 8-bitový řetězec. Znovu, netvrdím, že to nejde udělat lépe. Jde.
edison napsal(a):
nechápu, k čemu je tam potřeba odmazávat započítané znaky.
No.. nejspíš abych je při dalších průchodech nepotkal znovu. Pouze první znak by mohl zůstávat - když smažu i ten, můžu jít vždy od začátku, čímž kolegovi odpadne jeden index. Pokud má k dispozici nějaký dynamický kontejner (což v MATLABu nepochybně má), mazání kód zjednoduší.
edison napsal(a):
to bude fyzicky obnášet opakované kopírování řetězce
Ano, to bude. Viz text výše.
edison napsal(a):
S takovým přístupem se pak nelze divit, že nový Open Office nezvládne na 4jádrovém procesoru s několika GHz a několika GB RAM v rozumném čase zobrazit graf z tabulky 1000x10, zatímco před mnoha lety to dokázal v pohodě i z řádově větší tabulky na jednojádru se čtvrt GB RAM.
Ano, mirekjiranek hned po dokončení tohoto úkolu otevře repozitář OpenOffice a začne ho ničit neefektivním kódem. Ze stejného důvodu v sekci Fyzika nikdy nepoužíváme rovnici ideálního plynu, nezanedbáváme odpor vzduchu a nic nepočítáme v homogenním tíhovém poli. Jinak by totiž začala po světě padat letadla, a to jenom kvůli nám. (Tím nijak netvrdím, že kód, na kterém záleží, nemá být napsaný chytře.)
edison napsal(a):
Rozumné je prostě inkrementovat index.
Mají se počítat znaky, každému je jasné, že se něco bude inkrementovat. Otázka je co a jak to najít.
MichaloviAld děkuji za podnětné vyprávění o řetězci, co se nevejde do paměti a procesoru s jinou instrukční sadou. Jsou to palčivé problémy, které by mirekjiranek měl urychleně řešit. V podobné souvislosti si dovoluji poznamenat, že znaky nemusejí být 8-bitové (a na rozdíl od Tebou uváděných případů to může možná i v tomto případě nastat). A když se podívám pro změnu na Tvůj kód, v takovém případě je třeba alokovat na to pomocné pole skutečně značné množství paměti. To je už správně? Navíc když už jsem byl donucen to zkoumat, pokud dobře vidím, ve Tvém kódu je neinicializované pole, což je v jazyce C nedefinované chování - tedy mnohem větší problém, díky kterému to nemusí správně zpracovat ani ten řetězec ze zadání.
MichalAld napsal(a):
lze vymyslet ještě i zajímavější algoritmy. Jako třeba si ten řetězec nejprve setřídit...
Nepochybně lze. Ovšem diskuze o tom, jakým způsobem to pole setřídit, aby to fungovalo se streamovaným stringem, který se nevejde do paměti, a přitom se žádný krok neprovedl zbytečně bude nejspíš dlouhá. A já se jí účastnit nebudu:-)
"Správné" řešení je patrně to asociativní pole, kde nějaký efektivní algoritmus rychle najde správné počítadlo, aby se mohlo inkrementovat (a když ho nenajde, vytvoří ho). Pokud mirekjiranek neví, co to je, asi ho nemůže použít. A protože je evidentně začátečník, asi si ho také nenapíše hned sám (byť pokusy o optimalizaci budou k něčemu takovému nejspíš směřovat). Takže to asi bude muset udělat nějak jinak. Rád se přiučím, jak to udělat neprasácky a jednoduše současně.
Offline
LukasM napsal(a):
Rád se přiučím, jak to udělat neprasácky a jednoduše současně.
Tak to si myslím, že napsal Michal již na začátku: ↑ MichalAld: (druhý program) a pak už by stačilo jen tazateli trochu pomoct s implementací v Matlabu.
Offline
Nikdo se k tomu nemá, já zas neumím Matlab... Tak to zkusím obecně:
Budeme potřebovat pole 256 čísel (na začátku všechny 0), které nazveme dejme tomu seznam a jednu číselnou proměnnou jménem index.
Pak bude potřeba nějaký převod ze znaku na číslo (v c to nemí potřeba, protože řetězec je pole bajtů, dost jazyků na to má nějaké funkce, které se jmenují třeba asc, ascii, nebo code).
Pak musíme nějak získávat jednotlivé znaky (v c je to zas jaksi "samo", jinde na to bývají funkce, často trochu univerzálnější, např. mid ve VB vytáhne z jednoho většího řetězce menší kousek a pro náš účel pak budeme požadovat délku 1).
Pak to chce nějakou funkci na délku řetězce (len, strlen a pod.), nebo nějak poznat jeho konec (např. v c je za koncem prvek s hodnotou 0).
Dále to chce nějaký cyklus, třeba for, ten je skoro ve všech jazycích.
Takže uděláme cyklus, ve kterém se vezme znak z pozice index, jeho kód se použije jako adresa do pole seznam a v něm se hodnota daného prvku zvýší o 1. Pak se index zvýší o 1 a pokud nejsme na konci řetězce, cyklus se opakuje. Po ukončení cyklu máme v seznamu počty znaků s patřičnými kódy.
Při vypisování seznamu pak budeme potřebovat rozhodování (téměř všude if) a převod z čísla na znak (chr, char a pod).
Zase cyklus. Projede seznam a vypíše znaky, které mají nenulový počet s jejich počty.
Offline