[ Strojko @ 01.03.2011. 20:30 ] @
Uzeo sam da rešim par zadataka sa skorašnjeg školskog takmičenja, prvi glasi:

Napisati program kojim se za dati prirodan broj određuje i ispisuje poslednja cifra različita od nule proizvoda 1*2*3*...*n.
Na primer, za n=7 proizvod je 1*2*3*4*5*6*7=5040, pa je traženi rezultat 4.

Moje sklepano rešenje je:
Code:

#include<iostream>
using namespace std;

int faktorijel(int n){
    int i,f;
    for(i=f=1; i<=n;f*=i++);
    return f;
}
int main(){
    int n, duzina,pomocna, X,zadnja,i;
    char string[30];
    cout<<"Unesite neki prirodan broj:";
    cin>>n;
    X=faktorijel(n); 
    cout<<"Faktorijel unetog broja je: "<<X<<endl;
    sprintf(string,"%d",X);
    duzina=strlen(string);
    for(i=0;i<duzina;i++){
      pomocna=string[i]-48;
      if(pomocna!=0) zadnja=pomocna;
    }
      cout<<"Zadnja cifra razlicita od nule je: "<<zadnja<<endl;
      system("PAUSE");
      return 0;
      }


Sledeći zadatak sam rešio na još ružniji način:

Date su količine R vrsta robe i veličine V vreća (R,V<=100). Količine roba i veličine vreća su
date redom od najmanje do najveće. Potrebno je što više vrsta robe spakovati u vreće, tako da se različite vrste robe ne mešaju i da svaka roba bude u samo jednoj vreći. Napisati program koji učitava date podatke i ispisuje koliko se najviše vrsta robe može spakovati na ovaj način.
Primer : Ulaz : R=5, robe : 1, 3, 5, 7, 9; V=3, vreće : 2, 3, 4 ; Izlaz : 2
Ulaz : R=4, robe : 5, 7, 9, 11 ; V=5, vreće : 4, 5, 6, 7, 10 ; Izlaz : 3
Ulaz : R=5, robe : 2, 3, 4, 5, 6 ; V=4, vreće : 5, 6, 7, 8 ; Izlaz : 4

moje ubogo rešenje:
Code:

#include<iostream>
using namespace std;
int main(){
int R,V,i,j, niz1[50], niz2[50], brojac=0;
cout<<"\nUnesite broj vrsta robe R= ";
cin>>R;
for(i=0;i<R;i++){
  cout<<"\nUnesite "<<i+1<<". kolicinu robe: ";
  cin>>niz1[i];
}
cout<<"\nUnesite broj razlicitih velicina vreca V= ";
cin>>V;
for(j=0;j<V;j++){
  cout<<"\nUnesite "<<j+1<<". velicinu vrece: ";
  cin>>niz2[j];
}
prekid1:
       for(j=V-1;j>=0;j--){
         prekid2:
         for(i=R-1;i>=0;i--){
              if(niz1[i]<=niz2[j]){
                  brojac++; 
                  V--; 
                  R--;
                  goto prekid1;}
              else{R--; goto prekid2;}}}
cout<<"\nNa ovaj nacin se moze spakovati najvise "<<brojac<<" vrsta roba.\n"<<endl;
system("PAUSE");
return 0;
}            

Iako rade mislim da su antiprimeri kako treba programirati u C++, bio bih veoma zahvalan kad bi mi neko objasnio kako da poboljšam stil i da ovo napišem da liči na nešto. Naravno, gotova drugačija rešenja bi bila od velike pomoći. Hvala.


[Ovu poruku je menjao X Files dana 02.03.2011. u 07:10 GMT+1]

[Ovu poruku je menjao X Files dana 02.03.2011. u 07:11 GMT+1]
[ Goran Rakić @ 01.03.2011. 21:04 ] @
Za početak, izvuci logiku iz main() funkcije u int faktorijel_poslednja_nenulta(int n) jer to je funkcija koja se u zadatku traži. Toliko o stilu, u ovom zadatku nema razloga da postoji bilo kakav drugi bogatiji C++ kod, zadatak je čisto algoritamski. Sa ovakvim zadacima nećeš navežbati C++. Koliko se sećam sa takmičenja, STL nije bio dozvoljen pa ne znam zašto bi pisao C++ kod, a ne C.

Međutim grešiš u rešenju. Razmisli i primeti da ti se nigde ne traži računanje faktorijela. Faktorijel raste veoma brzo, pa će rezultat iskočiti van int opsega za relativno malo n. U zadatku ti je verovatno dato ograničenje da n može biti i neki veći broj. Tražena je samo poslednja nenula cifra u množenju. Poslednja cifra proizvoda određena je poslednjim ciframa činioca.

Code (cpp):

#include <iostream>

// nema potrebe za pretvaranjem u string jer nas
// interesuje samo poslednjih par bitova
int poslednja_nenulta(int n)
{
  while(n > 0) {
    int c = n % 10;
    if(c != 0) return c;

    n /= 10;
  }
  return 0;
}

