Programe cu vectori si matrice

PROGRAME CU VECTORI SI MATRICE

EXEMPLE DE PROGRAME

E2.1 Citire-scriere vector cu numerotare componente de la zero

// Citirea si afisarea unui vector de numere intregi

#include <stdio.h>

void main ()

E2.2 Vectori cu numerotare de la 1 a elementelor

// Citirea coordonatelor a n puncte din plan

// (x[1],y[1]),(x[n],y[n])

#define M 100 // nr maxim de puncte

void main()

E2.3 Initializare partiala vector

// Generare vector cu primele n numere Fibonacci

#include <stdio.h>

void main () ; // celelalte elemente sunt zero

int n,i;

printf ('n='); scanf('%d',&n);

for (i=2; i<=n && fib[i]>0 ;i++)

fib[i]=fib[i-1]+fib[i-2];

for (i=0; i<=n;i++)

printf ('%ld ',fib[i]);

}

E2.4 Cautare secventiala intr-un vector (prima si ultima aparitie a

numarului cautat).

# include <stdio.h>

void main () ; // un sir de intregi

int n,i,i1,i2, b; // b= valoare cautata

// repeta citire b si cautare in a

n=sizeof(a)/sizeof(a[0]); //lungime vector initializat

while ( scanf('%d',&b) ==1)

Obs. In expresia (i<n && b!=a[i]) ordinea celor 2 conditii este esentiala !

E2.5 Declarare si utilizare matrice

// Generare matrice unitate

#define M 20 // nr maxim de linii si de coloane

void main ()

E2.6 Initializare matrice cu zerouri

// Generare matrice unitate

#define M 20 // nr maxim de linii si de coloane

void main () ;

int i,j,n;

printf('nr.linii/coloane: '); scanf('%d',&n);

for (i=0;i<n;i++)

u[i][i]=1;

}

E2.7 Citire-scriere matrice de reali

void main ()

for (i=0;i<nl;i++)

for (j=0;j<nc;j++)

scnaf ('%f', &a[i][j]);

// afisare matrice

for (i=0;i<nl;i++)

}

PROBLEME PROPUSE

P2.1 Program care citeste un sir de note si calculeaza media notelor de

trecere ( >= 5) si ponderea notelor sub 5 in totalul notelor (procentual).

P2.2 Program care citeste un sir de note (intre 0 si 10) si calculeaza

procentul de note din fiecare valoare posibila ( se afiseaza 10 procente

a caror suma este 100).

P2.3 Program care citeste n numere reale X si m+1 numere intregi A si

afiseaza numarul de valori X situat in fiecare din cele m intervale

delimitate de valorile din A. Se verifica daca valorile A sunt introduse

in ordine crescatoare si in caz contrar programul se opreste.

P2.4 Program care citeste doi vectori neordonati de numere distincte si

verifica daca ei contin aceleasi numere, indiferent de ordine (fara

ordonarea lor). Se poate folosi programul scris si pentru vectori cu

elemente repetate diferit in cei doi vectori ? (Ex: , )

P2.5 Program pentru interclasarea a doi vectori ordonati intr-un singur

vector ordonat, care se va afisa.

Exemplu de date : a=, b=;

Rezultat: 1,2,3,4,6,7,9,11

P2.6 Program pentru citirea unui vector de intregi si extragerea

elementelor distincte intr-un al doilea vector, care se va afisa.

P2.7 Program pentru ordonarea unui vector de numere intregi prin metoda

bulelor: se compara elemente vecine din vector (a[i] si a[i+1] ) si, daca

este necesar, se schimba intre ele pentru ca a[i] <= a[i+1]. In general

sunt necesare mai multe treceri prin vector pentru ordonarea sa. Variante:

(a) Numarul de treceri este egal cu dimensiune vector minus 1.

(b) Se fac atatea treceri cate sunt necesare pentru ordonarea vectorului

(se memoreaza daca au fost necesare schimbari de elemente in vector si se

opreste repetarea cand nu a mai fost necesara nici o schimbare).

(c) O trecere prin vector se face de la prima la ultima pereche

(d) O trecere prin vector se face de la ultima pereche catre prima pereche

P2.8 Program de sortare prin selectie: se compara fiecare element cu

