III. Przykłady programów w języku C/C++ i zadania

1. Proste algorytmy i programy komputerowe

W rozdziale tym przedstawiono rozwiązania najprostszych zadań z zakresu

programowania, których celem jest praktyczne zapoznanie studenta z

podstawowymi funkcjami i instrukcjami języka C/C++. Dodatkowym

zamierzeniem autorów w tym etapie nauki programowania, było wykształcenie

u czytelnika zasad myślenia algorytmicznego oraz niezbędnej przy

programowaniu dokładności. Dlatego istotną częścią zadań w tym rozdziale są

sieci działań programów (schematy blokowe) będące graficznym obrazem toku

czynności przetwarzania danych według danego programu.

Przedstawione algorytmy, jak i zamieszczone wskazówki i zalecenia nie należy

rozumieć jako jedyne i najlepsze rozwiązania w danym przypadku. Zadania

mają służyć do ćwiczeń i nauki pewnego sposobu myślenia, a nie podania

uniwersalnych sposobów programowania. W pewnych przypadkach w celu

pokazania jakiejś konstrukcji programowej na możliwie prostym przykładzie

zrezygnowano z optymalności rozwiązania. Dla udokumentowania powyższych

faktów w kilku przykładach przedstawiono alternatywne możliwości

rozwiązania danego zagadnienia, pozostawiając studentom dokonania próby

określenia warunków, w których taki czy inny sposób będzie lepszy.

Rozwiązanie każdego zadania zawiera schemat blokowy algorytmu oraz tekst

ź

ródłowy programu w języku C.

Zadanie 1.

Dane są rozłączne przedziały [a,b], [c,d], [e,f] na osi x. Określić numer

przedziału, do którego należy dana wartość zmiennej x. Gdy wartość ta nie

należy do żadnego z przedziałów, podać nr = 0.

Dane: a,b,c,d,e,f,x (liczby zmiennoprzecinkowe, typ float).

Tekst programu:

#include <stdio.h>

float a,b,c,d,e,f,x;

int nr;

main()

{

printf("x=");scanf("%f",&x);

printf("a=");scanf("%f",&a);

printf("b=");scanf("%f",&b);

printf("c=");scanf("%f",&c);

printf("d=");scanf("%f",&d);

printf("e=");scanf("%f",&e);

printf("f=");scanf("%f",&f);

if ((x>a) && (x<b)) nr=1; else

if ((x>c) && (x<d)) nr=2; else

if ((x>e) && (x<f)) nr=3; else nr=0;

printf("nr=%d",nr);

return;

}

Zadanie 2

Dany jest n-wymiarowy wektor V {n}. Ułożyć program wyznaczający długość

L tego wektora.

Dane:

n (int)

V

1

, V

2

, ..., V

n

(float)

Uwagi do algorytmu

Długość wektora V=[

V

1

, V

2

, ..., V

n

] oblicza się ze wzoru:

∑

=

=

n

i

i

V

L

1

2

Tekst programu:

#include <stdio.h>

#include <math.h>

int n,i;

float s,l;

float v[100];

main()

{

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++)

{

printf("V[%d]=",i);

scanf("%f",&v[i]);

}

s=0;

for (i=1;i<=n;i++)

s=s+v[i]*v[i];

l=sqrt(s);

printf("Dlugosc L = %f",l);

return;

}

Zadanie 3

Obliczyć wartość całki S =

dx

x

b

b

∫

3

metodą trapezów przyjmując podział odcinka

ab na 100 równych części.

Dane:

a,b (float)

Uwagi do algorytmu

,

100

1

∑

=

=

i

i

S

S

,

2

1

h

y

y

s

i

i

i

+

−

100

a

b

h

−

=

W pętli wyznaczone i sumowane są pola stu trapezów. pola te obliczane są z

tego samego wzoru, przy czym przy plou następnym rzędna y

i

staje się rzedną

y

i-1

. Fakt ten wykorzystano w programie, aby nie przeprowadzać obliczania tej

rzędnej.

Tekst programu:

#include <stdio.h>

int i;

float a,b,s,y,yn,h,x;

main()

{

printf("a=");scanf("%f",&a);

printf("b=");scanf("%f",&b);

h=(b-a)*0.01;

s=0;

y=a*a*a;

for (i=1;i<=100;i++)

{

x=a*i*h;

yn=x*x*x;

s=s+(y+yn)*h/2;

y=yn;

}

printf("S=%f",s);

}

Zadanie 4

Ułożyć program obliczający sumę S elementów o wskaźnikach parzystych

macierzy prostokątnej A{m,n}.

Dane: m, n (int)

A [m][n] (float)

Uwagi do algorytmu

W przypadku macierzy A{4,5}:

























=

45

45

43

42

41

35

35

33

32

31

25

24

23

22

21

15

14

13

12

11

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

A

Suma elementów o indeksach parzystych wynosi:

S = a

22

+ a

24

+ a

42

+ a

44

Wybór odpowiednich elementów macierzy określenia odpowiednich wartości

indeksów, zadanych przez zmienne sterujące pętli i,j. Wartości parzyste tych

zmiennych uzyskamy przez przyjęcie zarówno wartości początkowej, jak i

kroku równego liczbie 2.

Tekst programu:

#include <stdio.h>

int i,k,m,n;

float s;

float a[50][50];

main()

{

printf("m=");scanf("%d",&m);

printf("n=");scanf("%d",&n);

for (i=1;i<=m;i++)

for (k=1;k<=n;k++)

{

printf("a[%d][%d]=",i,k);

scanf("%f",&a[i][k]);

}

s=0;

for (i=2;i<=n;i=i+2)

for (k=2;k<=n;k=k+2)

s=s+a[i][k];

printf("S=%f",s);

return;

}

