Zadatak u C-u

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Napisano: 26 Sep 2012 15:32

Duž kružnog puta nalazi se N gradova i u svakom od njih postoji prodavnica bele tehnike. Poznata je cena zamrzivača u svakom gradu, i cena vožnje do sledećeg grada sa povratkom. Za meštane svakog grada odredidi grad u kome će najekonomičnije proći prilikom kupovine zamrzivača (da bi minimizirali trošak), i u kom smeru da
putuju do njega.

1. #include<stdio.h>
2. #include<conio.h>
3. #define MAX 40
4.  
5. int main()
6. {
7.    int cena[MAX],karta[MAX],i,n,poz,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk;
8.    for(i=0;i<n;i++) cena[i]=karta[i]=0;
9.    do
10.    {
11.       printf("Broj gradova i broj zamrzivaca:");
12.       scanf("%d",&n);
13.       if(n>0 && n<MAX) break;
14.       clrscr();
15.    }            while(1);
16.     printf("Unesite cenu zamrzivaca");
17.     xu=wherex();
18.     yu=wherey();
19.     xu=1;
20.     yu++;
21.    for(i=0;i<n;i++)
22.    {
23.      gotoxy(xu,yu);
24.      scanf("%d",&cena[i]);
25.      xu+=5;
26.      if(xu>80) xu=1,yu++;
27.    }
28.    printf("Unesite cenu karte");
29.     xu=wherex();
30.     yu=wherey();
31.     xu=1;
32.     yu++;
33.    for(i=0;i<n;i++)
34.    {
35.       gotoxy(xu,yu);
36.      scanf("%d",&karta[i]);
37.      xu+=5;
38.      if(xu>80) xu=1,yu++;
39.    }
40.    printf("\n\nUnesite vas grad:");
41.    do{
42.        xu=wherex();
43.        yu=wherey();
44.    scanf("%d",&poz);
45.    if(poz>0 && poz<n) break;
46.    gotoxy(xu,yu);
47.    printf("         ");
48.    gotoxy(xu,yu);
49.    }while(1);
50.    s[0]=min;
51.    for(i=0;i<n;i++)
52.    {
53.         s[i]=karta[i]+cena[i];
54.         if(s[i]<min) min=s[i],pozk=j;
55.  
56.    }
57.    printf("Karta:%d\n Cena zamrzivaca:%d ",karta[pozk],cena[pozk]);
58.    getch();
59. }

• 2Ovo se svidja korisnicima: vasa.93, NIx Car
  
  Registruj se da bi pohvalio/la poruku!

Evo ovako napamet kako bih ja to uradio.

Imao bih 2 niza, jedan za cene zamrzivača, a jedan za cene puta. Onda bih pomoću dva for ili while ciklusa (jedan rastući, drugi opadajući) odredio najmanje cene, u dve zasebne varijable smeštao dva index-a najmanjeg za oba ciklusa. Na kraju bih uporedio te cene i ispisao rezultat (dve varijable koje će se uporediti, i na osnovu njih ispisati smer). Upoređivanje bih radio pod pretpostavkom da je početni najjefiniji, ali bih imao i jednu varijablu gde se smešta put (na početku 0, a posle se vremenom sabira sa predhodnim).

Ovo je možda malo konfuzno (a možda i ne radi). Videću večeras da napišem kod.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Mislim da je u pitanju dinamicko. Radio sam slican zadatak, Laundry ali mislim da je to na istu foru
Ideja kod laundry zadatka je bila da imas N hotela i M perionica. Neki hoteli nemaju perionice i oni idu do prvog najblizeg hotela koji ima, ali to kosta. Zadatak je bio da se rasporedi M perionica u N hotela tako da je trosak sto manji.

Evo kod: [Link mogu videti samo ulogovani korisnici]

Resenje je bilo da se uzme matrica N*M, i prva kolona popuni tako sto da ako imas 1 hotel dje ces da stavis jednu masinu, ako imas dva hotela, dje se najbolje isplati, ako imas 3 gdje ces da postavis jednu perionicu i sve tako. Kada popunis prvu kolonu kreces da racunas za drugu kada imas 2 perionice. Ali kreces od polja 2x2 (2 hotela i 2 perionice), i racunas koliko ti treba je trebalo za 1 hotel 2 perionice + koliko ti treba za ostatak hotela. i sve tako redjas. Drugim rijecima, svaku sledecu cijenu dobijas preko prethodne + min od preostalih.... Na kraju ces u donjem desnom cosku matrice (mem[N-1][M-1] ako indeksi idu od 0) da imas resenje... Malo je komplikovano
Ali mislim da je ovo slican zadatak tome, a mozda je ideja slicna, uglavnom 80% sam siguran da je ovo dinamicko programiranje

• 1Ovo se svidja korisniku: morando
  
  Registruj se da bi pohvalio/la poruku!

Mislim da je ovde rec o algoritmima za nalazenje najkraceg/najbrzeg puta. Pada mi na pamet Dijkstra algoritam, koji se koristi u navigacionim uredjajima (gde se recimo u obzir uzima duzina puta i dozvoljena brzina).
[Link mogu videti samo ulogovani korisnici]

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Napisano: 27 Sep 2012 21:57

Da li postoji sansa da se to uradi na jednostavniji nacin posto mi to radimo samo jednodimenzionalne nizove?