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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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 04. 06. 2018 21:30 — Editoval mirekjiranek (04. 06. 2018 21:31)

mirekjiranek
Příspěvky: 38
Pozice: student
Reputace:   
 

Algoritmus na určení počtu smybolů v řetězci

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

 

#2 04. 06. 2018 21:57

MichalAld
Moderátor
Příspěvky: 1544
Reputace:   48 
 

Re: Algoritmus na určení počtu smybolů v řetězci

No třeba takto:

Code:

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":

Code:

int CetnostZnaku[256];

for(int i = 0; i < strlen(AnalyzovanyText); i++)
{
    CetnostZnaku[((int)AnalyzovanyText[i])]++;
}

Offline

 

#3 04. 06. 2018 22:22

mirekjiranek
Příspěvky: 38
Pozice: student
Reputace:   
 

Re: Algoritmus na určení počtu smybolů v řetězci

↑ 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

 

#4 04. 06. 2018 23:06

check_drummer
Příspěvky: 2601
Reputace:   71 
 

Re: Algoritmus na určení počtu smybolů v řetězci

↑ mirekjiranek:
Ahoj, má MATLAB něco jako asociativní pole, tj. možnost indexovat pole řetězcem? Pak to bude ještě snadnější.


Definujme pojem "definice" jen pomocí předem definovaných pojmů.

Offline

 

#5 05. 06. 2018 10:48

mirekjiranek
Příspěvky: 38
Pozice: student
Reputace:   
 

Re: Algoritmus na určení počtu smybolů v řetězci

ano, má klasické pole, které můžeš nadimenzovat na velikost, kterou potřebuješ a naplnit jej nulama pro začátek

Offline

 

#6 05. 06. 2018 11:37

Davisek
Zelenáč
Příspěvky: 19
Reputace:   
 

Re: Algoritmus na určení počtu smybolů v řetězci

↑ 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

 

#7 05. 06. 2018 14:28

LukasM
Příspěvky: 3120
Reputace:   181 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#8 05. 06. 2018 15:00

Stýv
Vrchní cenzor
Místo: Q
Příspěvky: 5142
Reputace:   195 
Web
 

Re: Algoritmus na určení počtu smybolů v řetězci

↑ LukasM: Opravdu existuje mnoho způsobů, jak to udělat, ale procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)

Offline

 

#9 05. 06. 2018 15:49

edison
Příspěvky: 1054
Reputace:   26 
 

Re: Algoritmus na určení počtu smybolů v řetězci

:-) 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

 

#10 05. 06. 2018 17:52

MichalAld
Moderátor
Příspěvky: 1544
Reputace:   48 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#11 05. 06. 2018 17:56

MichalAld
Moderátor
Příspěvky: 1544
Reputace:   48 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#12 05. 06. 2018 21:25 — Editoval LukasM (05. 06. 2018 21:29)

LukasM
Příspěvky: 3120
Reputace:   181 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#13 08. 06. 2018 01:57

edison
Příspěvky: 1054
Reputace:   26 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#14 08. 06. 2018 19:28

edison
Příspěvky: 1054
Reputace:   26 
 

Re: Algoritmus na určení počtu smybolů v řetězci

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

 

#15 09. 06. 2018 22:35

Pluhtik
Příspěvky: 30
Pozice: student
Reputace:   
 

Re: Algoritmus na určení počtu smybolů v řetězci

S matlabem neumím. Neexistuje tam něco jako Slovník?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson