Forum@DeGiorgi :: Pogledajte temu

through

[^/[Print]\]
Idite na Prethodno 1, 2, 3, 4, 5, 6, 7, 8 Sljedeće :| |:
Forum@DeGiorgi -> Strukture podataka i algoritmi

#101: Autor/ica: dalmatinčica,

Postano: 19:18 uto, 8. 1. 2013
—
pozdrav,
imam problem sa zadatkom iz 2. zadaće

Napišite program koji će učitati dva stringa duljine max. 100. Ti stringovi predstavljaju zapise prirodnih brojeva x i y u bazi 10. Program treba te brojeve pretvoriti u binarne brojeve i treba pomoću algoritma za množenje n-bitnih brojeva izračunati x · y. Rezultat korisniku vratite u dekadskom obliku.

Ulazni podaci: dva stringa duljine max. 100.
Izlazni podaci: brojevi x i y u bazi 2, te njihov umnožak u bazi 2 i u bazi 10.
Na primjer, za ulazne podatke:
1099511627776 3
treba ispisati:
x u bazi 2: 10000000000000000000000000000000000000000
y u bazi 2: 11
x*y u bazi 2: 110000000000000000000000000000000000000000
x*y u bazi 10: 3298534883328

problem je što ga neznam riješiti.
pa ako ima neka dobra duša koja ima kakvu pametnu ideju da barem natukne kako bi se ovaj zadatak rješavao.
pokušavala sam ja ispisivati nekakve funkcije za potrebne operacije, ali se uvijek zapetljam i shvatim da zapravo nemogu tako riješiti...
hvala unaprijed
Very Happy

edit:
barem ideja za ovo zadnje, pretvaranje oakvog velikog binarnog broja u dekadski

#102: Autor/ica: Ryssa,

Postano: 16:01 ned, 13. 1. 2013
—
Zna li netko kako je najlakše učitavati m sortiranih listi(veze pomoću kursora) i pamtiti koji je element iz koje liste?

#103: Autor/ica: linus, Lokacija: subnet mask

Postano: 15:44 sri, 16. 1. 2013
—
Nije mi jasan zadatak
Osmislite algoritam i napišite odgovarajući program za sortiranje m vektora oblika: [tex]X^{(r)}=(x_1^{(r)},...,x_n^{(r)}), r=1,..,m.[/tex]
Dal su ovi brojevi u eksponentu potencija ili indeks pojedinog vektora/elementa?

mozda je glupo pitanje, ali nisam siguran jer svaka koordinata ima index dolje zapisan

#104: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 16:32 sri, 16. 1. 2013
—
Gornji index znaci "koji" (od [tex]m[/tex]) vektora; donji oznacava koja je to komponenta tog vektora. Ponekad se tako oznacava da se izbjegne konfuzija izmedju razlicitih indexa (jednog za vektor i drugi za element), recimo, da ne izgleda kao da je u igri matrica (sto bi se desilo da su oba indexa dolje).

#105: Autor/ica: aj_ca_volin_te,

Postano: 18:15 sri, 16. 1. 2013
—
moze mi itko ukazati na pogresku, problem je u tome sto mi u rijecnik ne unose ove rijeci iz maina, a kada ih unosim preko funkcije ''dodatno ucitavanje'' unose se bez problema Ehm?

Kod:

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

#define B 1000
#define EMPTY "0"
#define DELETED "-1"

typedef char elementtype[21];
typedef elementtype DICTIONARY[B];

void MAKE_NULL (DICTIONARY *Ap){
int i;
for(i=0; i<B; i++) strcpy((*Ap)[i],EMPTY);
}

int h(elementtype x){
int i, sum=0;
for(i=0;i<20;i++) sum += x'[i]';
return sum%B;
}

int locate(elementtype x, DICTIONARY A){
int initail, i;
initail=h(x);
i=0;
while((i<B) && strcmp(A[(initail+i)%B],x)!=0 && strcmp(A[(initail+i)%B],EMPTY)!=0) ++i;

return ((initail+i)%B);
}

