Spis algorytmów

Spis algorytmów

1. ALGORYTM OBLICZAJĄCY SUMĘ n KOLEJNYCH LICZB NATURALNYCH

2. Algorytm sprawdzający czy punkt P leży na prostej

3. Algorytm obliczający iloczyn kolejnych liczb naturalnych od 1 do n

4. Algorytm obliczający miejsce miejsce zerowe funkcji

5. Algorytm sprawdzający czy ciąg jest rosnący

6. Algorytm sprawdzający czy liczba jest liczbą pierwszą?

7. Algorytm obliczający wartość liczby podniesionej do potęgi a

8. Algorytm wyznaczający pierwiastki równania kwadratowego

9. Algorytm wyszukujący wartość max w ciągu liczb

10. Algorytm sprawdzający czy liczba jest pierwsza?

11. Algorytm Euklidesa

12. Algorytm Newtona-Raphsona

13. Zamiana systemu dziesiątkowego na binarny

14. Zamiana ułamka dziesiętnego na zwykły

15. Czy napis jest palindromem?

16. Czy napis jest anagramem?

17. Szyfr Cezara

18.  Schemat Hornera

19. Liczby narcystyczne

Liczby narcystyczne

Liczba narcystyczna, inaczej liczba Armstronga – jest to n-cyfrowa liczba naturalna, która jest sumą swoich cyfr podniesionych do potęgi n.

Lista kroków

Dane wejściowe:  liczba: int

Dane pomocnicze:  int n, i, pom, pom2, cyferki, suma : int

                                liczba: string

Dane wyjściowe:  suma: int, odpowiedź czy liczba jest narcystyczna

K01:   Wczytaj liczba

K02: Suma=0

K03: Cyferki=1

K04: Cyferki=strtoint(liczba)

K05: Wczytaj liczba

K06: n= liczba.size()

K07: i=0

K08: Dla i<=n-1 wykonuj od K09 do K12

K09: pom=strtoints(i,liczba)

K10: pom2=pow(pom,n)

K11: suma=suma+pom2

K12: i++

K13: Jeżeli suma==cyferki to Napisz "liczba jest narcystyczna", w przeciwnym wypadku Napisz "liczba nie jest narcystyczna"

Schemat blokowy

Rozwiązanie w C++

#include<iostream> 

#include<string>

#include<cmath>

#include<sstream>

using namespace std; 

int strtoint(string liczba) //tlumaczy string do int dla liczby

{

int rezultat;

istringstream convert(liczba);

convert>>rezultat;

return rezultat;

}

int strtoints(int i, string liczba) //tlumaczy string do int dla pojedynczych cyfr liczby

{

int rezultat;

string pom;

pom=liczba[i];

istringstream convert(pom);

convert>>rezultat;

return rezultat;

}

int main ()

{ 

int n; //dane

int i; 

int pom;

int pom2;

int cyferki;

int suma=0;

string liczba;

cout<<"Podaj liczbe:"<<endl; 

cin>>liczba; //Wczytanie zmiennej liczby

cyferki=1;

cyferki=strtoint(liczba);

n=liczba.size();

cout<<"n = "<<n<<endl;

for (i=0;i<=n-1; i++) //petla, ktora wyswietla pojedyncze cyfry liczby

{

pom=strtoints(i, liczba);

cout<<i+1<<" cyfra liczby: "<<pom<<endl;

pom2=pow(pom,n);

suma=suma+pom2; //suma jest zwiekszana o potęgę poszczególnej cyfry

}

cout<<"suma = "<<suma<<endl;

if (suma==cyferki)

{

cout<<"Liczba jest narcystyczna"<<endl;

}

else cout<<"Liczba nie jest narcystyczna"<<endl;

return 0; 

}

Rozwiązanie w EXCEL

Liczba wprowadzona na początku została podzielona na pojedyncze cyfry. Jest to widoczne w szóstym wierszu. Następnie skopiowano to do kolejnych komórek.

=JEŻELI(DŁ(C4)>10;WARTOŚĆ(FRAGMENT.TEKSTU(C4;DŁ(C4)-10;1));0)

Następnie cyfry te zostały podniesione do potęgi n, czyli ilości cyfr początkowej liczby.

Została wykorzystana poniższa formuła:

=DŁ(C4)

Na koniec program sumuje powyższe potęgi i sprawdza, czy ich suma jest równa liczbie wyjściowej.

=SUMA(D7:N7)

Jeżeli jest równa to początkowa liczba jest narcystyczna.

=JEŻELI(D8=C4;”Liczba jest narcystyczna”;”Liczba nie jest narcystyczna”)

Schemat Hornera

Schemat Hornera jest algorytmem służącym do bardzo szybkiego obliczania wartości wielomianu. Redukuje on ilość mnożeń do minimum.

Dany mamy wielomian stopnia n, gdzie n > 0

Lista kroków:

Specyfikacja:

Dane:

Liczba całkowita: n > 0 (stopień wielomianu).

n+1-elementowa tablica liczb rzeczywistych: A[0...n] (współczynniki wielomianu).

