Vežbe iz Osnova programiranja

 

Studentima se preporučuje da samostalno urade i testiraju rešenja zadataka koji se mogu pogledati na stranici vezba.html

28. NCP koji čita sa standardnog ulaza liniju teksta ograničene dužine (ograničenje broja karaktera se zadaje u programu, MAXLINE), upisuje je u string i ispisuje na standardni izlaz.


#include <stdio.h>
#define MAXLINE 1000  /*limit duzine linije */
#define USPEH 0
int getline( char Line[], int Limit);
/* ucitava sa ulaza liniju limitirane duzine u nisku Line i vraca njenu duzinu */
 

/* glavni program */
main()
{
int duz;  /*broj ucitanih  znakova*/
char linija[MAXLINE];     /*sadrzaj linije */
printf("Unesite red  teksta \n");
duz=getline(linija,MAXLINE);
printf("Uneseno je \n");
printf("%s", linija);
return USPEH;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char Line[], int Limit)
{
 int znak, indeks;
 for( indeks=0; indeks<Limit-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)
  Line[indeks]=znak;
 if( znak=='\n' )
 {
  Line[indeks++]=znak;
  //Line[indeks]=znak;
  //++indeks;
 }
 Line[indeks]='\0';
 return indeks;
}

29. NCP koji će sve linije teksta sa standardnog ulaza ispisati s obrnutim sadržajem na standardni izlaz. Broj linija NIJE unapred ograničen, ali je svaka linija sa ulaza ograničene dužine.


#include <stdio.h>
#define MAXLINE 1000
/* deklaracija funkcija */
int getline( char s[], int Max); /* ucitava liniju i vraca njenu duzinu */
void reverse( char s[] );/* obrce string s */
/* glavni program */
main()
{
  int Len; /*duzina ucitane linije */
  char Line[MAXLINE];/* sadrzaj ucitane linije */
 

/* ucitavanje linija sa ulaza limitirane duzine do markera kraja fajla */
while    ( (Len=getline(Line,MAXLINE)) > 0 )
{   reverse( Line );

/* na izlaz se salje linija okrenuta naopacke */
     printf( "%s\n", Line );
}
return 0;
}
/* reverse: obrce string */
void reverse( char s[] )
{
  int indeks, br; /* brojacke promenljive */
  char  Temp;/* posrednik u razmeni dva karaktera sa iz leve i desne polovine stringa */
  for(indeks=0; s[indeks]!='\0'; ++indeks )
  ;
  br=indeks-1;
/* string s ima br karaktera ne racunajuci \0 i poslednji karakter razlicit od \0 je s[br] */
 

   for( indeks=0; indeks<br; indeks++, br-- )
 {
/* izmena sadrzaja dva karktera: karaktera na i-toj poziciji udesno od pocetka stringa i i-toj poziciji ulevo od kraja stringa */
  Temp=s[indeks];
  s[indeks]=s[br];
  s[br]=Temp;
 }
 return;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char s[], int Limit)
{
int znak, indeks;
for( indeks=0; indeks<Limit-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)     s[indeks]=znak;
if( znak=='\n' )
{s[indeks]=znak;
   ++indeks;
}
s[indeks]='\0';
return indeks;
}

30. NCP koji čita tekst sa standardnog ulaza i svaku linju teksta ispisuje na standardni izlaz šifrirane po shemi koja utiče samo na slova.
SHEMA
A B ... Y Z a b ... y z
c d ... a b D E ... B C

Broj linija teksta nije unapred poznat, linije su limitirane dužine. Može se pretpostaviti da mašinski set znakova odgovara ASCII kôdu.


PRIMER
ULAZ IZLAZ
1. Baba 23/05 1. dDED 23/05
32. Zaza 34/04 32. bDCD 34/04


#include <stdio.h>
#define MAXLINE 1000    /*maksimalna duzina linije */
/* deklaracija funkcija */
int getline( char s[], int MaxLine);
void Cezar( char s[],int pom );
/* glavni program */
main()
{ int duz;        /*duzina tekuce linije */
   char s[MAXLINE];        /*tekuca linija */
  while( (duz=getline(s,MAXLINE)) > 0 )
   {
         Cezar( s,3 );       /*obrada linije po zadatoj shemi */
       printf( "%s\n", s );
   }
  return 0;
}
/* Cezar: sifrira string Cezarovom sifrom, ASCII  */
void Cezar( char s[] ,int pomeraj)
{
  int i;
  for(i=0; s[i]!='\0'; ++i )
  { if  ( s[i]>='A' && s[i]<='Z') s[i]='a' +(pomeraj-1   +     s[i]-'A')%26;
     else  if  ( s[i]>='a' && s[i]<='z') s[i]='A'+   ( pomeraj +    s[i]-'a') %26;
  }
return;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char Line[], int Limit)
{ int znak, indeks;
   for( indeks=0; indeks<Limit-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)  Line[indeks]=znak;
   if( znak=='\n' )
     {  Line[indeks]=znak;
         ++indeks;
      }
   Line[indeks]='\0';
   return indeks;
}

31. NCP kojiće učitati sa standardnog ulaza u jednoj liniji nisku cifara koja reprezentuje pozitivan ceo broj strogo manji od maksimalne vrednosti za tip int, kovertovati ga u numerički ekvivalent (funkcija atoi, str. 41 K&R) i ispisati broj za 1 veći.

NISKA "000723" predstavlja broj 723 čija vrednost se formira (po Hornerovoj shemi???) u formi ('7'-'0')*100 + ('2'-'0')*10 + ('3'-'0') = 7*100 + 2*10 + 3*100 = 10 * ( 10 * (7) + 2) + 3


