Articolele lui Candale Silviu (silviu)

De la simplu la complex, orice site web este un ansamblu de tehnologii care interacționează. Navigarea pe web are două părți:

• zona client, constând în pagina web, vizibilă în browser
• zona server, invizibilă vizitatorului

Acestor două părți le corespunde două componente diferite, din perspectiva programatorului:

• programarea pe client – folosind:
  • HTML – pentru crearea conțintului paginilor
  • CSS – pentru stabilirea aspectului paginilor
  • Javascript – pentru interactivitate și nu numai
• programarea pe server, în PHP, Java, ASP.NET, Node JS etc.

Programarea la nivel de client este posibilă fără utilizarea unui server web, deși nu este recomandat. Programarea la nivel de server necesită existența unui server, eventual unul local. În cazul programării în PHP, se poate folosi serverul web APACHE. ÎN Windows o soluție facilă este instalarea pachetului XAMPP, care integrează serverul de web Apache, server de baze de date MySQL (sau Maria DB), limbajul de programare PHP.

Programare la nivel de client

• Limbajul HTML
  • Introducere
  • Lucrul cu text
  • Stiluri CSS
  • Liste
  • Tabele
  • Legături și imagini
  • Entități HTML
  • Culori
  • Video și audio
  • Elementul HEAD
  • Formulare

WWW (World Wide Web) a fost proiectat ca un set de resurse globale (pagini web, imagini, alte fișiere, etc.), stocate pe diverse servere și conectate la Internet. Fiecare resursă are o adresă unică la nivel global, numită adresă URL (Uniform Resource Locator), iar utilizatorul poate accesa aceste resurse prin intermediul browser-ului și poate naviga între ele foarte ușor folosind mouse-ul sau tastatura.

Legăturile sunt elemente dintr-o pagină web care fac posibilă navigarea între resursele internet. Legătura este o proprietate a unui bloc de text și/sau a unei imagine de a accepta comenzi prin intermediul mouse-ului sau a tastaturii. Aceste comenzi conduc de regulă la navigarea la o altă resursă web.

Elementul a

Pentru a crea o legătură, folosim elementul ancoră <a>...</a>. Acesta trebuie să aibă atributul href, care conține adresa URL a resursei asociate cu legătura, ea fiind absolută sau relativă și poate fi adresa oricărul tip de fișier: document html, imagine, etc. Între etichetele elementului <a> se scrie un text (sau un element imagine) care va fi afișat în pagina web și care va accepta comenzi de la mouse sau de la tastatură.

<a href="https://www.pbinfo.ro">pbinfo.ro</a>

Ancorele pot avea atributul target, prin care se precizează fereastra în care se va deschide resursa precizată prin href. Valoarea implicită este _self, reprezentând fereastra curentă (tab-ul curent). O altă valoare frecvent utilizată este _blank, cu înțelesul de fereatră nouă (tab nou). Mai multe detalii aici: https://developer.mozilla.org/en-US/docs/Web/HTML/Element/a.

<a href="https://www.pbinfo.ro" target="_blank">pbinfo.ro</a>

Adrese relative și adrese absolute

O adresă absolută are următoarea formă:

protocol://nume.domeniu/cale/de/fisier.html

unde protocol este de regulă http sau https, nume.domeniu este numele de domeniu al site-ului în care este localizată resursa, /cale/de este calea spre directorul care conține fișierul resursă, iar fisier.html este fișierul propriu-zis. În acest fel fiecare resursă disponibilă în spațiul WWW este identificabilă.

Un site web reprezintă o colecție de fișiere localizate pe un server, într-un folder. Aceste fișiere pot fi documente html, imagini, fișiere de altă natură. De cele mai multe ori, crearea site-ului începe pe propriul calculator, fără a avea la dispoziție un server, deci fără ca fișierele din site să aibă o adresă URL validă. În acest context, în adresa URL lipsește partea protocol://nume.domeniu/, obținându-se o adresă relativă. Ea este relativă la structura de directoare care fac parte din folder-ul care conține site-ul și la documentul html din care face parte.

Considerăm următoarea structură de foldere și fișiere, în care site, pagini și img sunt foldere:

site
--pagini
----pagina1.html
----pagina2.html
--img
----poza1.jpg
----poza2.jpg
--index.html

În fișierul index.html, următoarele adrese sunt corecte:

<a href="pagini/pagina1.html">Pagina 1</a>
<a href="pagini/pagina2.html">Pagina 2</a>
<a href="img/poza1.jpg">Poza 1</a>
<a href="img/poza2.jpg">Poza 2</a>

Următoarele sunt greșite:

<a href="pagina1.html">Pagina 1</a>
<a href="poza1.jpg">Poza 1</a>
<a href="pagini/poza2.jpg">Poza 2</a>

În fișierul pagini/pagina1.html, următoarele adrese sunt corecte:

<a href="pagina2.html">Pagina 2</a>
<a href="../index.html">Index</a>
<a href="../img/poza1.jpg">Poza 1</a>

Ancore interne și externe

Legăturile de mai sus foloseau ancore externe – resursa destinație era în exteriorul documentului html curent. Putem defini și ancore interne, cu care putem naviga în interiorul paginii web curente.

Mecanismul este următorul:

• se stabilește destinația legăturii, folosind atributul id:

<a id="destinatie"></a>

• se definește elementul <a>:

<a href="#destinatie">Click</a>

Formatarea legăturilor cu CSS

<style>
	#nav{
    	background-color: #ffff00;
        list-style-type: none;
        padding:0;
    }
    #nav li{display: inline;}
    #nav li a{padding:5px; line-height: 20pt; text-decoration: none; background-color: #ff00ff; color: white; float:left; border-right: solid 1px white;}
    #nav li a:hover{background-color: black; text-deoration: underline;}
</style>
<ul id="nav">
	<li>
    	<a href="#">Link 1</a>
    </li>
    <li>
    	<a href="#">Link 2</a>
    </li>
    <li>
    	<a href="#">Link 3</a>
    </li>
    <li>
    	<a href="#">Link 4</a>
    </li>
</ul>

Inserarea imaginilor

Imaginile îmbunătățesc semnificativ aspectul paginilor web. Pentru a insera o imagini, vom folosi elementul <img>.

<img src="santas.gif">

Adresa propriu-zisă a fișierului imagine se stabilește prin atributul src și este o adresă URL, absolută sau relativă. Acest atribut este practic obligatoriu. Un atribut recomandat este alt – alternative text, care conține un text care va fi afișat în cazul in care nu se poate afișa imaginea:

<img src="santas.gif" alt="Mos Craciun">

