Základy algoritmizace a programování

Olga Majlingová, Luděk Beneš, Petr Sváček
Ústav technické matematiky

Přednáška č. 3

Jednorozměrná pole. Deklarace proměnné typu pole.

   typ jmeno[konstantni_vyraz];
   /* Napr. */
   int A[10];
   float B[20];

Indexy, meze, prvky pole.

Prvky pole se VŽDY číslují (indexují) od 0 do počet_prvků - 1. Dolní mez indexu nemůže mít jinou hodnotu než nula.

Deklarace int A[10]; definuje pole o velikosti 10, tedy blok po sobě jdoucích prvků pole typu typ pojmenovaných A[0], A[1],...,A[9].

Zápis A[i] odkazuje na i-tý prvek pole.

Zápis A[9] = 7; uloží hodnotu 7 do posledního (desátého) prvku pole A.

Zápis i=1; A[i] = 1; A[i+1] = 3; uloží 1 do druhého prvku pole A a 3 do třetího prvku pole A.

Zápis A[10] = 1; je chybný - pole A nemá jedenáctý prvek.

POZOR: Jazyk C nekontroluje meze !

Operace

Není možné provést operaci s celým polem NAJEDNOU. S prvky pole pracujeme stejně jako s jednoduchými proměnnými, respektive jako s proměnnými typu typ . Chceme li provést stejnou operaci se všemi prvky pole, můžeme zpracovat jednotlivé prvky v cyklu.

Vysvětlené progamy: Načtení posloupnosti dané počtem. Načtení posloupnosti ukončené číslem. Tisk pole po zpátku. Najít v poli největší záporný prvek. Najít prvek, který je nejblíže k aritmetickemu průměru. Určit počet výskytů posledního prvku v posloupnosti.

Stručně algoritmy z přednášek (zapsané v jazyce C)

Načtení posloupnosti dané počtem.
Program deklaruje proměnnou A typu pole, načte do pole hodnoty, zadávané z klávesnice hodnoty vytiskne (pozor: nekontroluje meze!)

#include <stdio.h>

main()
{
  int A[100]; /* pole celych cisel (maximalne 100) */
  int i;
  int n;
  
  printf("Kolik cisel (max. %d):",100);
  scanf("%d",&n);
  
  /* chybi kontrola jestli to omezeni uzivatel pochopil ...  */
  
  for(i=0; i<n; i++)
  {
    scanf("%d",&A[i]); 
  }

  printf("Pole obsahuje prvky:\n");
  for(i=0; i<n; i++)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}

Chtelo by to kontrolu, zda neni cisel moc, t.j. umistit na vhodne misto

  if (n>100) 
  {
    printf("Chyba, nelze ulozit tolik cisel.\n");
    return -1;
  }

nebo malo (n<1, ale to zatim neni tak podstatne).

Posloupnost cisel ukoncena cislem (napr. 999).
Program nacte do pole hodnoty zadavane z klavesnice (ukoncene hodnotou 999).
POZOR:
Nekontrolujeme meze!

#include <stdio.h>

main()
{
  int A[100];
  int i,n;
  
  printf("Zadejte posloupnost cisel (ukonceni zadanim cisla 999)\n");
  i=0;
  scanf("%d",&A[i]);
  while (A[i]!=999)
  {
    i=i+1;
    scanf("%d",&A[i]);
  }
  n=i;


  printf("Pole obsahuje prvky:\n");
  for(i=0; i<n; i++)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}

Tisk pole po zpátku.
Pole dane poctem.
POZOR:
Nekontrolujeme meze!

#include <stdio.h>

main()
{
  int A[100]; /* pole celych cisel (maximalne 100) */
  int i;
  int n;
  
  printf("Kolik cisel (max. %d):",100);
  scanf("%d",&n);
  
  /* chybi kontrola jestli to omezeni uzivatel pochopil ...  */
  
  for(i=0; i<n; i++)
  {
    scanf("%d",&A[i]); 
  }

  printf("Pole obsahuje prvky (pozpatku):\n");
  for(i=n-1; i>=0; i=i-1)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}

Najít v poli největší záporný prvek.
Program nacte do pole hodnoty zadavane z klavesnice (ukoncene hodnotou 999). V poli pak najde nejvetsi zaporny prvek.

POZOR:
Nekontrolujeme zda pole nejaky zaporny prvek obsahuje!
Nekontrolujeme meze!

#include <stdio.h>

main()
{
  int A[100];
  int i,n,NejvetsiZaporne;
  
  printf("Zadejte posloupnost cisel (ukonceni zadanim cisla 999)\n");
  i=0;
  scanf("%d",&A[i]);
  while (A[i]!=999)
  {
    i=i+1;
    scanf("%d",&A[i]);
  }
  n=i;

  /* -------------------------------------------------- */
  /* POLE NACTENO: Zpracujeme ... */

  i=0;
  /* Nalezneme prvni zaporny prvek. */
  while (A[i]>=0)
  {
    i=i+1;
  }
  /* Mame prvni zaporny: pozor, melo by se zkontrolovat zda nejsme mimo meze ! */
  NejvetsiZaporne=A[i]; 

  /* Ze zbytku pole porovname zaporne s tim, ktery si pamatujeme */
  while (i<n)
  {
    if ((A[i]<0) && (A[i]>NejvetsiZaporne))
    {
      NejvetsiZaporne=A[i];
    }
    i=i+1;
  }

  /* -------------------------------------------------- */
  /* VSE VYTISKNEME */
  printf("Pole obsahuje prvky (nejvetsi zaporny prvek je %d):\n",NejvetsiZaporne);
  for(i=0; i<n; i++)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}

