Difference between revisions of "LU-LSP-b13:L01"
(→Par simbolu virkņu meklēšanu) |
|||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
== Praktiskais darbs #1 == |
== Praktiskais darbs #1 == |
||
Darbs ir paredzēts, lai iepazītos Linux kā izstrādes un testēšanas vidi, un atkārtotu C programmēšanas pamatus. |
Darbs ir paredzēts, lai iepazītos ar Linux kā izstrādes un testēšanas vidi, un atkārtotu C programmēšanas pamatus. |
||
Darbu jāiesniedz Github Classroom laboratorijas darbu repozitorijā. Ielūguma links e-studijās. Faila nosaukums LSP_PD1_vards_uzvards.c |
|||
⚫ | |||
⚫ | |||
=== Uzdevumi === |
=== Uzdevumi === |
||
Line 20: | Line 22: | ||
* Piemērs: "abcd" -> "dcba" |
* Piemērs: "abcd" -> "dcba" |
||
* Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma! |
* Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma! |
||
5. ( |
5. (Neobligāts) Uzrakstīt funkciju ''void sv_vapgriezt(char *virkne)'', kas apgriež vārdus simbolu virknē |
||
* Piemērs: "hello world" -> "world hello" |
* Piemērs: "hello world" -> "world hello" |
||
* Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no |
* Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma! |
||
=== Papildinformācija === |
=== Papildinformācija === |
||
Line 104: | Line 105: | ||
Piezīme. Iepriekš jau atrisinātos uzdevumus drīkst izmantot tālāko uzdevumu risināšanai. Piemēram, uzdevumu 2.-5. risinājumos drīkst izmantot funkcijas <code>sv_garums</code> izsaukumu. |
Piezīme. Iepriekš jau atrisinātos uzdevumus drīkst izmantot tālāko uzdevumu risināšanai. Piemēram, uzdevumu 2.-5. risinājumos drīkst izmantot funkcijas <code>sv_garums</code> izsaukumu. |
||
=== Par strlen veiktspēju === |
|||
Vai Jūsu garuma funkcija strādā tik pat ātri kā GLibC strlen funkcija? |
|||
Interesei te ir: |
|||
* [https://elixir.bootlin.com/glibc/glibc-2.17/source/string/strlen.c GlibC strlen implementācija], |
|||
* un [https://www.eevblog.com/forum/programming/which-strlen-function-is-faster/ dažādu strlen implementāciju veiktspējas salīdzinājums] |
|||
=== Par simbolu virkņu meklēšanu === |
|||
Ir [https://en.wikipedia.org/wiki/String-searching_algorithm vairāki viltīgi algoritmi], |
|||
kas atšķiras no naivā meklēšanas algoritma ar labāku veiktspēju. |
|||
Piemēram, [https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm Boyer-Moore algoritms], kas meklē no otra gala un lec uz priekšu pa vairākiem burtiem, ja iespējams. |
Latest revision as of 15:02, 8 February 2024
Contents
Praktiskais darbs #1
Darbs ir paredzēts, lai iepazītos ar Linux kā izstrādes un testēšanas vidi, un atkārtotu C programmēšanas pamatus.
Darbu jāiesniedz Github Classroom laboratorijas darbu repozitorijā. Ielūguma links e-studijās. Faila nosaukums LSP_PD1_vards_uzvards.c
Beigās risinājumi tiek apskatīti kopīgi, pārrunājot risināšanas gaitu.
Uzdevumi
1. Uzrakstīt funkciju int sv_garums(char *virkne), kas atrod simbolu virknes garumu
- Šeit un turpmāk var pieņemt, ka simbolu virknes korekti beidzas ar nulles simbolu (C kodā pierakstāms kā '\0', vai arī vienkārši 0)
2. Uzrakstīt funkciju void sv_kopet(char *no, char *uz), kas nokopē simbolu virkni
- Var pieņemt, ka vietas pietiks.
- Izaicinājums – neizmantot papildus mainīgos!
3. Uzrakstīt funkciju int sv_meklet(char *kur, char *ko)
- Funkcija sameklē un atgriež simbolu skaitu no virknes "kur" sākuma līdz vietai, kur tajā pirmoreiz atrodama virkne "ko"
- Ja "ko" nav atrodams virknē "kur", tad atgriež -1
- sv_meklet("to be or not to be", "be") -> 3
- sv_meklet("something else", "be") -> -1
4. Uzrakstīt funkciju void sv_apgriezt(char *virkne), kas apgriež simbolu virkni.
- Piemērs: "abcd" -> "dcba"
- Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma!
5. (Neobligāts) Uzrakstīt funkciju void sv_vapgriezt(char *virkne), kas apgriež vārdus simbolu virknē
- Piemērs: "hello world" -> "world hello"
- Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma!
Papildinformācija
Risinājums rakstīt vienā vai vairākos C pirmkoda failos.
Risinājumus pārbaudīt, uzbūvējot bināro failu izmantojot GCC kompilatoru, un testējot ar saviem izdomātiem testa piemēriem.
Piemēram, ja risinājums un testa piemēri ir aprakstīti failā pd1.c, var rīkoties šādi:
Pirmkārt, uzbūvējam pd1 izpildāmo failu:
$ gcc pd1.c -o pd1
Otrkārt, palaižam pd1 izpildāmo failu:
$ ./pd1
Faila pd1.c šablons:
#include <stdio.h> int sv_garums(char *virkne) { // ... // TODO: PD1.1 kodu rakstīt te! // ... } void sv_kopet(char *no, char *uz) { // ... // TODO: PD1.2 kodu rakstīt te! // ... } int sv_meklet(char *kur, char *ko) { // ... // TODO: PD1.3 kodu rakstīt te! // ... } void sv_apgriezt(char *virkne) { // ... // TODO: PD1.4 kodu rakstīt te! // ... } void sv_vapgriezt(char *virkne) { // ... // TODO: PD1.5 kodu rakstīt te! // ... } int main(void) { char buferis[100]; printf("Tests uzdevumam PD1.1:\n"); printf("%d\n", sv_garums("hello world")); printf("%d\n", sv_garums("123")); printf("%d\n", sv_garums("")); printf("Tests uzdevumam PD1.2:\n"); // ... // TODO: PD1 testu kodu rakstīt te! // ... // Uzdevumus 4. un 5. testēt šādā veidā, lai izvairītos no access violation! // sv_kopet("abcd", buferis); // sv_apgriezt(buferis); // printf("%s\n", buferis); return 0; }
Piezīme. Iepriekš jau atrisinātos uzdevumus drīkst izmantot tālāko uzdevumu risināšanai. Piemēram, uzdevumu 2.-5. risinājumos drīkst izmantot funkcijas sv_garums
izsaukumu.
Par strlen veiktspēju
Vai Jūsu garuma funkcija strādā tik pat ātri kā GLibC strlen funkcija?
Interesei te ir:
Par simbolu virkņu meklēšanu
Ir vairāki viltīgi algoritmi, kas atšķiras no naivā meklēšanas algoritma ar labāku veiktspēju.
Piemēram, Boyer-Moore algoritms, kas meklē no otra gala un lec uz priekšu pa vairākiem burtiem, ja iespējams.