Innym sposobem zapisu dwóch pętli z krokiem 2 jest wykorzystanie instrukcji

do ... while. Poniżej zamieszczono program oparty o konstrukcję while...do:

#include <stdio.h>

int i,k,m,n;

float s;

float a[50][50];

main()

{

printf("m=");scanf("%d",&m);

printf("n=");scanf("%d",&n);

for (i=1;i<=m;i++)

for (k=1;k<=n;k++)

{ printf("a[%d][%d]=",i,k);

scanf("%f",&a[i][k]);

}

s=0;

i=0;

do

{

i+=2;

k=0;

do

{

k+=2;

s=s+a[i][k];

}

while (k<=n);

}

while (i<=m);

printf("S=%f",s);

return;

}

Możliwe jest również rozwiązanie zadania z zastosowaniem pętli while.

Najczęściej jednak z pętli tej korzystamy wtedy, gdy nie jest znana liczba

powtórzeń i być może pętla nie będzie wykonana.

Zadanie 5

Ułożyć program, który w danej macierzy kwadratowej o elementach

całkowitych A{n,n} oblicza iloczyny p i q elementów znajdujących się na obu

przekątnych oraz sumę s elementów k-tej kolumny (k<n).

Dane:

n,k (int),

a[n][n] (float)

Uwagi do algorytmu

p

s  q 









































nn

nk

n

n

n

k

n

k

a

a

a

a

a

a

a

a

a

a

a

a

...

...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

...

...

...

...

2

1

2

2

22

21

1

1

12

11

Ponieważ każdą z poszukiwanych wartości tworzy ta sama liczba elementów,

wszystkie operacje są wykonywane w jednej pętli. Dobór pożądanych

elementów odbywa się przez odpowiednie operacje na indeksach.

#include <stdio.h>

int i,j,n,k2;

float s,p,q;

float a[50][50];

main()

{

printf("n=");scanf("%d",&n);

printf("k=");scanf("%d",&k);

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

printf("a[%d][%d]=",i,j);

scanf("%f",&a[i][j]);

}

p=q=1;

s=0;

for (i=1;i<=n;i++)

{

s+=a[i][k];

q*=a[i][n+1-i];

p*=a[i][i];

}

printf("S=%f\tq=%f\tp=%f",s,q,p);

return;

}

Zadanie 6

Napisać program obliczający liczbę D elementów dodatnich, liczbę Z zer i

liczbę U elementów ujemnych w zbiorze n liczb całkowitych (n<1000).

Dane

a[n] (int)

Tekst programu:

#include <stdio.h>

int z,d,u,i,n;

int a[1000];

main()

{

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++)

{

printf("a[%d]=",i);

scanf("%d",&a[i]);

}

d=u=z=0;

for (i=1;i<=n;i++)

if (a[i]>0) d++; else if (a[i]<0) u++; else z++;

printf("Ilosc liczb ujemnych: %d\n",u);

printf("Ilosc liczb dodatnich: %d\n",d);

printf("Ilosc zer: %d\n",z);

return;

}

Zadanie 7.

Obliczyć w punkcie x sumę szeregu trygonometrycznego:

...,

cos

...

2

cos

cos

2

+

+

+

+

ix

x

x

e

ix

e

x

e

x

z zadaną dokładnością

ε

. Obliczenia należy zakończyć dopiero, gdy powyższy

warunek będą spełniać trzy kolejne sumy. Dodatkowo podać n wyrazów

tworzących szukaną sumę.

Dane

x (float)

Uwagi do algorytmu

Rozwiązanie zadania sprowadza się do zastosowania typowego algorytmu na

obliczanie sumy, z uwzględnieniem warunków podanych w zadaniu:

∑

=

=

n

i

ix

e

ix

S

1

cos

gdy jednocześnie:

,

0

cos

<

jx

e

jx

j=n-2, n-1, n

Tekst programu:

#include <stdio.h>

#include <math.h>

int i,n;

float x,s,s1,x1,eps;

main()

{

printf("x=");scanf("%f",&x);

printf("Dokladnosc obliczen, EPS=");

scanf("%f",&eps);

n=0;

s=0.0;

i=0;

do

{

i++;

x1=x*i;

s1=cos(x1)/exp(x1);

s=s+s1;

if (s1<eps) n++; else n=0;

}

while (n<3);

printf("i=%d\n",i);

printf("S=%f\n",s);

return;

}

Zadanie 8

Na płaszczyźnie 0XY dany jest dowolny wielobok zamknięty, którego

wierzchołki A

1

, A

2

, A

3

, ..., A

n

określone są przez współrzędne (x

1

, y

1

),...,(x

n

, y

n

).

Ułożyć program na obliczenie pola powierzchni S tego wieloboku. Ułożyć

program na obliczenie pola powierzchni S tego wieloboku. Położenie

wierzchołka A

1

jest dowolne, a numery następnych wierzchołków występują

kolejno zgodnie z dodatnią orientacją płaszczyzny 0XY (zwykle lewostronnie).

Dane

n (int)

x[n] ,y[n] (float)

Uwagi do algorytmu

Punkt 0 z każdym z boków wielokąta tworzy n trójkątów:

∆

0A

1

A

2

,

∆

0A

2

A

3

, ...,

∆

0A

n-1

A

n

,

∆

0A

n

A

1

. Ich pole powierzchni opisuje wzór:













