Totul despre PC și mai mult de atât!

Etichetă: algoritm c++

Algoritmul lui Euclid

Algoritmul lui Euclid ne poate ajuta să determinăm, având 2 numere, cel mai mare divizor comun, printr-o metodă simplă şi eficientă din punctul de vedere al consumului de resurse.

„Un număr întreg d se numește cel mai mare divizor comun a numerelor întregi a și b dacă și numai dacă pentru orice divizor comun c al lui a și b, d este un divizor al lui c.

În cazul în care impunem condiția d>0 este relativ simplu de verificat dacă d este unic. Acest număr se notează cu c.m.m.d.c(a,b), sau mai simplu: (a,b).

Folosind principiul bunei ordonări a numerelor naturale, putem deduce că c.m.m.d.c(a,b) este cel mai mic număr pozitiv care poate fi scris ca o combinație liniară a lui a și b, adică cel mai mic număr natural de forma a*x+b*y, unde x,y sunt numere întregi.”

Sursă: Wikipedia

Pseudocod

Di: n, m
De: n

citeşte n, m
┌cât timp n!=m execută
│   ┌dacă n>m
│   │   atunci n←n-m
│   │   altfel m←m-n
│   └■
└■
Scrie n

Limbaj C++

#include <iostream.h>
unsigned int n, m;
main()
{
cin>>n>>m;
while (n=m)
if (n>m) 
n=n-m;
else m=m-n;
Cout<<n;
}

Algoritmul pentru testarea unui număr prim

„Un număr prim este un număr natural care are exact doi divizori: numărul 1 și numărul în sine. Cel mai mic număr prim este 2, în afară de 2 toate numerele prime sunt numere impare.

Un număr natural p > 1 se numește prim dacă : p | ab atunci p | a sau p | b, unde a, b sunt numere naturale.

De exemplu 15 | 9 * 5, dar 15 | 9, 15 | 5, adică 15 nu este număr prim.

În anul 300 î.Hr. Euclid a demonstrat că există o infinitate de numere prime. Iată demonstrația: presupunând prin absurd că p ar fi cel mai mare număr prim, construim numărul n=2x3x5x……xp+1. Acesta nu se divide cu nici unul din numerele 2, 3, 5, ….., p, așadar sau este prim, sau are un divizor prim mai mare ca p, ceea ce contrazice presupunerea că p ar fi cel mai mare număr prim.

Nu se știe dacă există o infinitate de numere prime gemene (impare consecutive ca: [3, 5]; [41, 43]; [59, 61]; [101, 103] etc.).”

Sursă: Wikipedia

Considerand un numar n putem afla daca acesta este prim sau nu aplicand urmatorul algoritm:

Pseudocod

Di: n
De: mesaj (Da/Nu)
Daux: prim, d

citeşte n
prim←1
d←2
┌cât timp d<=n/2 execută
│   ┌dacă n%d=0
│   │   atunci prim←0
│   └■
│ d←d+1
└■
┌dacă prim=1
│   atunci scrie "Da"
│   altfel scrie "Nu"
└■

Limbaj C++

#include <iostream.h>
long int n, prim, d;
main()
{
cin>>n;
prim=1;
d=2;
while (d<=n/2)
{if (n%d==0) 
prim=0;
d=d+1;
}
if (prim==1)
cout<<"Da";
else cout<<"Nu";
}

Algoritmul de spargere a unui numar in cifre

„C++ este un limbaj de programare general, compilat. Este un limbaj multi-paradigmă, cu verificarea statică a tipului variabilelor ce suportă programare procedurală, abstractizare a datelor, programare orientată pe obiecte. În anii 1990, C++ a devenit unul din cele mai populare limbaje de programare comerciale, rămânând astfel până azi.

Bjarne Stroustrup de la Bell Labs a dezvoltat C++ (inițial denumit C cu clase) în anii 1980, ca o serie de îmbunătățiri ale limbajului C. Acestea au început cu adăugarea noțiunii de clase, apoi de funcții virtuale, suprascrierea operatorilor, moștenire multiplă, șabloane și excepții.”

Sursă: Wikipedia

 

Presupunem ca avem un numar n si vrem sa aflam suma cfrelor acestui numar. Pentru asta aveam nevoie de algoritmul de spargere a unui numar in cifre.

 

Pseudocod

Di: n
De: s
Daux: c

citeşte n
s←0
┌cât timp n>0 execută
│ c← n%10
│ s← s+c
│ n← n/10
└■

Limbaj C++

#include <iostream.h>
unsigned int n,s,c;
main()
{
cin>>n;
s=0;
while (n>0)
{c=c%10;
s=s+c;
n=n/10;}
cout<<s;
}

Problemă C++ (variantă BAC informatică III_v24_ex3)

a) Scrieți definiția completă a subprogramului p care primește prin intermediul parametrului n un număr natural nenul (n≤100), iar prin intermediul parametrului x un tablou unidimensional cu n componente întregi, de maximum patru cifre fiecare. Subprogramul furnizează prin intermediul parametrului mini valoarea minimă din tabloul x, prin intermediul parametrului maxi valoarea maximă din x, iar prin intermediul parametrului sum suma elementelor din tabloul x.

b) Scrieți un program C/C++ care citește de la tastatură o valoare naturală nenulă n, (3≤n≤100), apoi cele n elemente, distincte, ale unui tablou unidimensional x. Fiecare dintre aceste elemente este un număr natural având cel mult patru cifre. Folosind apeluri utile ale subprogramului p, programul calculează și afișează pe ecran media aritmetică a elementelor care ar rămâne în tabloul x dacă s-ar elimina valoarea minimă și valoarea maximă din tablou. Valoarea afișată va avea cel mult 3 cifre după virgulă. Exemplu: dacă se citesc pentru n valoarea 5, iar pentru tabloul x valorile (1,9,4,8,5), programul va afișa una dintre valorile 5.667 sau 5.666.

Rezolvare:

#include <iostream.h>
unsigned int n, i;
int x[100], mini, maxi, sum;
float media, sm;
void p (unsigned int n, int x[100], int &mini, int &maxi, int &sum)
{mini=9999;
maxi=-9999;
sum=0;
for (i=1; i<=n; i++)
{if (x[i]<mini) mini=x[i];
if (x[i]>maxi) maxi=x[i];
sum=sum+x[i];
}
}

void main()
{cin>>n;
for (i=1; i<=n; i++)
cin>>x[i];
sm=sum-(mini+maxi);
media=sm/(n-2);
cout<<media;
}

Cum compilăm un algoritm

Cu ceva timp în urmă, Dragoș a prezentat un program care ne ajuta sa scriem un algoritm. Programul se numește MinGW iar tutorialul îl găsiți aici. Acest tutorial este o continuare a ceea ce a făcut Dragoș. Așadar, astăzi vom scrie și executa un algoritm C++.

Algoritmul prezentat, citește dintr-un fișier un șir de numere și stabilește automat valorile maximă, minimă și medie. Apoi la cererea noastră, poate afișa valorile dintr-un anumit interval pe care îl stabilim în prealabil.

Deși pare destul de complicat, codul nu e chiar indescifrabil. Dacă vă veți uita cu atenție la tutorial, dacă veți urmări tutorialul lui Dragoș și dacă veți citi toate articolele pe care le găsiți în categoria Algoritmi C++, atunci cu siguranța veți reuși să înțelegeți ceea ce am vrut să arăt eu și veți putea face și voi mai mult decât copy/paste.

© 2024 PC-Config

Theme by Anders NorenUp ↑