int locate1(elementtype x, DICTIONARY A){
int initail, i;
initail=h(x);
i=0;
while( (i<B) && strcmp(A[(initail+i)%B],x)!=0 && strcmp(A[(initail+i)%B],EMPTY)!=0 && strcmp(A[(initail+i)%B],DELETED)!=0) ++i;

return ((initail+i)%B);
}

int MEMBER(elementtype x, DICTIONARY A)
{
if(strcmp(A[locate(x,A)],x)==0) return 1;

else return 0;
}

void INSERT(elementtype x, DICTIONARY *Ap)
{
int bucket;
if(MEMBER(x,*Ap)) return;
bucket = locate1(x,*Ap);
if(strcmp((*Ap)[bucket],EMPTY)==0 || strcmp((*Ap)[bucket],DELETED)==0){
strcpy((*Ap)[bucket],x);
}
else{
printf("error-table is full");
exit(1);
}

}

void DELETE(elementtype x, DICTIONARY *Ap)
{
int bucket;
bucket=locate(x,*Ap);
if(strcmp((*Ap)[bucket],x)==0) strcpy((*Ap)[bucket], DELETED);
}

void dodatno_ucitavanje(DICTIONARY *A){

while(1){

elementtype operacija, string;

scanf("%s", operacija);
scanf("%s", string);

if(strcmp(operacija,"UNESI")==0){
INSERT(string,A);
}
else if(strcmp(operacija,"OBRISI")==0){
DELETE(string,A);
}
else if(strcmp(operacija,"JELICLAN")==0){
if(MEMBER(string,*A)){
printf("%s: DA!\n", string);
}
else{
printf("%s: NE!\n", string);
}
}
else break;
}
}

int main(void)
{

DICTIONARY A;

MAKE_NULL(&A);

INSERT("auto",&A); INSERT("break",&A); INSERT("case",&A) ;INSERT("char",&A); INSERT("const",&A) ;INSERT ("continue",&A);
INSERT("do",&A); INSERT("double",&A) ;INSERT("default",&A); INSERT("else",&A); INSERT("enum",&A); INSERT("extern",&A); INSERT("float", &A);
INSERT("for",&A); INSERT("goto",&A); INSERT("if",&A); INSERT("int",&A); INSERT("long",&A); INSERT("register",&A);INSERT("return",&A);INSERT("short",&A);INSERT ("signed", &A);INSERT ("sizeof", &A);INSERT ("static", &A);
INSERT("struct",&A);INSERT("switch",&A);INSERT("typedef",&A);INSERT("union",&A);INSERT("void",&A);INSERT("volatile",&A);
INSERT("while",&A);

dodatno_ucitavanje(&A);

return 0;
}

NETREBA HVALA, RIJESENO! ispraviti cu gore u implementaciji pa ako ikome bude trebala neka ima Very Happy

Zadnja promjena: aj_ca_volin_te; 22:36 sri, 16. 1. 2013; ukupno mijenjano 1 put.

#106: BST pomoću polja Autor/ica: malenaa,

Postano: 18:44 sri, 16. 1. 2013
—
Zapela sam na implementaciji binarnog stabla traženja pomoću polja (u zadatku je riječnik tako implementiran), točnije na funkciji DELETE. Naime, nikako ne mogu zaključiti kako pomicati čvorove kada se neki čvor nadomješta svojim djetetom. U tu svrhu sam napisala funkciju PREPISI, međutim mislim nije točna jer neki onda nestanu, a koji ne bi trebali. Može li mi netko pomoći?

Kod:

void PREPISI (int i, int j, DICTIONARY *Dp) {
strcpy(Dp->elements[i], Dp->elements[j]);
if (2*j+1 < MAXSIZE) PREPISI (2*i+1, 2*j+1, Dp);
else if (2*j+2 < MAXSIZE) PREPISI (2*i+2, 2*j+2, Dp);

}

