Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
casa verde 2024

Intrerupator cu N - doza doar cu ...

Incalzire casa fara gaz/lemne

Incalzire in pardoseala etapizata
 Suprataxa card energie?!

Cum era nivelul de trai cam din a...

probleme cu ochelarii

Impozite pe proprietati de anul v...
 teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...

Rezultat RMN
 Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD.
 

Unibuc 2017 Admitere Informatica

- - - - -
  • Please log in to reply
14 replies to this topic

#1
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,702
  • Înscris: 24.09.2014
Subiect (IV) : http://fmi.unibuc.ro..._iulie_2017.pdf
Barem: http://fmi.unibuc.ro..._iulie_2017.pdf
Nu am voie cu biblioteci precum vector sau algorithm.
Cod pentru subpunctele a si b:


#include <iostream>
#include <fstream>
using namespace std;
void flip(int n, int v[],int i, int j);
int main(void)
{
int n, j, maxim=0, i; //maxim este o pozitie
ifstream f("univ.txt");
f>>n;
int v[n+1];
v[maxim]= -1; //cea mai mica valoare

for(j=1;j<=n;j++)f>>v[j]; //citire

for(j=n;j>1;j--)  //Complexitate O(N^2)
	 {   
	 for(i=j;i>=1;i--) if(v[i]>v[maxim]) maxim=i;  //gasim maximul si ii salvam pozitia
	 flip(n, v, 1, maxim); //schimbam primul element cu maximul
	 flip(n, v, 1, j); //schimbam primul element cu ultimul, pentru ca cel mai mare element
	 }			 //sa ajunga la finalul sirului, unde ii e locul

for(i=1;i<=n;i++)cout<<v[i]<<" "; //afisare optionala
}

void flip(int n, int v[], int i, int j){
while(i<j) //Complexitate O ( N/2)
{
v[i]+=v[j]; //de remarcat ca nu folosim var auxiliara pentru interschimbarea valorilor
v[j]=v[i]-v[j];
v[i]-=v[j];
i++; //parcurgere simultana din ambele capete
j--;
}}



Excluzand faptul ca citesc din fisier, credeti ca acest cod face punctajul maxim conform baremului ?
La punctul c matematica ma depaseste, incerc sa fac cu pixul pe foaie dar parte cu multimile e aiurea rau.

Edited by VladBtz, 27 July 2017 - 13:46.


#2
pupama

pupama

    Senior Member

  • Grup: Senior Members
  • Posts: 2,555
  • Înscris: 15.05.2010
si rezultatul final (nota obtinuta) care e?

#3
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
1. Algoritmul e incorect, trebuie să faci maxim = 0 înainte de for din interior, altfel sortarea nu va fi corectă.
2. Folosești flip de două ori, o singură dată ar fi suficient, trebuie doar să ai grijă cum folosești i, j din flip.

#4
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005

View PostVladBtz, on 27 iulie 2017 - 13:40, said:

La punctul c matematica ma depaseste, incerc sa fac cu pixul pe foaie dar parte cu multimile e aiurea rau.
E vorba de niste scaderi amarate,
eu te intreb, de cate mutari ai nevoie pentru a sorta multimea respectiva?

Edited by MarianG, 27 July 2017 - 15:29.


#5
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Iar la punctul c) dacă iai la mână i, j, k și vezi cum se împarte vectorul v observi că

Dacă grupezi elementele din vectorul v:

2 câte 2, grupurile au valori consecutive (14, 13), (15, 16), etc
4 câte 4, grupurile au valori consecutive (14, 13, 15, 16), (11, 12, 9, 10), etc
8 câte 8, grupurile au valori consecutive ...
2i câte 2i, grupurile au valori consecutive ...

Iar în cea ce privește sortarea, dacă folosești divide et impera, un grup de 2i, este format din două grupuri 2i-1, să le zicem a și b, a grupul din stânga, b grupul din dreapta, (a, b ). Dacă grupurile a și b au fost sortate la pasul precedent asta înseamnă că ai două cazuri:
1. a <= b, adică ultimul element din a e mai mic decât b, iar asta înseamnă că grupul 2i este deja sortat.
2. a > b, adică dacă schimbi grupul 2i din (a, b ) în (b, a), iar asta post să faci prin 3 apeluri către flip.

Edited by tavitu, 27 July 2017 - 16:44.


#6
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,702
  • Înscris: 24.09.2014

View Posttavitu, on 27 iulie 2017 - 15:18, said:

1. Algoritmul e incorect, trebuie să faci maxim = 0 înainte de for din interior, altfel sortarea nu va fi corectă.
2. Folosești flip de două ori, o singură dată ar fi suficient, trebuie doar să ai grijă cum folosești i, j din flip.

1. Sortarea e corecta si afiseaza ce trebuie pe fiecare exemplu. Functia flip oricum interschipa toate valorile din raza, inclusiv maximul.
2. i este obligatoriu 1, interschimbarile incep obligatoriu de la prima valoare. doar j este flexibil

#7
Mosotti

Mosotti

    Geniu umil

  • Grup: Senior Members
  • Posts: 33,295
  • Înscris: 21.04.2004
Cea mai buna metoda de a interschimba doua variabile este inca o variabila. You think you're clever, but you're not :)

#8
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
1. Pune în univ.txt
5
5 4 3 2 1
Și vezi ce se întâmplă. Eventual ia o foaie de hârtie și fă cu mâna ta exemplul dat de mine.

2. ok

#9
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,702
  • Înscris: 24.09.2014