toate elementele urmatoare si se fac schimbarile necesare. Se repeta acest

proces pentru un numar de elemente care scade progresiv. In aceasta varianta

se aduce minimul in prima pozitie din (sub)vector si se mareste indicele

primului element la trecerea urmatoare.

P2.9 Program de sortare prin selectie: se compara fiecare element (pornind

cu ultimul) cu toate elementele precedente si se fac schimbarile necesare.

Se repeta acest proces pentru un numar de elemente care scade progresiv.

In aceasta varianta se aduce maximul in ultima pozitie din (sub)vector si

se scade indicele ultimului element la trecerea urmatoare.

P2.10 Program de sortare prin numarare : se compara fiecare element cu

toate celelalte din vector si se creeaza un vector auxiliar care contine

in pozitia k numarul elemente din vectorul a mai mici decat a[k].

P2.11 Program pentru calculul valorii unui polinom cu coeficienti dati, prin

mai multe metode cu urmatoarea numerotare a coeficientilor:

P(x) = c[0]*x^n + c[1]*x^(n-1) + + c[n-1]*x + c[n]

Datele initiale : x, n, c[0],..c[n]

(a) Ca suma de termeni calculati separat (cu functia 'pow')

(b) Ca suma de termeni calculati unul din altul (fara ridicare la putere)

(c) Printr-o relatie de recurenta de forma P(x,k)=P(x,k-1)*x + c[k] si

P(x,0)=c[0].

P2.12 Program care calculeaza valoarea polinomului de interpolare Newton

cu coeficienti dati, ptr o valoare data xx :

P(xx) = c[0] + c[1]*(xx-x[1]) + c[2]*(xx-x[1])*(xx-x[2]) +

+ c[n]*(xx-x[1])*(xx-x[2])* *(xx-x[n])

Date: n, xx, Vectorul c, Vectorul x,

Obs. Produsele din fiecare termen se pot calcula unele din altele.

P2.13 Program pentru calculul normei pe linii a unei matrice de numere

reale. Norma este valoarea maxima dintre sumele valorilor absolute ale

elementelor din fiecare linie.

P2.14 Program pentru determinarea valorii minime dintre toate valorile

maxime pe liniile unei matrice de numere reale (punct in 'sa').

P2.15 Program pentru afisarea celei mai lungi secvente ordonate de elemente

consecutive dintr-un vector dat. Exemplu de date: 5 3 6 2 4 6 8 4 1

Rezultat: 2 4 6 8

Sa se verifice programul si pentru un vector ordonat descrescator.

P2.16 Un graf (orientat sau neorientat) este reprezentat printr-o matrice

de adiacente 'a', in care a[i][j]=1 daca exista muchie (arc) de la nodul

'i' la nodul 'j' si a[i][j]=0 daca nu exista arcul (i,j). Program pentru

citirea numarului de varfuri dintr-un graf neorientat si listei de muchii

si afisarea varfului cu numar maxim de vecini (de arce incidente).

P2.17 Un graf orientat poate fi reprezentat prin doi vectori de noduri

' v' si 'w', in care v[k]=i si w[k]=j daca exista muchie (arc) de la nodul

'i' la nodul 'j'. Program pentru citirea numarului de noduri din graf si

listei de arce si afisarea succesorilor si predecesorilor fiecarui nod.

Exemplu de date : 1 3 / 1 4 / 2 4 / 3 2 / 4 3 / 4 1 /

Liste de succesori: 1: 3,4 / 2: 4 / 3: 2 / 4: 3,1

Liste de predecesori: 1: 4 / 2: 3 / 3: 1,4 / 4: 1,2

P2.18 Program care citeste mai multe relatii de echivalenta intre

perechi de numere intregi si afiseaza clasele de echivalenta ce se pot

forma cu toate numerele citite. Exemplu de date:

3 6 / 5 7 / 2 5 / 1 3 / 1 6 / 4 8

Clasele de echivalenta sunt: , ,

Se va folosi o matrice patratica cu atatea linii si coloane cate numere

sunt in total. O linie corespunde unei clase de echivalente. Exemplu:

1 2 3 4 5 6 7 8

Clasa 1 1 0 1 0 0 1 0 0

Clasa 2    0 1 0 0 1 0 1 0