void DELETE (elementtype x, DICTIONARY *Dp)
{
int i=0, j;
//trazimo x
while ( i < MAXSIZE )
{
if ( strcmp(Dp->elements[i], x) == 0 ) break;
else if ( strcmp(Dp->elements[i], x) > 0) i=2*i+1;
else i=2*i+2;
}

if ( i < MAXSIZE )
{
//x je u listu
if ( ((strcmp(Dp->elements[2*i+1], "PRAZNO") == 0) || (2*i+1 >= MAXSIZE)) && ((strcmp(Dp->elements[2*i+2], "PRAZNO") == 0) || (2*i+2 >= MAXSIZE)) )
{
strcpy(Dp->elements[i], "PRAZNO");

}

//x ima samo desno dijete
else if ((strcmp(Dp->elements[2*i+1], "PRAZNO") == 0) || (2*i+1 >= MAXSIZE))
PREPISI(i, 2*i+2, Dp);

//x ima samo lijevo dijete
else if ((strcmp(Dp->elements[2*i+2], "PRAZNO") == 0) || (2*i+2 >= MAXSIZE))
PREPISI(i, 2*i+1, Dp);

//x ima oba djeteta
else
{
elementtype y = OBRISI_NAJMANJI(2*i+2, Dp); //brisemo najmanji cvor iz desnog podstabla
strcpy(Dp->elements[i], y);
}
}
if ( i > MAXSIZE ) printf("\nNema %s u rijecniku.\n", x);

}

elementtype OBRISI_NAJMANJI (int i, DICTIONARY *Dp)
{
elementtype mini;
elementtype brisi;

if ((strcmp(Dp->elements[2*i+1], "PRAZNO") == 0) || (2*i+1 >= MAXSIZE)) //i je najmanji
{
strcpy (mini,Dp->elements[i]);
if((strcmp(Dp->elements[2*i+2], "PRAZNO") != 0) && (2*i+2 < MAXSIZE)) //i ima desno dijete
PREPISI(i, 2*i+2, Dp);

else if(((strcmp(Dp->elements[2*i+1], "PRAZNO") == 0) || (2*i+1 >= MAXSIZE)) && ((strcmp(Dp->elements[2*i+2], "PRAZNO") == 0) || (2*i+2 >= MAXSIZE))) //i je list
strcpy(Dp->elements[i], "PRAZNO");

}
//i ima lijevo dijete
else if((strcmp(Dp->elements[2*i+1], "PRAZNO") != 0) || (2*i+1 < MAXSIZE))
strcpy(mini, OBRISI_NAJMANJI(2*i+1, Dp));
return mini;
}

#107: Autor/ica: Gino, Lokacija: Pula

Postano: 20:19 sri, 16. 1. 2013
—
Puno bi pomoglo znati(=vidjeti kod) sto je DICTIONARY.

#108: Autor/ica: malenaa,

Postano: 20:53 sri, 16. 1. 2013
—
evo definicije:

Kod:

#define MAXSIZE 100 //najveci dopusteni broj rijeci
#define elementtype char*

typedef struct {
elementtype elements[MAXSIZE];
} DICTIONARY;

Dakle, radi se o atp DICTIONARY koji je implementiran pomoću binarnog stabla trazenja, gdje je binarno stablo prikazano pomocu polja. Funkcija koja mi je "problematična" za napisati je funkcija DELETE (gore navedena u kodu). Ja sam za tu implementaciju iskoristila prikaz potpunog binarnog stabla pomoću polja tj lijevo dijete čvora i je 2*i+1, a desno 2*i+2. Dok sam one čvorove koji ne sadrže oznaku označila sa "PRAZNO"
U prilog sam stavila i cijeli kod ako je potreban.

Riječnik.c

Description:

Download

Filename:

Riječnik.c

Filesize:

6.64 KB

Downloaded:

290 Time(s)

#109: Autor/ica: Zenon, Lokacija: [tex]\pm\infty[/tex]

Postano: 4:10 čet, 17. 1. 2013
—
Može li mi itko reći zašto moja funkcija unesi_stablo ne unosi stablo pravilno? Ideja je da unese korijen pa njegovu djecu s desna na lijevo pa to isto za prvo, drugo, ... , nto dijete itd. Kod je ogroman, no ono što je relevantno za moje pitanje i nije. Inače, to je implementacija stabla preko polja uz vezu čvor → (roditelj, dijete, idući potomak). Unaprijed hvala!

Kod:

#include<stdio.h>

#define max 100

typedef int node;

typedef struct{
char label;
node mama, brat, sin;
}TREE;

