Algorytmy

Algorytmy C/C++ Python

Algorytm jest to ciąg czynności lub sposób postępowania prowadzący do wykonania określonego zadania lub rozwiązania problemu w skończonym czasie. Podstawowymi cechami algorytmów są: poprawność — algorytm powinien zwracać poprawne wyniki. jednoznaczność — algorytm powinien przy takim samym zbiorze danych wejściowych zwracać takie same wyniki. skończoność dla każdego zbioru poprawnych danych wejściowych algorytm powinien zwracać wyniki w skończonej liczbie kroków.

Spis treści

1. Rozwiązywanie równań kwadratowych
2. Parzystość liczb
3. Największy wspólny dzielnik rekurencyjnie
4. Silnia rekurencyjnie
5. Uogólniony schemat Hornera
6. Algorytm Newtona
7. Interpolacja Lagrange’a
8. Metoda najmniejszych kwadratów

Rozwiązywanie równań kwadratowych

C

#include<stdio.h>
#include<math.h>

int main()
{
float a, b, c, delta;
printf("Podaj odpowiednio a, b, c: ");
scanf("%f %f %f", &a, &b, &c);
delta = b*b - 4*a*c;
if(delta > 0) printf("Rownanie ma dwa pierwiastki: x1= %f i x2= %f",
( (-b-sqrt(delta)) / (2.0*a) ), ( (-b+sqrt(delta)) / (2.0*a) ));
else if(delta < 0) printf("Rownianie nie ma pierwiastkow");
else printf("Rownianie ma jednen pierwiastek x1= %f", -b/(2.0*a));
return 0;
}

C++

#include<iostream>
#include<cmath>

using namespace std;
int main()
{
float a, b, c, delta;
cout<<"Podaj odpowiednio a, b, c: "<<endl; 
cin>>a>>b>>c;
delta = b*b - 4*a*c;
if(delta > 0) cout<<"Rownanie ma dwa pierwiastki: x1="<<( (-b-sqrt(delta)) / (2.0*a) )
<<" x2= "<<( (-b+sqrt(delta)) / (2.0*a) )<<endl;
else if(delta < 0) cout<<"Rownianie nie ma pierwiastkow"<<endl;
else cout<<"Rownianie ma jednen pierwiastek x1= "<<-b/(2.0*a)<<endl;
return 0;
}

Python

import math

a = float(input("a = "))
b = float(input("b = "))
c = float(input("c = "))
delta = b*b - 4*a*c
if(delta > 0): print("Rownanie ma dwa pierwiastki x1=", (-b-math.sqrt(delta)) / (2*a),
" x2= ",(-b+math.sqrt(delta)) / (2*a))
elif(delta < 0): print("Rownanie nie ma pierwiastkow")
else: print("Rownanie ma jeden pierwiastek x1= ", -b / (2*a))

Parzystość liczb

C

#include<stdio.h>

int main()
{
int a;
printf("Podaj liczbe do sprawdzenia: ");
scanf("%d", &a);
if((a % 2)==1) printf("Nieparzysta");
else printf("Parzysta");
return 0;
}

C++

 

#include<iostream> 

using namespace std;
int main()
{
int a;
cout<<"Podaj liczbe do sprawdzenia: "; cin>>a;
if((a % 2)==1) cout<<"Nieparzysta";
else cout<<"Parzysta";
return 0;
}

Python

a = int(input("Podaj liczbe do sprawdzenia: "))
if((a % 2)==1): print("Nieparzysta")
else: print("Parzysta")

Algorytm korzysta z funkcji modulo

Największy wspólny dzielnik rekurencyjnie

C/C++

long long NWD(long long x, long long y)
{
if(y==0) return x;
else return NWD(y, x%y);
}

Python

def NWD(x,y):
if(y==0): return x
else: NWD(y, x%y)

W tym przykładzie kod nie różni się zbytnio w poszczególnych językach programowania jednak warto mieć na uwadze że funkcję modulo stosuje się na liczbach całkowitych. W przypadku języka C do wyświetlenia liczby należy użyć „%lli”.

Silnia rekurencyjnie

C/C++

long long silnia(int n)
{
if(n==0) return 1;
else return n * silnia(n-1);
}

Python

def silnia(n):
if(n==0): return 1;
else: return n * silnia(n-1);

Algorytm również można wykonać za pomocą iteracji potocznie mówiąc pętli.

Uogólniony schemat Hornera

C++

#include<iostream>
 