#include <stdio.h>
#define MAXLINE 1000
int getline( char s[], int Limit);
int atoi( char s[] );
/* glavni program */
main()
{
  int duzina,Number; /*broj unetih cifara broja, numericka vrednost broja */
char s[MAXLINE]; /*niska cifara unetog broja */
printf("Unesite pozitivan ceo broj strogo manji od maximalnog int \n");
duzina=getline(s,MAXLINE);
Number=atoi(s);
printf( "Uvecanjem za jedan se dobija:\n%d\n", ++Number );
return 0;
}
/* atoi: ascii to integer */
int atoi( char s[] )
{   int i, Num=0; /*brojacka promenljiva, numericki ekvivalent niske s*/

/* formiranje vrednosti broja od dekadnih cifara s[i] niske s*/
    for( i=0; s[i]>='0' && s[i]<='9'; ++i) Num=10*Num+(s[i]-'0');
 
 return Num;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char Line[], int Lim)
{
 int znak, indeks;
 for( indeks=0; indeks<Lim-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)
  Line[indeks]=znak;
 if( znak=='\n' )
 {  Line[indeks]=znak;
     ++indeks;
 }
 Line[indeks]='\0';
 return indeks;
}

32. NCP koji učitava nisku koja predstavlja ili heksadekadnu konstantu (npr. 0x1a ili 0XFF, pocinje sa 0x ili 0X) ili heksadekadni broj koji je strogo manji od maksimalne vrednosti INT_MAX. Potom konvertuje nisku u numerički dekadni ekvivalent i ispisuje broj za 1 veći.

PRIMER
ULAZ DEKADNI EKVIVALENT ++IZLAZ
0XA 10 11
0x7ffe 32766 32767




#include <stdio.h>
#include <ctype.h>
#define MAXLINE 1000
int getline( char s[], int Limit);
unsigned htoi( char s[] );
int hexvalue( int znak );

main()
{
int duz; /* duzina ucitane linije */
unsigned Number; /* numericki ekvivalent niske kojom je predstavljena heksadekadna vrednost sa ulaza */
  char linija[MAXLINE]; /* linija sa ulaza */

  printf("Unesite broj \n");
   duz=getline(linija,MAXLINE);
    Number=htoi(linija);
  printf( "Inkrementirani broj je:\n%u\n", ++Number );
return 0;
}

/* hvalue: vrednost hexadecimalne cifre  */
int hexvalue( int znak )
{
  if(isdigit(znak))   return(znak-'0');
   if    (znak>='A' && znak<='F')      return(znak-'A'+10);
   if     (znak>='a' && znak<='f')       return(znak-'a'+10);
return 0;
}
/* htoi: hexadecimal ascii -> integer */
unsigned htoi( char s[] )
{
   int Pos;
 unsigned  Num;
   if((s[0]=='0' && s[1]=='x')     || (s[0]=='0' && s[1]=='X') )        Pos=2;
  else   Pos=0;
for(Num=0; isdigit(s[Pos])
    || (s[Pos]>='A' && s[Pos]<='F')
   || (s[Pos]>='a' && s[Pos]<='f'); ++Pos)
  Num=16*Num+hexvalue(s[Pos]);
return Num;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char Linija[], int Limit)
{
 int  znak, indeks;
 for( indeks=0; indeks<Limit -1&& (znak=getchar())!=EOF && znak!='\n'; ++indeks)
  Linija[indeks]=znak;
 if( znak=='\n' )
 {Linija[indeks]=znak;
                 ++indeks;
 }
 Linija[indeks]='\0';
 return indeks;
}

33. NCP koji će učitati liniju limitirane duzine sa standardnog ulaza i ispisati na standardni izlaz bez
a) malog slova 'x'  b) bez malih slova 'x', 'y' c) bez malog slova 'x' i slova y (bilo malo ili veliko)

PRIMER
ULAZ IZLAZ a) IZLAZ b) IZLAZ c)
MAX xyzYYYZ MAX yzYYYZ MAX zYYYZ MAX zZ


#include <stdio.h>
#include <ctype.h>

#define MAXLINE 1000
int getline( char line[], int limit);
/* ucitava liniju sa ulaza limitirane duzine u string line i vraca njenu duzinu */

void squeeze( char s[], int ch); /* uklanja karakter ch iz stringa s */

main()
{  int duz; /* duzina ucitane linije */
  char linija[MAXLINE]; /* sadrzaj linije sa ulaza */

   printf("Unesite red teksta \n");
   duz=getline(linija,MAXLINE);
   squeeze(linija,'x');
    printf("Uneseni tekst bez slova x \n");
   printf("%s", linija);

/* drugi po redu poziv f-je squeeze radi sa linijom iz koje je prethodno izbaceno malo slovo 'x' */
   squeeze(linija,'y');
    printf("Uneseni tekst bez slova x, y \n");
   printf("%s", linija);

    squeeze(linija,'Y');
    printf("Uneseni tekst bez slova x, y, Y \n");
  printf("%s", linija);
  return 0;
}
/* squeeze: uklanja znakove iz stringa */
void squeeze( char niska[], int ch)
{int indeks, tekuci; /*brojacke promenljive */
for( indeks=tekuci=0; niska[indeks]!='\0'; indeks++)

/* ako je znak niske na poziciji indeks razlicit od znaka ch, onda je taj znak "zasluzio" da ostane u nisci i zadrzavamo ga na poziciji tekuci, a nakon naredbe dodele uveca se tekuci za 1, tj. vrsi se priprema za sledeci znak niske koji je zasluzio" da ostane u nisci */
 if(niska[indeks] != ch)    niska[tekuci++]=niska[indeks];

/*obavezno je zavrsiti nisku na poziciji tekuci*/
niska[tekuci]='\0';
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char lin[], int lim)
{int  ch, indeks;
for( indeks=0; indeks<lim-1 && (ch =getchar())!=EOF &&  ch!='\n'; ++indeks)       lin[indeks]=ch;
if( ch=='\n' )      lin[indeks++]=ch;
lin[indeks]='\0';
return indeks;
}

34. NCP koji će u tekstu sa standardnog ulaza prebrojati koliko puta se pojavila svaka cifra dekadnog brojnog sistema, koliko puta su se pojavile beline (blanko, horizontalni tab, prelaz u novi red) i koliko puta su se pojavili ostali znaci. Rezultat ispisati na standardni izlaz. /*uporediti sa zad.17  - broji cifre, beline i druge znake.*/


#include <stdio.h>
main()
{
  int znak, indeks,White, Other, cifre[10];
 /* inicijalizacija */
  White=Other=0;
for(indeks=0; indeks<10; ++indeks)    cifre[indeks]=0;
/* prebrojavanje */
while( (znak=getchar())!=EOF )
{
      switch( znak )
      {
      case '0': case '1': case '2': case '3':
      case '4': case '5': case '6': case '7':
      case '8': case '9':
 ++cifre[znak-'0'];
  break;
       case ' ': case '\n': case '\t':
   ++White;
   break;
       default:
   ++Other;
 break;
     }
  }
/* prikaz rezultata */
for( indeks=0; indeks<10; ++indeks )  printf( "\nBroj pojava cifre  %d je %d",indeks, cifre[indeks] );
printf(".\nBelih znakova ima: %d. Ostalih ima: %d\n", White, Other);
}

Zadaci za vežbu (praktikum):

1./*----------------------------switch-case/if-else vezba--------------------------*/
/* Napisati C program koji proverava korektnu uparenost zagrada ( i ) u tekstu koji dolazi sa standardnog ulaza. Npr. zagrade su korektno uparene u izrazu 5 * (8+3), a nisu u izrazu 3 + )2) ili izrazu ( (3+6) * 8 */

2./*----------------------------switch-case vezba--------------------------*/
/* Napisati C program koji pomocu funkcije scanf unosi koeficijente kvadratne jednacine, a na standrdni izlaz ispisuje njene korene.*/

REŠENJE

1.

#include <stdio.h> 
#include <stdlib.h> 

main() 
{ 
    int c;    /*tekuci karakter sa ulaza*/
    int br_otv = 0; /*brojac zagrada*/
    while((c=getchar()) != EOF) 
    { 
         if(c=='(')   br_otv++; 
         if (c== ')') 
             { br_otv--; 
              if (br_otv<0) { printf("Visak zatvorenih zagrada\n"); break; } 
             } 
    } 
     if (br_otv == 0) printf("Zagrade su u redu\n"); 
     else      if (br_otv >0) printf("Visak otvorenih zagrada\n"); 
} 



2.
/* Program za nalazenje korena kvadratne jednacine */

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

main () {
  double a, b, c,              /* Koeficijenti jednacine                      */
         d,                    /* Diskriminanta jednacine                     */
         x1, x2,               /* Realni koreni                               */
         z1r, z1i, z2r, z2i,   /* Kompleksni koreni                           */
         x;                    /* Resenje linearne jednacine                  */
  int    por;                  /* Poruka o vrsti resenja                      */

  printf ("Koeficijenti kvadratne jednacine: ");
  scanf ("%lf%lf%lf", &a, &b, &c);
  if (! a)
    if (! b)               por = 1;
    else     { x = -c / b; por = 2; }
  else {
    d = b * b - 4 * a * c;
    if (d < 0) {
      z1r = -b / (2 * a); z1i =  sqrt (-d) / (2 * a);
      z2r = z1r;          z2i = - z1i;                por = 3;
    } else {
      x1 = (-b + sqrt (d)) / (2 * a);
      x2 = (-b - sqrt (d)) / (2 * a);                 por = 4;
    }
  }

  switch (por) {
    case 1: printf ("Ulazni podaci nemaju smisla!\a\n");
            break;
    case 2: printf ("Koren linearne jednacine je %g\n", x);
            break;
    case 3: printf ("Kompleksni koreni su %g%ci%g i %g%ci%g\n",
                    z1r, ((z1i >= 0) ? '+' : '-'),  fabs (z1i),
                    z2r, ((z2i >= 0) ? '+' : '-'), fabs (z2i));
            break;
    case 4: if (x1 != x2)
              printf ("Realni koreni su %g i %g\n", x1, x2);
            else
              printf ("Jednacina ima dvostruki koren %g\n",x1);
            break;
  }
}






 

SORTIRANJE I BINARNA PRETRAGA

35. NCP koji sa prve linije standardnog ulaza prihvata broj n (n<=100), a zatim iz svake linije standardnog ulaza prihvata po jedan element n-dimenzionalnog niza celih brojeva. Ispisati na standardni izlaz elemente niza sortirane u neopadajućem poretku. Ucitavanje linija standardnog ulaza, konverziju niske cifara u dekadni broj, sortiranje izdvojiti u posebne korisničke funkcije getline, atoi, sort.   /*sortiranje clanova niza - unos preko getchar i preko scanf + prica da scanf se koristi tek od VII glave u knjizi */