=





















=

+

+

+

+

1

1

1

det

2

1

1

1

0

0

0

det

2

1

i

i

i

i

i

j

i

i

i

y

x

y

x

y

x

y

x

P

Jeżeli kierunek opisu trójkata jest zgodny z orientacją układu, to ze wzoru

otrzymujemy wartość dodatnią i odwrotnie. Suma pól trójkątów z

uwzględnieniem znaków daje szukane pole wielokąta.

∑

=

=

n

i

P

S

1

Ponieważ współrzędne punktu A

1

wchodzą do opisu zarówno pierwszego jak i

ostatniego trójkąta, należy więc tak przygotować tablicę X, Y w celu pamiętania

danych, aby współrzędne punktu A

1

były zarówno na 1 jak i na n+1 pozycji.

Tekst programu:

#include <stdio.h>

int i,n;

float s;

float x[50],y[50];

main()

{

printf("n=");scanf("%d",&n);

for (i=1;i<=n;i++)

{

printf("x[%d]=",i);

scanf("%f",&x[i]);

printf("y[%d]=",i);

scanf("%f",&y[i]);

}

x[n+1]=x[1];

y[n+1]=y[1];

s=0;

for (i=1;i<=n;i++)

s+=x[i]*y[i+1]-x[i+1]*y[i];

s*=0.5;

printf("Pole powierzchni wieloboku = %f\n",s);

return;

}

Zadanie 9

Ułożyć program, który w danej macierzy kwadratowej o elementach

całkowitych A{n,n} znajduje element o wartości maksymalnej znajdujący się w

części macierzy nad główną przekątną.

Dane:

n (int),

a[n][n] (float)

Tekst programu:

#include <stdio.h>

int i,j,n;

float a[50][50];

float max;

main()

{

printf("n=");scanf("%d",n);

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

printf("a[%d][%d]=",i,j);

scanf("%f",&a[i][j]);

}

max=a[1][2];

for (i=1;i<=n-1;i++)

for (j=i+1;j<=n;j++)

if (a[i][j]>max) max=a[i][j];

printf("Max = %f",max);

return;

}

Zadanie 10

Opracować program, który w zadanym n - elementowym zbiorze liczb

całkowitych (n>0) znajduje wartość występującą najczęściej, oraz liczbę jej

wystąpień. Jeżeli dwie różne wartości zbioru występują w nim tyle samo razy, to

można wybrać którąkolwiek z nich.

Dane:

n (int), zbior[100] (int)

W przedstawionym algorytmie wywoływana jest funkcja o nazwie ile_razy,

której schemat blokowy jest następujący:

Tekst programu:

#include <stdio.h>

#include <conio.h>

int i,n,max,element;

int zbior[100];

int ile_razy(int element); /*deklaracja funkcji*/

main()

{

clrscr(); /*czyszczenie ekranu*/

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++)

{

printf("zbior[%d]=",i);

scanf("%d",&zbior[i]);

}

max=ile_razy(zbior[1]);

element=zbior[1];

for (i=2;i<=n;i++)

{

if (ile_razy(zbior[i])>max)

{

max=ile_razy(zbior[i]);

element=zbior[i];

}

}

printf("W zbiorze najczesciej wystepowala liczba:

%d\n",element);

printf("Liczba wystapien wynosi: %d\n",max);

return;

}

int ile_razy(int element)

{

int i,znaleziono;

znaleziono=0;

for (i=1;i<=n;i++)

if (element==zbior[i])

znaleziono++;

return (znaleziono);

}

Zadanie 11

W danym zbiorze liczb naturalnych znaleźć najdłuższy podciąg liczb

parzystych.

Dane

n (int), a[100] (int).

Treść programu:

#include <stdio.h>

#include <conio.h>

int i,j,n,max_dlug,dlugosc;

int podciag[100],max_podciag[100],a[100];

main()

{

clrscr();

printf("n=");scanf("%d",&n);

for (i=1;i<=n;i++)

{

printf("a[%d]=",i);

scanf("%d",&a[i]);

}

max_dlug=0;

dlugosc=0;

for (i=1;i<=n;i++)

if (a[i]%2==0)

{

dlugosc++;

podciag[dlugosc]=a[i];

if (dlugosc>max_dlug)

{

max_dlug=dlugosc;

for (j=1;j<=dlugosc;j++)

max_podciag[j]=podciag[j];

}

}

else dlugosc=0;

printf("Najdluzszy podciag ma: %d",max_dlug);

printf("elementow\n");

for (i=1;i<=max_dlug;i++)

printf("a[%d]=%d\n",i,max_podciag[i]);

return;

}

Zadanie 12.

Analizując ciąg liczb naturalnych od 1 do 1000, znaleźć podciąg 9 liczb taki, że

nie ma wśród nich liczby pierwszej.

W przedstawionym algorytmie występuje wywołanie funkcji liczba_pierwsza,

której zadaniem jest sprawdzenie czy liczba całkowita będąca parametrem tej

funkcji jest liczbą pierwszą. Funkcja ta zwraca wartość 1 gdy liczba jest liczbą

pierwszą oraz wartość o gdy liczba nie jest liczbą pierwszą. Schemat blokowy

tej funkcji przedstawiono poniżej:

Tekst programu:

#include <stdio.h>

#include <conio.h>

int znaleziono,i;

int podciag[10];

int liczba_pierwsza(int liczba);

main()

