wiki:c-intro

Version 8 (modified by msitar, 15 years ago) (diff)

Reševanje sistema linearnih enačb

Uvod v programski jezik C

V naslednjih poglavjih bom poizkušal na čim bolj enostaven način razložiti osnove programskega jezika C, ki so obvezno potrebne za izdelavo nekega konkretnega programa.


Prvi program

Da bomo premagali strah glede programiranja s programskim jezikom C oziroma, da si bomo potešili željo po svojem prvem programu, napišimo enostaven program, ki nam bo izpisal naslednje besedilo: Moj prvi program.

#include <stdio.h>

int main()
{
   printf("Moj prvi program\n");
   return 0;
}


Sintaksa jezika

Kot vsi drugi programski jeziki ima tudi C značilno sintakso jezika, ki se jo moramo strogo držati. To pomeni, da moramo upoštevati pravilni vrstni red in izbrane kombinacije besed ter simbolov tako, da tvorimo sintaktično pravilne izraze. Če sintaksa zapisanega programa ni pravilna, nam bo prevajalnik javil napako.

Najpogostejši operatorji in izrazi:

  • OPERATORJI
    • Relacijski
      a==b //a je enak b
      a!=b //a ni enak b
      a<=b //a je manjši ali enak b
      a>b  //a je večji kot b
      
    • Logični
      (a<b) && (a<c) //IN
      (a<b) || (a<c) //ALI
      !(a<b)         //NI (negacija)
      
    • Prireditveni in aritmetični
      a=b //a-ju priredimo vrednost b
      a%b //Ostanek pri deljenju a z b 
      
    • Posebni
      a++  //a povečamo za 1. Pišemo lahko tudi a=a+1
      a+=b //a-ju prištejemo vrednost b. Pišemo lahko tudi a=a+b
      
  • KOMENTARJI
    //Enovrstični komentar
    
    /*Več vrstični
    komentar*/
    


Več o sintaksi jezika bo razvidno iz naslednjih poglavij.


Spremenljivke

Spremenljivke so osnovni gradniki programa. Če želimo uporabljati spremenljivke, jih moramo najprej deklarirati. To storimo tako, da podamo njen tip, ki določa kakšno vrednost hranimo v njen, in njeno ime.

float a;
a=5.12;       //Naknadno podamo vrednost spremenljivke a

int b=4;      //Vrednost spremenljivke lahko podamo že pri deklariranju

float c[10];  //Spremenljivka c bo sestavljena iz 10-ih elementov (imeli bomo 10 realnih števil v skladišču c)

Vrednost spremenljivke lahko poda tudi uporabnik. Za program bomo uporabili funkcijo scanf, ki prebere vnešeno vrednost in jo shrani pod nastavljeno spremenljivko.

float a;

printf("Podaj realno število:\n");
scanf("%f",&a);

Pri tem %f predstavlja formatni stavek, &a pa pomeni naslov spremenljivke, pod katero se shrani vrednost.


Najpogostejša tipa spremenljivke sta:

  • float - za realne vrednosti
  • int - za celoštevilčne vrednosti (integer)

Uporabljajo pa se še double, char, long,...


Kontrolni stavki

Pod kontrolne stavke štejemo:

  • If - else stavke
  • Switch - case stavke
  • For zanke
  • While zanke
  • Do - while zanke

If in switch stavki so stavki za pogojno izvrševanje delov programa. For, while in do - while zanke oziroma stavki pa so stavki za ponavljanje drugih stavkov.


Primeri uporabe posameznih vrst stavkov:

If stavek

if(a>b)
{
  max=a;
}
else 
{
  max=b;
}

V if stavke lahko dodamo še dodatne pogoje. To storimo z ukazom else if(pogoj).

if(a>b)
{
  max=a;
}
else if(c>a) 
{
  max=c;
}
else
{
  max=b;
}


For zanka

for(i=0; i<10; i++)
{
  printf("text\n");
}

Pri tem \n pomeni prehod v novo vrsto (New Line)


Switch stavek

switch(i)
{
  case 1:
   printf("text 1")
   break;
  case 2:
   printf("text 2")
   break;
  case 3:
   printf("text 3")
   break;
}

Lahko uporabimo še dodatni ukaz default, pri katerem se izvršijo stavki, kadar ni bil izbran določen case.

switch(i)
{
  case 1:
   printf("text 1")
   break;
  case 2:
   printf("text 2")
   break;
  default:
   printf("text")
}


While zanka

i=0;
while(i<10)
{
  printf("text\n");
  i=i+1;
}


Do - while zanka

i=0;
do
{
  printf("text\n");
  i=i+1;
}
while(i<10);

Pri do - while zanki se stavki izvedejo vsaj enkrat!


V praksi pa se pogosto uporablja kombinacija teh stavkov.

//Generiranje elementov matrike H

for(i=0; i<4; i++)  
{
  for(j=0; j<4; j++)
  {
    if(i==j)
    {
      H[i*4+j]=0.5;
    } 
    else
    { 
      H[i*4+j]=2.0;
    }
  }
}


Formatiran izpis

Vrednosti spremenljivk in konstant lahko izpisujemo z različnimi formati. Najbolj pogosto uporabljeni formatni stavki so:

  • %f - realna števila
  • %d - cela števila
  • %g - realna števila, format odvisen od velikosti


Format izpisa neke vrednosti lahko poljubno določimo. To storimo tako, da formatni stavek dopolnimo z ukazom, ki nam pove koliko mest naj izpis zavzame pred decimalko in koliko za njo. Za primer vzemimo, da želimo imeti pet mest pred decimalko in dva za njo. Formatni stavek se glasi %5.2f.


Primeri formatiranega izpisa

#include <stdio.h>

int main()
{
  float a=5.12; //Realno število
  int b=-5;     //Celo število

  printf("Vrednost a je enaka %f\n", a);    
  printf("Vrednost a je enaka %4.2f\n", a); //Nastavimo željen format izpisa
  printf("Vrednost a je enaka %g\n", a);    //Format bo odvisen od velikosti
  
  printf("Vrednost b je enaka %d\n", b);
  return 0;
}

Program izpiše naslednje:

Vrednost a je enaka 5.120000
Vrednost a je enaka 5.12
Vrednost a je enaka 5.12
Vrednost b je enaka -5


Polja, vektorji, matrike

Polja, vektorje in matrike definiramo z deklaracijo, enako kot to velja za spemenljivke.

float M[4];     //Enodimenzionalno polje - vektor oziroma matrika vsebuje 4 elemente z realnimi vrednostmi

Prvi element ima vedno indeks 0!

Za primer določimo vrednosti posameznim elementom:

float M[4];

M[0]=2.0;
M[1]=1.0;
M[2]=4.0;
M[3]=1.0;

Vrednosti posameznih elementov pa lahko definiramo že pri deklaraciji. To storimo na naslednji način:

float M[4]={2.0, 1.0, 4.0, 1.0};

Za izpis 1. elementa bomo torej zapisali:

printf("Vrednost 1. elementa znaša %f", M[0]);

V pomnilniku je to polje zloženo tako, kot kaže slika 1, kjer vsak element polja zavzame 4 byte pomnilnika.

Stanje pomnilnika

Slika 1: Stanje pomnilnika


Pri tem nas verjetno zmoti to, da lahko matriko definiramo kot vektor. Takšen način definiranja matrike je dokaj pogost, pri tem pa z elementi operiramo na sledeči način (gre za enodimenzionalno polje):

Za primer imamo matriko N velikosti 2×3 z elementi:

1.0  2.0  3.0
4.0  5.0  6.0

Sledi:

float N[2*3]={1.0, 2.0, 3.0, 4.0, 5.0, 6.0};  //Matriko zapišemo kot vektor v eni vrstici. Pišemo lahko tudi N[6]=...

//Primer izpisa elementa, ki se nahaja v drugi vrstici prvega stolpca. V tem primeru gre za četrti element matrike oziroma vektorja N

printf("Element v drugi vrstici prvega stolpca je %f", N[1*3+0]);


//Primer izpisa elementa, ki se nahaja v prvi vrstici tretjega stolpca.

printf("Element v prvi vrstici tretjega stolpca je %f", N[0*3+2]);

Poljubni element matrike zapišemo v splošni obliki kot:

N[indeks vrstice * število stolpcev + indeks stolpca]

S tem, ko pomnožimo indeks vrstice s številom stolpcev, si lahko predstavljamo, da preskočimo vse elemente v prejšnih vrsticah. Če temu produktu prištejemo še indeks stolpca, pridemo ravno do tistega elementa, ki ga želimo.

Enostaven primer generiranja elementov matrike nam kaže primer, ki smo ga spoznali pri kombiniranju kontrolnih stavkov.


Poleg omenjenega načina definiranja matrik obstaja še drug način, pri katerem uporabimo večdimenzionalna polja.

Primer definiranja matrike:

float N[2][3]={{1.0, 2.0, 3.0},
               {4.0, 5.0, 6.0}};

//Primer izpisa elementa, ki se nahaja v prvi vrstici tretjega stolpca.

printf("Element v prvi vrstici tretjega stolpca je %f", N[0][2]);