using namespace std; 
int main() 
{ 
    int n=1, i=0; 
    float wynik, punkt, wspolczynniki[n+1]; 
    cin>>punkt>>n; 
    for(i=0; i<=n; i++) { cin>>wspolczynniki[i]; 
    } 
    while(i<=n) 
    { 
        wynik= wynik*punkt + wspolczynniki[i]; 
        i++; 
    } 
    for(i=0; i<n; i++) 
    { 
        for(int k=1; k<n-1; k++) 
        { 
            wspolczynniki[k] = wspolczynniki[k-1]*punkt + wspolczynniki[k]; 
            wynik = wspolczynniki[k]; 
        } 
silnia = long long silnia(int n);
cout<<"Wynik: "<<wynik/silnia<<endl;
return 0;
}

Metoda Newtona

C++

#include<iostream>

using namespace std;

int main()
{
    int n=0,pom;
    float x[n+1],y[n+1], p, IR[n+1];
    cout << "Podaj liczbe wezlow: " << endl; cin >> n;
    cout << "Podaj kolejno x: "<<endl;
    for(int i=0; i<n; i++) { cin >> x[i];
    }
    for(int i=0; i<n-1; i++) { if(x[i]>x[i+1])
        {
            cout << "Zle podane x"<<endl;
            return 0;
        }
    }
    cout << "Podaj kolejno y: "<<endl;
    for(int i=0; i<n; i++) { cin >> y[i];
    }
    cout << "Podaj punkt pomiaru: "; cin >> p;
    if(p<x[0] || p>x[n-1])
    {
        cout <<  "Nie spelnione warunki";
        return 0;
    }
    //-------------------------------------------------------
    for(int i=0; i<=n; i++)
    {
        IR[i]=y[i];
    }

    for(int k=1; k<=n; k++) { for(int i=n; i>=k; i--)
        {
            IR[i]=(IR[i]-IR[i-1])/(x[i]-x[i-k]);
        }
    }
    //---------------------------------------------------------
    int s=0;
    for(int i=0; i<=n-1; i++)
    {
        cout<< "IR[ "<<i<<" ]= "<<IR[i]<<endl;
        pom=1;
        for(int k=0;k<=i-1;k++)
        {
            pom = pom * (p-x[k]);
        }
        s=s+IR[i]*pom;
    }
    cout<<"S "<<s<<endl;

    return 0;
}

Jest to algorytm iteracyjny służący do wyznaczania przybliżonej wartości pierwiastka

Interpolacja Lagrange’a

C++

#include<iostream>

using namespace std;

int main()
{
    int n=1,p;
    float x[n],y[n],wynik;
    float pom,s=0;
    cout << "Podaj liczbe wezlow: " << endl; cin >> n;
    cout << "Podaj kolejno x: "<<endl;
    for(int i=0; i<n; i++) { 
cin >> x[i];
    }
    for(int i=0; i<n-1; i++) { if(x[i]>x[i+1])
        {
            cout << "Zle podane x"<<endl;
            return 0;
        }
    }
    cout << "Podaj kolejno y: "<<endl;
    for(int i=0; i<n; i++) { cin >> y[i];
    }
    cout << "Podaj punkt pomiaru: "; cin >> p;
    if(p<x[0] || p>x[n-1])
    {
        cout <<  "Nie spelnione warunki";
        return 0;
    }

    for(int i=0; i<n; i++)
    {
       pom=1;
       for(int k=0; k<n; k++)
       {
           if(k!=i)
           {
               pom = pom*(p-x[k])/(x[i]-x[k]);
           }
       }
       s=s+pom*y[i];
    }
    cout<<"wynik "<<s<<endl;

    return 0;
}

Jak widać część kodu w tym algorytmie zaciągnięta jest z poprzedniego (metody Newtona)

Metoda najmniejszych kwadratów

C++

#include<iostream>

using namespace std;


int main()
{
    int n;
    float x[100], y[100];
    cout << "\nWprowadz liczbe par:\n"; cin >> n;                           //liczba par x i y
    cout << "\n\nPodaj wartosc pary:\n" << endl;

    for (int i = 0; i < n; i++) //wprowadzanie wartosci poszczegolnych x i y
    {
        cout << "Wartosc: " << i + 1 << " :\n";
        cout << "x: "; cin >> x[i];
        cout << "y: "; cin >> y[i];
    }
    float sumy = 0, sumx = 0, sumxy = 0, sumxx = 0;
    for (int i = 0; i < n; i++)
    {
        sumy += y[i];       //obliczanie sumy y'greków
        sumx += x[i];       //obliczanie sumy x'ów
        sumxx += x[i] * x[i];   //obliczanie sumy x'ów do kwadratu
        sumxy += y[i] * x[i];   //obliczanie sumy y*x
       // sumxx += x[i] * x[i];
    }
    cout << "\n\nWyniki sumx, sumy, sumxy, sumxx: " << sumx << "," //wyniki sum wszystkich
        << sumy << "," << sumxx << "," << sumxy << "." << endl;
    float a = (sumy * sumxx - sumx * sumxy) / (sumx * sumx - n * sumxx);    //tutaj obliczone jest a0=Wa0/W taki jest wzór
    float b = (sumy * sumx - n * sumxy) / (sumx * sumx - n * sumxx);        //tutaj obliczone jest a1=Wa1/W taki jest wzór

    cout << "\n\nWartosc a i b: " << a << " i " << b << "." << endl;
    cout << "\n\nWynik: y = " << a << " + " << b << "x.\n\n" << endl;

    return 0;

}

Standardowa metoda przybliżania rozwiązań układów nad określonych, tzn. zestawu równań, w którym jest ich więcej niż zmiennych