{

clrscr();

i=2;

znaleziono=0;

do

{

i++;

if (!liczba_pierwsza(i))

{

znaleziono++;

podciag[znaleziono]=i;

}

else znaleziono=0;

}

while (znaleziono<=9);

for (i=1;i<=9;i++)

printf("%d ",podciag[i]);

return;

}

int liczba_pierwsza(int liczba)

{

int i,prawda;

prawda=1;

i=1;

do

{

i++;

if ((liczba % i)==0) prawda=0;

}

while (i<liczba-1);

return (prawda);

}

2. Programy z zagadnień rachunku macierzowego

Zadanie 13.

Opracować program generujący wartości elementów macierzy kwadratowej

stopnia n-tego (n<=10).

Dane:

n (int)

Uwagi do programu

Generowanie wartości elementów macierzy odbywa się poprzez użycie funkcji

random(int zakres), która losuje wartość całkowitą z przedziału 0-zakres.

Użycie tej funkcji wymaga przyłączenia piku nagłówkowego stdlib.h. Przed

pierwszym użyciem funkcji random() należy wywołać funkcję randomize(),

która inicjuje generator liczb pseudolosowych.

Tekst programu:

#include<iostream.h>;

#include<conio.h>;

#include<stdlib.h>;

int i,j,n;

int a[10][10];

void main(void)

{

clrscr();

gotoxy(1,1);

do

{

cout<<"Podaj stopien macierzy:";

cin>>n;

}

while (n>10);

clrscr();

randomize();

for (i=0;i<n;i++)

for (j=0;j<n;j++)

{

a[i][j]=random(100);

gotoxy((i+1)*7,j+2);

cout<<a[i][j];

};

cout<<"\nKONIEC !!!";

getch(); // zatrzymanie programu do czasu

// nacisniecia klawisza

return;

}

Ponieważ plik zawiera funkcje języka C++ np. cout i cin, uruchamiany program

w środowisku Borland C++ należy zapisać w pliku o rozszerzeniu .cpp.

Zadanie 14

Napisać program w języku C++ wczytujący dwie macierze kwadratowe A i B

stopnia 3 i wyznaczający macierz C stanowiącą sumę tych dwóch macierzy.

Dane

macierzA[5][5], macierzB[5][5] (int)

Tekst programu:

#include <iostream.h>

#include <conio.h>

int main()

{

const rozmiar=3;

int macierzA[rozmiar][rozmiar];

int macierzB[rozmiar][rozmiar];

int macierzC[rozmiar][rozmiar];

clrscr();

cout<<"\nWprowdz wartosci macierzy A :"<<endl;

for(int a=0; a<rozmiar; a++)

{

cout<<"rzad "<<a+1<<":"<<endl;

for(int b=0; b<rozmiar; b++)

{

cin>>macierzA[a][b];

}

}

cout<<"Wprowdz wartosci macierzy B :"<<endl;

for(int c=0; c<rozmiar; c++)

{

cout<<"rzad "<<c+1<<":"<<endl;

for(int d=0; d<rozmiar; d++)

{

cin>>macierzB[c][d];

}

}

for(int i=0; i<rozmiar; i++)

{

for(int j=0; j<rozmiar; j++)

{

macierzC[i][j]=0;

for(int k=0; k<rozmiar; k++)

{

macierzC[i][j] += macierzA[i][k] * macierzB[k][j];

}

}

}

cout<<"Macierz wynikowa C: "<<endl;

for(i=0;i<rozmiar;i++)

{

for(int j=0;j<rozmiar;j++)

{

cout<<macierzC[i][j]<<" ";

}

cout<<"\n";

}

getch();

return 0;

}

Zadanie 15

Obliczyć iloczyn macierzy prostokątnej X{m,n} przez macierz prostokątną

Y{n,p}.

Dane:

m,n,p (int)

x[m][n], y[n][p] (float)

Uwagi do algorytmu

W wyniku iloczynu:

=





















































np

n

n

p

p

mn

m

m

n

n

y

y

y

y

y

y

y

y

y

x

x

x

x

x

x

x

x

x

...

...

...

...

...

...

...

*

...

...

...

...

...

...

...

2

1

2

22

21

1

12

11

2

1

2

22

21

1

12

11

otrzymujemy macierz o m. wierszach i p kolumnach Z{m,p}, której elementy są

określone wzorami:

∑

=

=

n

j

jk

ij

ik

y

x

z

1

dla i=1,2,...m; k=1,2,...,p

Tekst programu:

#include <stdio.h>

int i,j,k,n,m,p;

float x[10][10],y[10][10],z[10][10];

main()

{

printf("n=");scanf("%d",&n);

printf("m=");scanf("%d",&m);

printf("p=");scanf("%d",&p);

for (i=1;i<=m;i++)

for (j=1;j<=n;j++)

{

printf("x[%d][%d]=",i,j);

scanf("%f",&x[i][j]);

}

for (i=1;i<=n;i++)

for (j=1;j<=p;j++)

{

printf("y[%d][%d]=",i,j);

scanf("%f",&y[i][j]);

}

for (i=1;i<=m;i++)

for (k=1;k<=p;k++)

{

z[i][k]=0;

for (j=1;j<=n;j++)

z[i][k]+=x[i][j]*y[j][k];

printf("z[%d][%d]=%f\n",i,k,z[i][k]);

}

return;

}

Dla tego zadania opracowany został również program w języku C++, w którym

wprowadzono zdefiniowaną funkcję o nazwie mnoz_w_k. Parametrami tej

funkcji są numer wiersza pierwszej macierzy oraz numer kolumny drugiej

macierzy. Funkcja zwraca wartość obliczonego elementu macierzy wynikowej