Clasa 3    0 0 0 1 0 0 0 1

P2.19 Program care citeste mai multe relatii de echivalenta intre

perechi de numere intregi si afiseaza clasele de echivalenta ce se pot

forma cu toate numerele citite. Exemplu de date:

3 6 / 5 7 / 2 5 / 1 3 / 1 6 / 4 8

Clasele de echivalenta sunt: , ,

Se vor folosi doi vectori: un vector cu elementele clasificate si un

vector cu numarul clasei de care apartine un element. Exemplu:

Elem. 1 2 3 4 5 6 7 8

Clasa 1 2 1 3 2 1 2 3

Obs. Clasele de echivalenta corespund unor grafuri neorientate conexe.

SOLUTII LA PROBLEME PROPUSE

R2.1

// media studentilor integralisti si ponderea restantierilor

#include <stdio.h>

void main ()

if ( m )

printf(' Medie integralisti= %5.2f n', (float)s/m );

printf (' Procent restantieri= %5.2f % n', 100.*(n-m)/n);

R2.2

// statistica notelor unor elevi

#include <stdio.h>

void main ()

R2.3

// clasifica n valori X in m intervale cu limitele A

#include <stdio.h>

void main () ; // init. vector nr

int n,m,i,j; float y;

// citire date

printf ('n='); scanf('%d',&n);

for (i=0;i<n;i++)

printf ('m='); scanf('%d',&m);

for (i=0;i<=m;i++)

scanf('%d',&a[i]);

// verifica daca vectorul a este ordonat

for (i=0;i< m;i++)

if (a[i] >= a[i+1] )

// numara valorile din fiecare interval

for (i=0;i<n;i++)

for (j=0;j<=m;j++)

if ( x[i] > a[j] && x[i] <=a[j+1])

nr[j+1]++;

// afisare contoare

for (j=1;j<=m;j++)

printf ('%4d valori in intervalul %d n', nr[j],j);

R2.4

// comparatie de vectori neordonati

#include <stdio.h>

void main () , b[]=;

int egale, este, i,j;

egale=1; // presupunem ca sunt egali

n=sizeof(a)/sizeof(a[0]); // dimensiune vector a

for (i=0;i<n;i++)

}

printf (egale ? 'egalen':'diferiten');

Obs. Programul se simplifica daca se defineste o functie de cautare a

unui numar intr-un vector.

R2.5

// interclasare vectori ordonati

void main ()

// copiaza in c elem. ramase in a sau in b

for (k=ia;k<=na;k++)

c[ic++]=a[k];

for (k=ib;k<=nb;k++)

c[ic++]=b[k];

nc=--ic; // dimensiune vector rezultat

// afisare vector rezultat

for (k=1;k<=nc;k++)

printf ('%d ',c[k]);

R2.6

// extragere elemente distincte dintr-un vector

#include <stdio.h>

void main () ;    // un vector de intregi

int b[100]; // aici se pun elementele distincte din a

int n,m,i,j, gasit;

n=sizeof(a)/sizeof(a[0]);

m=0; // dimensiune vector b

for (i=0;i<n;i++)

}

m=m-1; // dimensiune vector b

// scrie vector b

for (j=0;j<m;j++)

printf ('%3d',b[j]);

Obs. Programul se simplifica daca se defineste o functie de cautare a

unui numar intr-un vector.

R2.7

// ordonare prin metoda bulelor (var. a)

#include <stdio.h>

void main ()

// afisare vector ordonat

for (i=0;i<n;i++)

printf ('%4d',a[i]);

// ordonare prin metoda bulelor (var. b)

#include <stdio.h>

void main ()

} while ( ! gata);

// afisare vector ordonat

for (i=0;i<n;i++)

printf ('%4d',a[i]);

R2.8

// sortare prin selectie directa (aduce valori mici la inceput)

#include <stdio.h>

void main ()

// scrie vector ordonat

for (i=0;i<n;i++)

printf ('%d ',a[i]);

R2.9

// sortare prin selectie directa (aduce valori mari la sfarsit)

#include <stdio.h>

void main ()

// scrie vector ordonat

for (i=0;i<n;i++)

printf ('%d ',a[i]);

R2.10

// sortare prin numarare

#include <stdio.h>

void main ()