Najít prvek, který je nejblíže k aritmetickemu průměru. Z klavesnice budou zadavana realna cisla. Poslednim cislem bude cislo, jehoz absolutni hodnota je vetsi nebo rovna nez 999.
Urcete jejich aritmeticky prumer a cislo, ktere ma nejmensi odchylku od tohoto aritmetickeho prumeru.
POZOR:
Nekontrolujeme meze!

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

main()
{
  float A[100];
  int i,n,idx;
  float vzdalenost,prumer,val;
  
  printf("Zadejte posloupnost cisel (ukonceni zadanim cisla 999)\n");
  i=0;
  scanf("%f",&A[i]);
  while (A[i]!=999)
  {
    i=i+1;
    scanf("%f",&A[i]);
  }
  n=i;

  /* -------------------------------------------------- */
  /* zpracovani dat: 1. vypocet prumeru */
  prumer=0.;
  for(i=0;i<n;i++)
  {
    prumer=prumer+A[i];
  }
  prumer=prumer/n;

  /* zpracovani dat: hledame prvek ktery je nejblize prumeru */
  idx=0; vzdalenost=fabs(A[idx]-prumer);
  for(i=1;i < n;i++)
  {
    val=fabs(A[i]-prumer);
    if (val<vzdalenost)
    {
      vzdalenost=val;
      idx=i;
    }
  }
  /* -------------------------------------------------- */

  printf("Hledany prvek je A[%d]=%f. Prumer je %f.\n",idx,A[idx],prumer);
  printf("Pole obsahuje prvky:\n");
  for(i=0; i<n; i++)
  {
    printf("A[%d]=%f\n",i,A[i]); 
  }

}

Určit počet výskytů posledního prvku v posloupnosti.
Z klavesnice budou zadavana CELA cisla (typ int). Poslednim cislem bude cislo 999.
Urcete, kolikrat se mezi zadavanymi cisly opakovalo posledni cislo (tj.ktere predchazelo 999)

#include <stdio.h>

main()
{
  int A[100];
  int i,n;
  int pocet_vyskytu, posledni;
  
  printf("Zadejte posloupnost cisel (ukonceni zadanim cisla 999)\n");
  i=0;
  scanf("%d",&A[i]);
  while (A[i]!=999)
  {
    i=i+1;
    scanf("%d",&A[i]);
  }
  n=i;
  
  posledni=A[n-1]; /* tady muze nastat problem! */

  pocet_vyskytu=0;
  for(i=0; i<n; i++)
  {
    if (A[i]==posledni)
    {
      pocet_vyskytu=pocet_vyskytu+1;
    }
  }
  
  
  printf("Posledni cislo (%d) se v posloupnosti vyskytuje %d-krat\n",posledni,pocet_vyskytu);

  printf("Pole obsahuje prvky:\n");

  for(i=0; i<n; i++)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}

Úlohy pro 4. cvičení:
Načtení posloupnosti dané počtem nebo ukončené číslem. Naplnit pole do 10 faktoriálem (hloupá a chytrá varianta).
Určit počet maxim a jejich indexy. Program pro nalezení všech prvočísel do 100 (nejprve metoda "progr. kladivo" - pak Eratosthenovo síto).

Dalsi

Druhy nejvetsi prvek v poli
Je dano pole (zadane poslednim prvkem). Urcete druhe nejvetsi cislo v poli a jeho pozici (index).
Predpokladame, ze v poli jsou alespon 2 cisla (lze zkontrolovat).
POZOR:
Nekontrolujeme meze!

#include <stdio.h>

main()
{
  int A[100];
  int i,n,maximalni,druhe;
  
  printf("Zadejte posloupnost cisel (ukonceni zadanim cisla 999)\n");
  i=0;
  scanf("%d",&A[i]);
  while (A[i]!=999)
  {
    i=i+1;
    scanf("%d",&A[i]);
  }
  n=i;

  if (A[1]>A[0])
  {
    maximalni=A[1];
    druhe=A[0];
  }
  else
  {
    maximalni=A[0];
    druhe=A[1];
  }
  
  for(i=2;i<n;i++)
  {
     if (A[i]>maximalni) 
     {
       druhe=maximalni;
       maximalni=A[i];
     }
     else if (A[i]>druhe)
       {
         druhe=A[i];
       }
  
  } 
  printf("Maximum je %d, druhe maximalni je %d\n",maximalni,druhe);
  printf("Pole obsahuje prvky:\n");
  for(i=0; i<n; i++)
  {
    printf("A[%d]=%d\n",i,A[i]); 
  }

}