Škôlka jazyka C

Fórum o programovaní v jazyku C založené 3. januára 2012

Aktuálny čas je 19 Nov 2019, 12:06

Všetky časy sú v GMT + 1 hodina




Vytvoriť novú tému Odpovedať na tému  [ Príspevkov: 5 ] 
Autor Správa
 Predmet príspevku: Klebety(Liahen ksp)
PoslaťNapísal: 30 Mar 2015, 20:24 
Offline
Školák
Školák

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


Prílohy:
Klebety.c [1.77 KiB]
139 krát
Detaily príspevku Upozorniť užívateľa
Hore
 Profil  
 
 Predmet príspevku: Re: Klebety(Liahen ksp)
PoslaťNapísal: 31 Mar 2015, 06:01 
Offline
Stredoškolák
Stredoškolák
Obrázok užívateľa

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.


Detaily príspevku Upozorniť užívateľa
Hore
 Profil  
 
 Predmet príspevku: Re: Klebety(Liahen ksp)
PoslaťNapísal: 31 Mar 2015, 11:55 
Offline
Stredoškolák
Stredoškolák
Obrázok užívateľa

Registrovaný: 06 Jan 2012, 19:26
Príspevky: 458
Bydlisko: pod Pátrovom
Udelené body: 228 bodov
Získané body: 21 bodov
Pripravil som ti podklady na testami riadený vývoj systémom Black-box Testing:
databaza.h
Spoiler:
Kód:
#ifndef DATABAZA_H_INCLUDED
#define DATABAZA_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/** 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");

    free(jednotlivci);
    free(dvojice);

    return 0;
}
#endif

porovnanie.h
Spoiler:
Kód:
#ifndef POROVNANIE_H_INCLUDED
#define POROVNANIE_H_INCLUDED
#include "databaza.h"

/** 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;

    jednotlivci = vytvor_pole_pointerov(5, 21);
    strcpy(jednotlivci[0], "Julka");
    strcpy(jednotlivci[1], "Misof");
    strcpy(jednotlivci[2], "Monika");
    strcpy(jednotlivci[3], "Palo");
    strcpy(jednotlivci[4], "YoYo");
    dvojice_ok = vytvor_pole_pointerov(5, 41);
    strcpy(dvojice_ok[0], "Julka YoYo");
    strcpy(dvojice_ok[1], "YoYo Misof");
    strcpy(dvojice_ok[2], "Misof Julka");
    strcpy(dvojice_ok[3], "Palo Monika");
    strcpy(dvojice_ok[4], "Misof Monika");
    dvojice_nok = vytvor_pole_pointerov(4, 41);
    strcpy(dvojice_nok[0], "Julka YoYo");
    strcpy(dvojice_nok[1], "YoYo Misof");
    strcpy(dvojice_nok[2], "Misof Julka");
    strcpy(dvojice_nok[3], "Palo Monika");
    dvojice_ok4 = vytvor_pole_pointerov(4, 41);
    strcpy(dvojice_ok4[0], "Julka Misof");
    strcpy(dvojice_ok4[1], "Misof Monika");
    strcpy(dvojice_ok4[2], "Monika Palo");
    strcpy(dvojice_ok4[3], "Palo YoYo");

    assert(porovnaj(jednotlivci, dvojice_ok) == 1);
    assert(porovnaj(jednotlivci, dvojice_nok) == 0);
    assert(porovnaj(jednotlivci, dvojice_ok4) == 1);
    printf("Testy funkcie porovnaj() presli.\n");

    uvolni_pole_pointerov(jednotlivci, 5);
    uvolni_pole_pointerov(dvojice_ok, 5);
    uvolni_pole_pointerov(dvojice_nok, 4);
    uvolni_pole_pointerov(dvojice_ok4, 4);

    return 0;
}
#endif


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.


Detaily príspevku Upozorniť užívateľa
Hore
 Profil  
 
 Predmet príspevku: Re: Klebety(Liahen ksp)
PoslaťNapísal: 31 Mar 2015, 16:48 
Offline
Školák
Školák

Registrovaný: 05 Mar 2015, 18:22
Príspevky: 17
Udelené body: 3 bodov
Získané body: 8 bodov
vďaka, pozriem to


Detaily príspevku Upozorniť užívateľa
Hore
 Profil  
 
 Predmet príspevku: Re: Klebety(Liahen ksp)
PoslaťNapísal: 31 Mar 2015, 16:59 
Offline
Stredoškolák
Stredoškolák
Obrázok užívateľa

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.


Detaily príspevku Upozorniť užívateľa
Hore
 Profil  
 
Zobraziť príspevky z predchádzajúceho:  Zoradiť podľa  
Vytvoriť novú tému Odpovedať na tému  [ Príspevkov: 5 ] 

Všetky časy sú v GMT + 1 hodina


Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 2 hostia


Rýchla úprava:
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

Hľadať:
Skočiť na:  
cron
Powered by phpBB® Forum Software © phpBB Group

Hosted by FreeSpace SK