Pri tem ne smemo pozabiti, da se indeksi vrstic in stolpcev vedno začnejo z 0.


Branje datotek

Velikokrat se zgodi, da dobimo vhodne podatke, s katerimi bo program operiral, zapisane v datoteki.

Primer datoteke s podatki, z imenom datoteka.dat:

2 4
00 02 12 08
14 05 07 11

Da bo naš program prebral to datoteko in shranil podatke pod spremenljivke, uporabljamo naslednjno kombinacijo ukazov:

int i;
int n, d;
float M[4], N[4];

FILE *f;                     //Povemo, da gre za podatkovo strukturo
f=fopen("datoteka.dat","r"); //"r" pomeni, da bo datoteka samo za branje
fscanf(f, "%d %d", &n, &d);  //Prebere iz datoteke in shrani prva dva podatka pod spremenljivke n in d

for(i=0; i<4; i++)
{
  fscanf(f, "%f", &M[i]);    //Prebere in shrani naslednje štiri podatke
}
for(i=0; i<4; i++)
{
  fscanf(f, "%f", &N[i]);   
}
fclose(f);

Zaporedje branja podatkov poteka vedno po vrsticah! (Lahko si predstavljamo, kot da so podatki zapisani v eni vrstici)


Dinamična alokacija pomnilnika

V primerih, ko za določene spremenljivke ne poznamo, koliko elementov bo nosila oziroma koliko pomnilnika bo zavzela, se uporabi dinamično alokacijo le tega, in sicer z uporabo funkcije malloc. Ta sprejme en sam argument, ki pove koliko bytov pomnilnika rabimo.

Funkcija malloc se nahaja v knjižnjici stdlib.h, zato je ne smemo pozabiti vključiti v našem programu.

Primer dinamične alokacije pomnilnika

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

float *m  //Velikost vektorja m še ne poznamo

int main()
{
  int x=10;
  m=malloc(x*sizeof(float));  //Naredi vektor velikosti x
  return 0;
}


Reševanje sistema linearnih enačb

Sistem linearnih enačb lahko rešujemo na različne načine. Klasična Gaussova eliminacijska metoda se pri konkretnih problemih pokaže kot počasna (N3 operacij). Predlagana metoda, ki se v praksi tudi največ uporablja za reševanje sistema enačb je Lower/Upper? dekompozicija, ki ima časovno zahtevnost 1/3N3. Reševanje sistema po tej metodi se sestoji iz dveh korakov:

  1. decomposition, ki razdeli matriko M na dve matriki (zgornja / spodnja), katerih produkt je M. Obe matriki sta shranjeni v matriki M, le da je zgornji del matrike M matrika U, spodnji pa matrika L.

  1. backsubstitution, ki množi desno stran enačbe z zgornjo matriko in pri tem izračuna neznane linearne spremenljivke.

Rešujemo sistem enačb velikosti N. Matrika M predstavlja levo stran sistema enačb. N opisuje velikost matrike M. indx je celoštevilčni vektor permutacij v matriki M in se prenaša naprej v podprogram lubksb, kateri zahteva še desno stran sistema enačb v vektorju u. Po izračunu se rezultat nahaja v vektorju u. Prejšnje vrednosti matrike M in vektorja u se ne ohranijo! Potek izračuna sistema linearnih enačb prikazuje naslednji primer, ki izpiše rezultat:

u[0]= 1
u[1]= 2
u[2]= 3
u[3]= 4
u[4]= 5
/******   M*u=b   ******/
#include <stdio.h>
#include <stdlib.h>
#include "lupack.h"

#define N 5

float M[N*N]={2,  3,  0,  0,  0,
              3,  0,  4,  0,  6,
              0, -1, -3,  2,  0,
              0,  0,  1,  0,  0,
              0,  4,  2,  0,  1};

float b[N]={8, 45, -3, 3, 19};

int main()
{
  int i;
  int *indx;
  float d;
 
  indx=(int *)malloc(N*sizeof(int));
  ludcmp(M, N, indx, &d);
  lubksb(M, N, indx, b);
  free(indx);

  for(i=0;i<N;i++)
  {
    printf("u[%d]= %g\n", i, b [i]);
  }
  return 0;
} 

Kodo za reševanje sistema linearnih enačb v jeziku C lupack.c uporabimo kot zunanje podprograme.

Programe lahko dobimo s klikom na naslednje povezave:

example-lin.c - Primer reševanja sistema linearnih enačb

lupack.c - Obvezen dokument za reševanje sistema linearnih enačb

lupack.h - Obvezen dokument za reševanje sistema linearnih enačb

Attachments (5)

Download all attachments as: .zip