node MAKE_ROOT(char l, TREE* tree){
node i;
tree->label = l;
tree->mama = -1;
tree->brat = -1;
tree->sin = -1;
for(i = 1; i < max; i++){
   (tree + i)->label = '\0';
   (tree + i)->mama = -1;
   (tree + i)->brat = -1;
   (tree + i)->sin = -1;
}

return 0;
}

node INSERT_CHILD(char l, node i, TREE* tree){
if(i >= max || tree->label == '\0') return -1;

node j;

for(j = 1; j < max; j++)
   if((tree + j)->label == '\0') break;

if(j >= max) return -1;

(tree + j)->label = l;
(tree + j)->mama = i;
(tree + j)->brat = (tree + i)->sin;
(tree + j)->sin = -1;

return j;
}

node INSERT_SIBLING(char l, node i, TREE* tree){
if(i >= max || tree->label == '\0' || i == 0) return -1;

node j, k;

for(j = 1; j < max; j++)
   if((tree + j)->label == '\0') break;

if(j >= max) return -1;

for(k = 1; k < max; k++)
   if((tree + k)->label == '\0') break;

if(k >= max) return -1;
(tree + j)->label = l;
(tree + j)->mama = (tree+i)->mama;
(tree + j)->brat = (tree + i)->brat;
(tree + i)->brat = j;
(tree + j)->sin = -1;

return j;
}

void DELETE(node i, TREE* tree){
if(i >= max || tree->label == '\0' || i == 0 || (tree + i)->sin != -1) return;

if((tree + i)->brat != -1){
   if((tree + (tree + i)->mama)->sin == i)(tree + (tree + i)->mama)->sin = (tree + i)->brat;

   else{
      node j;
      j == (tree + (tree + i)->mama)->sin;
      while((tree + j)->brat != i)
         j = (tree + j)->brat;

      (tree + j)->brat = (tree + i)->brat;

   }
}

(tree + i)->label = '\0';
(tree + i)->mama = -1;
(tree + i)->brat = -1;
(tree + i)->sin = -1;
}

node ROOT(TREE* tree){
return 0;
}

node FIRST_CHILD(node i, TREE* tree){
if(i >= max || tree->label == '\0') return -1;

return (tree + i)->sin;
}

node NEXT_SIBLING(node i, TREE* tree){
if(i >= max || tree->label == '\0') return -1;

return (tree + i)->brat;
}

node PARENT(node i, TREE* tree){
if(i >= max || tree->label == '\0') return -1;

return (tree + i)->mama;
}

char LABEL(node i, TREE* tree){
if(i >= max || tree->label == '\0') return '\0';

return (tree + i)->label;
}

void CHANGE_LABEL(char l, node i, TREE* tree){
if(i >= max || tree->label == '\0') return;

(tree + i)->label = l;
}

int broj_potomaka(node i, TREE* tree){
if(i >= max || LABEL(ROOT(tree), tree) == '\0' || i == -1) return 0;

int suma = 0;
node j;

j = FIRST_CHILD(i, tree);
while(j != -1){
   suma = suma + 1 + broj_potomaka(j, tree);
   j = NEXT_SIBLING(j, tree);
}

return suma;
}

void unesi_stablo(TREE* tree, node i){
int n, k;
char c;
node j;

if(i != ROOT(tree)) printf("Promatramo cvor %c", LABEL(i, tree));
else{
   printf("Unesite ime korijena: ");
   scanf("%c", &c);
   CHANGE_LABEL(c, ROOT(tree), tree);
}
printf("Unesite broj djece cvora: ");
scanf("%d", &n);
if(n == 0) return;

for(k = 0; k < n; k++){
   printf("Unesite ime %d. djeteta: ", k+1);
   scanf(" %c", &c);
   INSERT_CHILD(c, i, tree);
}

for(k = 0; k < n; k++){
   if(k == 0) j = FIRST_CHILD(i, tree);
   else j = NEXT_SIBLING(j, tree);
   unesi_stablo(tree, j);
}
}

