Prelucrarea tablourilor bidimensionale

Algoritmi pentru parcurgerea pseudiagonalelor

Prof. Carmen Mincă

Diagonala principală/secundară pentru o matrice patratică

Se consideră matricea următoare:

1. Completaţi enunţul următor încât afirmaţia obţinută să fie adevărată.

O matrice cu n linii şi n coloane admite diagonală principală, respectiv secundară, dacă şi numai dacă .....................

2. Enumeraţi elementele, din matricea alăturată, situate pe diagonala principală.

3. Enumeraţi elementele, din matricea alăturată, situate pe diagonala secundară .

4. Ce relaţie există între indicii elementului a[i][j] situat pe diagonala principală, respectiv secundară, a unei matrice pătratice cu n linii, cu indicii de la 1?

5. Ce structură de control putem utiliza pentru parcurgerea elementelor unei diagonale?

Pseudodiagonale

Fie A o matrice cu n=3 linii şi m=5 coloane (1<n<m<50) cu elemente întregi.

pseudodiagonalele corespunzătoare sunt:

Pseudodiagonale principale

Pseudodiagonale secundare

Problema1:

Scrieţi un program care să determine suma elementelor de pe fiecare pseudodiagonală principală a matricei A cu n linii şi m coloane (1<n<m<50) cu elemente întregi.

Pentru stabilirea algoritmului de rezolvare este necesar să răspundem la următoarele întrebări (completaţi fişa de lucru A):

a) Câte pseudodiagonale principale există în matricea A cu n linii şi m coloane, n<m?

b) Care este poziţia de început şi poziţia de sfârşit pentru fiecare pseudodiagonală principală, poziţii date prin indicii de linie şi coloană?

c) Care este relaţia dintre dintre indicele de linie şi cel de coloană corespunzători elementelor situate pe fiecare pseudodiagonală principală?

Observaţii:1. Fiecare pseudodiagonală principală începe pe linia 1

şi se termină pe linia n

Observaţii:

2. Pseudodiagonala 1 începe din coloana 1, pseudodiagonala 2 începe din coloana 2, pseudodiagonala 3 începe din coloana 3,...., ultima pseudodiagonală începe din coloana n, astfel coloana de început a unei pseudodiagonale este egală cu numărul pseudodiagonalei.

Observaţii

3. Interpretând geometric, observăm că o pseudodiagonală principală, reprezentată printr-o dreaptă ca în desen, formează un unghi de 45o cu orizontala, deci este ipotenuza unui triunghi dreptunghic isoscel. Pentru a calcula coloana de sfârşit pentru fiecare pseudodiagonală, punem condiţia de egalitate a catetelor.

n

n

m- col + 1=n => col=m-n+1

Răspunsurile la întrebări:

a) Câte pseudodiagonale principale există într-o matrice cu n linii şi m coloane?

Răspuns:

Răspunsurile la întrebări:

sunt m-n+1 pseudodiagonale principale în matricea A.

Răspunsurile la întrebări:

b) Care este poziţia de început şi poziţia de sfârşit pentru fiecare pseudodiagonală principală, poziţii date prin indicii de linie şi coloană?

Răspuns:

Răspunsurile la întrebări:

Răspunsurile la întrebări:

c) Care este relaţia dintre dintre indicele de linie şi cel de coloană corespunzători elementelor situate pe fiecare pseudodiagonală principală?

Răspuns:

Răspunsurile la întrebări:

Studiem valorile indicilor poziţiilor elementelor situate pe pseudodiagonala k:

Tema 1 pentru acasă Pe baza rezultatelor obţinute, răspundeţi la următoarele

întrebări referitoare la pseudodiagonalele secundare ale matricei A, completând fişa de lucru B:

a) Câte pseudodiagonale secundare există în matricea A?b) Care este poziţia de început şi poziţia de sfârşit pentru

fiecare dintre pseudodiagonale secundare, pozitii date prin indicii de linie şi coloană?

c) Care este relaţia dintre dintre indicele de linie şi cel de coloană corespunzători elementelor situate pe fiecare pseudodiagonală secundară?

Linia 1 2 3 i n

Coloana n+k-1 n+k-2 n+k-3 n+k-i k+n-1

linie+coloana=n+k

linie+coloana=n+k

1. Sarcina de lucru: Scrieţi o secvenţă pseudocod care să realizeze

parcurgerea pseudodiagonalei principale k şi determinarea sumei elementelor corespunzătoare.

Răspuns

Răspunsurile la întrebări:

2. Sarcină de lucru:

Scrieţi în limbajul C++ programului care rezolvă problema 1 pe baza secvenţei pseudocod de la sarcina 1.

Soluţie

4. Sarcina de lucru>. Submulţimi cu sume egale – Submdij(autor: Prof. Emanuela Cerchez)http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=991

Fie n un număr natural nenul.CerinţăScrieţi un program care să determine n submulţimi disjuncte două câte două de câte n elemente distincte din mulţimea {1, 2, ..., n2}, submulţimi pentru care suma elementelor este aceeaşi.Date de intrareDin fişierul de intrare submdisj.in se citeşte de pe prima linie numărul natural nenul n.Date de ieşireFişierul de ieşire submdisj.out conţine n linii, câte una pentru fiecare submulţime determinată. Pe linia i se află cele n elemente ale submulţimii i, separate prin câte un spaţiu.Restricţii• 0 < n < 101• Două submulţimi sunt disjuncte dacă nu au elemente comune.• Soluţia nu este unică, puteţi afişa orice soluţie care respectă condiţiile din enunţul problemei.• Ordinea submulţimilor sau a elementelor submulţimii NU contează.

Soluţie

Tema pentru acasă

2. Realizaţi modificările necesare asupra programului care rezolva problema 1 (problema1.cpp) astfel încât programul obţinut să rezolve problema:

Problema2: Scrieţi un program care să determine ultima cifră a produsului elementelor situate pe fiecare pseudodiagonală secundară a matricei A cu n linii şi m coloane, 1<n<m<50 şi elemente întregi.

Tema pentru acasă3. Scrieţi un program care să determine suma elementelor de pe

fiecare pseudodiagonală principală a matricei A cu n linii şi m coloane (50>n>m>1) şi elemente întregi.

4. Scrieţi un program care să determine ultima cifră a produsului elementelor situate pe fiecare pseudodiagonală principală a matricei A cu n linii şi m coloane, (50>n>m>1) şi elemente întregi.

Scrieţi pe o foaie de hârtie:

a) 3 termeni ( concepte ) din ceea ce aţi învătat în această oră;

b) 2 idei despre care aţi dori să învăţaţi mai mult în continuare;

c) o capacitate, pricepere sau o abilitate pe care consideraţi că aţi dobândit-o în urma activităţilor de predare – învăţare la Informatică.

Bibliografie Emanuela Cerchez, Marinel Şerban,

Programarea în limbajul C/C++, Ed. Polirom, 2005

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=991