Wstęp do programowania w języku C/Zadanie algorytmiczne

From Studia Informatyczne

Spis treści

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:

  • 1/2 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.

Przepis:

  1. Cukier, jajka i olej ubijać mikserem przez 2 minuty.
  2. W odrębnej miseczce wymieszać mąkę, sól, sodę i cynamon, a następnie dodać wymieszane składniki do ubitych jajek.
  3. Miksować 1 minutę.
  4. Dołożyć marchew, orzechy, skórkę cytrynową i pomarańczową.
  5. Wymieszać.
  6. Piec około 30 minut w temperaturze 180 stopni.
  7. Przygotować krem waniliowy.
  8. Zimne ciasto posmarować na górze i po bokach kremem waniliowym.

Krem waniliowy

Składniki:

  • 3 łyżki miękkiego masła,
  • 2 szklanki cukru pudru,
  • 2 łyżki mleka albo śmietanki,
  • 1/2 torebki cukru waniliowego.

Przepis:

  1. Ubijać przez chwilę masło mikserem.
  2. Wsypywać stopniowo połowę cukru pudru jednocześnie ubijając.
  3. Następnie dodać mleko i wanilię jednocześnie ubijajac.
  4. Na koniec dodać resztę cukru pudru ciągle miksując.
  5. Jeśli masa jest zbyt gęsta, to dodać więcej mleka.

Schemat pieczenia ciasta:

SKŁADNIKI (dane wejściowe) → [PRZEPIS, (PIEC, NARZĘDZIA, PIEKARZ)] (oprogramowanie i sprzęt) → CIASTO (wynik)

Rozwiązywanie równania kwadratowego

Równanie ma postać ax^2+bx+c=0.

jeżeli a = 0, to
  jeżeli b = 0, to
    jeżeli c = 0, to równanie 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óżne) rozwiązania:
    \frac{-b + \sqrt{delta}}{2a} oraz \frac{-b - \sqrt{delta}}{2a}.

Schemat rowziązywania równania:

[DANE WEJŚCIOWE (liczby rzeczywiste a,b,c)] → [CZŁOWIEK, MASZYNA] → [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 rozwiązywać równanie kwadratowe za pomocą przedstawionego algorytmu. Należą do nich operacje arytmetyczne `+', `-', `*', `/', sqrt oraz porównania `= 0' i `< 0'.

Algorytm Euklidesa

Algorytm Euklidesa obliczania największego wspólnego dzielnika dwóch liczb całkowitych m i n.

dopóki m ≠ 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.

Schemat obliczania NWD(n,m)

[DANE WEJŚCIOWE: (dodatnie liczby całkowite $m$ i $n$)] → [CZŁOWIEK, MASZYNA] → [WYNIK: NWD(n,m)].

Algorytm Euklidesa działa dla liczb całkowitych dodatnich z operacją `-' i relacjami ≠ oraz >. Jeżeli zamiast operacji odejmowania '-' wprowadzimy operację brania reszty z dzielenia mod, algorytm Euklidesa można zapisać następująco.

policz r równe n mod m
dopóki r ≠ 0 wykonuj
  zastąp n przez m i m przez r
  policz r równe n mod m 

wynikiem jest m.

Zadanie algorytmiczne

Zadanie algorytmiczne składa się ze:

  1. scharakteryzowania dopuszczalnego, być może nieskończonego zbioru potencjalnych zestawów danych wejściowych oraz
  2. określenia pożądanych wyników jako funkcji danych wejściowych.

Warunki na dane wejściowe i na dane wyjściowe (wyniki) nazywamy 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 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:

  • następstwo,
  • wybór,
  • iteracja (ograniczona, warunkowa).


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ą 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 programem. Programowaniem nazywamy proces układania programów dla komputerów.

Etapy Programowania

  1. Etap projektowania
    • analiza problemu
    • specyfikacja rozwiązania problemu
    • układanie algorytmu
    • sprawdzenie poprawności rozwiązania (zgodności ze specyfikacją)
  2. Etap implementacji
    • kodowanie (tłumaczenie algorytmu na język programowania)
    • testowanie i usuwanie błędów (z pomocą komputera)
  3. Etap instalacji na docelowym komputerze
  4. Etap użytkowania i pielęgnacji

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*a),(-b+sqrt(delta))/(2*a));
    }
  }
 
  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("NWD(%d,%d) = ", m, n);
 
  while ( n != m)
    if ( n > m)
      n = n - m;
    else
      m = m - n;
   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("NWD(%d,%d) = ", m, n);
 
  r = n % m;
  while ( r != 0){
    n = m;
    m = r;
    r = n % m;
  }
  printf("%d\n", m);
  return 0;
}

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.
 
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 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 (semantyki) każdego wyrażenia dozwolonego składniowo.


Ogólna struktura prostego programu w C:
dyrektywy preprocesora
main()
{
deklaracje
instrukcje
}

Żeby komputer wykonał algorytm należy postępować według następującego schematu:

algorytm → programowanie (w C) → program (w C) → kompilacja → program w asemblerze → kod maszynowy → ł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.