int main(void){
TREE T[max];
node i;
int n, m;

MAKE_ROOT('\0', T);
unesi_stablo(T, ROOT(T));
printf("%c ", LABEL(ROOT(T), T));
CHANGE_LABEL('\0', ROOT(T), T);

while(FIRST_CHILD(ROOT(T), T) != -1){
   i = ROOT(T);

   while(FIRST_CHILD(i, T) != -1){
      if(LABEL(i, T) != '\0'){
         printf("%c ", LABEL(i,T));
         CHANGE_LABEL('\0', i, T);
         i = NEXT_SIBLING(i, T);
      }
   }

   if(LABEL(i, T) != '\0'){
      printf("%c ", LABEL(i,T));
      CHANGE_LABEL('\0', i, T);
   }

   DELETE(i, T);
}

return 0;
}

#110: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 4:25 čet, 17. 1. 2013
—
Ne bi li u INSERT_CHILD() trebalo postaviti sina od mame (tj. i-tog cvora)?

#111: Autor/ica: Zenon, Lokacija: [tex]\pm\infty[/tex]

Postano: 7:57 čet, 17. 1. 2013
—
Da, to i jesam bio napisao, samo malo krivo pa me je kasnije zbunilo. Sada taj dio radi. Puno hvala! No, nešto drugo ne štima. Dio koda if(i != ROOT(tree)) printf("Promatramo cvor %c", LABEL(i, tree)); mi ispiše samo Promatramo cvor i ne razumijem zašto. Nikada ne ispiše label čvora. :S

#112: Autor/ica: Leolinus,

Postano: 9:26 čet, 17. 1. 2013
—

Zenon (napisa):

Da, to i jesam bio napisao, samo malo krivo pa me je kasnije zbunilo. Sada taj dio radi. Puno hvala! No, nešto drugo ne štima. Dio koda if(i != ROOT(tree)) printf("Promatramo cvor %c", LABEL(i, tree)); mi ispiše samo Promatramo cvor i ne razumijem zašto. Nikada ne ispiše label čvora. :S

Možda zato što u label stavljaš int 1, koji se casta u char 00000001 što je u ASCII-ju SOH znak.

'\0' je doslovno NUL karakter, vrijednost dekadska mu je 0, to nije znamenka 0. '0' i '1' su znamenke.
Možda ti želiš da ti je to int vrijednost, onda jednostavno umjesto %c u ispisu stavi %d.

#113: Autor/ica: Zenon, Lokacija: [tex]\pm\infty[/tex]

Postano: 11:19 čet, 17. 1. 2013
—
Ne razumijem. U strukturi, label je tipa char, a kada predajem funkciji CHANGE_LABEL dajem joj na prvom mjestu char c. Funkcija LABEL samo čita oznaku čvora i.

#114: Autor/ica: Leolinus,

Postano: 11:26 čet, 17. 1. 2013
—

Zenon (napisa):

Ne razumijem. U strukturi, label je tipa char, a kada predajem funkciji CHANGE_LABEL dajem joj na prvom mjestu char c. Funkcija LABEL samo čita oznaku čvora i.

Char je tip podataka, a u C-u sadrži 8 bitova. Ti, ako ideš spremiti 1 u char. To je integer po defaultu. Automatski se 1 cast-a u char tako da se uzme zadnjih 8 bitova zapisa 0000 0000 0000 0000 0000 0000 0000 0001.

Nakon toga ti spremaš 0000 0001 u svoju varijablu label, a 0000 0001 nije binarni zapis ZNAKA 1, nego znaka SOH (start of header) u ASCII-ju.
Ako želiš da ti bude ZNAK 1, onda ćeš upisati char c = '1', a ne = 1.

Isto tako '\0' je znak za NUL karakter koji ima binarni zapis 0000 0000. To će ti na ekranu ispisati ništa. Ako želiš ispisati nulu, onda trebaš zapisati znak '0'(char c = '0')

EDIT: Sorry, tek sad vidio da ono nije 1 nego 'l' (L).

#115: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 12:07 čet, 17. 1. 2013
—
Zenone, previse copy/paste-a:

Kod:

void CHANGE_LABEL(char l, node i, TREE* tree){
if(i >= max || tree->label == '\0') return;

(tree + i)->label = l;
}

Po defaultu, tree→label je uvijek jednak '\0 (v. fju MAKE_ROOT() i njen poziv u main()). Nadalje, funkcije koje rade s tree + i provjeravaju
if(i >= max || tree→label == '\0'),
dakle ne "ima li tree[i] praznu labelu", nego "ima li korijen praznu labelu" (a to je uvijek istina).