#include <stdio.h>
#include <ctype.h>
#define MAXLINE 1000
int getline( char line[], int granica);
int atoi( char niska[] );
void sort( int niz[], int ukupno);
/* glavni program */
main()
{
int duzina; /*duzina tekuce linije */
char line[MAXLINE]; /*niska koja cuva sadrzaj tekuce linije */
int ukupno; /*broj clanova niza */
int a[100]; /*niz sa standardnog ulaza */
int indeks; /*brojac u ciklusu */

printf("Unesite broj elemenata niza\n");
duzina=getline(line,MAXLINE);
ukupno=atoi(line);

/*unos n clanova niza: najpre se unesu cifre jedne linije, formira niska korisnickom funkcijom getline, a potom se niska konvertuje u broj pozivom korisnicke funkcije atoi i rezultat se dodeli clanu niza a na poziciji indeks*/
 for( indeks=0; indeks<ukupno; indeks++)
 {printf("%d. clan niza je:\t", indeks+1);
  duzina=getline(line,MAXLINE);
  a[indeks]=atoi(line);
}

/*sortiranje n clanova niza a korisnockom funkcijom sort */
sort(a,ukupno);

/*ispis sortiranog niza */
for( indeks=0; indeks<ukupno; indeks++)
  printf("%d\t", a[indeks]);
printf("\n");
return 0;
}
/* sort: jednostavnije sortiranje */
void sort( int niz[], int ukupno)
{int j, k;
 for(j=0; j<ukupno-1; j++)
     for(k=j+1; k<ukupno; k++)
  if( niz[j]>niz[k] )
   {
     int rezerva;
     rezerva=niz[j];
     niz[j]=niz[k];
     niz[k]=rezerva;
    }
}
/* atoi: ascii to integer */
int atoi( char niska[] )
{int k, broj, predznak;
/* preskociti escape znake */
for( k=0; isspace(niska[k]); k++ )  ;
/* odredi predznak broja */
predznak = (niska[k]=='-')?-1:1;
if( niska[k]=='+' || niska[k]=='-' ) k++;
for( broj=0; isdigit(niska[k]); ++k)  broj=10*broj+(niska[k]-'0');
return broj*predznak;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char line[], int granica)
{int znak, indeks;
for( indeks=0;indeks<granica-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)
line[indeks]=znak;
if( znak=='\n' ) line[indeks++]=znak;
line[indeks]='\0';
return indeks;
}

 


Ilustracija algoritama za sortiranje (napomena: u zadatku 35. primenjenjen je selection sort)

36.         /* verzija 35. sa scanf   */
#include <stdio.h>
#include <ctype.h>
void sort( int niz[], int ukupno);
/* glavni program */
main()
{
int ukupno;int a[100];int indeks;
printf("Unesite broj elemenata niza\n");
scanf("%d", &ukupno);
 for( indeks=0; indeks<ukupno; indeks++)
 {printf("%d. clan niza je:\t", indeks+1);
  scanf("%d",&a[indeks]);
  }
sort(a,ukupno);
for( indeks=0; indeks<ukupno; indeks++)
  printf("%d\t", a[indeks]);
printf("\n");
return 0;
}
/* sort: jednostavnije sortiranje */
void sort( int niz[], int ukupno)
{int j, k;
 for(j=0; j<ukupno-1; j++)
     for(k=j+1; k<ukupno; k++)
  if( niz[j]>niz[k] )
   {
     int rezerva;
     rezerva=niz[j];
     niz[j]=niz[k];
     niz[k]=rezerva;
    }
}
 

Zadaci za vežbu (praktikum):

/* Linearna pretraga u niza karaktera
NCP koji sa standardnog ulaza unosi pomocu funkcije scanf nisku sa ne vise od 20 karaktera i proverava da li niska sadrzi znak @ */

Postupak linearnog pretraživanja

Traženi element x se može naći lineranim (sekvencijalnim) pretraživanjem.
Redom se porede elementi ulaznog niza v sa vrednošću od x, sve do prvog elementa v[i] za koji važli v[i] >=x.
Tada, ako je: Ako je svaki element niza v manji od vrednosti od x, onda se x ne nalazi u nizu v (izvrsi se n poredjenja).
#include <stdio.h>
#include <string.h>
/* Funkcija proverava da li se dati element x nalazi 
   u datom nizu a. 
   Funkcija vraca poziciju u nizu na kojoj je x pronadjen
   odnosno -1 ukoliko elementa nema.
*/
int linear_search(char a[], int n, int x) 
{
	int i;
	for (i = 0; i<n; i++)
		if (a[i] == x)
			return i;
		/* nema potrebe za  else!!! */
	return -1;	
}

main()
{
	char a[21] ; /*niska sa stdin */
                  int n; /*broj unetih karaktera niske a*/
	int i; /*brojacka promenljiva*/
	printf("Unesite nisku : ");
	 scanf("%s",a);
	n = strlen(a);
	i = linear_search(a, n, '@');
	if (i == -1)
		printf("Karakter @ nije nadjen\n");
	else	
		printf("Karakter @  je na poziciji %d\n", i);
}



/* Binarna pretraga u niza karaktera
NCP koji sa standardnog ulaza unosi pomocu funkcije scanf leksikografski uredjenu nisku sa ne vise od 20 karaktera i proverava da li niska sadrzi znak @. ASCII(@) = 64 */


/*-----------------------Binarna pretraga niza celih brojeva - iterativna verzija-------------------------------*/

#include <stdio.h>
#include <string.h>

/* Funkcija proverava da li se element x javlja unutar niske a.
   Funkcija vraca poziciju na kojoj je element nadjen odnosno
   -1 ako ga nema.
 
   !!!!! VAZNO !!!!!
   Pretpostavka je da je niska a sortirana
*/