Alte atribute utile sunt height și width, care precizează înălțimea, respectiv lățimea, exprimate în pixeli, cu care se va afișa imaginea.

<img src="santas.gif" alt="Mos Craciun" width="100" height="200">

Mai multe informații despre elementul <img> sunt disponibile aici: https://developer.mozilla.org/en-US/docs/Web/HTML/Element/img.

Tabelele permit afișarea informațiilor într-o formă organizată pe rânduri și coloane. Elementul <table> este unul dintre elementele HTML cu complexitate ridicată.

Orice tabel este compus din:

• un element <table>...</table> – acesta conține toate celelalte elemente care definesc tabelul;
• rânduri, definit prin elementul <tr> – table row;
• celule, definite prin elementul <td> – table data, o celulă oarecare a tabelului sau <th> – care definește o celulă care este antet (header) pentru un grup de celule.

Un tabel implicit

În exemplul următor se afișează un tabel cu parametri impliciți.

<p> Un paragraf inaintea tabelului</p>
<table>
    <tr>
        <th>Nume</th>
        <th>Prenume</th>
        <th>Nota</th>
    </tr>
    <tr>
        <td>Popescu</td>
        <td>Ionel</td>
        <td>7</td>
    </tr>
    <tr>
        <td>Vlad</td>
        <td>Gregoria</td>
        <td>8</td>
    </tr>
    <tr>
        <td>Lipan</td>
        <td>Victoria</td>
        <td>10</td>
    </tr>
</table>
<p> Un paragraf dupa tabel.</p>

Un tabel formatat

Următorul tabel este formatat cu CSS:

<style>
	table, td, th {border: solid 1px gray;}
    table{ border-collapse: collapse; width: 100%;}
    th{background-color:lightgray;}
    tr:nth-child(even) td{color:red;}
</style>
<table>
    <tr>
        <th>Nume</th>
        <th>Prenume</th>
        <th>Nota</th>
    </tr>
    <tr>
        <td>Popescu</td>
        <td>Ionel</td>
        <td>7</td>
    </tr>
    <tr>
        <td>Vlad</td>
        <td>Gregoria</td>
        <td>8</td>
    </tr>
    <tr>
        <td>Lipan</td>
        <td>Victoria</td>
        <td>10</td>
    </tr>
</table>

Câteva elemente/atribute utile

Elementele care se folosesc pentru inserarea tabelelor au numeroase atribute. Aici discutăm o mică parte a lor. Pentru detalii consultați următoarele reurse:

• elementul <table> – MDN
• elementul <tr> – MDN
• elementul <td> – MDN

Elementele thead, tbody, tfoot

Rândurile dintru tabel pot fi împărțite din punct de vedere semantic în trei categorii:

• rânduri antet ale tabelului – prin elementul <thead>
• rânduri care desemnează corpul tabelului – prin elementul <tbody>
• rânduri subsol ale tabelului – prin elementul <tfoot>

Aceste elemente fac parte din elementul <table> și conțin zero sau mai multe rânduri (<tr>). Înțelesul lor este pur semantic, dar pot fi folosite și pentru formatarea CSS:

<style>
	table, td, th {border: solid 1px gray;}
    table{ border-collapse: collapse; width: 100%;}
    thead tr{background-color: lightgray;}
    tbody tr{background-color: #55CCFF;}
    tfoot tr{background-color: #FFFF66;}
</style>
<table>
	<thead>
        <tr>
            <th>Nume</th>
            <th>Prenume</th>
            <th>Nota</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>Popescu</td>
            <td>Ionel</td>
            <td>7</td>
        </tr>
        <tr>
            <td>Vlad</td>
            <td>Gregoria</td>
            <td>8</td>
        </tr>
        <tr>
            <td>Lipan</td>
            <td>Victoria</td>
            <td>10</td>
        </tr>
    </tbody>
    <tfoot>
    	<tr>
        	<td colspan="2">Media</td>
            <td>8.33</td>
        </tr>
    </tfoot>
</table>

Atributele colspan și rowspan

o, Aceste atribute se aplică celulelor (<td> și <th>) și stabilesc pe câte rânduri se extinde celula (atributul rowspan), respectiv pe câte cloane se extinde celula (atributul colspan).

<style>
	table, td{border: solid 1px gray;}
    table{ border-collapse: collapse; width: 100%;}
</style>
<table>
	<tr>
    	<td colspan="2"> 1 </td>
        <td colspan="2"> 2 </td>
    </tr>
    <tr>
    	<td rowspan="2"> 1 </td>
        <td rowspan="2" colspan="2"> 2 </td>
        <td> 3 </td>
    </tr>
    <tr>
    	<td> 1 </td>
    </tr>
    <tr>
    	<td colspan="4"> 1 </td>
    </tr>
</table>

Valorile implite ale atributelor rowspan și colspan sunt 1. Pentru colspan valorile mai mari decât 100 sunt considerate incorecte și redevin 1. Valorile rowspan egale cu 0 extind celula până la sfârșitul secțiunii de tabel din care face parte aceasta (secțiunile sunt definite de elementele <thead>, <tbody> și <tfoot>), iar valorile mai mari decât 65534 sunt reduse la 65534.

Alinierea celulelor

Conținutul unei celule (<td> sau <th>) poate fi aliniat pe orizontală și pe verticală. În acest scop putem folosi atributele align și valign, dar sunt învechite. Utilizarea lor nu este recomandată și se propune folosirea proprietăților CSS, astfel:

• alinierea pe orizontală se realizează prin intermediul proprietății CSS text-align, cu valorile left, right, center sau justify;
• alinierea pe verticală se realizează prin intermediul proprietății CSS vertical-align, cu valorile baseline, top, middle sau bottom;

<style>
	table, td{border: solid 1px gray;}
    td {padding:3px; text-align: center;  height:100px;}
    table{ border-collapse: separate; border-spacing: 3px;}
</style>
<table>
	<tr>
    	<td style="text-align: left; width:120px;"> left </td>
        <td style="text-align: center;"> center </td>
    </tr>
    <tr>
    	<td style="text-align: right;"> right </td>
        <td style="text-align: justify;"> O propozitie mai lunga, care se va intinde pe mai multe linii. </td>
    </tr>
</table>

<style>
	table, td{border: solid 1px gray;}
    td {padding:3px; height:100px;}
    table{ border-collapse: separate; border-spacing: 3px; width: 100%;}
</style>
<table>
	<tr>
    	<td style="vertical-align: baseline;"> baseline </td>
        <td style="vertical-align: top;"> top </td>
    	<td style="vertical-align: middle;"> middle </td>
        <td style="vertical-align: bottom;"> bottom </td>
    </tr>
</table>

O listă este o serie de articole. Putem insera mai multe feluri de liste:

• liste neordonate (marcate)
• liste ordonate (numerotate)
• liste de definiții

Liste neordonate și ordonate

Aceste liste sunt asemănătoare; fiecare element al listei are la început un marcaj care îl evidențiază. În listele neordonate toate elementele listei au același marcaj, în timp ce în listele ordonate marcajele sunt valori în ordine (numere, litere, numere romane).

Pentru definirea acestor liste folosim trei elemente HTML:

• <ol> – pentru a defini o listă ordonată – ordered list;
• <ul> – pentru a defini o listă neordonată – unordered list;
• <li> – pentru a defini un element de listă, indiferent dacă este o listă marcată sau numerotată – list item.

<p>Meniul zilei</p>
<ol>
	<li>
    	Mic dejun
        <ul>
        	<li>Paine</li>
            <li>Unt</li>
            <li>Ceai</li>
    	</ul>
    </li>
    <li>
    	Pranz
        <ul>
        	<li>Ciorba</li>
            <li>Fel principal</li>
            <li>Desert</li>
            <li>Paine</li>
        </ul>
    </li>
    <li>
    	Cina
        <ul>
        	<li>Peste</li>
            <li>Garnitura</li>
        </ul>
    </li>
 <ol>

Aspectul listelor poate fi modificat în felul următor:

• pentru listele numerotate se poate stabili modul de numerotare, cu atribulul type="X", un X poate fi:
  • 1 – implicit, pentru numerotarea cu cifre arabe;
  • A – pentru numerotarea cu litere mari;
  • a – pentru numerotarea cu litere mici;
  • I – pentru numerotarea cu cifre romane scrise cu litere mari;
  • i – pentru numerotarea cu cifre romane scrise cu litere mici;
• valoarea de început a numerotării unei liste este implicit 1, dar poate fi modificată prin intermediul atributului start="N", unde N este un număr întreg;
• marcatorul pentru listele neordonate poate fi ales cu atributul type="T", unde T poate fi disc – implicit, circle sau square. Atributul type este învechit. Pentru stabilirea marcatorului se poate folosi și CSS – vezi următorul exemplu;
• listele pot fi imbricate în orice mod.

<p>Meniul zilei</p>
<ol start="3" type="A">
	<li>
    	Mic dejun
        <ul type="circle">
        	<li>Paine</li>
            <li>Unt</li>
            <li>Ceai</li>
    	</ul>
    </li>
    <li>
    	Pranz
        <ul style="list-style-type: square;">
        	<li>Ciorba</li>
            <li>Fel principal</li>
            <li>Desert</li>
            <li>Paine</li>
        </ul>
    </li>
    <li>
    	Cina
        <ul style="list-style-type: none;">
        	<li>Peste</li>
            <li>Garnitura</li>
        </ul>
    </li>
 <ol>

Liste de definiții

O listă de definiții este o serie de termeni și definițiile acestora. Pentru a insera o listă de definiții folosim marcajele:

• <dl>..</dd> – Description List – pentru a încorpora lista
• <dt>..</dt> – Description Term – pentru a preciza termenul definit
• <dd>..</dd> – Description Details – pentru a preciza descriere (definiția) termenului

<p>Tehnologii web</p>
<dl>
	<dt>HTML</dt>
    <dd>Un limbaj de marcare prin care se precizează conținutul paginii Web.</dd>
    <dd>Înseamnă HyperText Markup Language</dd>

    <dt>CSS</dt>
    <dd>Un standard prin care se formatează elementele din pagina Web.</dd>

    <dt>Javascript</dt>
    <dt>Ecmascript</dt>
    <dd>Un limbaj de programare prin care se adaugă paginii Web interacțiune cu utilizatorul.</dd>
</dl>

Așa cum se vede în exemplul anterior, putem asocia mai multe descrieri cu un anumit termen, și putem asocia mai mulți termeni cu o descriere.

HTML5 promovează separarea prezentării de conținut, în sensul că elementele HTML și atributele lor definesc conținutul paginii, nu aspectul lor. Acesta este lăsat în seama CSS. Avem nevoie de CSS pentru că dorim ca paginile create să arate bine, nu doar să conțină informații utile! Acest articol prezintă pe scurt Foile de Stil în Cascadă – CSS (Cascading Style Sheets).

Când lucrăm cu CSS avem în vedere următoarele:

1. cum formatăm conținutul paginii: culori, fonturi, fundaluri, etc. Acestea sunt stabilite prin intermediul regulilor CSS.
2. cum aplicăm formatările elementelor din pagină. Putem folosi:
   • stiluri inline – pentru un anumit element din pagină se stabilește un set de reguli;
   • selectori – mecanisme prin care un set de reguli CSS se aplică mai multor elemente din pagină.

<h1 style="color:red; text-align: right;">Salut</h1>
<p style="color: #0f0;"> Acesta este un paragraf.</p>
<p> Acesta este alt paragraf.</p>

În exemplul de mai sus am folosit stiluri inline, prin intermediul atributului style, aplicat la elementele <h1> și <p>. S-au folosit câteva reguli CSS:

• color:red; – stabilește culoarea textului, folosind pentru identificare culorii numele acesteia;
• color:#0f0; – stabilește culoarea textului, folosind pentru identificare culorii codul hexazecimal al ei;
• text-align: right; – stabilește aliniarea conținutului unui element de tip block.

<style>
   	h1{
		color:red; text-align: right;
   	}
    p{
    	color: #0f0;
    }
</style>
<h1>Salut</h1>
<p> Acesta este un paragraf.</p>
<p> Acesta este alt paragraf.</p>

În exemplul de mai sus am folosit selectori pentru a preciza elementele cărora li se aplică regulile. Aceștia se scriu în interiorul marcajului <style> și sunt de tipuri diverse. În exemplul de mai sus am folosit selectori element.

Paginile web conțin text. Limbajul HTML oferă o serie de elemente ce permit lucrul cu acesta:

• împărțirea textului în secțiuni
• formatarea textului

Limbajul HTML a evoluat în timp. La început, elementele erau gândite să precizeze direct modul de afișare în pagină a conținutului. De exemplu, elementul <b> precizează că textul este îngroșat, folosit pentru a întări textul. În timp, limbajul HTML a devenit semantic, elementele precizând rolul lor în pagină, nu modul de afișare. Astfel, pentru a întări o porțiune de text se folosește elementul <strong>. Efectul vizual implicit este același cu cel al marcajului <b>.

Elementele care descriu modul de afișare a conținutului, precum și atributele care descriu aspectul conținutului au devenit în prezent învechite (deprecated, obsolete) și se recomandă evitarea lor. Pentru a descrie aspectul elementelor din pagină se folosesc foile de stil în cascadă (CSS).

Elemente block și elemente inline

Elementele cu efect vizual în pagina web pot fi clasificate după modul în care se afișează în pagină:

• elementele block se afișează în pagină unele sub altele, pe verticală;
• elementele inline se afișează în pagină pe orizontală, unele după altele și de regulă fac parte din elemente block.

Elementul p

Când avem un text mai lung, îl împărțim în paragrafe, pentru a ușura citirea lui. Paragrafele se definesc în HTML prin intermediul elementului <p>, un element de tip bloc.

<p> Un paragraf oarecare. </p>

Elementul <p> poate avea atributul align, cu valorile posibile left, center, right sau justify, care stabilește modul în care este aliniat pe orizontală conținutul paragrafului, dar este un atribut învechit. Valoarea sa implicită este left, adică paragraful va avea conținutul aliniat la stânga.

<p align="left"> Un paragraf aliniat la stânga. </p>
<p align="right"> Un paragraf aliniat la dreapta. </p>
<p align="center"> Un paragraf aliniat la centru. </p>

Între blocul definit de elementul <p> și blocul de text anterior se lasă un spațiu.

Titluri

În pagina web se pot introduce titluri. Afișarea lor diferă între ele și diferă de restul paginii.

Sunt șase categorii de titluri, definite prin intermediul elementelor <h1>, <h2>, <h3>, <h4>, <h5>, <h6>. Elementul <h1> definește titlul de importanță maximă, iar <h6> pe cel de importanță minimă.

Conținutul titlurilor poate fi aliniat cu atributul align, care este însă învechit.

<h1>Titlu 1</h1>
<h2>Titlu 2</h2>
<h3>Titlu 3</h3>
<h4>Titlu 4</h4>
<h5>Titlu 5</h5>
<h6>Titlu 6</h6>
<p>Un paragraf oarecare</p>

Citate

În pagina web se pot introduce citate, prin intermediul elementelor <blockquote> și <q>.

<blockquote> este un element block. De regulă se afișează cu o margine vizibilă în partea stângă. Poate avea atributul cite, a cărui valoare este adresa URL a documentului citat. Dacă se dorește afișare în text a documentului citat se poate folosi elementul <cite>.

Elementul <q> este un element inline – se folosește pentru a introduce un citat în interiorul unui block de text – de exemplu în interiorul unui paragraf. Și el are atributul cite, cu același înțeles.

<blockquote cite="https://www.huxley.net/bnw/four.html">
    <p>Words can be like X-rays, if you use them properly—they’ll go through anything. You read and you’re pierced.</p>
    <footer>—Aldous Huxley, <cite>Brave New World</cite></footer>
</blockquote>

<p>Aldous Huxley sayd: <q cite="Brave New World">Words can be like X-rays</q>!</p>

Linii orizontale

Pentru a separa secțiunile unei pagini se pot folosi linii orizontale, prin intermediul elementului <hr>. Acesta are următoarele atribute, toate învechite:

• align, cu valorile posibile left, center și right – precizează alinierea liniei în blocul din care face parte;
• color – stabilește culoarea liniei;
• size – stabilește înălțimea (grosimea) liniei, în pixeli
• width – stabilește lungimea liniei, în pixeli sau procente

<hr>
<hr align="right" width="150" color="red" size="10">
<hr width="150" color="green" size="5">

Blocuri de text preformatat

În pagina web caracterele albe consecutive sunt implicit ignorate. Dacă totuși dorim să afișam un text exact așa cum este scris, putem folosi marcajul <pre>, care definește un bloc de text preformatat. Conținutul său va fi afișat în pagină exact așa cum este scris în documentul HTML, folosind un corp de literă monospațiat.

<pre>Un     text

preformatat,      în care sunt vizibile

spatiile     albe!
</pre>

Elementele div și span

Elementul <div> este un element de tip block generic, care poate fi utilizat în foarte multe moduri. Nu are niciun efect asupra conținutului sau aranjării în pagină dacă nu are atașat CSS.

Elementul <span> este un element inline generic, utilizabil în foarte multe moduri. La fel ca <div>, un are efect asupra conținutului sau aranjării în pagină dacă nu are atașat CSS.

<div style="border: solid 1px red; padding:5px; margin:5px;"> Un bloc DIV.
<div style="border: solid 1px red;  padding:5px; margin:5px;">Alt DIV.</div>
<div style="border: solid 1px green; padding:5px; margin:5px;">Acest DIV contine un <span style="border: dotted 1px red">SPAN</span>.</div>
</div>

Atributul style este folosit pentru formatarea elementelor prin intermediul CSS.

Elemente de frază

Elementele de frază ne permit să dăm un înțeles specific unei secțiuni din document:

• <em>...</em> – pentru evidențiere; textul conținut se afișează înclinat (cursiv);
• <strong>...</strong> – pentru evidențiere; textul conținut se afișează îngroșat (aldin);
• <code>...</code> – pentru inserarea unui fragment de cod de calculator; este afișat cu un font monospațiat;
• <kbd>...</kbd> – pentru inserarea unui caracter sau secvențe de caractere introduse de la tastatură; este afișat de regulă cu un font monospațiat;
• <samp>...</samp> – pentru inserarea text care reprezintă date de ieșire pentru un program de calculator; este afișat de regulă cu un font monospațiat;
• <var>...</var> – pentru a insera nume de variabile dintr-un text matematic sau dintr-un program de calculator; textul conținut se afișează înclinat (cursiv);
• <abbr>...</abbr> – pentru a insera o abrevier sau un acronim; textul conținut se afișează de regulă evidențiat într-un anume fel (de exemplu prin subliniere cu o linie); atributul title are un înțeles semantic – trebuie să conțină doar textul care este abreviat;

<p>
    <em>Text evidentiat</em> cu font inclinat.
</p>
<p>
    <strong>Text evidentiat</strong> cu font ingrosat.
</p>
<p>
    <code>Cod de calculator</code>.
</p>
<p>
    <kbd>CTRL</kbd> + <kbd>S</kbd> realizeaza salvarea documentelor.
</p>
<p>
    <samp>Date de iesire</samp> - font monospatiat.
</p>
<p>
    <var>x + y + z</var> - o expresie matematica.
</p>
<p>
    Invatam <abbr title="HyperText Markup Language">HTML</samp>!
</p>

Introducere

Limbajul HTML este folosit pentru a descrie conținutul paginilor web și este folosit împreună cu alte tehnologii, precum CSS și Javascript.

HTML înseamnă HyperText Markup Language.

Documentele html conțin cod HTML. Ele sunt încărcate în browser, de pe calculatorul local sau de pe Internet. Conținutul său este interpretat de browser; acesta mai încarcă și alte fișiere, de exemplu imagini, precizate în document, și afișează pagina web.

Documentele HTML conțin doar text. Acesta poate fi creat cu orice editor de texte, de exemplu Notepad, dar un editor specializat poate ajuta în realizarea mai rapidă a documentului. Exemple de editoare de text utile în realizarea documentelor HTML: Notepad++, Komodo Edit, Sublime Text Editor, etc.

Pe internet există numeroase locuri unde putem învăța limbajul HTML, și nu numai. Dintre acestea, amintim:

• W3Schools – o platformă de învățare cu tutoriale de mici dimensini, simple și clare, foarte potrivite pentru începători;
• Khan Academy – o suită de lecții interactive, gândite să fie parcurse pas cu pas;
• MDN Web Docs – o platformă a fundației Mozilla – care conține atât tutoriale, cât și referințe complete pentru tehnologiile folosite în crearea unei pagini web.

Ciclul de proiectare a unei pagini web

1. editarea documentul html folosind un editor de text;
2. salvarea cu extensia .html;
3. afișarea paginii web folosind un browser – de exemplu Mozilla Firefox sau Google Chrome.

Primul document HTML

Scrieți codul de mai jos într-un editor de text.

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>Prima pagină</title>
    </head>
    <body>
        <!-- acest text este un comentariu -->
        <h1>Salut</h1>
        <hr>
        <p> Aceasta este prima pagină web.</p>
        <p> <a href="https://www.pbinfo.ro">Link spre pbinfo.</a> </p>
    </body>
</html>

Mai departe:

• salvați fișierul cu numele salut.html, într-un folder pe disc. Extensia html este importantă!
• deschideți folderul unde l-ați salvat și deschideți fișierul cu un browser!

Explicația exemplului

• declarația <!DOCTYPE html> precizează că documentul respectă standardul HTML5.
• elementul <html> este elementul râdăcină al oricărui document html.
• elementul <head> conține informații despre document care nu se vor afișa în pagina web.
• elementul <title> precizează titlul document, așa cum va fi afișat în bara de titlu a browser-ului.
• elementul <meta charset="utf-8"> precizează că documentul este scris folosind codificare UTF-8 pentru caractere. Aceasta permite utilizarea caracterelor cu diacritice, specifice limbii române: ă, â, î, ș, ț.
• elementul <body> conține ceea ce se afișează în fereastra browser-ului.
• elementul <h1> definește un titlu de cel mai important nivel.
• elementul <hr> definește o linie orizontală (horizontal rule)
• elementul <p> definește un paragraf (aliniat) oarecare.
• elementul <a> definește o ancoră; prin intermediul lui se introduc în pagina web link-uri.
• secvența <!-- ... --> este un comentariu. Browserul îl ignoră și nu îl afișează în pagina web; el are importanță numai pentru cei care editează documentul html.

Structura unui document html

Un document html este alcătuit din elemente, sau marcaje (engl. elements): html, head, body, title, h1, p, a , meta, hr.

Elementele sunt inserate în document prin intermediul etichetelor (engl. tags). Acestea conțin elementul între simbolurile <>.

• Majoritatea elementelor sunt definite prin intermediul a două etichete: eticheta de deschidere (ex. <h1>) și eticheta de închidere (ex. </h1>), iar între cele două etichete se află conținutul elementului: <h1>Salut</h1>.
• Există și elemente cu o singură etichetă, de exemplu hr. Eticheta de închidere nu este necesară, deoarece aceste elemente nu au conținut.

Unele elemente pot avea atribute (engl. attributes). Ele furnizează informații suplimentare despre element și se scriu în eticheta de deschidere. Un atribut are de regulă o valoare (engl value), dar există și atribute care nu au valori – simpla prezență a atributului în element este suficientă. Pentru atributele care au valori, ele se dau în forma atribut="valoare"!

De exemplu, în elementul <a href="https://www.pbinfo.ro">Link spre pbinfo.</a>, href este un atribut, iar https://www.pbinfo.ro; valoarea sa stabilește destinația link-ului.

• elementele și atributele lor se scriu cu litere mici
• valorile se scriu între ghilimele duble: "

Spații albe

Browser-ele ignoră spațiile albe (caracterele spațiu, tab, sfârșit de rând). Următoarele secvențe au același efect.

<p> Aceasta este prima pagină web.</p>
<p> 
	Aceasta este prima pagină web.
</p>
<p> 
    Aceasta           este 

prima
            pagină web.
</p>

Pentru a insera un spațiu de dimensiuni mai mari, putem folosi o construcție specială a limbajului HTML:  . Ea se numește entitate HTML (engl. HTML entity).

Pentru trece la rând nou în interiorul unui paragraf, putem folosi elementul <br> (break).

Operațiile logice lucrează cu valori de adevăr. Le folosim instinctiv în viața de zi cu zi, dar uneori ne pun în dificultate atunci când trebuie să le aplicăm într-un algoritm.

Valori de adevăr. Propoziții adevărate și false

Operațiile logice se fac cu valori de adevăr (notate TRUE / FALSE, sau ADEVĂRAT / FALS) sau propoziții care au ca rezultat valori de adevăr. De exemplu:

• “Orașul Sibiu este în România.” – este o propoziție adevărată, are valoarea ADEVĂRAT;
• “Orașul Sibiu este în Bulgaria.” – este o propoziție falsă, are valoare FALS.

Exemple din matematică:

• numărul 19 este impar – ADEVĂRAT
• 10 se divide cu 3 – FALS
• comparații:
  • 3 ≠ 4 – ADEVĂRAT
  • 10 < 5 – FALS
  • x > 3 – nu știm rezultatul; depinde de valoarea lui x!!

Exemple din algoritmică (C/C++):

• 19%2==1 – ADEVĂRAT, în C/C++ rezultatul este 1
• 10%3==0 – FALS, în C/C++ rezultatul este 0
• 3 != 4 – ADEVĂRAT, în C/C++ rezultatul este 1
• 10 < 5 – FALS, în C/C++ rezultatul este 0
• x > 3 – nu știm rezultatul; depinde de valoarea lui x din momentul in care se face comparația!!

De multe ori o propoziție logică conține variabile, iar valoarea de adevăr a ei depinde de valorile variabilelor.

Două propoziții logice, care depind de anumite variabile, sunt echivalente dacă, pentru orice valori ale variabilelor, sunt fie amândouă adevărate, fie amândouă false. De exemplu, propoziția “numărul natural n este par” este echivalentă cu propoziția “restul împărțirii numărului natural n la 2 este 0”.

Operațiile logice

Negarea

Negarea este o operație foarte folosită în viața de zi cu zi. Prin negare, propoziția “Orașul Sibiu este în România.” devine “Orașul Sibiu nu este în România.”, care este FALSĂ. Prin negarea unei propoziții adevărate se obține o propoziție falsă, iar prin negarea unei propoziții false se obține o propoziție adevărată.

În C/C++, negarea este o operație unară, cu prioritate mare, iar operatorul său este !. Ea poate fi aplicată pentru orice valori numerice (și nu numai), dar de regulă se aplică asupra altor valori logice.

• dacă p este o expresie cu valoarea 0 (FALS), atunci !p are valoarea 1 (ADEVĂRAT).
• dacă p este o expresie cu valoarea diferită de 0 (ADEVĂRAT), atunci !p are valoarea 0 (FALS).

Exemple:

int x = 10;
cout << !(x == 10); // 0: x == 10 este adevărat și are rezultat 1, 1 negat este 0
cout << !x == 10; // tot 0, dar se efectuează mai întâi !x, adică !10, cu rezultat 0, apoi 0 == 10, cu rezultat fals, adică 0
cout << !(x < 5); // 1: x < 5 este fals, adică 0, 0 negat este 1

Conjuncția

Conjuncția realizează “compunerea” a două propoziții prin intermediul cuvântului ȘI. Exemple:

• Propoziția “Orașul Sibiu este în România.” ȘI “Orașul Craiova este în România.” este obținută prin compunerea a două propoziții adevărate și este la rândul său adevărată;
• Propoziția “Orașul Sibiu este în România.” ȘI “Orașul Craiova este în Bulgaria.” este obținută prin compunerea unei propoziții adevărate cu una falsă și este la rândul său falsă;
• Propoziția “Orașul Sibiu este în Bulgaria.” ȘI “Orașul Craiova este în România.” este obținută prin compunerea unei propoziții false cu una adevărate și este la rândul său falsă;
• Propoziția “Orașul Sibiu este în Bulgaria.” ȘI “Orașul Craiova este în Bulgaria.” este obținută prin compunerea a două propoziții false și este la rândul său falsă.

Astfel, conjuncția a două propoziții este ADEVĂRAT dacă ambele propoziții sunt adevărate, în toate celelalte cazuri este FALSĂ.

În C/C++ simbolul conjuncției este &&. La fel ca negarea, și conjuncția poate fi aplicată pentru orice valori numerice (și nu numai), dar de regulă se aplică asupra altor valori logice.

Fie p și q două valori numerice:

• dacă p este nenul și q este nenul, atunci (p&&q)==1;
• dacă p este nenul și q este nul, atunci (p&&q)==0;
• dacă p este nul și q este nenul, atunci (p&&q)==0;
• dacă p este nul și q este nul, atunci (p&&q)==0;

Exemple:

cout << (1 < 2 && 2 == 1 + 1); // 1; ADEVĂRAT ȘI ADEVĂRAT este ADEVĂRAT
cout << (1 < 2 && 2 != 1 + 1); // 0; ADEVĂRAT ȘI FALS este FALS
cout << (1 == 2 && 2 == 1 + 1); // 0; FALS ȘI ADEVĂRAT este FALS
cout << (1 == 2 && 2 != 1 + 1); // 0; FALS ȘI FALS este FALS

Disjuncția

Conjuncția realizează “compunerea” a două propoziții prin intermediul cuvântului SAU. Exemple:

• Propoziția “Orașul Sibiu este în România.” SAU “Orașul Craiova este în România.” este obținută prin compunerea a două propoziții adevărate și este la rândul său adevărată;
• Propoziția “Orașul Sibiu este în România.” SAU “Orașul Craiova este în Bulgaria.” este obținută prin compunerea unei propoziții adevărate cu una falsă și este la rândul său adevărată;
• Propoziția “Orașul Sibiu este în Bulgaria.” SAU “Orașul Craiova este în România.” este obținută prin compunerea unei propoziții false cu una adevărate și este la rândul său adevărată;
• Propoziția “Orașul Sibiu este în Bulgaria.” SAU “Orașul Craiova este în Bulgaria.” este obținută prin compunerea a două propoziții false și este la rândul său falsă.

Astfel, disjuncția a două propoziții este ADEVĂRATĂ dacă cel puțin una dintre ele este adevărată; dacă ambele propoziții sunt false, disjucția lor este FALSĂ.

În C/C++ simbolul disjuncției este ||. La fel ca negarea și conjuncția, și disjuncția poate fi aplicată pentru orice valori numerice (și nu numai), dar de regulă se aplică asupra altor valori logice.

Fie p și q două valori numerice:

• dacă p este nenul și q este nenul, atunci (p || q)==1;
• dacă p este nenul și q este nul, atunci (p || q)==1;
• dacă p este nul și q este nenul, atunci (p || q)==1;
• dacă p este nul și q este nul, atunci (p || q)==0;

Exemple:

cout << (1 < 2 || 2 == 1 + 1); // 1; ADEVĂRAT SAU ADEVĂRAT este ADEVĂRAT
cout << (1 < 2 || 2 != 1 + 1); // 1; ADEVĂRAT SAU FALS este ADEVĂRAT
cout << (1 == 2 || 2 == 1 + 1); // 1; FALS SAU ADEVĂRAT este ADEVĂRAT
cout << (1 == 2 || 2 != 1 + 1); // 0; FALS SAU FALS este FALS

Exerciții

7 11 17 19 28 509

Legile lui De Morgan

Acestea stabilesc niște reguli legate de situația în care aplicăm operația de negare asupra unor conjuncții și disjuncții. Formal, ele se exprimă astfel:

Fie p și q două expresii logice. Atunci:

• !(p && q) ↔ !p || !q
• !(p || q) ↔ !p && !q

Prin ↔ se înțelege echivalența a două propoziții.

Exemplu

Fie n un număr natural. Dorim o condiție care să fie adevărată dacă și numai dacă n are exact două cifre. Această condiție este: “mai mare sau egal cu 10 și mai mic decât 100”. Expresia C/C++ este: n >= 10 && n < 100.

Care este condița inversă? Adică, cum exprimăm faptul că n nu are exact două cifre? Dacă n nu are exact două cifre înseamnă că n are o cifră sau n are cel puțin trei cifre. Adică “este mai mic decât 10 sau mai mare sau egal cu 100”. În C/C++: n < 10 || n >= 100.

Adică !(n >= 10 && n < 100) este echivalent cu n < 10 || n >= 100.

Atenție: nu există nicio valoare pentru care n < 10 && n >= 100.

Exerciții

15 18 61 476 529

De exemplu, pentru n=10 și șirul A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2), cel mai lung subșir crescător va conține 5 elemente (5, 7, 8, 9, 10) sau (4, 5, 8, 9, 10).

Problema este una clasică și se rezolvă prin programare dinamică. Subșirul cerut se mai numește și subșir crescător maximal.

O soluție \(O(n^2)\)

Determinarea lungimii maxime

Pentru a determina lungimea maximă a unui subșir crescător al lui A, vom construi un șir suplimentar LG[], cu proprietatea că LG[i] este lungimea maximă a unui subșir care se începe în A[i]. Atunci lungimea maximă a unui subșir crescător va fi cel mai mare element din tabloul LG.

Vom construi șirul LG progresiv, începând de la ultimul element din A, bazându-ne pe următoarele observații:

• LG[i] ≥ 1, ∀i
• LG[n] = 1
• vom determina LG[i] astfel: analizăm toate elementele A[j], cu j>i și îl alegem pe acela pentru care LG[j] este maxim și A[i]≤A[j]. Fie jmax indicele acestui element. Atunci LG[i] devine LG[i] = LG[jmax] + 1 – elementul A[i] se lipește de subșirul care începe în A[jmax].

Secvență C++:

LG[n] = 1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1;
}