będącego sumą iloczynów elementów w i-tym wierszu macierzy pierwszej oraz

w j-tej kolumnie macierzy drugiej.

Zarówno macierze wejściowej jak i macierz wynikowa są prezentowana na

ekranie w bardzo czytelny sposób dzięki wykorzystaniu funkcji gotoxy.

#include<iostream.h>;

#include<conio.h>;

int macierz1[10][10],macierz2[10][10];

int i,j,n;

int mnoz_w_k(int i,int j)

{ int x,suma=0;

for (x=0;x<n;x++)

suma=suma+macierz1[i][x]*macierz2[x][j];

return(suma);

};

void main(void)

{ clrscr();

gotoxy(1,1);

cout<<"Podaj stopien macierzy:";

cin>>n;

gotoxy(1,3);

cout<<"Podaj wyrazy macierzy pierwszej:";

for (i=0;i<n;i++)

for (j=0;j<n;j++)

{ gotoxy(j*4+1,i*2+4);

cin>>macierz1[i][j];

};

gotoxy(1,3);

cout<<"Podaj wyrazy macierzy drugiej: ";

for (i=0;i<n;i++)

for (j=0;j<n;j++)

{ gotoxy(j*4+31,i*2+4);

cin>>macierz2[i][j];

};

gotoxy(1,12);

cout<<"Wynik pomnozenia tych dwoch macierzy:";

for (i=0;i<n;i++)

for (j=0;j<n;j++)

{ gotoxy(j*4+1,i*2+14);

cout<<mnoz_w_k(i,j);

};

getch();

};

Zadanie 16

Opracować program służący do rozwiązywania układu równań linowych metodą

eliminacji Gaussa. Układ N równań linowych:

n

n

nn

n

n

n

b

x

a

x

a

b

x

a

x

a

=

+

+

=

+

+

...

...

..........

..........

..........

...

1

1

1

1

1

11

jest określony przez macierz A{n,n} oraz wektor B{n}.

Dane

n (int)

A[n][n] (float)

B[n] (float)

Uwagi do algorytmu

Metoda Gaussa polega na takim systematycznym przekształcaniu nieosobliwej

macierzy A (niezerowy wyznacznik), aby na diagonali zostały tylko jedynki,

pozostałe zaś elementy były zerowe. Wtedy przekształcony wektor B jest

szukanym rozwiązaniem układu równań. W programie zastosowano

uproszczony wariant metody Gaussa, sprowadzający macierz A do postaci

trójkątnej, skąd łatwo już metodą podstawiania można uzyskać rozwiązanie

układu równań liniowych. Gdy macierz A jest osobliwa, a wektor B niezerowy,

wówczas brak jest rozwiązań układu równań, o czym program informuje

komunikatem „brak rozwiązań nietrywialnych”. W przypadku szukania

rozwiązania układu równań jednorodnych (wektor B zerowy), gdy macierz jest

nieosobliwa, program znajdzie rozwiązanie zerowe (w granicach dokładności

numerycznej). Gdy macierz A jest osobliwa, istnieje nieskończenie wiele

rozwiązań, ale program nie potrafi ich znaleźć, informuje więc również o

„braku rozwiązań nietrywialnych”.

Tekst programu:

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<stdlib.h>

int n,i,j,n1,r,i1,k;

float a[6][6],b[6],x[6];

float m,s;

main()

{

clrscr();

n=0;

do {

gotoxy(10,10);

printf("Ilosc niewiadomych: n=");

scanf("%d",&n);

if (n>5) {gotoxy(40,10);

printf("n<=5");}

}

while (n>5);

clrscr();

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

{ gotoxy(3+(j-1)*12,i+1);

printf("a[%d,%d]=",i,j);

scanf("%f",&a[i][j]); }

gotoxy(3+n*12,i+1);

printf("b[%d]=",i);

scanf("%f",&b[i]);

}

n1=n-1;

for (i=1;i<=n1;i++)

{

r=i;

m=a[i][i];

i1=i+1;

for (j=i1;j<=n;j++)

if (abs(a[j][i])>abs(m)) r=j;

if (m==0)

{clrscr();

gotoxy(10,10);

puts("Brak rozwiazan nietrywialnych !!!");

exit(0);}

if (r!=i)

{for (k=1;k<=n;k++)

{s=a[i][k];

a[i][k]=a[r][k];

a[r][k]=s;}

s=b[i];

b[i]=b[r];

b[r]=s;

}

for (j=i1;j<=n;j++)

{ m=a[j][i]/a[i][i];

for (k=1;k<=n;k++)

a[j][k]-=m*a[i][k];

b[j]-=m*b[i]; }

}

if (a[n][n]==0)

{clrscr();

gotoxy(10,10);

puts("Brak rozwiazan nietrywialnych !!!");

exit(0);}

x[n]=b[n]/a[n][n];

for (i=n1;i>=1;i--)

{

s=0;

i1=i+1;

for (j=i1;j<=n;j++)

s+=x[j]*a[i][j];

x[i]=(b[i]-s)/a[i][i];

}

clrscr();

for (i=1;i<=n;i++)

{gotoxy(5,i+2);

printf("X[%d]=%f",i,x[i]);}

return;

}

Zadanie 17

Opracować program służący do obliczania wyznacznika macierzy kwadratowej

A{n,n} oraz do znajdowania macierzy odwrotnej X[n,n]. Wymienione macierze

muszą spełniać równanie:

A * X = I

gdzie: I jest macierzą jednostkową (tylko jedynki na diagonali);

Uwagi do algorytmu