int binary_search(char a[], int n, int x)
{
	/* Pretrazujemo interval [l, d] */
	int l = 0;
	int d = n-1;
	
	/* Sve dok interval [l, d] nije prazan */
	while (l <= d)
	{
		/* Srednja pozicija intervala [l, d] */
		int s = (l+d)/2;
		
		/* Ispitujemo odnos x i srednjeg elementa a[s]*/
		if (x == a[s])
			/* Element je pronadjen */
			return s;
		else if (x < a[s])
		{
			/* Pretrazujemo interval [l, s-1] */	
			d = s-1;
		}
		else
		{
			/* Pretrazujemo interval [s+1, d] */
			l = s+1;
		}
	}

	/* Element je nadjen */
	return -1;	
}

main()
{
	char a[21] ; /*niska sa stdin */
                  int n; /*broj unetih karaktera niske a*/
	int i; /*brojacka promenljiva*/
	printf("Unesite nisku : ");
	scanf("%s",a);

	i = binary_search(a, strlen(a), '@');
	
	if (i==-1)
		printf("Nema karaktera @\n");
	else
		printf("Pronadjen @ na poziciji %d\n", i);
}




Odnos broja poredjenja kod linearne i binarne pretrage


NCP koji sa standardnog ulaza unosi pomocu funkcije scanf dve niske sa ne vise od 20 karaktera i proverava da li su niske anagrami. Na primer, niske VATRA i TRAVA su anagrami, jer se sastoje od jednakog broja istih slova, dok niske TRAVA i TATAR nisu anagrami zbog viska slova T i manjka slova V u drugoj niski.

NAPOMENA: uneti obe niske, sortirati ih, uporediti ih (npr. pomocu funkcije strcmp)


NCP koji sa standardnog ulaza unosi nisku sa ne vise od 20 karaktera i pronalazi poziciju poslednje pojave karaktera @.

NAPOMENA: obrnut nisku, naci poziciju 1. pojave linearnom pretragom i tu poziciju oduzeti od strlen(niska)


NCP koji sa standardnog ulaza unosi nisku sa ne vise od 20 karaktera koja sadrzi e-mail adresu i ispisuje na standardni izlaz user name. Pretpostaviti da email adresa se zadaje u formi username@host.domen. Npr. mr05007@yubc.net, mr05007@alas.matf.bg.ac.yu

NAPOMENA: kao u funkciji linearne pretrage naci poziciju prve pojave karaktera @ i ispis vrsiti od 0-te do te pozicije.


NCP koji sa standardnog ulaza unosi nisku sa ne vise od 20 karaktera koja sadrzi e-mail adresu i ispisuje na standardni izlaz naziv drzave domena. Pretpostaviti da email adresa se zadaje u formi username@host.domen i da domen obavezno sadrzi naziv drzave Npr. mr05007@gauss.matf.br.ac.de, mr05007@alas.matf.bg.ac.yu

NAPOMENA: naci poziciju poslednje pojave . u nisci i ispis vrsiti od te pozicije do kraja niske


NCP koji sa standardnog ulaza unosi nisku sa ne vise od 20 karaktera koja sadrze e-mail studenta Matematickog fakulteta, a na standardni izlaz ispisuje izmenjenu nisku tako da naziva servera alas iza znaka @ bude zamenjen nazivom arhimed (primer: niska="mr05007@alas.matf.bg.ac.yu" se transformise u niska="mr05007@arhimed.matf.bg.ac.yu")

NAPOMENA: moze se vrsiti ispis do prve pojave @, te ispisati arhimed. te vrsiti ispis od prve pozicije tacke (iza @) do kraja niske
Moze se izvrsiti i pronalazenje prve pozicije NISKE alas i od te pozicije do strlen("arhimed")-1 izvrsiti umetanje niske "arhimed"


NCP koji sa standardnog ulaza unosi dve niske sa ne vise od 20 karaktera koje sadrze e-mail adrese, a na standardni izlaz ispisuje da li su im jednaka korisnicka imena. Na primer, niska1="mr05007@alas.matf.bg.ac.yu" , niska2="mr05007@EUnet.yu" sadrze isto korisnicko ime mr05007

NAPOMENA: nalazi prve pozicije @ u obe niske i poredi podniske do te pozicije


NCP koji sa standardnog ulaza unosi niz linija sa ne vise od 80 karaktera, pronalazi najduzu liniju i ispisuje na standardni izlaz broj pojava svake dekadne cifre. Izvestaj treba urediti u nerastucem poretku broja pojava cifara, tj. najpre se ispisuje broj pojava za najfrekventnije cifre.
PRIMER: Neka najduza linija je: 222 + 35 je 257 gledano u sistemu sa osnovom 10.
Izvestaj: Cifra 2 se pojavljuje 4 puta, cifra 5 se pojavljuje 2 puta, cifra 0 se pojavljuje 1 put, cifra 1 se pojavljuje 1 put...

NAPOMENA: broj pojava cifri se moze cuvati u nizu, ali se niz mora sortirati, pazecu pri tom da i kad se sortira cifra[i] mora biti broj pojave cifre i sto nece vaziti nakon sortiranja. Zato treba porazmisliti o memorisanju za koju cifru j=0..9 clan cifra[i] je broj pojave cifre j. Ili uz malu pomoc algebre, uociti da broj pojave svake cifre je <=80, te formirati niz brojeva oblika broj=80*i*10+cifra[i], gde broj%800 je cifra[i], broj/800 je cifra i

37. NCP koji unosi realan broj sa standardnog ulaza i ispisuje na standardni izlaz: taj broj, najmanji ceo broj ne manji ( >=) od tog broja, najveći ceo broj ne veći ( <=) od tog broja, kvadratni koren tog broja (ako broj je nenegativan), kosinus tog broja.

