Question

Un program care determina ordinea de amplasare a fisierelor (f1,f2,...fn) pe o banda magnetica,intr-un timp minim de acces.Frecvența de citire a fisierelor este aceeasi.Iar pentru citirea fisierului fi(i=1,2,3...n) sunt necesare ti secunde.
la rezolvarea problemei se vor folosi 2 fisiere
1. f1.in-in prima linie contine un numar intreg pozitiv n
in urmatoarele n linii sunt inscrise cite doua valori separate printr-un spatiu:numele fisierului-un sir de caractere si un numar intreg- numarul de secunde necesare pentru citirea acestui fisier
2.f2.out-contine n linii in care sunt inscrise a cite doua valori separate printr-un spatiu:numele fisierului-un sir de caractere si un numar intreg-numarul de secunde necesare pentru citirea acestui fisier,in ordinea de amplasare a fisierelor pe banda astfel incit timpul mediu de acces sa fie minim

Answer 1

M-am gandit aseara la problema aceasta si nu cred ca e nevoie de metoda greedy.
Probabil nu stii asta, dar pe o banda magnetica pentru a citi fisierul de pe pozitia k, trebuie sa citesti toate fisierele aflate pe pozitii aflate inainte de k.
Deci daca am nota timpurile de citire cu T[i], ca sa citesti fisierul de pe pozitia k 
$cost(k)-T[1]+T[2]+T[3]+...+T[k]=\sum_{i=1}^{k}{T[i]}$
Daca este nevoie sa calculam timpul mediu de acces si presupunem ca este egal probabil sa citim oricare fisier(frecventa de acces este egala) atunci costul mediu va fi suma tuturor costurilor supra numarul lor(media aritmetica a costurilor)
$cost_{mediu}=\frac{\sum_{k=1}^{n}{cost(k)}}{n}=\sum_{k=1}^{n}{\sum_{i=1}^{k}{\frac{T[i]}{n}}}$
Asta e o demonstratie matematica a unei idei simple: cu cat urci mai departe pe fiecare pozitie, cu atat costul mediu de acces va creste. Atunci, este logic sa ai un fisier mai mare citit pe o pozitie unde este un cost mai ridicat. Nu are rost sa vrei sa citesti un fisier de 1 kB si sa astepti 15MB cititi pana cand iti iei fisierul tau. Atunci, ordinea logica este sa le pui pe cele de scurta durata primele, si pe cele mai mari la final. Astfel, astepti ceva mai mult sa citesti un fisier mai mare, dar merita pentru ca costul e proportional cu rezultatul: mai multa informatie obtinuta.

Asadar, sortam fisierele crescator in functie de timpul de citit. Am folosit algoritmul insert_sort care are timp O(nlog(n)) de executie fata de O(n^{2}) cat ar avea un algoritm greedy

#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;


struct fisiere{
char nume[20];
int timp;
} X[10],temp;
//void swap(fisiere &a,fisiere &b){
// fisiere temp;
// temp.nume=a.nume;
// a.nume=b.nume;
// b.nume=temp.nume;
// temp.timp=a.timp;
// a.timp=b.timp;
// b.timp=temp.timp;
//}

void insert_sort(int n,fisiere X[]){
int i,j,temp_timp;
char temp_nume[20];
for(i=1;i<n;i++){
//pornesti de pe pozitia a doua
j=i;
//cat timp nu s-a sfarsit sirul si elementul actual este mai mic decat cel precedent
//fa schimb intre termeni
while(j>0&&X[j].timp<X[j-1].timp){

strcpy(temp_nume,X[j-1].nume);
strcpy(X[j-1].nume,X[j].nume);
strcpy(X[j].nume,temp_nume);
temp_timp=X[j-1].timp;
X[j-1].timp=X[j].timp;
X[j].timp=temp_timp;

j--;
}
}
} 
int main(){
int n,i;
ifstream fif("f1.in");
ofstream fof("f1.out");
fif>>n;
for(i=0;i<n;i++){
fif>>X[i].nume>>X[i].timp;
}
insert_sort(n,X);
for(i=0;i<n;i++){
fof<<X[i].nume<<" "<<X[i].timp<<endl;
}
return 0;
}