Registrovaný: 05 Mar 2015, 18:22 Príspevky: 17 Udelené body:3 bodov Získané body:8 bodov
Zdravím, narazil som na ďalšiu úlohu, ktorá mi prišla zaujímavá, tak som sa rozhodol ju sem pridať. Zadanie úlohy:
Spoiler:
Citácia:
Bolo raz jedno KSP alebo tiež Klebetná Spoločnosť Programátorov. Ako iste vieš, KSP už má svoje roky, takže nepozná každý každého. Ak sa ale niekto dozvie nejakú klebetu, ihneď ju vedia aj všetci, ktorých tento človek pozná. Naša databáza presne vie, kto koho pozná. My by sme radi vedeli, či sa klebeta dokáže rozšíriť po celom KSP.
Vstup
Na prvom riadku vstupu sa nachádza jedno prirodzené číslo N (1 ≤ N ≤ 100) – počet KSPákov. Ďalších N riadkov obsahuje mená KSPákov. Každé meno je reťazec veľkých a malých písmen anglickej abecedy, dĺžky mien sú medzi 1 a 20 vrátane. V nasledujúcom riadku je jedno celé číslo M – počet známostí v KSP. Nasleduje M riadkov. V každom z týchto riadkov sú uvedené mená dvoch KSPákov, ktorí sa navzájom poznajú. Medzi menami je práve 1 medzera. Môžete predpokladať, že každá dvojica ľudí sa v tomto zozname vyskytuje najviac raz.
Výstup
Tvoj program by mal vypísať jediný riadok obsahujúci slovo "ANO", ak sa každá klebeta rozšíri po celom KSP, alebo "NIE", ak tomu tak nie je.
Príklad
vstup
Citácia:
5 Julka Misof Monika Palo YoYo 4 Julka YoYo YoYo Misof Misof Julka Palo Monika výstup NIE
Citácia:
vstup 5 Julka Misof Monika Palo YoYo 5 Julka YoYo YoYo Misof Misof Julka Palo Monika Misof Monika výstup ANO
Vysvetlenie
V prvom príklade vstupu a výstupu sa klebety, ktoré vie Julka, k Paľovi a Monike nijako nedostanú, preto je odpoveď NIE.
Prikladám aj svoj kód(taktiež v prílohe), ktorý danú úlohu rieši:
Spoiler:
Kód:
/**Vyuzivam algoritmus rýchleho hľadania**/
#include<stdio.h> int main() { int i,j = 0,m,n,t,p,q,r,s,pocet = 0; scanf("%d",&n); //pocet zadanych mien char meno[n][21],meno1[21],meno2[21]; //dvojrozmerne pole pre zadanie vsetkych mien, jednorozmerne polia pre jednotlive mena,ktore sa maju pospajat int id[n],sz[n]; //pomocne pole, ktore naplnim jednotkami for(i = 0; i < n; i++){ id[i] = i; sz[i] = 1; } for(i = 0; i < n; i++){ scanf("%s",meno[j++]); } scanf("%d",&m); //pocet znamosti for(i = 0; i < m; i++){ scanf("%s %s",meno1, meno2); //do poli nacitam obe mena for(j = 0; j < n; j++){ //pre kazde meno priradim ciselnu hodnotu, ktora sa rovna riadku, v ktorom sa v dvojrozmernom poli nachadzaju int pomoc1 = strcmp(meno1,meno[j]); //porovnavanie poli if(pomoc1 == 0) p = j; //ked su rovnake, priradim hodnotu int pomoc2 = strcmp(meno2,meno[j]); if(pomoc2 == 0) q = j; } for(r = p; r != id[r]; r = id[r]) id[r] = id[id[r]]; for(s = q; s != id[s]; s = id[s]) id[s] = id[id[s]]; if(r == s) //pole vyuzivam, lebo ma vlastnost, ze id[p] a id[q] sa rovanjú len vtedy, keď je p a q prepojene, takze ak su prepojene, nepokracujem dalej continue; if(sz[r] < sz[s]){ id[r] = s; sz[s] +=sz[r]; } else{ id[s] = r; sz[r] += sz[s]; } pocet++; //pocitam, kolko spojeni sa vykonalo } if(pocet == n-1) //ak sa vykonalo n-1 spojeni, klebetu pozna kazdy printf("ANO\n"); else printf("NIE\n"); return 0; }
Registrovaný: 06 Jan 2012, 19:26 Príspevky: 458 Bydlisko: pod Pátrovom Udelené body:228 bodov Získané body:21 bodov
@alim97, myslím, že už je na čase, aby si začal používať dynamickú alokáciu, pointery a modulárne (funkcionálne) programovanie. Čo ty na to?
_________________ kódy píšem na platforme: linux Ubuntu 12.04 (Geany, Code::Blocks), WinXP (Code::Blocks, PsPad editor), Skype: libcokamo, ICQ: 56312279 Ak treba, napíš mi na libcosenior@gmail.com. To mám v mobile a stále po ruke.
/** Vytvori dynamicky prazdne pole retazcov o zadanom pocte prvkov * @param int pocet prvkov pola * @param int maximalna velkost retazca * @return pointer na pole pointerov */ char** vytvor_pole_pointerov(const int pocet_prvkov, const int velkost_retazca);
/** Uvolni pamat pola pointerov * @param pointer na pole * @param int pocet prvkov pola * return void */ void uvolni_pole_pointerov(char **p_pole, const int pocet_prvkov);
/** Vytvori dynamicky retazec a vrati ho * @param pointer na string * @return pointer na string */ char* vytvor_retazec(char *p_zdroj);
/** Naplni pole zadanym poctom retazcov * @param int pocet prvkov pola * @param pointer na pole stringov (vstupno-vystupny parameter) * @return void */ void napln_pole_stringov(const int pocet_prvkov, char **p_pole);
#endif // DATABAZA_H_INCLUDED
databaza.c
Spoiler:
Kód:
#include "databaza.h" //#define TESTY // zakomentovaním sa testy odstavia
char** vytvor_pole_pointerov(const int pocet_prvkov, const int velkost_retazca) { }
void uvolni_pole_pointerov(char **p_pole, const int pocet_prvkov) { }
char* vytvor_retazec(char *p_zdroj) { }
void napln_pole_stringov(const int pocet_prvkov, char **p_pole) { }
#ifdef TESTY #define POCET_PRVKOV 5 // Jano, Ivan, Miro, Jozef, Jana int main(void) { char **jednotlivci, **dvojice;
jednotlivci = vytvor_pole_pointerov(5); dvojice = vytvor_pole_pointerov(5);
// Test funkcie vytvor_retazec() char buffer[] = "Popokatepetl"; assert(strlen(vytvor_retazec(buffer)) == 12); printf("Test funkcie vytvor_retazec() presiel.\n");
// Test funkcie napln_pole_stringov() printf("\nZadaj po jednom retazce Jano, Ivan, Miro, Jozef, Jana a kazdy odentruj.\n"); napln_pole_stringov(POCET_PRVKOV, jednotlivci); assert(strcmp(jednotlivci[1], "Ivan") == 0); assert(strcmp(jednotlivci[4], "Jana") == 0); printf("\nZadaj po jednom retazce Jano Ivan, Jano Miro, Jozef Jana, Jana Ivan, Jozef Jano a kazdy odentruj.\n"); napln_pole_stringov(POCET_PRVKOV, dvojice); assert(strcmp(dvojice[1], "Jano Miro") == 0); assert(strcmp(dvojice[4], "Jozef Jano") == 0); printf("Tesy funkcie napln_pole_stringov() presli.\n");
/** Zisti ci je prepojenie medzi vsetkymi menami, * teda ked sa da informacia jednemu z nich, ci sa dostane ku kazdemu * @param pointer na pole jednotlivych mien * @param pointer na pole dvojic mien * @return int 1 alebo 0 v true / false */ int porovnaj(char **jednotlivci, char **dvojice);
#endif // POROVNANIE_H_INCLUDED
porovnanie.c
Spoiler:
Kód:
#include "porovnanie.h" //#define TESTY // zakomentovaním sa testy odstavia
int porovnaj(char **jednotlivci, char **dvojice) { }
#ifdef TESTY int main(void) { char **jednotlivci, **dvojice_ok, **dvojice_nok, **dvojice_ok4;
V header súboroch sú popisy jednotlivých funkcií vrátane funkčných prototypov. V source súboroch sú len názvy funkcií a testy funkcií. Aby si mohol testovať, treba odkomentovať riadok //#define TESTY // zakomentovaním sa testy odstavia Začať treba s modulom databaza. Ak sa ti bude chcieť, toto je najlepší spôsob programovania. Samozrejme treba vedieť tie testovacie časti aj napísať. To znamená, že problém treba rozdeliť na malé časti, na tie vymyslieť funkcie a mať prestavu, aké vstupy do nich a výstupy z nich použiť pri testoch. Čím viac rôznych testov prejde v poriadku, tým je menšia pravdepodobnosť chyby v programe. Nie je to ešte úplné, chýba tam modul behu celého programu(napr. priebeh.h a priebeh.c) a súbor main.c.
Ešte doplním, že do modulu porovnanie bude dobré pridať niekolko ďalších funkcií, aby tá jedna nebola špagety kód.
_________________ kódy píšem na platforme: linux Ubuntu 12.04 (Geany, Code::Blocks), WinXP (Code::Blocks, PsPad editor), Skype: libcokamo, ICQ: 56312279 Ak treba, napíš mi na libcosenior@gmail.com. To mám v mobile a stále po ruke.
Registrovaný: 06 Jan 2012, 19:26 Príspevky: 458 Bydlisko: pod Pátrovom Udelené body:228 bodov Získané body:21 bodov
Skontroluj si tie testy, či tam náhodou nie je nejaká chyba. Aj to sa môže stať, že pri programovaní na to prídem.
_________________ kódy píšem na platforme: linux Ubuntu 12.04 (Geany, Code::Blocks), WinXP (Code::Blocks, PsPad editor), Skype: libcokamo, ICQ: 56312279 Ak treba, napíš mi na libcosenior@gmail.com. To mám v mobile a stále po ruke.
Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 2 hostia
Nemôžete zakladať nové témy v tomto fóre Nemôžete odpovedať na témy v tomto fóre Nemôžete upravovať svoje príspevky v tomto fóre Nemôžete mazať svoje príspevky v tomto fóre Nemôžete zasielať súbory v tomto fóre
Prihlásenie
Registrovať
Návody
Hľadať
Zoznam bodov