Pri upotrebi kompajlera gcc, mora se upotrebiti opcija -l za naziv biblioteke s kojom se linkuje program, a za matematicku biblioteku libm(#include <math.h>) oznaka je m, tj. kompilacija zad37.c bi mogla biti:
gcc zad37.c -lm -o racunaj


#include <stdio.h>
#include <math.h>
/*NAPOMENA: Funkcije ceil(x), floor(x), sqrt(x), sin(x) su iz zaglavlja math.h
Argumenti su tipa double, rezultati su tipa double*/

 main()
{  double x;
   printf("Unesite broj: ");
   scanf( "%lf", &x);
   printf("\n\nUneli ste: %lf", x);
   printf("\nCeil Vaseg broja: %lf", ceil(x));
   printf("\nFloor: vaseg broja %lf", floor(x));
   if( x >= 0 )  printf("\nKvadratni koren: %lf", sqrt(x) );
    else printf("\nNegativni broj" );
  printf("\nCosinus: %lf\n", cos(x));
 return(0);
}

Testirajte program za x =4.9998887, x=4.11199, x=0.001, x=-0.001, x=0.25, x=0, x=-1, x=1

38. NCP koji prihvata sa standardnog ulaza liniju limitirane dužine i ispisuje je na standardni izlaz sa uklonjem belinama zdesna.
TESTIRAJTE ZADATAK UPOTREBOM NEKOG IDE-a za Windows OS: DEV C/C++, MSVC++, BC++, TURBO C, QUICK C

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXLINE 1000
/*getline: ucitava sa ulaza liniju limitirane duzine u line i vraca njenu duzinu */
int getline( char line[], int lim);

/*iseca beline sdesna iz niske i vraca duzinu isecene niske */
int rtrim( char niska[] );

main()
{int duz; /* duzina ucitane linije */
char line[MAXLINE];/* sadrzaj linije sa ulaza */

printf("Unesite string \n");
duz=getline(line,MAXLINE);
printf("Broj znakova u stringu je %d\n", strlen(line));

/*isecanje belina sa kraja stringa*/
duz=rtrim(line);
printf( "Sdesna iseceni string\n%s\nsadrzi %d znakova\n", line, duz );
return 0;
}
 

/* rtrim: iseca beline sa desne strane */
int rtrim( char niska[] )
{int desnapoz; /* brojacka promenljiva */

/*pocev od kraja niska prelazi se preko belina (ako postoje) i ... */
for( desnapoz=strlen(niska)-1; desnapoz>0; desnapoz-- )

/* ... cim se naidje na znak u nisci razlicit od: blanko, tabulatora i znaka prelaska u novi red ... */
if( niska[desnapoz]!=' ' && niska[desnapoz]!='\t' && niska[desnapoz]!='\n'
/*!isspace(niska[desnapoz])*/ )
/* zaustavimo se kod tog znaka i izadjimo iz ciklusa */
   break;
 

/* kako niska[desnapoz] je prvi karakter "otpozadi" koji nije blanko, tab, new line, onda moramo iseceni string zavrsiti na poziciji desnapoz+1 */
niska[desnapoz+1]='\0';
return desnapoz+1; /* vraca se duzina isecenog stringa */
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char line[], int lim)
{int znak, indeks;
for( indeks=0; indeks<lim-1 && (znak=getchar())!=EOF && znak!='\n'; ++indeks)
line[indeks]=znak;
if( znak=='\n' ) line[indeks++]=znak;
line[indeks]='\0';
return indeks;


}

39. NCP koji prihvata sa standardnog ulaza pozitivan ceo broj n (n <=50), proverava korektnost unete vrednosti, a zatim prihvata po jedan element n-dimenzionalnog niza celih brojeva. Formirati drugi niz koji sadrži samo nenegativne elemente unetog niza, a potom članove drugog niza ispisati na standardni izlaz. /*prepis pozitivnih clanova niza u drugi niz i stampanje drugog niza */

#include <stdio.h>
#include <ctype.h>
main()
{
int n; /* dimenzija niza */
int indeks; /* brojac */
int a[50];/*niz celih brojeva iz kog se izdvajaju nenegativni brojevi */
  int j; /*broj nenegativnih clanova*/
  int rezultat[50];/* niz nenegativnih clanova*/
 

/*unos dimenzije niza : 1..50 */
do
{printf("Unesite broj elemenata niza\n");
scanf("%d", &n);
} while (n <1 || n > 50);
 

/* unos clanova niza celih brojeva */
for( indeks=0; indeks<n; indeks++) scanf("%d", &a[indeks]);
 

/* prepis nenegativnih elemenata u niz rezultat */
for( indeks=0, j=0; indeks<n; indeks++)
{

/* ignorisanje clanova niza a koji ne mogu biti clanovi niza rezulat */
if(a[indeks]<0)    continue;
/* dopuni niz rezultat */rezultat[j++]=a[indeks];
}
 

/* ispis niza rezultat */
  for( indeks=0; indeks<j; indeks++) printf("%d\t", rezultat[indeks]);

printf("\n");
return 0;
}

Praktikum: obrada HTML datoteka i upotreba steka

NCP koji će HTML datoteku sa ulaza prepisati na standardni izlaz tako da nazivi svih etiketa otvarača budu prikazani velikim slovima na izlazu. Program mora da radi sa preusmeravanjem standardnog ulaza i izlaza. Etiketa otvarac jeste <h1> ili <h2 align="center">, ALI NIJE </h2> Dakle, etiketu <taBle align="center"> treba transformisati u <TABLE align="center"> IDEJA: treba transformisati u velika slova samo one niske koje pocinju sa < za kojim sledi niz slova ili cifara




     
  #include <stdio.h>
  #include <ctype.h>
  /* zbog f-ja isalnum, toupper */
  
  void obradiOtvarac(int c);
  /* transformise naziv etikete otvaraca tako
  da sadrzi samo velika slova */
  
  main()
  {  int c; /*znak sa ulaza */
     
     /*ucitava se karakter po karakter HTML datoteke
       sve do EOF */
     while ( (c=getchar()) != EOF)
      if (c!='<') putchar(c); 
              //nije deo etikete, prepisuje se
      else 
        {
          putchar(c); /*stampa se < */
          if (isalnum(c=getchar())) 
          /*ako je etiketa otvarac,
           ona pocinje slovom iza <*/
            obradiOtvarac(c);
          else putchar(c); /*stampa se / ili ... */
        }
  }
  
  void obradiOtvarac(int c)
  {  /*odstampati samo naziv etikete VELIKIM (toupper)
      slovima */
    do
      { putchar(toupper(c));
      } while (isalnum(c=getchar()));
    
      
      putchar(c); /*stampa se doslovce 
      prvi znak iza etikete 
      koji nije slovo ili cifra */
  }
  

NCP koji će HTML datoteku sa ulaza prepisati na standardni izlaz tako da samo nazivi (ne i atributi) svih etiketa otvarača budu prikazani velicinom slova koja se poklapa sa velicinom pocetnog slova u nazivu. Program mora da radi sa preusmeravanjem standardnog ulaza i izlaza. Na primer, etiketa otvarac <HtmL> mora na izlazu imati oblik <HTML> ili <tABle align="center"> transformisati u <table align="center">, dok etiketu </h2> ne treba modifikovati, jer nije etiketa otvarac.

NCP koji će HTML datoteku sa ulaza prepisati na standardni izlaz tako da svaki naslov nivoa 1-5 (etikete: h1,h2, h3, h4, h5) se ispise kao naslov sledeceg nizeg nivoa (etikete: h2, h3, h4, h5, h6), etiketa <b> ... </b> se zameni etiketom <strong> ... </strong>, etiketa <u> ... </u> se zameni etiketom <em> ... </em>. Program mora da radi sa preusmeravanjem standardnog ulaza i izlaza. PRIMER: <h2 align="center> Naslov </h2> se transformise u <h3 align="center> Naslov </h3> <b style="color:..."> Nesto</b> se transformise u <strong style="color:..."> Nesto</strong>




STEK - kolekcija podataka sa kojima se radi po LIFO(Last In First Out) principu;
Stek je prazan ako mu se vrh nije pomerio iz inicijalnog stanja
Funkcijom push se formira sadrzaj steka - dodavanjem elemenata na vrh steka
Funkcijom pop elementi se uzimaju sa steka po LIFO redosledu (njapre se uzima element sa vrha steka)
Upotreba steka: IV glava K&R - primer sa kalkulatorom, uparenost HTML etiketa,...

NCP koji ce proveriti uparenost etiketa u ulaznoj HTML datoteci. Slozena etiketa A (poseduje otvaracA i zatvaracA) je korektno ugnjezdena u etiketu B ako je otvaracA iza otvaracB i zatvaracA ispred zatvaracB. Pretpostaviti da u ulaznoj datoteci nema prostih etiketa (onih koje nemaju zatvarac). Jednostavnosti radi, pretpostaviti da maksimalna dubina ugnjezdenosti je do nivoa 3 (dakle, nivo tipa <B><I>...</I> <I><p> </p></i></b> se pojavljuje, dok nivo tipa <B><I>...<p><a href="nesto.htm">...</A> </p></i></b> se ne pojavljuje). Pretpostaviti da nazivi etiketa su jednoslovni (P,Q,B,I,U,S,A,...). Pri nailasku na nekorektno uparenu etiketu, prekinuti dalju proveru i ispisati poruku o gresci na standardni izlaz.
TEST PRIMER:
<P align="center">Pasus 1 </P>
<p><B><q>Citat 1</q> <A href="link1.htm"> Hiperveza 1 </a> <Q> Citat 2 </q> ... </b>...</p>
<p><q>Citat 2</Q> <A href="link2.html"> Hiperveza 2 </a> <B> <A href="link3.htm"> Hiperveza 3 </a>
...</B> </P> IDEJA:

  1. Svaka otvorena etiketa stavi se na stek
  2. Pri nailasku na zatvorenu etikete proveravamo da li je stek prazan. Ako jeste, nekorektna uparenost. Takođe se proveri i da li se na vrhu steka za tekucu zatvorenu etiketu nalazi odgovarajuca otvorena etiketa. Ako ne, nekorektna uparenost. Ako da, skine se otvorena etiketa sa vrha steka.
#include <stdio.h>
#include <ctype.h>

#define MAX  3  
/*maksimalna dubina steka*/

void push(char); /*stavlja etiketu na stek */
char pop(void); /*vraca etiketu skinutu sa vrha steka */

/*globalne promenljive */
char Stek[MAX];  /*stek realizovan kao niz*/
int vrh;  /*naredna slobodna pozicija na steku */
int greska=0; /*indikator nailaska na pojavu nekorektne ugnjezdenosti*/

main()
{
    int c; /*znak sa ulaza*/
    int rez; /*rezultat skidanja sa steka*/
    
  while ( (c=getchar()) != EOF  && !greska)
     if (c=='<')
     {   if (isalnum(c=getchar()) )  push(toupper(c)); 
                 /*etiketa otvarac(<isalnum...) se stavlja na stek, naziv se bez smanjenja opstosti
                   smesta veliki slovima u steku, zbog kasnijeg case insensitive poredjenja
                   naziva etiketa otvaraca i zatvaraca; ne zaboravite da u HTMLu je naziv
                   iste etikete i <Table> i <taBLE> */


          if (c=='/')  /*obrada zatvaraca, ali samo ako je oblika </slovo...> */
             { if (isalnum(c=getchar()) )  rez=pop();
                if (toupper(c) != rez)  {printf("Greska: etiketa %c\n", c); greska=1; }
             }
     }

    if (!greska) printf("\nKorektna uparenost unutar HTML datoteke\n");
}


void push(char c)  /*smesta etiketu c na vrh steka */
{   
     if (vrh<MAX) Stek[vrh++]=c;
     else { greska=1;
                printf("\nGreska: stek je pun, dubina je %d, nemoguce je smestiti %c\n", MAX, c);
             }
}

char pop(void) /*kao rezultat daje etiketu skinutu sa vrha steka*/
{
   if (vrh>0) return Stek[--vrh];
   else
        { greska=1; printf("\nGreska: stek je prazan\n");  return 0; }
 }
                                                                                    



40. NCP koji poseduje funkcionalnost kalkulatora sa operacijama sabiranja, oduzimanja, množenja, deljenja nad racionalnim brojevima. Program treba da prihvati izraz koji se unosi sa linije standardnog ulaza u postfiksnom obliku

gcc main.c stack.c getop.c getch.c

/*Kalkulator sa +, -, *, / u inverzoj poljskoj (postfiksnoj) notaciji.  */
#include <stdio.h>
#include <math.h>   /* zbog atof () po K&R, #include <stdlib.h> inace */
#define MaxOpSIZE 100 /* maksimalna velicina operatora ili operanda*/
#define NUMER '0' /* indikator da je operand broj */
void push( double );  /*stavlja na stek  element tipa double*/
double pop( void );  /*skida sa steka i vraca vrednost sa vrha */
int getop( char [] );   /*ocitavanje sledeceg operatora ili operanda */
/* glavni program */
main()
{
     int type;     /*signal da je ocitan numericki operand ili operator  ili new line ili ma sta drugo*/
    double dOperand2;  /*cuva drugi operand da bi se pravilno izvrsile i nekomutativne operacije */ 
    char inString[MaxOpSIZE];   /*niska kojom se uvodi operand ili operator */
    /*ocitavanje izraza  sa standardnog ulaza*/
        while( (type = getop(inString)) != EOF)
        {
                switch( type )
                {
                        case NUMER:
                                push( atof(inString) );
                                break;
                        case '+':
                                push( pop() + pop() );
                                break;
                        case '*':
                                push( pop() * pop() );
                                break;
                        case '-':
                                dOperand2 = pop();
                                push( pop() - dOperand2 );
                                break;
                        case '/':
                                dOperand2 = pop();
                                if( dOperand2 != 0.0 )
                                        push( pop() / dOperand2 );
                                else
                                        printf("greska: deljenje sa nulom");
                                break;
                        case '\n':
                                printf("\t%.8g\n", pop() );
                                break;
                        default:
                                printf("greska: nepoznata komanda %s\n", inString);
                                break;
                }
        }
  return 0;
}


#define MAXSTACKLEN 100 /* maksimalna dubina steka */
double StoreStack[MAXSTACKLEN];              /*vrednost steka */
int posStackPointer;              /*naredna  slobodna pozicija na steku  */
/* push: gurni na stek */
void push( double dArg )
{
if( posStackPointer < MAXSTACKLEN )  StoreStack[posStackPointer++] = dArg;
else       printf("greska: stek je pun, nemoguce je smestiti %g\n", dArg);
}
/* pop: skini sa steka*/
double pop( void )
{  if( posStackPointer > 0 )    return StoreStack[--posStackPointer];
   else
      {  printf("greska: stek je prazan\n" );
         return 0.0;
      }
}



#include <ctype.h>
int getch( void );
void ungetch( int );
/* getop: uzmi sa ulaza sledeci operator ili   numericki operand */
int getop( char inString[] )
{   int poz;       /*tekuca pozicija niske */ 
     int CharCurr;     /*ocitani znak */
while( (inString[0]=CharCurr=getch())==' ' || CharCurr=='\t' )  ;
 inString[1] = '\0';
        /* da li se radi o broju */
if( !isdigit(CharCurr) && CharCurr!='.' )       return CharCurr;
poz=0;
/* uzeti celobrojni deo */
if( isdigit(CharCurr) )
        while( isdigit(inString[++poz]=CharCurr=getch()) )      ;
/* uzeti  razlomljeni deo */
if( CharCurr=='.' )
     while( isdigit(inString[++poz]=CharCurr=getch()) )             ;
inString[poz]='\0';
if( CharCurr != EOF ) ungetch( CharCurr );
return NUMER;
}


#define FULLBUF 100
int nextBuffer = 0;        /*sledeca slobodna pozicija zajednickog bafera */
char aBuffer[FULLBUF];  /*bafer  za getch/ungetch */ 
/* getch: uzmi (mozda vraceni) znak */
int getch(void)
{
        return( nextBuffer > 0 ) ? aBuffer[--nextBuffer]:getchar();
}
/* ungetch: vrati znak*/
void ungetch( int CharCurr )
{
        if( nextBuffer >= FULLBUF )
                printf("greska: ungetch-isuvise znakova\n");
        else
                aBuffer[nextBuffer++]=CharCurr;
}

Jelena Grmuša Osnovi programiranja

e-mail: Jelena Grmuša


Copyright © 2002, Jelena Grmusa
Poslednja izmena: februar 2005.
URL: http://www.matf.bg.ac.yu/~jelenagr/op/