Powyższe równanie można zapisać w postaci wektorowej:

A * x

i

= e

i

i=1,...,N

gdzie:

x

i

oznacza wektor zbudowany z i-tej kolumny macierzy X,

e

i

jest wektorem mającym jedynkę na i-tek pozycji oraz zerowe pozostałe

elementy.

W ten sposób problem odwracania macierzy został sprowadzony do problemu

rozwiązania N układów N równań liniowych. W tym celu program

wykorzystuje metodę eliminacji Gaussa, opisaną w zadaniu nr 16.

Dane

n (int)

a[n][n] (float)

Tekst programu:

#include<stdio.h>;

#include<stdlib.h>;

#include<math.h>;

#include<conio.h>

int n,i,j,k,i1,i2;

float a[10][10];

float t,w;

int p[10];m[10][2];

void wydruk_macierzy(int x ,int y);

main()

{

do

{

clrscr();

gotoxy(1,1);

printf("Wymiar macierzy N: ");

scanf("%d",&n);

}

while(n>10);

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

gotoxy(1,3);

puts(" ");

gotoxy(1,3);

printf("a[%d,%d]=",i,j);

scanf("%f",&a[i][j]);

}

clrscr();

wydruk_macierzy(1,1);

w=1;

for (i=1;i<=n;i++)

p[i]=0;

for (i=1;i<=n;i++)

{

t=0.0;

for (j=1;j<=n;j++)

if (p[j]!=1)

{

for (k=1;k<=n;k++)

if ((p[k]!=1)||(abs(t)<abs(a[j][k])))

{

i1=j;

i2=k;

t=a[j][k];

}

}

p[i2]+=1;

if (i1!=i2)

{

w=-w;

for (j=1;j<=n;j++)

{

t=a[i1][j];

a[i1][j]=a[i2][j];

a[i2][j]=t;

}

}

m[i][1]=i1;

m[i][2]=i2;

t=a[i2][i2];

w*=t;

a[i2][i2]=1;

for (j=1;j<=n;j++)

a[i2][j]=a[i2][j]/t;

for (j=1;j<=n;j++)

if (j!=i2)

{

t=a[j][i2];

a[j][i2]=0;

for (k=1;k<=n;k++)

a[j][k]-=a[i2][k]*t;

}

}

for (i=1;i<=n;i++)

{

j=n-i+1;

i1=m[j][1];

i2=m[j][2];

if (i1!=i2)

{

for (k=1;k<=n;k++)

{

t=a[k][i1];

a[k][i1]=a[k][i2];

a[k][i2]=t;

}

}

}

gotoxy(2,n+3);

printf("Wyznacznik W=%4.4f",w);

wydruk_macierzy(1,n+5);

return;

}

void wydruk_macierzy(int x ,int y)

{

int i,j;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

gotoxy(x+j*7,y+i);

printf("%3.3f",a[i][j]);

}

return;

}

Zadanie 18

Opracować program służący do diagonalizacji macierzy symetrycznej w celu

wyznaczenia wartości własnych i obliczający wektory własne.

Dane:

n (int)

q[n][n] (float)

Uwagi do algorytmu

Program stosuje metodę Jacobiego, czyli metodę przekształceń unitarnych przez

obroty płaskie. Najpierw wyszukiwany jest największy element pozadiagonalny,

a następnie dokonuje takiego przekształcenia macierzy, by ten element

wyzerować. Proces ten jest powtarzany tak długo, aż moduł największego

elementu pozadiagonalnego, otrzymanego w wyniku przekształceń, będzie

mniejszy niż zadana liczba – dokładność. Przyjmuje się wtedy, że na przekątnej

otrzymanej macierzy znajdują się wartości własne, równolegle zaś

przekształcana macierz jednostkowa tworzy macierz złożoną z wektorów

własnych.

Program ma charakter iteracyjny, więc wykonanie dużej liczby kroków

prowadzi do małej dokładności numerycznej. W szczególności, gdy macierz

wyjściowa ma duże elementy pozadiagonalne (w stosunku do elementów

diagonalnych), liczba iteracji może być duża, a co za tym idzie i błędy

numeryczne mogą być znaczne.

Z uwagi na złożony schemat algorytmu zawierający szereg warunków

powodujących powrót do wcześniejszych operacji, zastosowano w programie

instrukcje skoku goto.

Tekst programu:

#include<stdio.h>;

#include<stdlib.h>;

#include<math.h>;

#include<conio.h>

int n,m,m1,m2,i,j,i1,j1,l;

float d,p1,x1,p,t,c,s,q1;

float q[10][10],v[10][10];

float x[10];

int k[10];

main()

