piątek, 21 października 2011

Schemat Hornera


Program na obliczenie wartości wielomianu schematem Hornera iteracyjne i rekurencyjnie

#include <iostream>

using namespace std;


float horner_r (int stopien, int tablica_wsploczynnikow[], int argument)
{
    if (stopien==0)
        return tablica_wsploczynnikow[0];
    else
        return horner_r(stopien-1,tablica_wsploczynnikow,argument)*argument+tablica_wsploczynnikow[stopien];
}

float horner_i (int stopien, int tablica_wsploczynnikow[], int argument)
{
    float wynik=tablica_wsploczynnikow[0];
    for (int i = 1; i<= stopien; i++)
    {
        wynik = wynik * argument + tablica_wsploczynnikow[i];
        cout << i<<": "<<wynik<<endl;
    }
    return wynik;
}
int main()
{
    int stopien,argument;
    cout << "Podaj stopien wielomianu: " << endl;
    cin>> stopien;
    int tablica_wsploczynnikow[stopien];
    cout << "Podaj argument dla ktorego chcesz obliczyc wielomian: " << endl;
    cin >> argument;
    cout << "Podaj wsploczynniki: "<< endl;
    for(int i = 0; i <= stopien; i++)
    {
        cin >> tablica_wsploczynnikow[i];
    }

 cout <<"rekurencyjnie: " << horner_r(stopien,tablica_wsploczynnikow,argument)<<endl;
cout << "itercyjnie: " << horner_i(stopien,tablica_wsploczynnikow,argument);
    return 0;
}

Program na zmianę liczby o podstawie 2-9 na liczbę dziesiętną

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  unsigned podstawa,L,c;

  cout << "Podaj podstawe (2 do 10):";
  cin >> podstawa;
  cout << "\nPodaj liczbe: ";
  cin>>s;
  L = s[0] - int('0');  // Od pierwszego znaku w ASCII w s[] odejmujemy znak ASCII zera (48)
  for(int i = 1; i < s.length(); i++)
  {
    c = s[i] - int('0');  //wczytujemy do c znak ASCII na i-pozycji i zmieniamy go na odpowiadaj¹ca mu liczbê
    L = L * podstawa + c; // stosujemy schemat hornera
  }
  cout << "\nLiczba " << s << "(" << podstawa << ") = " << L << "(10)";

    return 0;
}

niedziela, 9 października 2011

Algorytm szukania najmniejszej i największej liczby w podanym zbiorze

Algorytm 1 - min

Zadanie: Znajdź najmniejszą liczbę spośród podanego zbioru i podaj jej miejsce w zbiorze.

Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza spośród liczb w zbiorze i jej miejsce w zbiorze.

Implementacja w C++

#include <iostream>

using namespace std;

int main()
{
    unsigned int n, min, miejsce;
    cout << "Podaj ilosc elementow: " << endl;
    cin >> n;
    unsigned int t[n];
    for (unsigned int i = 1; i<=n; i++ )
    {
        cout << i << ": ";
        cin >> t[i-1];
        cout << endl;
    }

    min = t[0];

    for (int i = 1; i<n; i++ )
    {
        if(t[i] < min)
        {
            min = t[i];
            miejsce = i;
        }
    }


    cout << "Najmniejsza: "<< min << endl<< "Jest " << miejsce+1<< " liczba w zbiorze";
    return 0;
}

Złożoność algorytmu: T(n) = n - 1

Algorytm 2 - min i max - metodą dziel i zwyciężaj

Zadanie: Znajdź najmniejszą i największą liczbę spośród podanego zbioru.

Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza i największa spośród liczb w zbiorze

Implementacja w C++
#include <iostream>

using namespace std;

int main()
{
    unsigned int n, min, max;

    cout << "Podaj ilosc elementow: " << endl;
    cin >> n;
    unsigned int t[n];

    for (unsigned int i = 1; i<=n; i++ )
    {
        cout << i << ": ";
        cin >> t[i-1];
        cout << endl;
    }

  if (n % 2){ t[n] = t[n-1] }

     min = t[0];
     max = t[0];

    for (unsigned int i = 0; i<n; i=i+2 )
    {
        if (t[i]<t[i+1])
        {
            if(t[i] < min)
                min = t[i];
            if(t[i+1] > max)
                max = t[i+1];
        }

       else //if (t[i] > t[i+1])
       {
            if(t[i+1] < min)
                min = t[i+1];
            if(t[i] > max)
                max = t[i];
       }

    }

    cout << "Najmniejsza: "<< min << endl;
    cout << "Najwieksza: "<< max << endl;

    return 0;
}


Złożoność algorytmu: 3/2 * n

sobota, 1 października 2011

Matura z informatyki - algorytmy

Algorytmy i metody algorytmiczne które są wymagane przez cke:

Poziom podstawowy:
a) algorytmy badające własności liczb całkowitych i naturalnych
b) algorytmy wyszukiwania i porządkowania (sortowania)
c) algorytmy na tekstach
d) proste algorytmy szyfrowania
e) dziel i zwyciężaj
f) iteracja i rekurencja

Poziom rozszerzony:
to co na podstawie +
- metoda zachłanna
- schemat Hornera
- algorytmy numeryczne
- algorytmy kompresji

Strasznie to wygląda, ale damy rady ;) W następnych artykułach opiszę każdy z tych podpunktów.