Wstęp do programowania w języku C/Zadanie algorytmiczne: Różnice pomiędzy wersjami
| Linia 61: | Linia 61: | ||
\pagebreak | \pagebreak | ||
=== Algorytm Euklidesa | === Algorytm Euklidesa === | ||
\begin{tabbing} | \begin{tabbing} | ||
do\=p\a'oki $m \ne n$ wykonuj\\ | do\=p\a'oki $m \ne n$ wykonuj\\ | ||
| Linia 125: | Linia 125: | ||
\pagebreak | \pagebreak | ||
\begin{center} | \begin{center} | ||
== Etapy Programowania == | == Etapy Programowania == | ||
\end{center} | \end{center} | ||
Wersja z 16:00, 13 paź 2006
Przykłady algorytmów
Ciasto marchewkowe
Jeżeli weźmiesz produkty w podanych ilościach i postąpisz zgodnie z opisanymi czynnościami na pewno osiągniesz sukces - otrzymasz wspaniałe ciasto marchewkowe.
Składniki: szklanki cukru, 2 jajka, $3/4$ szklanki oleju, szczypta soli, 1 szklanka mąki, 1 łyżeczka sody, 1 łyżeczka cynamonu, 2 duże marchwie, $3/4$ szklanki posiekanych orzechów, 1 łyżeczka utartej skórki z pomarańczy, 1 łyżeczka utartej skórki z cytryny.\\[.5cm] {\bf Przepis:}\\ Cukier, jajka i olej ubijać mikserem przez 2 minuty.\\ W odrębnej miseczce wymieszać mąkę, sól, sodę i cynamon, a następnie dodać wymieszane składniki do ubitych jajek.\\ Miksować 1 minutę.\\ Dołożyć marchew, orzechy, skórkę cytrynową i pomarańczową.\\ Wymieszać.\\ Piec około 30 minut w temperaturze 180 stopni.\\ Przygotować {\it krem waniliowy}.\\ Zimne ciasto posmarować na górze i po bokach kremem waniliowym.\\[.5cm]
Krem waniliowy
{\bf Składniki:}
3 lyżki miękkiego masła, 2 szklanki cukru pudru,
2 lyżki mleka albo śmietanki, $1/2$ torebki cukru waniliowego.\\[0.5cm]
{\bf Przepis:}\\
Ubijać przez chwilę masło mikserem.\\
Wsypywać stopniowo połowę cukru pudru jednocześnie ubijając.\\
Następnie dodać mleko i wanilię jednocześnie ubijajac.\\
Na koniec dodać resztę cukru pudru ciągle miksując.\\
Jeśli masa jest zbyt gęsta, to dodać więcej mleka.\\[.5cm]
Oto schemat pieczenia ciasta:\\[.5cm] SKŁADNIKI (``dane wejściowe) $\rightarrow$ [PRZEPIS, (PIEC, NARZĘDZIA, PIEKARZ] (``oprogramowanie i sprzęt) $\rightarrow$ CIASTO ( ``wynik)
Rozwiązywanie równania kwadratowego
jeż\=eli a = 0, to\\
\>jeż\=eli b = 0, to\\
\>\>jeżeli c = 0, to r\a'ownanie jest nieoznaczone\\
\>\>w przeciwnym razie nie ma rozwiązania\\
\>w przeciwnym razie jest jedno rozwiązanie -c/b\\
w przeciwnym razie\\
\>policz delta = b*b - 4*a*c\\
\>jeżeli delta $<$ 0, to nie ma rozwiązania\\
\>w przeciwnym razie istnieją dwa (niekoniecznie r\a'ożne)\\
\>\>rozwiązania
$\frac{-b + \sqrt{delta}}{2a}$ oraz
$\frac{-b - \sqrt{delta}}{2a}$.
Schemat rowziązywania równania:\\[.5cm] [DANE WEJŚCIOWE: liczby rzeczywiste $a,b,c$] $\rightarrow$ [CZŁOWIEK, MASZYNA] $\rightarrow$ [WYNIK: rozwiązanie równania kwadratowego $ax^2+bx+c=0$].
Zwróćmy uwagę na operacje, które musimy umieć wykonywać na liczbach rzeczywistych, żeby móc ro\-zwią\-zy\-wać równanie kwadratowe za pomocą przedstawionego algorytmu. Należą do nich operacje arytmetyczne `+', `-', `*', `/', sqrt oraz porównania `$= 0$' i `$< 0$'. \pagebreak
Algorytm Euklidesa
\begin{tabbing} do\=p\a'oki $m \ne n$ wykonuj\\
\>jeżeli $m > n$, to zastąp $m$ przez $m - n$\\ \>w przeciwnym razie zastąp $n$ przez $n - m$\\
\\ wynikiem jest $m$. \end{tabbing} Schemat obliczania $NWD(n,m)$:\\[.5cm] [DANE WEJŚCIOWE: dodatnie liczby całkowite $m$ i $n$] $\rightarrow$ [CZŁOWIEK, MASZYNA] $\rightarrow$ [WYNIK: $NWD(n,m)$]. Algorytm Euklidesa działa dla liczb całkowitych dodatnich z operacją `-' i relacjami $\ne$ oraz $>$. Jeżeli zamiast operacji odejmowania `-' wprowadzimy operację brania reszty z dzielenia ($\bmod$), algorytm Euklidesa można zapisać następująco. \begin{tabbing} policz r r\a'owne $n \bmod m$\\ do\=p\a'oki $r <> 0$ wykonuj\\
\>zastąp $n$ przez $m$ i $m$ przez $r$\\ \>policz r r\a'owne $n \bmod m$\\
\\ wynikiem jest $m$. \end{tabbing}
\end{itemize} \pagebreak {\it Zadanie algorytmiczne} składa się ze \begin{enumerate}
- scharakteryzowania dopuszczalnego, być może nieskończonego zbioru
potencjalnych zestawów danych wejściowych oraz
- określenia pożądanych wyników jako funkcji danych wejściowych.
\end{enumerate}
Warunki na dane wejściowe i na dane wyjściowe (wyniki) nazywamy {\it specyfikacją} zadania algorytmicznego.
Przyjmuje się, że są zadane z góry, albo opis dozwolonych akcji podstawowych, albo konfiguracja sprzętowa, w ktorą je wbudowano. Rozwiązanie zadania algorytmicznego stanowi {\it algorytm} złożony z elementarnych instrukcji zadających akcje z ustalonego zbioru. Algorytm taki, wykonany dla dowolnego dopuszczalnego zestawu danych wejściowych, zawsze rozwiąże zadanie dostarczając wynik zgodny z oczekiwaniami. Algorytm musi zawierać instrukcje sterujące, które wskazują kolejność wykonywania akcji podstawowych. Są trzy podstawowe typy instrukcji sterujących: \begin{itemize}
- następstwo,
- wybór,
- iteracja (ograniczona, warunkowa).
\end{itemize} Możliwe jest składanie instrukcji podstawowych. Algorytmy powinny być zapisywane w jednoznaczny i formalny sposób. Językami zapisu algorytmów na użytek komputerów są {\it języki programowania}. Język programowania składa sie z notacji i reguł, według których zapisujemy algorytmy. Algorytm zapisany w języku programowania nazywamy {\it programem}. {\it Programowaniem} nazywamy proces układania programów dla komputerów. \pagebreak \begin{center}
Etapy Programowania
\end{center} \begin{enumerate}
- Etap projektowania
\begin{itemize}
- analiza problemu
- specyfikacja rozwiązania problemu
- układanie algorytmu
- sprawdzenie poprawności rozwiązania (zgodności ze specyfikacją)
\end{itemize}
- Etap implementacji
\begin{itemize}
- kodowanie (tłumaczenie algorytmu na język programowania)
- testowanie i usuwanie błędów (z pomocą komputera)
\end{itemize}
- Etap instalacji na docelowym komputerze
- Etap użytkowania i pielęgnacji
\end{enumerate}
\pagebreak
Język C
Na tych zajęciach do zapisywania algorytmów będziemy używać języka programowania C. Język C został zaprojektowany przez Dennisa Ritchie w 1972 roku. W roku 1973 część systemu operacyjnego UNIX została przepisana w C. W 1978 Brian Kernigham i Dennis Ritchie opublikowali książkę ``Język programowania C, która wkrótce stała się biblią dla programujących w C. W roku 1989 Amerykański Narodowy Instytut Standaryzacji (American National Standards Institute) przyjął standard języka C zwany odtąd ANSI C. Ta wersja będzie podstawą tego wykładu.
Oto omówione poprzednio algorytmy zapisane w języku C:
Równanie kwadratowe
#include <stdio.h>
#include <math.h>
main()
{
double a, b, c,
delta;
printf(" Podaj wspolczynniki a, b, c < ");
scanf("%lf %lf %lf", &a, &b, &c);
if ( a == 0 )
if ( b == 0 )
if ( c == 0)
printf(" Rownanie nieoznaczone.\n ");
else
printf(" Rownanie nie ma rozwiazania.\n");
else{
printf(" Rownanie ma jedno");
printf(" rozwiazanie: %.2f\n ", -c/b);
}
else{
delta = b*b - 4*a*c;
if ( delta < 0 )
printf(" Rownanie nie ma rozwiazania.\n ");
else{
printf(" Rownanie ma dwa rozwiazania:\n ");
printf("x1 = %.2f, x2 = %.2f",
(-b-sqrt(delta))/2,(-b+sqrt(delta))/2);
}
}
return 0;
}Algorytm Euklidesa
/* Algorytm Euklidesa z odejmowaniem. */
#include <stdio.h>
main()
{
int m, n;
printf("Podaj dwie liczby calkowite");
printf(" dodatnie m i n < ");
scanf("%d %d", &m, &n);
printf(ŃWD(%d,%d) = ", m, n);
while ( n != m)
if ( n > m)
n = n - m;
else
m = m - n;
^M printf("%d\n", m);
return 0;
}
/* Algorytm Euklidesa z ``dzieleniem''. */
#include <stdio.h>
main()
{
int m, n, r;
printf("Podaj dwie liczby calkowite");
printf(" dodatnie m i n < ");
scanf("%d %d", &m, &n);
printf(ŃWD(%d,%d) = ", m, n);
r = n % m;
while ( r != 0){
n = m;
m = r;
r = n % m;
}
printf("%d\n", m);
return 0;
}\end{enumerate}
Inny język
Oto te same algorytmy zapisane w innym języku programowania --- w Pascalu (Wirth, 1971).
program Rownanie(Input,Output);
var
a,b,c,
delta : Real;
begin
Write('Podaj wspolczynniki rownania');
Writeln(' oddzielone pojedynczym odstepem:');
Readln(a,b,c);
if a = 0 then
if b = 0 then
if c = 0 then
Writeln('Rownanie nieoznaczone.')
else Writeln('Rownanie nie ma rozwiazania.')
else Writeln('Rownanie ma jedno rozwiazanie: ',
-c/b)
else
begin
delta := b*b - 4*a*c;
if delta < 0 then
Writeln('Rownanie nie ma rozwiazania.')
else
Writeln('x1 = ',(-b+Sqrt(delta))/(2*a),
' x2 = ',(-b-Sqrt(delta))/(2*a)
end
end.
\pagebreak
program NWD1(input,output);
var
n, m : Integer;
begin
Writeln('Podaj n i m oddzielone znakiem odstepu.');
Readln(N,M);
while n <> m do
if n > m then n := n - m
else m := m - n;
Writeln('Najwiekszy wspolny dzielnik wynosi : ', m)
end.
program NWD2(input,output);
var
n, m,
r : Integer;
begin
Writeln('Podaj n i m oddzielone znakiem odstepu.');
Readln(N,M);
r := n mod m;
while r <> 0 do
begin
n := m; m := r; r := n mod m
end;
Writeln('Najwiekszy wspolny dzielnik wynosi : ', m)
end.Struktura programu w C
Żeby program był zrozumiały przez komputer musi być napisany zgodnie ze sztywnymi regułami dopuszczającymi używanie jedynie specjalnych kombinacji wybranych symboli i słów kluczowych języka programowania, w którym piszemy nasz program. Zestaw reguł, o których jest mowa powyżej nazywamy {\it składnią języka programowania}.\\ Oprócz wyposażenia języka programowania w precyzyjną składnię potrzebne jest jeszcze formalne i jednoznaczne określenie znaczenia ({\it semantyki}) każdego wyrażenia dozwolonego składniowo. \\[0.5cm] Ogólna struktura prostego programu w C:\\
{\it dyrektywy preprocesora} \\
main()\\ \{\\ {\it deklaracje}\\ {\it instrukcje}\\ \}\\[0.5cm] Żeby komputer wykonał algorytm należy postępować według następującego schematu:\\[.5cm] algorytm $\rightarrow$ programowanie ( w C ) $\rightarrow$ program ( w C ) $\rightarrow$ kompilacja $\rightarrow$ program w asemblerze $\rightarrow$ kod maszynowy $\rightarrow$ ładowanie i wykonanie programu.
Pojęcie algorytmu
Geneza pojęcia algorytm:
Jest to termin średniowieczno-łaciński, ale wywodzący się z arabskiego. Pochodzi od imienia perskiego uczonego Muhammeda Al-Chwarizmi (IX wiek). Jego nazwisko pisane po łacinie brzmialo Algorismus. Dlaczego imię Al-Chwarizmiego przetrwało w postaci terminu algorytm? Otóż napisał on wiele prac naukowych, z których większość zachowała się. Oto one: Tablice (astronomia, kalendarz, sinus, cotangens), Arytmetyka (hinduski zapis pozycyjny, metody rachunkowe), Algebra (równania liniowe i kwadratowe), Kalendarz Żydowski, Kroniki, Geografia, Astrologia. Oczywiscie czerpal wiele z nauki greckiej i hinduskiej. Te dwa połączone nurty dały wspaniały wynik w postaci pozycyjnego zapisu liczby i rozwoju metod rachunkowych.