După construirea șirului LG, lungimea subșirului maximal se determină ca fiind cea mai mare valoare din tabloul LG.

int pmax = 1;
for(int i = 2 ; i <= n ; i ++)
    if(LG[i] > LG[pmax])
        pmax = p;
cout << LG[pmax];

Reconstituirea subșirului

Există mai multe modalități de reconstituire a subșirului maximal. De asemenea, trebuie spus că pot exista mai multe șiruri maximale; în unele probleme poate fi determinat oricare, în altele trebuie determinat un subșir cu proprietăți suplimentare.

O soluție constă în construirea unui șir suplimentar, Next cu următoarea semnificație: Next[i] este următorul element în subșirul crescător maximal care începe cu A[i]. Dacă nu există un element următor, atunci LG[i] = -1. Acest tabloul se construiește în același timp cu LG, astfel:

LG[n] = 1, Next[n] = -1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1 , Next[n] = -1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1, Next[i] = j;
}

Pentru a afișa subșirul, vom extrage informațiile necesare din șirul Next, pornind de la indicele pmax determinat mai sus:

int p = pmax;
do
{
    cout << p << " ";
    p = Next[p];
}
while(p != -1);

Putem reconstitui subșirul fără a construi șirul Next. La fiecare pas al structurii repetitive de mai sus vom determina un indice pUrm cu proprietatea că LG[pUrm]==LG[p]-1 și A[p] ≤ A[pUrm]:

int p = pmax;
do
{
    cout << p << " ";
    int pUrm = p + 1;
    while(pUrm <= n && ! (A[pUrm] >= A[p] && LG[pUrm] == LG[p] - 1))
        pUrm ++;
    if(pUrm <= n)
        p = pUrm;
    else
        p = -1;
}
while(p != -1);

Altă soluție \(O(n^2)\)

Putem regândi algoritmul de mai sus, astfel încât LG[i] să reprezinte lungime a maximă a unui subșir maximal care se termină în A[i].

• evident, LG[1]=1;
• pentru fiecare element A[i] din șirul dat, vom parcurge elementele din fața sa și îl vom alege pe A[p] atfel încât A[p]≤A[i] și LG[p] este maxim. În acest caz, A[i] se adaugă la subșirul care se încheie în A[p], adică LG[i] devine LG[p]+1.

Lungimea subșriului maximal este cea mai mare valoare din LG, iar recosntituirea lui se face asemănător cu metoda de mai sus, folosind un șir de predecesori Prev[], unde Prev[i] este elementul din fața lui A[i] în subșirul crescător maximal care se încheie în A[i].

O soluție \(O(n \cdot \log n)\)

Algoritmul de mai sus are complexitate pătratică. Următoarea idee permite obținerea unui algoritm \(O(n \cdot \log{n})\).