{

do {

clrscr();

gotoxy(1,1);

printf("Wymiar macierzy N: ");

scanf("%d",&n);

}

while(n>10);

for (i=1;i<=n;i++)

{

for (j=i;j<=n;j++)

{

gotoxy(1,3);

puts(" ");

gotoxy(1,3);

printf("q[%d,%d]=",i,j);

scanf("%f",&q[i][j]);

v[i][j]=0.0;

v[j][i]=0.0;

}

v[i][i]=1.0;

}

start:

clrscr();

gotoxy(1,5);

printf("Dokladnosc wyznaczenia: d=");

scanf("%f",&d);

m=0;

m1=n-1;

for (i=1;i<=m1;i++)

{x[i]=0.0;

m2=i+1;

for (j=m2;j<=n;j++)

{p1=abs(q[i][j]);

if (x[i]<=p1)

{x[i]=p1;

k[i]=j;}

}

}

x1=x[1];

i1=1;

j1=k[1];

for (i=2;i<=m1;i++)

if (x1<=x[i])

{x1=x[i];

i1=i;

j1=k[i];}

if (x1<=d) goto wyjscie;

m=m+1;

l=1;

if (q[i1][i1]<=q[j1][j1]) l=-1;

p=q[i1][i1]-q[j1][j1];

p1=pow((p*p+4*q[i1][j1]*q[i1][j1]),2);

t=2*l*q[i1][j1]/(abs(p)+p1);

c=1/pow((1+t*t),2);

s=t*c;

p1=q[i1][i1];

q[i1][i1]=c*c*(p1+t*(2*q[i1][j1]+t*q[j1][j1]));

q[j1][j1]=c*c*(q[j1][j1]-t*(2*q[i1][j1]-t*p1));

q[i1][j1]=0.0;

if (q[i1][i1]<q[j1][j1])

{

p1=q[i1][i1];

q[i1][i1]=q[j1][j1];

q[j1][j1]=p1;

if (s>=0) p=-c;

else p=c;

c=s;

s=p;

}

for (i=1;i<=m1;i++)

{

if ((i!=i1)&&(i!=j1))

if (k[i]==j1)

{

p1=k[i];

p=q[i][p1];

q[i][p1]=0;

m2=i+1;

x[i]=0.0;

for (j=m2;j<=n;j++)

{

t=abs(q[i][j]);

if (x[i]<=t)

{

x[i]=t;

k[i]=j;

}

}

q[i][p1]=p;

}

}

x[i1]=0.0;

x[j1]=0.0;

for (i=1;i<=n;i++)

{

if (i==i1) goto E3;

if (i>i1) goto E4;

p=q[i][i1];

q[i][i1]=c*p+s*q[i][j1];

q1=abs(q[i][i1]);

if (x[i]>=q1) goto E1;

x[i]=q1;

k[i]=i1;

E1:

q[i][j1]=-s*p+c*q[i][j1];

q1=abs(q[i][j1]);

if (x[i]>=q1) goto E3;

x[i]=q1;

k[i]=j1;

goto E3;

E4:

if (i==j1) goto E3;

p=q[i1][i];

if (i>j1) goto E2;

q[i1][i]=c*p+s*q[i][j1];

q1=abs(q[i1][i]);

if (x[i1]>=q1) goto E1;

x[i1]=q1;

k[i1]=i;

goto E1;

E2:

q[i1][i]=c*p+s*q[j1][i];

q1=abs(q[i1][i]);

if (x[i1]<q1)

{

x[i1]=q1;

k[i1]=i;

}

q[j1][i]=-s*p+c*q[j1][i];

q1=abs(q[j1][i]);

if (x[j1]>=q1) goto E3;

x[j1]=q1;

k[j1]=i;

E3:

}

for (i=1;i<=n;i++)

{

p=v[i][i1];

v[i][i1]=c*p+s*v[i][j1];

v[i][j1]=-s*p+c*v[i][j1];

}

wyjscie:

clrscr();

for (i=1;i<=n;i++)

{

printf("\nWartosc wlasna nr:%d=%f\n",i,q[i][i]);

puts("Skladowe wektora wlasnego\n");

for (j=1;j<=n;j++) printf("%f\n",v[j][i]);

}

printf("\nDokladnosc %f po %d obrotach\n",d,m);

l=2;

do

{printf("\nCzy zmiana dokladnosci: 1-Tak,0-Nie");

printf("\nL=");scanf("%d",&l);}

while (l>1);

if (l==1) goto start;

return;

}

3. Sortowanie liczb

Sortowanie liczb lub znaków tj. ustawianie ich w zdefiniowanym wcześniej

porządku w celu późniejszego łatwiejszego ich wyszukiwania – stanowi jeden z

najważniejszych problemów przetwarzania danych. Sortowane liczby ustawione

są początkowo na ogół w nieznanym porządku. Z reguły wymaga się, żeby po

sortowaniu liczby występowały w porządku wzrastających ich wartości.

Istnieje wiele metod sortowania różniących się od siebie rozmaitymi cechami,

jak: szybkością działania, prostotą algorytmu, wielkością wymaganej pamięci.

Najprostszą z tych metod jest metoda pęcherzykowa (ang. bubble-sort), której

nazwa wiąże się z faktem unoszenia się ku górze największych (jako

najlżejszych) pęcherzyków gazu w wodzie.

W przypadku tablicy a jednowymiarowej o rozmiarze n, za jej „górę” można

uważać jej część zawierającą elementy a

k

o indeksach k największych. Tę

„górę” nazwiemy jednak stronę prawą tablicy a w odróżnieniu od strony lewej,

zawierającej elementy a

k

o najmniejszych indeksach.

Sortowanie pęcherzykowe liczb (tj. sortowanie ich metodą pęcherzykową)

polega na przeglądaniu sąsiadujących ze sobą kolejnych par elementów a

k

i a

k+1

tablicy a od jej strony lewej do prawej i przestawianiu (zamianie miejscami) w

elementach a

k

i a

k+1

liczb o zaburzonym porządku. Łatwo stwierdzić, że po

jednym takim „przejrzeniu” całej tablicy a, w jej ostatnim elemencie, a

n

znajdzie

się liczba największa. Takie jedno „przejrzenie” nazywa się przebiegiem lub

przejściem.

W przebiegu drugim odbywa się analogiczne przeglądanie (oczywiście z

ewentualnym przestawianiem liczb w elementach a

k

i a

k+1

w razie zaburzonego

porządku) obejmujące już jednak tylko elementy a