// glavna funkcija
int faktorijel_poslednja_nenulta(int n) {
  int i, c1;

  // abc * def = ...f*c
  c1 = poslednja_nenulta(n);
  for(i=1; i<n; i++) {
    int c2, c1new;

    c2    = poslednja_nenulta(i);
    c1new = poslednja_nenulta(c1*c2);

    printf("   ...%d * %d = ...%d\n", c1, i, c1new);

    // raspisano radi ispisa, inače:
    // c1 = poslednja_nenulta(c1*poslednja_nenulta(i));
    // spoljni poziv je zbog c1 = 8*5 kada c1 treba da bude 4

    c1 = c1new;
  }
  return c1;
}

// za testiranje
int faktorijel(int n)
{
  int i, f = 1;
  for(i=n; i>0; i--) f*=i;
  return f;
}


int main() {

  int n;
  std::cin >> n;
  std::cout << n, faktorijel(n) << std::endl;
  std::cout << faktorijel_poslednja_nenulta(n) << std::endl;

  return 0;
}
 


Nemoj da ubacuješ taj system poziv na kraju pošto tako program neće nikada završiti, pa će vreme izračunavanja svakako biti veće nego što je dozvoljeno ;) Ako programe pokreneš iz već otvorenog komandnog prozora, rezultat će ostati ispisan u prozoru.



Ovaj drugi je u prilogu. Opet, podeli kod na manje funkcije. Tvoj goto nisam čitao, nisam siguran da ti program ispravno radi za nesortirane nizove.

Dopuna: Vidim da piše kako su nizovi već sortirani neopadajuće, onda samo čitamo od zadnjeg jer nam to daje dobar poredak:
Code (c):
  v--; r--;
  while(v >= 0 && r >= 0)
  {
    // staje roba u vrecu, vreca zauzeta, roba stavljena ili idemo na manju robu
    if(V[v] >= R[r]) {
      c++; v--; r--;
    }
    else r--;
  }



[Ovu poruku je menjao Goran Rakić dana 01.03.2011. u 23:00 GMT+1]
[ Strojko @ 01.03.2011. 22:42 ] @
Hvala.
Nama su dati ulazni podaci kojima možemo da proverimo ispravnost koda i u prvom zadatku sam na osnovu toga zaključio da je u pitanju faktorijel. Dali su nam n=5 ili 7 ili 8. Verovatno veće brojeve ne bi ni unosili pri proveri zadatka baš iz razloga iskakanja rezultata van int opsega. Što se tiče C i C++ potpuno se slažem, ali jednostavno nas teraju da koristimo C++ (ne znam kako je došlo do toga ali C sad rade samo mašinci, potpuno je izbačen iz srednjoškolskog programa za elektrotehničare ovde u republici srpskoj ). Kao, pogrešno je mišljenje da C++ treba koristiti pretežno za OOP, pošto je preuzeo 99% C sintakse treba ga koristiti i za proceduralno programiranje (pri čemu se C sintaksa, paradoksalno, smatra zastarelom i nepotrebnom i prećutno je zabranjena !? ). C je tako ispao višak a printf i scanf, recimo, gledaju se kao jeres, kad god ih koristim kažu mi nešto u stilu "prevedi to u C++".

Za ovaj zadatak sa robama čudim se samom sebi kako sam uspeo ovako da unesrećim ovu for petlju, svo vreme sam razmišljao veoma slično ovom tvom rešenju ali nikako nisam uspevao da to napišem ovako jasno i prosto kao ti. Grčevito se držim for petlje i sad mi jasno da je to problem.

Hvala puno.
[ Goran Rakić @ 01.03.2011. 22:57 ] @
Citat:
Verovatno veće brojeve ne bi ni unosili pri proveri zadatka baš iz razloga iskakanja rezultata van int opsega


Uvek se navode jednostavni primeri, da bi mogao i na papiru da ispratiš rešavanje i tako potvrdiš da si dobro razumeo zadatak.

Već za n=13 faktorijel ispada iz opsega, a u zadatku sigurno piše da je 1 < n < 1000 ili tako nešto. Primeri sa kojima se testira budu takvi da bude jedan do dva primera sa n < 13 i nekoliko preko, pa na taj način dobiješ samo manji deo bodova ako zadatak rešiš neoptimalno primenom sile. Ovde uočiš da su ti samo poslednje cifre važne, i to primeniš u rešavanju.

Za C/C++, da li je scanf ili std::cin složićeš se da nije neka razlika ;) Organizuj kod lepo u modularne funkcije, piši propisno uvlačenje i dodaj poneki komentar. OOP koristiš po potrebi, kada se pojavi neka struktura (u ravni tačka, duž,...) i funkcije koje njome barataju (rastojanje, presecanje,...), ubaciš to sve u klasu. U ova dva primera nema potrebe za posebnim tipovima podataka.