zapocet 9. 6.

Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

zapocet 9. 6.

Příspěvek od Lukas Mach »

Meli jsme, myslim, celkem snadnou ulohy, rozhodne nejake slevani databazi, ktere tu nekdo posilal minule, mi pripadalo tezsi. Takze, u nas byl zadan orientovany graf:

Kód: Vybrat vše

uzel1:uzel2,uzel5
uzel2:uzel3
uzel3:uzel1
uzel4:
uzel5:uzel1
Na kazde radku je definovan jeden vrchol a za dvojteckou pak vrcholy, kam vede z toho prvniho orientovana hrana. Program mel stejnym zpusobem vypsat doplnek tohoto grafu (tj. vsechny hrany, co tam nejsou).

Pak tam mely byt nejake parametry z prikazove radky, vstup bud ze stdin nebo ze souboru, vystup to melo umet vypsat bud na stdout nebo do souboru (to neni vyber, program mel umet oboje). Nicmene mne to cteni parametru nekontroloval, takze zpetne si myslim, ze je asi lepsi si tyhle rutinni zalezitosti nechat az nakonec.

Cas na to byl 2,5 hodiny, pak to bylo jeste prodlouzeno. Kolik lidi to dalo nevim.

Reseni je asi jasny, jen je nutny dat si pozor na par veci.

Pokud to delat v C++, tak vam tam mozna Microsoft Visual Studio vnuti tuhle hlavicku funkci:

Kód: Vybrat vše

int _tmain(int argc, _TCHAR* argv[])
Je nutne to zmenit na

int main(int argc, char* argv[])

Protoze jinak to bude posilat parametry z prikazovy radky zakodovany v (patrne) Unicode a nebude to UTF-8, takze to neni zpetne kompatibilni se 7-bit ASCII. Cili kdyz se podivate na retezec *argv, tak bude mit jen jeden znak, protoze hned ten druhy je \0 (to unicode dela). Ja o tom nevedel az do vcerejska vecer, protoze sem se nikdy s parametrama na prikazovy radce neotravoval, kdybych se s tim babral behem zapoctu, urcite bych to neudelal.

Pak mi taky pripada fajn neotravovat se se spojovyma seznamama a pokud to jde, pouzit dynamicky realokovane pole. Tj. mit nasledujici funkci (ktera je bez zaruky, mozna je v ni nejaka pekelna chyba, ale uz dva cvicici mi ji uznaly):

(ta funkce je tu i s examplem a ve skutecnosti je fakt kratka; jo a ten zdrojak je striktne receno v C++)

Kód: Vybrat vše

// grow.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>

// zavolanim tehle funkce rikam programu "mam pole p, s poctem prvku count, velikost 
// polozek je element_size a chtel bych zapisovat do p[index], ocheckuj mi to a pripadne 
// to pole realokuj na dvojnasobnou velikost"

void * grow(void * p, size_t index, size_t * count, int element_size)
{
	if (index < *count)
	{
		// vsechno dobre
		if (index < 0)
		{
			// pretekli jsme
			abort(); 
			return NULL; // asi zbytecny, ale jinak z toho je warning
		}
		else
		{
			// ok
			return p;
		}
	}
	else
	{
		// zdvojnasobime velikost pole
		void * q; 

		if (*count == 0) 
		{
			*count = 4;
		}
		else
		{
			*count *= 2;
		}

		// realokujeme
		if (NULL == (q = realloc(p, *count * element_size)))
		{
			// dosla pamet
			abort(); 
			return NULL; 
		}
		else
		{
			// zatim dobry, zavolame se rekurzivne a osetrime tak stav, 
			// kdy je nutne pole zvetsit jeste vic nez dvakrat
			p = q; 
			return grow(p, index, count, element_size);
		}
	}
}


int main(int argc, char * argv[])
{
	int * pole = NULL; // to NULL tam velmi nutne MUSI byt!
	size_t velikost_pole = 0; // rovnez dobre inicializovat na 0

	// chceme zapsat do pole[100], pred kazdym takovym zapisem zavolame:
	pole = (int *)grow(pole, 100, &velikost_pole, sizeof(int));

	// a uz se nemusime o nic starat, samo se to realokovalo (pokud to bylo nutne)
	pole[100] = 12345;
	printf("To cislo je %d
", pole[100]);

	// jeste
	pole = (int *)grow(pole, 2500, &velikost_pole, sizeof(int));
	pole[2500] = 172;
	printf("Jine cislo je %d
", pole[2500]);

	// konec
	free(pole);
	fgetc(stdin);
	return 0;
}
S ni je pak prace se dynamickym polem dost jednodussi (pokud clovek teda nemuze pouzivat ty vymozenosti knihoven C++), proste kdyz chci pouzit pole, tak pred to napisu:

pole = (int *)grow(pole, i, &velikost_pole, sizeof(int));

A muzu to pouzit na delani poli cehokoliv...
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Jo a ta podminka if (index < 0) tam byt nemusi, protoze je vzdycky nesplnena (size_t je unsigned, myslim). Ja ji tam mam jen pro pripad, ze by me nekdy napadlo size_t zmenit na int.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
Zdeněk Vilušínský
Matfyz(ák|ačka) level III
Příspěvky: 110
Registrován: 16. 1. 2006 22:04
Typ studia: Informatika Bc.
Bydliště: Železný Brod/Troja A1923
Kontaktovat uživatele:

Příspěvek od Zdeněk Vilušínský »

Tak to jste měli o dost jednodušší, než my den předtím.. Já bych tohle řešil třeba přes dynamicky alokovanou matici sousednosti a pak ji znegoval.
Věda je jako sex. Jistěže má nějaké praktické výsledky, ale proto ji přece neděláme. - R.P.Feynman

I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Fakt by mi dost pomohlo, kdyby nekdo vedel, jak se jmenuje cvicici, ktery tuhle zkousku (9. 6.) vedl. Protoze pred nim mi nekdo do grupicku napsal nejaky nesmysl do kolonky Test 1, takze on mi tam pak uz nic pochopitelne nenapsal.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
eVe
Matfyz(ák|ačka) level I
Příspěvky: 43
Registrován: 11. 2. 2006 11:49
Typ studia: Informatika Bc.
Bydliště: B1405
Kontaktovat uživatele:

Příspěvek od eVe »

Lukas Mach píše:Fakt by mi dost pomohlo, kdyby nekdo vedel, jak se jmenuje cvicici, ktery tuhle zkousku (9. 6.) vedl. Protoze pred nim mi nekdo do grupicku napsal nejaky nesmysl do kolonky Test 1, takze on mi tam pak uz nic pochopitelne nenapsal.
Jiri Dokulil..
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Diky, je to on. Doufam, ze jim tam nekde jeste lezi ten papir, na kterym je napsany, ze sem to udelal.
For every epsilon, there is delta.
Where is my delta?
Odpovědět

Zpět na „2005“