Vom construi șirul D[], unde D[j] reprezintă un element al șirului A în care se termină un subșir crescător maximal de lungime j. Numărul de elemente pe care le va avea la final tabloul D va reprezenta lungimea subșirului crescător maximal al întregului șir A.

Vom construi șirul D în felul următor:

• fie k lungimea șirului D. Inițializăm k=1 și D[k]=A[1];
• parcurgem șirul A, începând de la al doilea element:
  • dacă A[i]≥D[k], îl adăugăm pe A[i] în șirul D – subșirul crescător maximal al lui A crește cu încă un element
  • dacă A[i]<D[k], vom înlocui cu A[i] pe cel mai mai mic element din D care este mai mare decât acesta

ATENȚIE: Șirul D[] nu conține un subșir crescător al șirului A[]!

Exemplu

Pentru A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2).

Inițial k=1; D[k]=5; parcurgem șirul A, începând de la al doilea element:

Observații

• valorile din șirul D sunt în ordine crescătoare
• fiecare element din șirul A modifică exact un element din șirul D (prin adăugare sau înlocuire).

Aceste observații ne permit să folosim căutarea binară pentru a stabili elementul din D care va fi înlocuit la fiecare pas: vom căuta primul element din D care este mai mare decât A[i]. Acest lucru poate fi realizat manual sau folosind funcția STL upper_bound. Complexitatea va fi \(O(n \cdot \log k)\).

