Dynamická alokácia pamäti (riešené príklady)
Obsah
Filtrovanie textu
Zadanie úlohy
Zostavte program na filtrovanie textu - vyhľadávanie riadkov s hľadaným slovom. Program z klávesnice načíta hľadané slovo (nebude mať viac ako 100 znakov). Ďalej bude čítať z klávesnice riadky textu (reťazce ukončené ENTERom), až kým nenačíta prázdny riadok. Môžeme predpokladať, že žiaden riadok nebude dlhší ako 1000 znakov a že riadkov nebude viacej ako 1000.
Po načítaní prázdneho riadku program začne na obrazovku vypisovať výsledky (do tohoto okamihu NESMIE nič písať na obrazovku) v tvare:
V prvom riadku bude text "nachadza N:", kde N je počet riadkov, v ktorých sa nachádza hľadané slovo.
- Pod týmto riadkom budú vypísané všetky riadky, v ktorých sa nachádza hľadané slovo.
- Pod nimi bude prázdny riadok a ďalej riadok s textom "nenachadza N:", kde N je počet riadkov, v ktorých sa hľadané slovo nenachádza.
- Pod týmto riadkom budú vypísané všetky riadky, v ktorých sa nenachádza hľadané slovo.
Vzorový príklad
Príklad vstupu
slovo
Program bude hladat riadky s urcitym slovom.
V tomto riadku sa nenachadza.
A ani v tomto dalsom
Príklad výstupu:
nachadza 1:
Program bude hladat riadky s urcitym slovom.
nenachadza 2:
V tomto riadku sa nenachadza.
A ani v tomto dalsom.
Netreba zabúdať na to, že každý textový reťazec je ukončený znakom '\0', preto musíme rezervovať miesto aj preň.
Pre načítavanie hľadaného slova je vhodné použiť príkaz cez cin.getline, pretože cin>> akosi necháva ENTER za slovom nepovšimnutý a prvý cin.getline je potom prázdny.
Analýza riešenia
Keďže v tejto úlohe vopred nevieme, koľko riadkov bude obsahovať, je vhodné pole riadkov vytvoriť staticky – je ich, podľa zadania, nanajvýš 1000. Riadky samotné by však statickébyť nemali – je zbytočné mať maticu 1000×1001 znakov (čo predstavuje 1 MB dát), keď väčšina riadkov bude oveľa kratších. Riadok preto najskôr načítame do pomocnej premennej (textový reťazec dostatočnej dĺžky), „zmeriame“ jeho dĺžku a dynamicky vytvoríme riadok, do ktorého sa vojde (pozor, musíme dať dĺžku o jedno väčšiu).
Úlohu je možné riešiť použitím jedného poľa riadkov, no potom je problém s určením, v ktorom riadku sa hľadané slovo nachádza a v ktorom nie – dá sa to riešiť dvojako:
- hneď pri čítaní vstupu budeme počítať riadky s hľadaným slovom a riadky bez neho, aby sme toto mohli vopred vypísať, potom druhýkrát musíme prechádzať poľom a vypisovať riadky, v ktorých sa hľadané slovo nachádza a nakoniec tretíkrát ním prechádzať a opäť hľadať riadky, v ktorom sa slovo nenachádza – toto riešenie nie je veľmi efektívne, keďže 3-krát hľadáme to isté (a hľadanie slova v reťazci je relatívne náročná operácia),
- do pomocného poľa si budeme hneď pri čítaní vstupu zapisovať, či v danom riadku je alebo nie je hľadané slovo (hodnotou 1 alebo 0) a zároveň ich počítať zvlášť do počítadiel – pri vypisovaní stačí pozerať do tohto poľa a netreba znovu hľadať slovo v reťazcoch.
Praktickejšie však bude ukladať si riadky do dvoch polí – zvlášť tie, v ktorých sa hľadané slovo nachádza a zvlášť tie, kde nie. Keďže ale nevieme, koľko ktorých je, musíme počítať s najhoršou možnosťou pre obe polia – že riadkov bude plný počet (1000). Či sa hľadané slovo v riadku nachádza, nám pomôže zistiť funkcia strstr, na kopírovanie textu použijeme funkciu strcpy. V žiadnom prípade nemôžeme použiť len jednoduché priradenie, lebo by sa skopíroval len ukazovateľ na reťazec a nie reťazec samotný!. Keď už dynamicky vytvorené reťazce nepotrebujeme, je vhodné ich zmazať – po skončení programu sa síce vymažú automaticky, no je dobré zvyknúť si "upratať po sebe".
Riešenie v jazyku C
#include <iostream.h>
#include <string.h>
#include <conio.h>
int main()
{
char text[1001], hladane[101], *najdene[1000], *nenajdene[1000];
int pocet_najdenych = 0, pocet_nenajdenych = 0;
cin.getline(hladane, 100);
cin.getline(text, 1000);
int dlzka = strlen(text);
while (dlzka)
{
if (strstr(text, hladane)) // nachadza sa
{
najdene[pocet_najdenych] = new char[dlzka + 1];
strcpy(najdene[pocet_najdenych], text);
pocet_najdenych++;
}
else // nenachadza sa
{
nenajdene[pocet_nenajdenych] = new char[dlzka + 1];
strcpy(nenajdene[pocet_nenajdenych], text);
pocet_nenajdenych++;
}
cin.getline(text, 1000);
dlzka = strlen(text);
}
int i;
cout << "nachadza " << pocet_najdenych << ":\n";
for (i = 0; i < pocet_najdenych; i++)
{
cout << najdene[i] << endl;
delete[] najdene[i];
}
cout << "\nnenachadza " << pocet_nenajdenych << ":\n";
for (i = 0; i < pocet_nenajdenych; i++)
{
cout << nenajdene[i] << endl;
delete[] nenajdene[i];
}
getch();
}
Práca so špeciálnymi maticami
LU rozklad
V lineárnej algebre existuje metóda riešenia maticových rovníc nazvaná LU rozklad[1][2]. Podstatou tejto metódy je rozložiť štvorcovú maticu na hornú a dolnú trojuholníkovú maticu: [math]A=LU[/math]
[math] A=\left( \begin{matrix} a_{1,1} & a_{1,2} & a_{1,3} & ... & a_{1,n} \\ a_{2,1} & a_{2,2} & a_{2,3} & ... & a_{2,n} \\ a_{3,1} & a_{3,2} & a_{3,3} & ... & a_{3,n} \\ ... & ... & ... & ... & ... \\ a_{n,1} & a_{n,2} & a_{n,3} & ... & a_{n,n} \\ \end{matrix} \right)=\left( \begin{matrix} 1 & 0 & 0 & ... & 0 \\ l_{2,1} & 1 & 0 & ... & 0 \\ l_{3,1} & l_{3,2} & 1 & ... & 0 \\ ... & ... & ... & ... & ... \\ l_{n,1} & l_{n,2} & l_{n,3} & ... & 1 \\ \end{matrix} \right)\left( \begin{matrix} u_{1,1} & u_{1,2} & u_{1,3} & ... & u_{1,n} \\ 0 & u_{2,2} & u_{2,3} & ... & u_{2,n} \\ 0 & 0 & u_{3,3} & ... & u_{3,n} \\ ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & u_{n,n} \\ \end{matrix} \right)[/math] (vzťah 1)
Kde matice L a U sú:
[math]\begin{align} & L=\left( \begin{matrix} 1 & 0 & 0 & ... & 0 \\ l_{2,1} & 1 & 0 & ... & 0 \\ l_{3,1} & l_{3,2} & 1 & ... & 0 \\ ... & ... & ... & ... & ... \\ l_{n,1} & l_{n,2} & l_{n,3} & ... & 1 \\ \end{matrix} \right) \\ & U=\left( \begin{matrix} u_{1,1} & u_{1,2} & u_{1,3} & ... & u_{1,n} \\ 0 & u_{2,2} & u_{2,3} & ... & u_{2,n} \\ 0 & 0 & u_{3,3} & ... & u_{3,n} \\ ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & u_{n,n} \\ \end{matrix} \right) \\ \end{align}[/math](vzťah 2 a 3)
Dôvod prečo sa tento rozklad robí je, že operácie s trojuholníkovými maticami sú jednoduchšie ako so štvorcovými.
Úloha
Vytvorte program, v ktorom načítate 2 trojuholníkové matice (maticu L a maticu U) a tieto matice vynásobte. Takto získame pôvodnú maticu A.
Vstupné údaje
V programe načítajte rozmer matíc –n. Následne načítajte maticu L. Počet prvkov pozostáva z [math]\sum\limits_{i=1}^{n}{i}[/math] prvkov. Prvý načítaný prvok je 1, ďalší [math]L_{2,1}[/math]1, … [math]L_{n,n-1}[/math],1 (pozri vzťah 3). Ako druhú maticu načítajte maticu U. Matica U má taktiež [math]\sum\limits_{i=1}^{n}{i}[/math] prvkov. Prvý prvok je [math]U_{1,1}[/math], následne [math]U_{1,2}[/math] až [math]U_{1,n}[/math], [math]U_{2,2}[/math], ..., [math]U_{n,n}[/math]
Príklad vstupu:
4 1 2 1 3 4 1 5 6 7 1 2 4 3 5 4 6 5 7 6 9
Matice majú nasledovný tvar:
[math]L=\left( \begin{matrix} 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & 4 & 1 & 0 \\ 5 & 6 & 7 & 1 \\ \end{matrix} \right),\,U=\left( \begin{matrix} 2 & 4 & 3 & 5 \\ 0 & 4 & 6 & 5 \\ 0 & 0 & 7 & 6 \\ 0 & 0 & 0 & 9 \\ \end{matrix} \right)[/math]
resp.
[math]L=\left( \begin{matrix} 1 & {} & {} & {} \\ 2 & 1 & {} & {} \\ 3 & 4 & 1 & {} \\ 5 & 6 & 7 & 1 \\ \end{matrix} \right),\,U=\left( \begin{matrix} 2 & 4 & 3 & 5 \\ {} & 4 & 6 & 5 \\ {} & {} & 7 & 6 \\ {} & {} & {} & 9 \\ \end{matrix} \right)[/math]
Výstup pre vzorový príklad:
[math]\left( \begin{matrix} 2 & 4 & 3 & 5 \\ 4 & 12 & 12 & 15 \\ 6 & 28 & 40 & 41 \\ 10 & 44 & 100 & 106 \\ \end{matrix} \right)[/math]
Analýza problému
Pri vytváraní vhodnej štruktúry reprezentujúcu trojuholníkovú maticu budeme vychádzať so skutočného tvaru matice. Vytvoríme maticu, ktorá má v prvom riadku 1 prvok, v druhom 2 prvky a v n-tom riadku bude mať n prvkov. Vytvoriť takúto maticu môžeme pomocou dynamickej alpkácie pamäti nasledujúcim princípom:
int **A=new int*[n];
for(int i=0;i<n;i++)
A[i]=new int[i+1];
A sme si definovali ako dvojitý smerník na int. Alebo inak povedané pole smerníkov o veľkosti n. Pre každý smerník v tomto poli alokujeme pamäť o veľkosti (i+1) int.
Pre násobenie matíc môžeme vytvoriť efektívnejší algoritmus ako pri násobení štvorcových matíc. Pri násobení štvorcových matíc (pri násobení Z=XY) je prvok výslednej matice rovný:
[math]z_{i,j}=\sum\limits_{k=0}^{n}{x_{i,k}\cdot y_{k,j}}[/math]
Pri násobení matíc LU môžeme tento vzorec modifikovať na
[math]z_{i,j}=\sum\limits_{k=0}^{min(i,j)}{x_{i,k}\cdot y_{k,j}}[/math]
Túto modifikáciu je možné urobiť, pretože pri násobeniach, ktoré sme odstránili bolo násobenie nulou. Okrem iného, v našej implementácii matíc L a U nemôžeme použiť pôvodný vzorec, pretože matice sú trojuholníkové – v matici L neexistujú prvky nad hlavnou diagonálou a v matici U neexistujú prvky pod hlavou diagonálou.
V našom zdrojovom kóde vytvoríme funkciu sucinLU, ktorá bude násobiť matice L a U.
Riešenie v jazyku C
1 #include<iostream>
2 #include<math.h>
3
4 using namespace std;
5 void sucinLU(int **XL, int **XU, int **XA, int n)
6 {
7 int i,j,k;
8 for(i=0;i<n;i++)
9 for(j=0;j<n;j++)
10 { XA[i][j]=0;
11 for(k=0;k<min(i+1,j+1);k++)
12 XA[i][j]+=XL[i][k]*XU[k][j-k];
13 }
14 }
15
16 void vypis(int **XA, int n)
17 {
18 int i,j;
19 for(i=0;i<n;i++)
20 {
21 for(j=0;j<n;j++)
22 cout<<XA[i][j]<<"\t";
23 cout<<endl;
24 }
25 }
26 int main()
27 {
28 int n,i,j;
29 cin>>n;
30
31 // L - dolna trojuholnikova matica
32 int **L=new int*[n];
33 for(i=0;i<n;i++)
34 L[i]=new int[i+1];
35
36 // U - horna trojuholnikova matica
37 int **U=new int*[n];
38 for(i=0;i<n;i++)
39 U[i]=new int[n-i];
40
41 // A = LU
42 int **A=new int*[n];
43 for(i=0;i<n;i++)
44 A[i]=new int[n];
45
46 //nacitanie matice L
47 for(i=0;i<n;i++)
48 for(j=0;j<i+1;j++)
49 cin>>L[i][j];
50
51 //nacitanie matice U
52 for(i=0;i<n;i++)
53 for(j=0;j<n-i;j++)
54 cin>>U[i][j];
55
56 sucinLU(L,U,A,n);
57
58 vypis(A,n);
59 }
Zaujímavosťou v zdrojovom kóde je násobenie matíc L a U, konkrétne riadok 12, keď namiesto očakávaného výrazu:
XA[i][j]+=XL[i][k]*XU[k][j];
je riadok
XA[i][j]+=XL[i][k]*XU[k][j-k];
Dôvod: Matica U je horná obdĺžniková matica, ktorá má tvar:
[math]U=\left( \begin{matrix} 2 & 4 & 3 & 5 \\ {} & 4 & 6 & 5 \\ {} & {} & 7 & 6 \\ {} & {} & {} & 9 \\ \end{matrix} \right)[/math]
My ju však reprezentujeme nasledovne: [math]U=\left( \begin{matrix} 2 & 4 & 3 & 5 \\ 4 & 6 & 5 & {} \\ 7 & 6 & {} & {} \\ 9 & {} & {} & {} \\ \end{matrix} \right)[/math]
V tejto matici tvoria stĺpce nasledovné čísla
- 2
- 4, 4
- 3, 6, 7
- 5, 5, 6, 9
Zdroje a odkazy
- ↑ LU metoda http://kfe.fjfi.cvut.cz/~limpouch/numet/linalg/node9.html
- ↑ Priame metódy - http://www.math.sk/skripta/node73.html