1

÷

a

n-1

(bo liczba największa

jest już w wymaganym elemencie a

n

). W wyniku, liczba największa spośród

występujących w elementach a

1

÷

a

n-1

znajdzie się w elemencie a

n-1

.

Dalsze przebiegi obejmą kolejno elementy: a

1

÷

a

n-2

, a

1

÷

a

n-3

itd. aż do a

1

÷

a

2

, po

tym na pewno nastąpi spełnienie wymaganej nierówności: a

1

<a

2

<...<a

n

.

Algorytm sortowania pęcherzykowego n liczb zawartych w elementach a

1

, a

2

,

...,

a

n

ma więc dla przebiegu i-tego (i=1,2,...,n-1), w którym jest m=n-i

następującą postać:

- dla kolejnych wartości j od 1 do m. co 1, czyli dla j=1(1)m bada się, czy

spełniona jest nierówność a

i

>a

j+1

i w razie jej spełnienia zamienia się ze sobą

miejscami liczby w elementach a

j

i a

j+1

.

Przykład wykorzystania metody sortowania metodą pęcherzykową przedstawia

zadanie nr 19.

Zadanie nr 19

Opracować program porządkujący rosnąco zbiór n-elementowy stosując metodę

sortowania pęcherzykowego. Program ma zawierać moduł generowania

wartości elementów zbioru w zakresie liczb od –100 do 100.

Dane

n (int)

a[n] (int)

Tekst programu:

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<time.h>

int i,j,c,znak,kolumna,wiersz,n;

int a[101];

main()

{

randomize();

clrscr();

printf("(0<n<100) n=");

scanf("%d",&n);

n--;

clrscr();

for (i=0;i<=n;i++)

{

a[i]=random(100);

znak=random(2)-1;

if (znak==0) a[i]=a[i]*(-1);

}

for (i=n-1;i>=0;i--)

for (j=0;j<=i;j++)

if (abs(a[j]) > abs(a[j+1]))

{

c=a[j];

a[j]=a[j+1];

a[j+1]=c;

}

for (i=0;i<=n;i++)

{

kolumna=5*(i%10)+1;

wiersz=i/10+1;

gotoxy(kolumna,wiersz);

printf("%d ",a[i]);

}

return;

}

Inną znaną metodą sortowania liczb jest metoda sortowanie szybkiego (quick-

sort). W metodzie tej w odróżnieniu od metody pęcherzykowej porównuje się ze

sobą (i przestawia) nie elementy sąsiadujące bezpośrednio ze sobą, ale elementy

odległe.

Zadanie 20

Opracować w języku C++ program komputerowy zawierający funkcję

sortowania tablicy n liczb metodą sortowania quicksort.

Tekst programu:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

void quicksort(int tablica[10], int x, int y)

{

int i,j,v,temp;

i=x;

j=y;

v=tablica[div(x+y,2).quot];

do {

while (tablica[i]<v) i++;

while (v<tablica[j]) j--;

if (i<=j)

{

temp=tablica[i];

tablica[i]=tablica[j];

tablica[j]=temp;

i++;

j--;

}

}

while (i<=j);

if (x<j) quicksort(tablica,x,j);

if (i<y) quicksort(tablica,i,y);

}

void main(void)

{

int ile_liczb,i,liczba;

int tablica[10];

clrscr();

printf("Ile liczb chcesz posortowac (do 10) ? ");

scanf("%i",&ile_liczb);

for(i=0; i<ile_liczb; i++)

{

printf("Wprowadz liczbe #%i: ",i+1);

scanf("%i",&liczba);

tablica[i]=liczba;

}

clrscr();

printf("Tablica przed posortowaniem:");

for(i=0; i<ile_liczb; i++)

printf("\n%i",tablica[i]);

quicksort(tablica,0, ile_liczb-1);

printf("\nTablica po posortowaniu:");

for(i=0; i<ile_liczb; i++)

printf("\n%i",tablica[i]);

printf("\nDowolny klawisz...");

getch();

}

Trzecim przykładem sortowania jest metoda sortowania przez wstawianie

(insertionsort). Algorytm tej metody usprawnia metodę pęcherzykową poprzez

kolejne wstawianie analizowanych elementów w właściwe im miejsca ustalone

w wyniku porównań z elementami o malejących indeksach.

Zadanie 21

Opracować w języku C++ program komputerowy zawierający funkcję

sortowania tablicy n liczb metodą sortowania insertionsort.

Tekst programu:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

void insertionsort(int tablica[10], int ile_liczb)

{

int i,j,v;

for (i=1;i<ile_liczb;i++)

{

j=i;

v=tablica[i];

while ((tablica[j-1]>v)&&(j>0))

{

tablica[j]=tablica[j-1];

j--;

}

tablica[j]=v;

}

printf("\nTablica po posortowaniu:");

for(i=0; i<ile_liczb; i++) printf("\n%i",tablica[i]);

}

void main(void)

{

int ile_liczb,i,liczba;

int tablica[10];

clrscr();

printf("Ile liczb chesz posortowac (do 10) ? ");

scanf("%i",&ile_liczb);

for(i=0; i<ile_liczb; i++)

{

printf("Wprowadz liczbe #%i: ",i+1);

scanf("%i",&liczba);

tablica[i]=liczba;

}

clrscr();

printf("Tablica przed posortowaniem:");

for (i=0; i<ile_liczb; i++)

printf("\n%i",tablica[i]);

insertionsort(tablica,ile_liczb);

printf("\nDowolny klawisz...");

getch();

}