// afisare vector a pe baza lui nr

for (i=0;i<n;i++)

for (j=0;j<n;j++)

if (nr[j]==i)

printf ('%3d',a[j]);

R2.11

// calcul valoare polinom cu coeficienti dati

#include <stdio.h>

#include <math.h>

void main () ;   // vector coeficienti polinom

int n,i; // n= nr coef. polinom

int x, y, px; // x=valoare ptr care se calculeaza polinom

n=sizeof(c)/sizeof(c[0]); // nr de coeficienti

while (scanf('%d',&x)==1)

printf ('%d ',y);

// metoda 3 : relatie de recurenta intre polinoame

y=0; // polinom de grad 0

for (i=0;i<n;i++)

y=y*x+c[i];

printf ('%d n',y);

}

R2.12

// valoare polinom de interp. Newton

#include <stdio.h>

void main () , x[]=;

n=4;

xx=5;

// mai putin eficient

yy=c[0];

for (i=1;i<=n;i++)

printf ('%f ',yy);

// mai eficient

yy=c[0];

p=1;

for (i=1;i<=n;i++)

printf ('%f n',yy);

R2.13

// norma unei matrice (cu numerotare de la 1 ptr linii si col)

#include <math.h>

#include <stdio.h>

#define M 20    // dimensiuni maxime matrice

void main () , , , };

int i,j; float s, smax;

smax=0;

for (i=1;i<=n;i++)

printf ('%f n', smax);

R2.14

// valoare in 'sa' dintr-o matrice

// minim dintre val. maxime pe linii

#include <stdio.h>

#include <math.h>

#define M 20 // nr maxim de linii/coloane

void main () , , , };

int i,j; float min, max;

min = 1e30;

for (i=1;i<=n;i++)

printf ('%f n', min);

R2.15

// secventa ordonata de lungime maxima

#include <stdio.h>

void main () ; // un sir terminat cu zero

int i,j,imax,l, lmax; // imax,lmax = inceput si lungime secventa maxima

imax=i=0; lmax=0; // sau lmax=1

while (a[i])

i=j+1; // continua cautarea din poz. j+1

}

printf ('n %d n', lmax); // lungime secventa

for (i=imax; i<imax+lmax;i++)

printf ('%d ', a[i]);

R2.16

# include <stdio.h>

# define M 30 // nr. maxim noduri graf

void main ()

// determina nod cu nr maxim de vecini

max=0; imax=0; // nr maxim de vecini

for (i=1;i<=n;i++) // retine nr maxim de vecini

}

// afisare nod cu nr maxim de vecini

printf ('Varful %d are %d vecini n ', imax, max);

R2.17

// graf reprezentat prin lista arcelor sale

#include <stdio.h>

# define M 30 // nr. maxim noduri graf

void main ()

// afisare liste de succesori noduri

printf ('Liste de succesori:n');

for (i=1; i<=n;i++)

// afisare liste de predecesori noduri

printf ('Liste de predecesori:n');

for (i=1; i<=n;i++)

// R2.19

/* Program care citeste mai multe relatii de echivalenta intre

perechi de numere intregi si afiseaza clasele de echivalenta ce se pot

forma cu toate numerele citite.

Exemplu de date:

30 60 / 50 70 / 20 50 / 10 30 / 10 60 / 40 80

Clasele de echivalenta sunt: , ,

Se vor folosi doi vectori: un vector cu elementele clasificate si un

vector cu numarul clasei de care apartine un element. Exemplu:

Elem. 10 20 30 40 50 60 70 80

Clasa 1 2 1 3 2 1 2 3

#include <stdio.h>

#define M 100 // numar maxim de elemente clasificate

// reunire clase ce contin valorile p si q

void unif (int cls[],int n,int p,int q) else

// determina indice in vector de valori

int indexOf (int val[],int n, int x)

void main () , cls[M]=;  // valorile si clasele lor

int i,j,p,q,n,m,cl;

// citire relatii de echivalenta

cl=0; // numar clase curente

n=0;

while (scanf('%d%d',&p,&q) > 0)

j=indexOf(val,n,q);

if (j < 0)

unif(cls,n,i,j);

}

// afisare clase

for (i=1;i<=cl;i++)

if (m)

printf('n');

}