Secvență C++

k = 1, D[k] = A[1];
for(int i = 2 ; i <= n ; i ++)
{
    if(A[i] >= D[k])
        P[++k] = A[i];
    else
    {
        int st = 1 , dr = k , poz = k + 1;
        while(st <= dr)
        {
            int m = (st + dr) / 2;
            if(D[m] > A[i])
                poz = m , dr = m - 1;
            else
                st = m + 1;
        }
        D[poz] = A[i];
    }
}
cout << k << endl;

Reconstituirea subșirului

Pentru a reconstitui sub șirul crescător maximal vom folosi încă un șir P[], unde P[i] reprezintă poziția în șirul D unde a fost plasat (prin adăugare sau prin înlocuire) A[i]. Acesta este construit, pas cu pas, odată cu șirul D[]. Dacă un element A[i] face parte din subșirul crescător maximal, atunci P[i] reprezintă poziția sa în subșir.

Pentru exemplul de mai sus, șirul P[] va fi la final (1,2,2,1,2,3,4,4,5,1).

Reconstituirea propriu-zisă a subșirului se face în felul următor:

• fie k – lungimea subșirului crescător maximal;
• căutăm în șirul P[] un element egal cu k. Fie Ik poziția sa. Atunci A[Ik] reprezintă ultimul element al subșirului crescător maximal – cel de pe poziția k;
• căutăm în șirul P[] un element egal cu k-1, anterior elementului de indice Ik. Fie Ik-1 poziția sa.
• analog se caută în P[] valorile k-2, k-3, ..., 2, 1.
• subșirul crescător maximal va fi (A[I1], A[I2], ..., A[Ik]).