#116: Autor/ica: Zenon, Lokacija: [tex]\pm\infty[/tex]

Postano: 12:15 čet, 17. 1. 2013
—
Hvala Vam puno! You're a life saver! Thank you

Sada funkcija napokon radi.

#117: definiranje tipova Autor/ica: flux,

Postano: 21:44 pet, 17. 1. 2014
—
na satu nam je dan kod za funkciju MaCompute implementiranu pomoću sortiranog polja

Kod:

int MaCompute(Mapping *M, domain d, range r)
{
int l=0, m, n=M->last;
domain dm;
while (l<=n)
{
m=(l+n)/2;
dm= M->pairs[m].domainelement;
if (dm==d) {*r=M->pairs[m].rangeelement;
return 1;}
else if (dm<d) l=m+1;
else n=m-1;
}
return 0;
}

e sad ja sam napisala i sve ostale funkcije iz implementacije ali me muči kako da definiram tip domain
u zadatku kaže "Pretpostavite da je domena skup imena duljine max. 20 slova, a kodomena skup telefonskih brojeva (cijeli brojevi). "

e sad ja sam to napisala ovako

Kod:

#define Max 100
#define burek 20

typedef long range;
typedef struct
{
char ime[burek];
}domain;

typedef struct
{
domain domainelement;
range rangeelement;
}celltype;

typedef struct
{
celltype pairs[Max];
int last;
}Mapping;

ali onda mi javlja grešku kod macompute i maassigne kod if (dm==d) i sličnog jer (logično) ne želi tako uspoređivati stringove
dal moram u svakoj if naredbi pisati funkcije koje uspoređuju strignove?
makar bi koliko sam ja shvatila funkcije macompute maassign i te moraju bit iste za sve domain tipove

#118: Autor/ica: beuler,

Postano: 20:33 sub, 18. 1. 2014
—
moze pomoc, kako dodati novi element u potpuno binarno stablo (definirano pointerima) ?

(zadatak je sortirat listu pomocu hrpe definirane pointerima)

edit:
smislio sam nesto, izbrojat lijevo stablo i desno pa gledat jesu li oblika i=i+2*K

nakon mukotrpnih modificiranja koda, uspio sam doci do verzije koja actually i radi
ako kome treba : http://pastebin.com/g117J3cx
u ovoj verziji sortira intove iz liste pomocu hrpe (oboje prikazano pomocu pointera)

Zadnja promjena: beuler; 17:44 ned, 19. 1. 2014; ukupno mijenjano 1 put.

#119: Autor/ica: nuclear,

Postano: 15:58 ned, 19. 1. 2014
—
Već je bio ovaj zadatak kao pitanje, ali nitko nije dao odgovor. U vezi zadatka:

Implementirajte atp Mapping pomoću sortiranog polja. Elementi domene su uređeni parovi oblika (a,b), a,b € {0,1,2...n}, a kodomena skup {0,1,2...n}. Svako ovakvo preslikavanje f je binarna operacija f(a,b)=a*b za neku operaciju *.....

dalje nije bitno. Muči me (kao i moje prethodnike) domena. Napisala sam sljedeće, ali ne znam kako onda konstruirati Mapping:

Kod:

#define max 100
typedef int range;

typedef struct{
int a;
int b;
} domain;

typedef struct {
range elements[max];
int last;
} Mapping;

je li uopće dobro postavljati u Mapping umjesto elementtype range? i kako to sad sa domenom uskladiti?

#120: Autor/ica: nuclear,

Postano: 18:12 ned, 19. 1. 2014
—
Evo ovo mi funkcionira, bi li se ovo priznalo kako su tražili?

Kod:

#define max 100
typedef int range;

typedef struct{
int a;
int b;
} domain;

typedef struct {
domain d;
range r;
} element;

typedef struct{
element polje[max];
int last;
} Mapping;

Forum@DeGiorgi -> Strukture podataka i algoritmi

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Idite na Prethodno 1, 2, 3, 4, 5, 6, 7, 8 Sljedeće :| |: Stranica 6 / 8.