Liczba rzeczywista: x (wartość argumentu).

Wynik:

Wartość rzeczywista wielomianu stopnia n dla wartości argumentu x.

Schemat blokowy

Krok 1:Wczytaj wartości danych n, A[0...n], x.

Krok 2:Przypisz w = A[0].

Krok 3:Dla kolejnych wartości i: 1,2, ..., n, wykonuj krok 4.

Krok 4:Przypisz w = wx+A[i].

Krok 5:Wypisz wartość wielomianu: w. Zakończ algorytm.

C++

#include <iostream>

using namespace std;

int main(void){

int n;

cout<<"Podaj n: "; cin>>n;

float A[n];

float x;

float w;

int i;

//n++;

for(i=0;i<=n;i++){ cout<<"Podaj element nr "<<i<<": ";cin>>A[i];cout<<endl; }

w=A[0];

cout<<"Podaj x: "; cin>>x;

for (i=1;i<=n;i++) w=w*x+A[i];

cout<<"wynik: "<<w;

return 0;

}

Opracował: Jakub W.

Szyfr Cezara

Co to jest?
Zastępuje każdą literę tekstu jawnego inną, przesuniętą względem litery kodowanej o stałą liczbę pozycji w alfabecie.

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście

Łańcuch tekstowy s zaszyfrowany kodem Cezara

Wyjście:

Tekst jawny

Elementy pomocnicze:

i  –  indeks, i N 

kod(x)  – zwraca kod litery x

znak(x)  – zamienia kod x na odpowiadający mu znak ASCII 

Lista kroków:

K01: Dla i = 0,1,...,|s| - 1 wykonuj K02...K03 ; przetwarzamy kolejne znaki tekstu 

K02:     Jeśli s[i] < "A" ∨ s[i] > "Z", to następny obieg pętli K01 ; pomijamy znaki nie będące literami A...Z 

K03:     s[i] ← znak(65 + (kod(s[i] - 42) mod 26) ; deszyfrujemy 

K04: Pisz s   

K05: Zakończ

Schemat blokowy

C++

#include <iostream>

#include <string>

using namespace std;

int main()

{

  string z;

  int i;

// odczytujemy wiersz znaków

cout<<"Podaj tekst do zaszyfrowania ";

  getline(cin,z);

// zamieniamy małe litery na duże

// i kodujemy szyfrem cezara

  for(i = 0; i < z.length(); i++)

  {

    z[i] = toupper(z[i]);

    if((z[i] >= 'A') && (z[i] <= 'Z')) z[i] = char(65 + (z[i] - 62) % 26);

  }

// wypisujemy zaszyfrowany tekst

  cout << z << endl << endl;

  return 0;

} 

Program w Excel

Projektujemy tabelę

1) Numerujemy kolejne litery alfabetu łacińskiego od 0 do 25 (zakres od c4:AB4)

2) Do komórki C4 wprowadzamy funkcję: =ZNAK(C5+65)

3) W 6 wierszu w komórce c6 wprowadzamy klucz będący numerem przesunięcia

4) W komórce C6 wprowadzono formułę, która obliczy nową wartość znaku

W komórki F16-Q16 należy wpisywać litery do zaszyfrowania

W następnym wierszu używamy funkcji: =KOD(komórka wiersz wyżej)-97

W wierszu 20 używamy funkcji: =ZNAK(F19+65) – za F19 wstawiamy komórkę wiersz wyżej, tak samo jak w kroku 2

Po kolei algorytm w Excelu

• wycięcie literki z ciągu -funkcja
•  zamieniasz litery na cyfrę -funkcja
•  dodanie warunku. Chodzi o to, że np. litera 'z' ma numer 122, jeśli dodasz 3 (tak jak normalnie w cyfrze cezara) to dostałbyś znaczek '}' taki. więc musisz napisać, że jeśli ten kod litery > 122, to wracasz do początku etc.
•  nowy kod – zamiana na literę
•  wpisanie w komórkę wyjściową
•  powtarzanie powyższego tyle razy, jaka jest długość słowa.

Opracował:Adam D.

Czy napis jest anagramem?

Anagram 
Anagram jest to wyraz (lub całe zdanie) powstały w wyniku przestawiania liter innego wyrazu, wykorzystując wszystkie jego litery. Pojęcie anagramu jest podstawowym pojęciem jakie należy sobie przyswoić, przed przystąpieniem do matury z informatyki. Zadania związane z anagramami trafiają się bardzo często i wszystkie są do siebie podobne.
Aby sprawdzić czy dany wyraz jest anagramem drugiego, należy sprawdzić czy ich długość jest taka sama. Następnie posortować obydwie zmienne za pomocą sortowania bąbelkowego. Jeżeli posortowane zmienne są takie same i mają taką samą długość, oznacza to że są anagramami.
Dla przykładu:
anagramem wyrazu karol jest wyraz rolka
anagramem wyrazu matura jest wyraz trauma.

Lista kroków:

1. Początek algorytmu
2. Wczytaj pierwsze słowo do zmiennej wyraz1
3. Wczytaj drugie słowo do zmiennej  wyraz2
4. Jeżeli długości zmiennych wyraz1 i wyraz2 są różne, to wyrazy nie są anagramami
5. Posortuj bąbelkowo zmienną wyraz1 i zapisz do zmiennej wyraz1
6. Posortuj bąbelkowo zmienną wyraz2 i zapisz do zmiennej słowo2
7. Jeżeli wyraz1=wyraz2 to wyrazy są anagramami
8. W przeciwnym wypadku nie są anagramami
9. Koniec algorytmu

C++

include <cstdlib>

#include <iostream>

#include <string>

using namespace std;

bool anagram(string wyraz1, string wyraz2)

{

    if (wyraz1.length()!=wyraz2.length())

        return false;   // dlugosc sie nie zgadza

    // sortujemy babelkowo obydwa stringi

    for (int i = 0; i<wyraz1.length()-1; i++)

    {

        for (int j = 0; j<wyraz2.length()-1; j++)

        {

            if (wyraz1[j]>wyraz1[j+1])

                swap(wyraz1[j], wyraz1[j+1]);

            if (wyraz2[j]>wyraz2[j+1])

                swap(wyraz2[j], wyraz2[j+1]);

        }

    }

  return wyraz1==wyraz2; //zwracamy true lub false

}

int main()

{

    string wyraz1, wyraz2;

    cout << "Podaj wyraz pierwszy" << endl;

    cin >> wyraz1;

    cout << "Podaj wyraz drugi" << endl;

    cin >> wyraz2;

    cout << anagram(wyraz1, wyraz2) << endl;

    system("PAUSE");

    return 0;

}

Excel
Jak sprawdzić czy dane słowo jest anagramem w Excelu?
1. Po wprowadzeniu wartości z treścią pierwszego i drugiego wyrazu należy wyodrębnić z wyrazu litery, które tworzą ten wyraz. tą operację wykonujemy za pomocą instrukcji "FRAGMENT TEKSTU" którą stosujemy w kolejnych komórkach kolumny M.

=FRAGMENT.TEKSTU($C$3;1;1)

Analogicznie postępujemy z drugim wyrazem.
2. Pierwszy wyodrębniony wyraz skopiować do komórki C9 (uwaga wkleić tylko wartość a nie formułę). Wklejanie odbywa się za pomocą  makra.
3. Tworzenie makra
a. Rysujemy prostokąt, dodajemy mu tekst o treści "wklej pierwszy wyraz"
b. Uruchamiamy opcję rejestracji makra
c. Wybieramy narzędzie: Deweloper >> Zarejestruj makro
d. Nazywamy makro "Skopiuj1"
e. Nacisnąć "ok"
f. Ustawić się w C9
g. Wykonać kopiowanie z wklejeniem wartości
h. Zatrzymaj makro (z narzędzia Deweloper)
4. Analogicznie postępujemy z drugim wyrazem
5. Utworzyć makro które będzie sortować dane od A do Z w analogiczny sposób dla obydwu wyrazów
6. Projektujemy funkcję która sprawdzi czy wyrazy składają się z takich samych liter
=JEŻELI(C10=E10;0;1)
7. Na końcu należy podsumować (funkcja SUMA, która podsumowuje wyniki)
=SUMA(G10:G23)
8. Wypisujemy funkcję JEŻELI sprawdzającą czy wyrazy składają się z takich samych liter

=JEŻELI(G24=0;"TAK - wyrazy tworzą anagram";"NIE- wyrazy nie są anagramami")

Opracował: Szymon G.

Czy napis jest palindromem?

// post w trakcie tworzenia

Zamiana ułamka dziesiętnego na zwykły

Zasady zmiany
Ułamki dziesiętne zamieniamy na ułamki zwykłe, zapisując je za pomocą kreski ułamkowej, tak jak się czyta. W wyniku zostawia się ułamek nieskracalny tzn. w miarę możliwości należy skrócić ułamek.

C++

#include<iostream>

using namespace std;

int main()

{

  float num, origNum, rem = 1;

  int den = 1, i, count=0, gcd=1;

cout << "wprowadz cyfre dziesietna: ";

 cin >> origNum;

num = origNum - static_cast<int>(origNum);  

 if (num > 0.1)

    {

        while ( (rem > 0.1) )

        {

            num = num * 10;

            rem = num - static_cast<int>(num);

            count++;

        }

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

        {

            den = den * 10;

        }                                                             

for (i = 2; i <= num|| i<=rem; i++)

        {

            if( (static_cast<int>(num) % i == 0) && (den % i == 0) )

            {

                gcd = i;

            }   

        }

        cout << (static_cast<int>(origNum)) << " and " << (static_cast<int>(num))/gcd << "/" << den/gcd;

    }

    else

        cout << (static_cast<int>(origNum));

    return 1;   

}

Program w Excel

Wpisujemy w pole C7 liczbe dziesiętną która automatycznie zamienia nam liczbe dziesiętną w ułamek zwykły.

Opracował: Daniel Gleba