Secvența C++

În secvența de mai jos șirul I[] construit va conține indicii elementelor din A[] care fac parte din subșirul comun maximal.

k = 1;
D[k] = A[1];
P[1] = 1;
for(int i = 2 ; i <= n ; i ++)
	if(A[i] >= D[k])
		D[++k] = A[i], P[i] = k;
	else
	{
		int st = 1 , dr = k , p = k + 1;
		while(st <= dr)
		{
			int m = (st + dr) / 2;
			if(D[m] > A[i])
				p = m, dr = m - 1;
			else
				st = m + 1;
		}
		D[p] = A[i];
		P[i] = p;
	}
int j = n;
for(int i = k ; i >= 1 ; i --)
{
	while(P[j] != i)
		j --;
	I[i] = j;
}

Probleme propuse

• #sclm
• #plopi1
• #radiera
• #sclmprime
• #joc6
• #sclm2
• #inserari

Introducere

Considerăm o matrice (labirint, teren, etc.) cu n linii și m coloane și un mobil aflat inițial în elementul de coordonate (1,1) – colțul stânga-sus, care se poate deplasa din elementul curent, de coordonate (i,j) în unul dintre elementele de coordonate (i+1,j) – aflat pe linia următoare, și (i,j+1) – aflat pe următoarea coloană. Să se determine în câte moduri poate ajunge mobilul în elementul de coordonate (n,m) – colțul dreapta-jos.

Problema are cel puțin două soluții, una care folosește metoda programării dinamice și una care se bazează pe combinatorică.

Rezolvare cu programare dinamică

Să constatăm mai întâi că numărul de drumuri căutat depinde de n și m – la mintea cocoșului, am putea spune. În general, numărul de drumuri de la poziția (1,1) la poziția (i,j) depinde de i și j, și numai de acestea. Atunci, formula recursivă care calculează rezultatul pentru (i,j) va depinde numai de i și de j!

Ne propunem să determinăm numărul de modalități în care mobilul ajunge de la poziția (1,1) în poziția (i,j). Fie acest număr \(F_{i,j}\). Constăm următoarele:

• în orice element de pe linia 1 se poate ajunge într-un singur mod, dinspre stânga, deoarece în poziția (1,j) se poate ajunge numai din poziția (1,j-1). Astfel, \(F_{1,j} = 1\).
• în orice element de pe coloana 1 se poate ajunge într-un singur mod, dinspre linia anterioară, deoarece în poziția (i,1) se poate ajunge numai din poziția (i-1,1). Astfel, \(F_{i,1} = 1\).
• în poziția (i,j) (cu i>1 și j>1) se poate ajunge în două moduri:
  • de sus, din poziția (i-1,j);
  • din stânga, din poziția (i,j-1);
• atunci numărul de posibilități de a ajunge în poziția (i,j) este numărul de posibilități de a ajunge în poziția (i-1,j) adunat cu numărul de posibilități de a ajunge în poziția (i,j-1). Astfel, \(F_{i,j} = F_{i-1,j} + F_{i,j-1}\).
• rezultatul este \(F_{n,m}\).

În concluzie:

\( F_{i,j} = \begin{cases}
1& \text{dacă } i = 1 \text{ sau } j = 1, \\
F_{i-1,j} + F_{i,j-1}& \text{ dacă } i > 1 \text{ și } j > 1
\end{cases} \)

Deoarece formulele se suprapun, implementarea recursivă este foarte lentă. În consecință vom folosi o structură de date suplimentară, mai precis un tablou bidimensional în care A[i][j] reprezintă numărul de modalități de a ajunge din poziția (1,1) în poziția (i,j).

Acest tablou poate fi construit în maniera bottom-up:

int n, m, A[NN][NN];
...
for(int i = 1 ; i <= n ; ++ i)
	A[i][1] = 1;
for(int j = 1 ; j <= m ; ++ j)
	A[1][j] = 1;
for(int i = 2 ; i <= n ; ++ i)
	for(int j = 2 ; j <= m ; ++ j)
		A[i][j] = (A[i-1][j] + A[i][j-1]) % 9901;
cout << A[n][m];

De asemenea, recurența poate fi rezolvată în maniera top-down, cu memoizare:

int n, m, A[NN][NN];

int F(int i , int j)
{
    if(A[i][j] != 0)
        return A[i][j];
    if(i == 1 || j == 1)
        A[i][j] = 1;
    else
        A[i][j] = (F(i-1,j) + F(i,j-1)) % 9901;
    return A[i][j];
}
...
cout << F(n,m);

Rezolvare folosind calcul combinatorial

Pentru această soluție, să observăm că oricare traseu din poziția (1,1) în poziția (n,m), are respectă regulile de deplasare, va face exact n-1 pași spre dreapta și exact m-1 pași în jos. Traseele diferă numai prin ordinea acestor pași, nu prin numărul lor!

Atunci numărul de trasee este egal cu numărul de combinații de n-1 pași spre stânga și m-1 pași spre în jos; altfel spus n+m-2 pași, dintre care n-1 sunt în jos, adică: \(C_{n+m-2}^{n-1}\).

Observații

• numărul de trasee crește foarte repede. Pentru valori relativ mici ale lui n și m se produce overflow. Pentru valori mai mari ale acestora este necesară implementarea operațiilor cu numere mari!
• de multe ori, pentru a rezolva problema cu valori mai mari ale lui n și m, fără însă a implementa operații cu numere mari, se cere determinarea restului împărțirii rezultatului la o valoare dată MOD, adică realizarea operațiilor modulo MOD!
• rezolvarea cu programare dinamică are complexitatea timp \(O(n \cdot m)\). Spațiul de memorie poate fi optimizat, folosind doar două tablouri unidimensionale, unul pentru linia curentă și celălalt pentru linia precedentă. Asta deoarece în calculul valorilor de pe linia curentă i se folosesc doar elemente de pe aceasta și de pe linia precedentă, i-1.
• complexitatea rezolvării cu combinări este cea a algoritmului de determinare a combinărilor. Acestea pot fi determinate fie folosind formula uzuală, fie folosind triunghiul lui Pascal.

Probleme propuse

• #Cladire
• #Cladire1
• #Alice_XI
• #PacMan_XI
• #Expozitie