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();
}
