Wst˛ep do programowania – cz˛e´s´c IV
Marcin Szpyrka
Katedra Automatyki
Akademia Górniczo-Hutnicza w Krakowie
Instytut Fizyki
Uniwersytet Humanistyczno-Przyrodniczy Jana Kochanowskiego w Kielcach
2009/10
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
1/24
Funkcje biblioteczne
Funkcje biblioteczne nie s ˛
a cz˛e´sci ˛
a j˛ezyka C. Stanowi ˛
a one zbiór funkcji, które
doł ˛
aczane s ˛
a do kompilatora j˛ezyka i z których mo˙zemy korzysta´c skracaj ˛
ac czas
tworzenia programu.
Przykładowe funkcje matematyczne (math.h)
1
double
sin
(double
x
);
2
double
cos
(double
x
);
3
double
tan
(double
x
);
4
double
exp
(double
x
);
5
double
log
(double
x
);
--
logarytm naturalny
6
double
log10
(double
x
);
7
double
pow
(double
x
, double
y
);
--
x
do
pot˛
egi y
8
double
sqrt
(double
x
);
9
double
fabs
(double
x
);
--
warto´
s´
c bezwzgl˛
edna
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
2/24
Funkcja main z argumentami
Funkcja main mo˙ze by´c funkcj ˛
a wywoływan ˛
a z parametrami. Parametry tej funkcji
wysyłane s ˛
a z linii wywołania programu.
int
main
(int
argc
, char *
argv
[]) { ... }
Funkcj˛e main definiujemy jako funkcj˛e z dwoma argumentami.
z Pierwszy argument argc jest typu int i jest on licznikiem argumentów, tzn.
mówi nam ile parametrów system operacyjny wysłał do programu. Licznik ten
ma warto´s´c co najmniej 1, gdy˙z pierwszym wysyłanym argumentem jest nazwa
programu.
z Drugi argument argv jest wska´znikiem do tablicy argumentów. Poszczególnymi
elementami tej tablicy s ˛
a napisy, tzn. wszystkie argumenty s ˛
a przechowywane
jako napisy i aby wykorzysta´c argumenty b˛ed ˛
ace liczbami, nale˙zy je
odpowiednio przekształci´c.
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
3/24
Funkcja main z argumentami – przykład
1
#include
<stdio.h>
2
#include
<stdlib.h>
3
4
int
main
(int
argc
, char *
argv
[])
/* suma.c */
5
{
6
int
a
,
b
;
7
8
if
(
argc
== 3)
9
{
10
a
=
atoi
(
argv
[1]);
11
b
=
atoi
(
argv
[2]);
12
printf
(
"%d\n"
,
a
+
b
);
13
}
14
else
printf
(
"Bł˛
edna liczba parametrów.\n"
);
15
16
return
0;
17
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
4/24
Funkcja main z argumentami – przykład 2
1
#include
<stdio.h>
2
#include
<stdlib.h>
3
4
int
silnia
(int
n
)
5
{
6
int
i
,
w
= 1;
7
for
(
i
= 1;
i
<=
n
; ++
i
)
w
*=
i
;
8
return
w
;
9
}
10
11
int
main
(int
argc
, char *
argv
[])
12
{
13
int
n
,
k
,
w
;
14
15
if
(
argc
== 3)
16
{
17
n
=
atoi
(
argv
[1]);
18
k
=
atoi
(
argv
[2]);
19
w
=
silnia
(
n
)/(
silnia
(
k
) *
silnia
(
n
-
k
));
20
printf
(
"%d\n"
,
w
);
21
}
22
else
printf
(
"Składnia: newton n k\n"
);
23
24
return
0;
25
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
5/24
Operacje na plikach
Przetwarzanie plików w j˛ezyku C odbywa si˛e w trzech etapach:
1) otwarcie pliku (fopen),
2) zapis lub odczyt do/z pliku (np.: fgetc, fputc, fscanf, fprintf),
3) zamkni˛ecie pliku (fclose).
Komunikacja z plikiem odbywa si˛e przez wska´znik do struktury FILE,
zadeklarowanej w pliku nagłówkowym
stdio
.
h
. Wska´znik ten nazywamy
wska´znikiem pliku.
1
int
main
()
/* pliki.c */
2
{
3
int
a
,
b
,
c
;
4
FILE
*
in
, *
out
;
5
in
=
fopen
(
"liczby.txt"
,
"r"
);
6
out
=
fopen
(
"wynik.txt"
,
"w"
);
7
8
fscanf
(
in
,
"%d%d"
, &
a
, &
b
);
9
c
=
a
+
b
;
10
fprintf
(
out
,
"%d"
,
c
);
11
12
fclose
(
in
);
13
fclose
(
out
);
14
return
0;
15
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
6/24
Operacje na plikach
Funkcja fopen otwieraj ˛
aca plik przyjmuje dwa parametry:
FILE
*
fopen
(char*
name
, char *
mode
);
Parametr name powinien zawiera´c ´scie˙zk˛e dost˛epu do pliku, który chcemy otworzy´c.
Parametr mode decyduje o trybie dost˛epu do pliku:
z
"r"
– plik b˛edzie otwarty do czytania;
z
"w"
– plik b˛edzie otwarty do zapisu – je´sli plik o podanej nazwie istnieje, to
zostanie usuni˛ety z dysku, a nast˛epnie ponownie utworzony;
z
"a"
– plik b˛edzie otwarty do dopisywania na ko´ncu.
Funkcja fopen w przypadku pomy´slnego nawi ˛
azania komunikacji z plikiem zwraca
wska´znik na struktur˛e FILE. W przypadku braku pliku funkcja zwraca warto´s´c
NULL (0).
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
7/24
Operacje na plikach – przykład
1
#include
<stdio.h>
2
3
int
main
(int
argc
, char *
argv
[])
/* pliki3.c */
4
{
5
if
(
argc
!= 3)
6
{
7
printf
(
"Bł˛
edna liczba parametrów.\n"
);
8
return
1;
9
}
10
11
char
c
;
12
FILE
*
in
, *
out
;
13
in
=
fopen
(
argv
[1],
"r"
);
14
out
=
fopen
(
argv
[2],
"w"
);
15
16
c
=
getc
(
in
);
17
while
(
c
!=
EOF
)
18
{
19
if
((
c
>= 65) && (
c
<= 90))
c
+= 32;
20
putc
(
c
,
out
);
21
c
=
getc
(
in
);
22
}
23
24
fclose
(
in
);
25
fclose
(
out
);
26
return
0;
27
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
8/24
Operacje na plikach – przykład (maksymalna warto´s´c w pliku)
1
int
main
(int
argc
, char *
argv
[])
/* maksimum.c */
2
{
3
float
a
,
max
;
4
5
if
(
argc
!= 2)
6
{
7
printf
(
"Wywołanie: maksimum nazwa-pliku\n"
);
8
return
1;
9
}
10
11
FILE
*
f
;
12
f
=
fopen
(
argv
[1],
"r"
);
13
if
(
fscanf
(
f
,
"%f"
, &
a
) !=
EOF
)
14
{
15
max
=
a
;
16
}
17
else
18
{
19
printf
(
"Plik jest pusty.\n"
);
20
return
1;
21
}
22
while
(
fscanf
(
f
,
"%f"
, &
a
) !=
EOF
) if(
max
<
a
)
max
=
a
;
23
24
printf
(
"Maksimum: %.2f\n"
,
max
);
25
fclose
(
f
);
26
return
0;
27
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
9/24
Operacje na plikach – przykład (zliczanie znaków)
1
int
main
(int
argc
, char *
argv
[])
2
{
3
if
(
argc
!= 3)
4
{
/* ... */
}
5
6
FILE
*
f
;
7
f
=
fopen
(
argv
[2],
"r"
);
8
if
(
f
==
NULL
)
9
{
10
printf
(
"Nie ma takiego pliku.\n"
);
11
return
1;
12
}
13
14
int
i
= 0;
15
char
x
=
argv
[1][0];
16
char
y
=
getc
(
f
);
17
while
(
y
!=
EOF
)
18
{
19
if
(
x
==
y
) ++
i
;
20
y
=
getc
(
f
);
21
}
22
23
printf
(
"Liczba znaków: %.d\n"
,
i
);
24
fclose
(
f
);
25
return
0;
26
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
10/24
Rekurencja
Ze zjawiskiem rekurencji mamy do czynienia wtedy je´sli funkcja wywołuje sam ˛
a
siebie. Obiekt nazywamy rekurencyjnym, je´sli cz˛e´sciowo składa si˛e z siebie samego
lub jego definicja odwołuje si˛e do niego samego (np. płatek ´sniegu, kalafior, fraktale
itp.).
Dywan i trójk ˛
at Sierpi´nskiego
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
11/24
Rekurencja – labirynt
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
12/24
Rekurencja – płatek Kocha
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
13/24
Rekurencja – płatek Kocha (modyfikacje)
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
14/24
Przykłady funkcji rekurencyjnych
1
int
silnia
(int
n
)
2
{
3
if
((
n
== 0) || (
n
== 1)) return 1;
4
else return
n
*
silnia
(
n
- 1);
5
}
6
7
8
double
potega
(double
x
, int
n
)
9
{
10
if
((
x
<= 0) || (
n
< 0)) return -1.0;
11
12
if
(
n
== 0) return 1.0;
13
else return
x
*
potega
(
x
,
n
- 1);
14
}
15
16
17
int
fib
(int
n
)
18
{
19
if
(
n
==0) return 0;
20
else if
(
n
==1) return 1;
21
else return
(
fib
(
n
-1) +
fib
(
n
-2));
22
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
15/24
Problem 8 hetmanów
Problem 8 hetmanów polega na ustawieniu na
szachownicy tych˙ze figur tak, aby ˙zadna z nich
nie mogła zabi´c innej.
Algorytm
Stawiamy hetmana w pierwszym wierszu w
pierwszej kolumnie. Przechodzimy do drugiego
wiersza i szukamy pierwszej wolnej kolumny, w
której mo˙zna postawi´c hetmana. Podobnie
post˛epujemy z kolejnymi wierszami. W
momencie, gdy którego´s hetmana nie da si˛e
postawi´c, (w ka˙zdej z 8 kolumn hetman b˛edzie
atakowany) to cofamy si˛e o jeden wiersz i
przesuwamy hetmana na kolejne wolne pole.
Je´sli takie nie istnieje, to znowu si˛e cofamy itd.
Gdy uda si˛e postawi´c 8. hetmana oznacza to, ˙ze
znale´zli´smy rozwi ˛
azanie. Gdy hetmana z
pierwszego wiersza nie ma ju˙z gdzie postawi´c,
to znaczy, ˙ze sprawdzono wszystkie kombinacje.
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
16/24
Problem 8 hetmanów – rozwi ˛
azanie
1
short
plansza
[
N
][
N
];
2
/*
3
0 - pole puste nieatakowane
4
1 .. 8 - pole atakowane
5
-1 ..-8 - pole z hetmanem
6
pole (0,0) znajduje si˛
e w lewym dolnym rogu */
7
8
void
wyczyscPlansze
(void)
9
{
10
int
i
,
j
;
11
for
(
i
= 0;
i
<
N
; ++
i
)
12
for
(
j
= 0;
j
<
N
; ++
j
)
plansza
[
i
][
j
] = 0;
13
}
14
15
void
drukujWynik
(void)
16
{
17
int
i
,
j
;
18
for
(
i
=
N
- 1;
i
>= 0; --
i
)
/* takie zakresy bo pole (0,0) */
19
{
/* jest w lewym dolnym rogu */
20
for
(
j
= 0;
j
<
N
; ++
j
)
21
if
(
plansza
[
i
][
j
] < 0)
printf
(
" H"
);
22
else
printf
(
" *"
);
23
printf
(
"\n"
);
24
}
25
printf
(
"\n\n"
);
26
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
17/24
Problem 8 hetmanów – rozwi ˛
azanie
1
void
zaznaczAtakowane
(int
w
, int
k
)
2
{
3
int
i
,
j
;
4
int
nr
=
w
+ 1;
/* wiersz w zawiera hetmana o numerze w + 1. */
5
6
for
(
i
= 0;
i
<
N
; ++
i
)
/* wiersz i kolumna */
7
{
8
if
(
plansza
[
w
][
i
] == 0)
plansza
[
w
][
i
] =
nr
;
9
if
(
plansza
[
i
][
k
] == 0)
plansza
[
i
][
k
] =
nr
;
10
}
11
i
=
w
;
j
=
k
;
/* przek ˛
atna (w lewo i w dół) */
12
while
((--
i
>= 0) && (--
j
>= 0))
13
if
(
plansza
[
i
][
j
] == 0)
plansza
[
i
][
j
] =
nr
;
14
15
i
=
w
;
j
=
k
;
/* przek ˛
atna (w prawo i do góry) */
16
while
((++
i
<
N
) && (++
j
<
N
))
17
if
(
plansza
[
i
][
j
] == 0)
plansza
[
i
][
j
] =
nr
;
18
19
i
=
w
;
j
=
k
;
/* przek ˛
atna (w lewo i do góry) */
20
while
((++
i
<
N
) && (--
j
>= 0))
21
if
(
plansza
[
i
][
j
] == 0)
plansza
[
i
][
j
] =
nr
;
22
23
i
=
w
;
j
=
k
;
/* przek ˛
atna (w prawo i w dół) */
24
while
((--
i
>= 0) && (++
j
<
N
))
25
if
(
plansza
[
i
][
j
] == 0)
plansza
[
i
][
j
] =
nr
;
26
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
18/24
Problem 8 hetmanów – rozwi ˛
azanie
1
int
ustawHetmana
(int
w
, int
k
)
2
{
3
short
i
,
sukces
;
4
if
(
plansza
[
w
][
k
] == 0)
5
{
6
plansza
[
w
][
k
] = -(
w
+ 1);
/* ustaw hetmana */
7
if
(
w
==
N
- 1)
/* mamy rozwi ˛
azanie */
8
{
drukujWynik
();
return
1; }
9
10
/* w inny przypadku */
11
zaznaczAtakowane
(
w
,
k
);
12
i
= 0;
13
sukces
= 0;
14
/* Próbujemy ustawi´
c kolejnego hetmana w poszczególnych
15
kolumnach nast˛
epnego wiersza. Robimy to tak długo, a˙
z
16
b˛
edzie sukces lub braknie kolumn. */
17
while
((
i
<
N
) && !(
sukces
=
ustawHetmana
(
w
+ 1,
i
))) ++
i
;
18
19
if
(
sukces
) return 1;
20
else
/* wycofujemy si˛
e i zgłaszamy brak rozwi ˛
azania */
21
{
22
usunHetmana
(
w
+ 1);
23
return
0;
24
}
25
}
26
else return
0;
27
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
19/24
Problem 8 hetmanów – rozwi ˛
azanie
1
/* Odznacza pola uprzednio zaznaczone
2
przy ustawianiu hetmana o numerze nr. */
3
void
usunHetmana
(int
nr
)
4
{
5
int
i
,
j
;
6
for
(
i
= 0;
i
<
N
; ++
i
)
7
for
(
j
= 0;
j
<
N
; ++
j
)
8
if
((
plansza
[
i
][
j
] ==
nr
) || (
plansza
[
i
][
j
] == -
nr
))
9
plansza
[
i
][
j
] = 0;
10
}
11
12
13
int
main
() {
14
int
i
=
N
- 1;
15
printf
(
"Podaj pocz ˛
atkow ˛
a kolumn˛
e dla hetmana"
16
" w pierwszym wierszu (0-%d): "
,
i
);
17
scanf
(
"%d"
, &
i
);
18
ustawHetmana
(0,
i
);
19
return
0;
20
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
20/24
Problem konika szachowego
Dana jest szachownica o wymiarach
8x8. Na jednym z pól stoi konik
szachowy. Zadanie polega na
przej´sciu planszy konikiem tak, aby
ka˙zde pole odwiedzi´c dokładnie 1
raz.
Algorytm
Stawiamy konika w wybranym
miejscu i wybieramy jeden z
kolejnych mo˙zliwych ruchów itd.
Je˙zeli uda si˛e nam wykona´c N × N
ruchów, to zostało znalezione
rozwi ˛
azanie. Je˙zeli nie znaleziono
drogi i nie jest mo˙zliwe wykonanie
kolejnego ruchu, to cofamy si˛e o
jeden krok i wybieramy kolejny z
mo˙zliwych ruchów. Je˙zeli nie ma
ju˙z takich, to cofamy si˛e ponownie o
krok itd.
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
21/24
Problem konika szachowego – rozwi ˛
azanie
1
#define
N 5
2
#define
M 9
3
4
short
plansza
[
M
+ 4][
M
+ 4];
5
/* Dodatkowe pola maj ˛
a umo˙
zliwi´
c konikowi wykonanie
6
8 ruchów, nawet je´
sli znajduje si˛
e w rogu szachownicy.
7
Pole (0,0) znajduje si˛
e w lewym dolnym rogu.
8
Pola o warto´
sciach 0 s ˛
a wolne, pozostałe s ˛
a zaj˛
ete. */
9
10
/* Tablice h i v opisuj ˛
a mo˙
zliwe ruchy w pionie i w poziomie. */
11
int
h
[] = {2,
2, 1,
1, -2, -2, -1, -1};
12
int
v
[] = {1, -1, 2, -2, -1,
1, -2,
2};
13
14
/* Zeruje tablic˛
e reprezentuj ˛
ac ˛
a plansz˛
e, ustawia
15
warto´
s´
c 1 na dodatkowych polach otaczaj ˛
acych wła´
sciw ˛
a plansz˛
e. */
16
void
wyczyscPlansze
(void)
17
{
18
int
i
,
j
;
19
for
(
i
= 0;
i
<
M
; ++
i
)
20
for
(
j
= 0;
j
<
M
; ++
j
)
plansza
[
i
][
j
] = 1;
21
for
(
i
= 2;
i
<
M
- 2; ++
i
)
22
for
(
j
= 2;
j
<
M
- 2; ++
j
)
plansza
[
i
][
j
] = 0;
23
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
22/24
Problem konika szachowego – rozwi ˛
azanie
1
int
przesun
(int
x
, int
y
, int
nr
)
2
{
3
int
i
;
4
int
sukces
;
5
6
if
(
plansza
[
x
][
y
] == 0)
7
{
8
plansza
[
x
][
y
] =
nr
;
9
if
(
nr
==
N
*
N
)
10
{
drukujWynik
(); return 1; }
11
12
sukces
= 0;
13
i
= 0;
14
/* Próbujemy wykona´
c kolejne kroki, a˙
z b˛
edzie sukces
15
lub wyczerpiemy mo˙
zliwo´
sci ruchów. */
16
while
((
i
< 8) && !(
sukces
=
przesun
(
x
+
v
[
i
],
y
+
h
[
i
],
nr
+ 1))) ++
i
;
17
18
if
(
sukces
) return 1;
19
else
/* Wycofujemy nasz krok. */
20
{
21
plansza
[
x
][
y
] = 0;
22
return
0;
23
}
24
}
25
else return
0;
26
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
23/24
Problem konika szachowego – rozwi ˛
azanie
1
void
drukujWynik
(void)
2
{
3
int
i
,
j
;
4
for
(
i
=
M
- 3;
i
>= 2; --
i
)
/* takie zakresy bo pole (0,0) */
5
{
/* jest w lewym dolnym rogu */
6
for
(
j
= 2;
j
<
M
- 2; ++
j
)
printf
(
"%3d"
,
plansza
[
i
][
j
]);
7
printf
(
"\n"
);
8
}
9
printf
(
"\n\n"
);
10
}
11
12
int
main
()
13
{
14
wyczyscPlansze
();
15
int
x
,
y
;
16
printf
(
"Podaj pole pocz ˛
atkowe (dwie liczby z zakresu 0 - %d): "
,
17
N
- 1);
18
scanf
(
"%d%d"
, &
x
, &
y
);
19
if
(!
przesun
(
x
+ 2,
y
+ 2, 1))
printf
(
"Brak rozwi ˛
azania!\n"
);
20
return
0;
21
}
Marcin Szpyrka
Wst˛ep do programowania – cz˛e´s´c IV
24/24