View PostMosotti, on 28 iulie 2017 - 06:48, said:

Cea mai buna metoda de a interschimba doua variabile este inca o variabila. You think you're clever, but you're not Posted Image

why ?

#10
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
pentru ca ai mai mult control

#11
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007

View PostVladBtz, on 07 august 2017 - 21:16, said:

why ?

Cum interschimbi, de exemplu, doua float'uri folosind metoda ta?

View PostVladBtz, on 27 iulie 2017 - 13:40, said:

Nu am voie cu biblioteci precum vector sau algorithm.

Te opreste cineva sa scrii tu implementarea unui algoritm de acolo? Majoritatea sunt de cateva linii si usor de retinut.

#12
VladBtz

VladBtz

    Active Member

  • Grup: Members
  • Posts: 1,702
  • Înscris: 24.09.2014

View Postdani.user, on 11 august 2017 - 18:49, said:


Te opreste cineva sa scrii tu implementarea unui algoritm de acolo? Majoritatea sunt de cateva linii si usor de retinut.

Chiar, sortarea pe care am folosit-o la punctul b ( cu maxim si un element care sta pe loc ) are nume de algoritm ? Se numeste cumva anume ?

#13
politete

politete

    Junior Member

  • Grup: Junior Members
  • Posts: 40
  • Înscris: 02.06.2017
salut,
referitor la metoda de interschimbare a 2 variabile, pt a folosi respectiva metoda de adunare/scadere trebuie sa te asiguri ca tipul variabilelor nu este depasit de acele adunari. de exemplu daca ai a,b:byte; a=200; b=100 , cand incerci sa le aduni vei depasi limita byteului
daca vrei o metoda fara a folosi o alta variabila temporara (in sensul variabilei temporare explicite), poti folosi un inline asm in care faci interschimbarea folosind stiva procesorului
uite ceva in pascal:
var a,b:integer;
begin
a:=5;
b:=20;
writeln('a=',a);
writeln('b=',B);
asm
	 push a
	 push b
	 pop a
	 pop b
end;
writeln('a=',a);
writeln('b=',B);
end.
folosind aceasta metoda se pot interschimba si nr reale (ridicase mai sus un coleg problema interschimbarii nr reale)
var c,d:real;
begin
c:=23.11;
d:=1234.1234;
writeln('c=',c:5:5);
writeln('d=',d:5:5);
asm
push dword [c]
push dword [c+4]
push dword [d]
push dword [d+4]
pop dword [c+4]
	 pop dword [c]
	 pop dword [d+4]
pop dword [d]
end;
writeln('c=',c:5:5);
writeln('d=',d:5:5);
end.
de mentionat ca la nr reale exista un set separat de instructiuni ce poate fi folosit (instructiuni 'floating point')
de asemenea, tot folosind un inline asm, poti face uz de instructiunea xchg pt a interschimba 2 variabile, dar atentie, cel putin o variabila trebuie atribuita unui registru al procesorului, deoarece nici xchg, ca de fapt nici o instructiune a setului x86 din cate stiu nu lucreaza cu 2 sau mai multi operanzi exclusiv adrese de memorie

var a,b:integer;
begin
a:=5;
b:=20;
writeln('a=',a);
writeln('b=',B);
asm
push ax
mov ax,a
xchg ax,b
mov a,ax
pop ax
end;
writeln('a=',a);
writeln('b=',B);
end.
push/pop ax sunt pt a nu deranja registrul acumulator, deoarece in momentul in care se intra in inline asm de mai sus, noi ca programatori, nu cunoastem valoarea lui ax sau ce stocheaza, si va trebui sa-i pastram valoarea
atentie insa, chiar si operatia xchg (conform manualului de instructiuni intel ex:http://www.uio.no/studier/emner/matnat/ifi/INF3151/v16/annet/24547112.pdf) face referire la ceva 'temporar' pt interschimb
[...]
Exchanges the contents of the destination (first) and source (second) operands[...]
Operation
TEMP ←  DEST
DEST ← SRC
SRC ← TEMP
[...]
exemplele de mai sus au fost compilate cu freepascal

#14
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
Doar ca n-ai nevoie de assembly pentru asa ceva. O interschimbare clasica cu variabila temporara si are grija compilatorul sa genereze codul potrivit.

#15
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,195
  • Înscris: 24.02.2007
Ia sa vedem ce assembly genereaza o versiune noua a compilatorului gcc.

Attached File  Untitled.png   77.9K   10 downloads

Ce se observa?
  • Varianta cu adunari si scaderi, dupa ce are probleme cu overflow sau variabile float, e si mai lenta si mai greu de urmarit/inteles
  • std::swap pe care-l foloseste cine se respecta, genereaza, pentru int, acelasi assembly ca o interschimbare clasica
  • Nu se aloca memorie pe stiva, memoria fiind mai lent de accesat decat registrii procesorului


Anunturi

Chirurgia cranio-cerebrală minim invazivă Chirurgia cranio-cerebrală minim invazivă

Tehnicile minim invazive impun utilizarea unei tehnologii ultramoderne.

Endoscoapele operatorii de diverse tipuri, microscopul operator dedicat, neuronavigația, neuroelectrofiziologia, tehnicile avansate de anestezie, chirurgia cu pacientul treaz reprezintă armamentarium fără de care neurochirurgia prin "gaura cheii" nu ar fi posibilă. Folosind tehnicile de mai sus, tratăm un spectru larg de patologii cranio-cerebrale.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate