Zadaci za prijemni ispit za PMF

[PeTkO]

Otvaram ovu temu kako bih u njoj trazio pomoc od iskusnijih programera oko zadataka koje imam za prijemni ispit na PMF-u u Nisu, odesk racunarske nauke.

Na prijemnom ima stvarno jako zanimljivih zadataka koji traze mozganje ali i iskustva u programiranju.

Mene trenutno muci ovaj zadatak:

Data je kvadratna matrica a dimenzije n x n. Odrediti proizvod elemenata ispod glavne dijagonale. Glavnu dijagonalu
čine elementi sa koordinatama (1, 1), (2, 2), ..., (n, n). Na primer za matricu a = ((1, 2, 3), (4, 5, 6), (7, 8, 9)) – odgovor
je 224.

Uzmimo na primer neku matricu koja izgleda ovako:

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Glavna dijagonala ide od broja 1 do 25, a nama je potreban zbir svih brojeva ispod te dijagonale, tj. brojeva 6, 11, 12, 16, 17, 18, 21, 22, 23, 24. Tako da sam ja zakljucio da je meni tu potreban dvodimenzionalni niz, koji ima 5 podnizova, a svaki taj podniz ima 5 clanova. Za izracunavanje trazenog proizvoda, iz prvog podniza mi ne treba nijedan njegov clan, iz drugog mi treba njegov prvi clan, iz treceg njegova prva dva clana itd s'tim sto se broj trazenih clanova podniza linearno uvecava za 1.
Mene sada muci, kako da napravim program koji ce da izracunava trazeni proizvod.
Evo sta sam ja do sada uradio:

#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
    int n;
    cout << "Unesite velicinu matrice: ";
    cin >> n;
    int i = 0;
    int array[n][n];
    for(i=1; i<n*n+1; i++)
    {
      cout << i << " " << endl;
      array[n][n] = i;
    }

    system("pause");
}

Bilo bi jako lepo, ako bi moderatori izasli meni, a siguran sam i drugima u susret, i ako ostave ovu temu, posto osim ovog zadatka, video sam jos par koje stvarno ne znam kako da resim.

[Ivan452]

Dugo nisam radio u C++u. A i nemam nikakav kompajler da bih ti ovo dobro uradio.
Ali evo prokomentarisacu dok ne naidje neko sa vise iskustva.

Prepodstavljam da si u ovom kodu pokusao da uneses brojeve u matricu. Ali gresis, uopste ne kapiram koja ti je ideja za unos.
Ti u tvojoj for petlji ides od 1 do 25 i u matrici na mestu (n,n) tj. (5,5) upisujes u svakom prolazu novu vrednost (1,2,3,4,5 ... 25)

Znaci prvo. Da bi dobro uneo brojeve u matricu, trebaju ti 2 for petlje da bi pristupio svakom clanu.
Trebalo bi ovako to da izgleda:

int i,j,broj;
broj=1;

for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
	  array[i][j]=broj++;
    }
}

potom kada imas matricu popunjenu sa brojevima od 1 do 25. Proizvod brojeva ispod glavne dijagonale radis bas onako sto si napisao. Probaj sam to, pa ako ne ide javi se.
Takodje, vidim da ne razumes najbolje for petlje u kombinaciji sa matricama. Moja preporuka ti je da to DOBRO proucis, jer ce ti sigurno nesto tog tipa doci.

[BobaL]

int brojac = 1, suma = 0;
for(int i = 1; i < N; ++i) {
     for(int j = 0; j < b; ++j) suma += matrica[i][j];
     ++b;
}

int brojac = 1, proizvod = 1;
for(int i = 1; i < N; ++i) {
     for(int j = 0; j < b; ++j) proizvod *= matrica[i][j];
     ++b;
}

[PeTkO]

@BobaL
Tvoj kod mi nije bas najjasniji, pa bih te zamolio, ako ti nije problem, da mi napises ceo kod programa, koji ce na kraju da ispise rezultat proizvoda brojeva ispod glavne dijagonale. Pokusavam da sam sebi objasnim, pa mi je zato potreban ceo kod.

[MG-RAY]

C#, ali, kapiraš poentu...

static void Main()
        {
            int d = 5;

            int[,] matrica = new int[d, d];

            // popunjavamo elementima redom, od 1 do WxH
            for (int i = 0; i < d * d; i++)
                matrica[i / d, i % d] = i + 1;

            // racunamo zbir bojeva ispod dijagonale, ovog puta dupla petlja, lakse je
            long proizvod = 1;
            for (int i = 0; i < d - 1; i++)
                for (int j = i + 1; j < d; j++)
                    proizvod *= matrica[j, i];

            Console.WriteLine("Proizvod elemenata je: {0}", proizvod);

            Console.ReadKey();
        }

[korisnickoime]

Matricu ucitavas ovako:

int matrica[10][10];
int n; //matrica dimenzija n x n
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
         scanf("%d",&matrica[i][j]);

Ovo su indeksi elemenata matrice 5x5:

(0,0)  (0,1)  (0,2)  (0,3)  (0,4)
(1,0)  (1,1)  (1,2)  (1,3)  (1,4)
(2,0)  (2,1)  (2,2)  (2,3)  (2,4)
(3,0)  (3,1)  (3,2)  (3,3)  (3,4)
(4,0)  (4,1)  (4,2)  (4,3)  (4,4)

Ako pazljivo pogledas, videces da je elementima matrice koji su ispod glavne dijagonale prvi indeks veci od drugog((1,0), (4,3)...), to bi trebalo da iskoristis ovako nekako:

int p = 1; //pocetna vrednost proizvoda
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
         if(i > j){
             p = p * a[i][j];
         }

Detaljnije o matricama u C-u:
http://poincare.matf.bg.ac.rs/~sana/Programiranje2/07/IIcasC07.pdf

[clzola]

Imas trougao brojeva koji ti se nalazi ispod glavne dijagonale, to znaci da je krajnja gornja tacka trougla zapravo element matrice, m[1][0]. Ide ti sve do kraja, i u svakom redu uzimas za po jedan vise broj od prethodnog reda. ali u zadjem redu elemente uzimas do n-2. (U C++ indeksiranje pocinje od nule, pa ako imas niz od 10 elemenata zadnji je a[9], a u nasem slucaju treba da se ide do predzadnjeg elementa a to je a[n-2] odnosno u matrici m[n-1][n-2]).

Sad ti trebaju samo dvije for petlje. Jedna ide po kolonama a druga po redovima. U svakom sledecem redu imas za po 1 elemenat vise.

int proizvod = 1;   // moras da postavis na 1 ako zelis da mnozis, ako je nula, sve ce biti 0
for(int i=1; i<=n-1; i++) // pocinjemo od prvog reda
    for(int j=0; j<i; j++) // pocinjemo od prvog elementa u tom redu i idemo do i-tog elemenata
        prozivod = proizvod * matrica[i][j] // ili ako treba da sabiras, sta vec

Probaj matricu da nacrtas kao tabelu na papiru, pa ce ti biti jasnije kako sam vrsio kretanje po matrici

@korisnickoime
ideja ti je odlicna, samo dodaj, da ako su "i" i "j" jednaki da predje na sledeci red u matrici, nema potrebe da vrtis for petlju skroz do kraja reda
Trosi vrijeme, ako je matrica ogromne velicine

[rastamankg]

Evo ti program pisan u fortranu, valjda je lako snaci se :P
Sutra cu da odradim u C-u. Ako ti nesto nije jasno, pitaj.


PROGRAM MATRICA
DIMENSION M(100,100)
INTEGER P
PRINT *,"Uneti red matrice:"
READ (*,*) N
DO I=1,N
DO J=1,N
READ (*,*) M(I,J)
ENDDO
ENDDO
P=1
DO I=1, N-1
DO J=I+1, N
P=P*M(J,I)
ENDDO
ENDDO
PRINT *,P
END

[BobaL]

PeTkO kaže:

@BobaL
Tvoj kod mi nije bas najjasniji, pa bih te zamolio, ako ti nije problem, da mi napises ceo kod programa, koji ce na kraju da ispise rezultat proizvoda brojeva ispod glavne dijagonale. Pokusavam da sam sebi objasnim, pa mi je zato potreban ceo kod.

Matrica je sastavljena od redova:
0-ti red: Nema elemenata
1-vi red: Ima jedan element
2-gi red: Ima dva elementa itd.

Za to koristis brojac b, b je broj elemenata u i-tom redu. N oznacava broj redova pa kroz prvu FOR petlju prolazis kroz redove i za svaki red sumiras/mnozis b elemenata, a to se radi u drugoj FOR petlji (sumiranje ili mnozenje). Kada zavrsis sa jednim redom inkrementiras brojac b jer trebas preci u naredni red. Brojac b je postavljen inicijalno na vrednost 1 jer nulti red nema elemenata.

[PeTkO]

Resio sam ovaj zadatak, i sto je najbolje, ukapirao sam na koju foru se radi, i uopste nije tesko
Ja kad zaglavim negde, javicu vam se. Imam dva zadatka koje uopste ne znam ni da postavim, ali njih cu kasnije da radim, ne mogu sad da se nerviram oko njih, radicu ove koje znam.

Jos jednom hvala svima.

[PeTkO]

Problem, again Izgleda da cete mi biti potrebni vise nego sto sam mislio.

Zadatak glasi:
Za dati broj x formiramo niz x, p(x), p(p(x)), … gde je p(x) proizvod cifara broja x. Ispisati sve brojeve u nizu do pojave
prvog jednocifrenog broja. Na primer, za n = 199 ispisati 199, 81, 8.

Ja sam napravio program koji dati broj deli na cifre...ali kako dalje? Potrebno mi je da te cifre mnozim, pa taj proizvod ponovo podelim na cifre, i tako u krug sve dok ne dobijem jednocifreni broj.

Evo koda:

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char** argv)
{
    int num = 0;
    cout << "Unesite broj: ";
    cin >> num;
    while(num > 0)
    {
        int cifra = num%10;
        num /=10;
        cout << cifra << endl;
    }
    system("pause");
}

[EclipsE]

Dok uzimas cifre, kreni da ih mnozis. Kada num bude jednak nuli, znaci da si pomnozio sve cifre i one ti se nalaze u proizvodu. Ispises taj proizvod, i onda proveris da li ti je taj proizvod manji od 10 (da bi bio jednocifren broj). Ukoliko jeste, kraj. Ukoliko nije, odradis sve to opet samo sto moras da resetujes promenljive.

Really bad primer:

proizvod = 1
num = 199

cifra = 9
num = 19
proizvod *= cifra = 9

cifra = 9
num = 1
proizvod *= cifra = 81

cifra = 1
num = 0
proizvod *= cifra = 81

print proizvod

if proizvod < 10
  finish
else
  num = proizvod
  proizvod = 1
  repeat

[Markonije]

Petko ovo su gola voda zadaci,knjigu u ruke,ne trazi na gotovo...

Tako neces nauciti,ponavljam ovo je lako da lakse ne moze biti,dobro 'Hello World' je laksi

Knjigu,zbirku i kucaj,kucaj,kucaj


Prijateljski savet

[PeTkO]

Evo jednog zadatka koji sam sam resio. Jedino sam morao da nadjem pomoc na googlu oko sortiranja brojeva u nizu.

Tekst zadataka:
Napisati program koji za dati niz ocena, izbacuje najveću i najmanju ocenu i računa prosek preostalih ocena. Na
primer, za niz ocena 2, 3, 5, 3, 2, 2, odstranjujemo ocene 5 i 2 – pa je odgovor (2 + 2 + 3 + 3) / 4 = 2.5.

Resenje:

#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <iterator>
#include <algorithm>
using namespace std;

int main()
{
    int x = 0;
    cout << "Unesite broj ocena: ";
    cin >> x;
    cout << "Unesite ocene... "<<endl;
    int niz[x];
    int nesto = 0;
    int brojac = 0;
    float brojPodataka = 0;
    float sum = 0;
    for (brojac=0; brojac<x; brojac++)
    {
        cout << "Unesite ocenu broj "<< brojac+1 <<":";
        cin >> niz[brojac];
        if(brojac == x-1)
        {
            nesto = 1;
            brojPodataka = brojac-1;
            break;
        }
    }
    for (int nStartIndex = 0; nStartIndex < x; nStartIndex++)
    {
        int nSmallestIndex = nStartIndex;

        for (int nCurrentIndex = nStartIndex + 1; nCurrentIndex < x; nCurrentIndex++)
        {
            if (niz[nCurrentIndex] < niz[nSmallestIndex])
            nSmallestIndex = nCurrentIndex;
        }
        swap(niz[nStartIndex], niz[nSmallestIndex]);
    }
    for(int i=1; i<x-1; i++)
    {
        sum += niz[i];
    }
    float defRezultat = sum/brojPodataka;
    cout << "Prosek ocena je: "<<defRezultat<<endl;

    system("pause");
}

@Markonije

Zadaci jesu laki za vas, ali su za mene jako komplikovani, jer prvi put u zivotu radim ovakav tip zadataka. Do sada sam samo radio konkretne stvari, a i plus sto imam skoro nikakvo iskustvo u aplikativnom programiranju, ja se vec 4 godine bavim web programiranjem, pa mi je malo teze da predjem u aplikativno programiranje. A za web mi ovakve stvari nisu nikada trebale.

[Fantastic]

1. zadatak sa matricama

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]) {
    
    int n,i,j; 
    cin >> n;
    int a[n][n];

    int e = 1;

    for (i = 0; i<n; i++) 
    {
        for (j = 0; j<n; j++) 
        {
            a[i][j] = e; 
            e++;
        }
    }

    // sabiranje 
    int c = 0; 
    for (i = 0; i<n - 1; i++) 
    {
        for (j = i + 1; j<n; j++) 
        {
            c = c + a[j][i];
        }
    }
    
    cout << c << endl; 
    return 0;
}

2. zadatak sa ciframa

#include <iostream>
#include <cstdlib>

using namespace std;


int mnozi(int n) 
{
    int p = 1; 
    while (n>0) 
    {
        p = p * (n%10); 
        n = n / 10; 
    }
    return p; 
}

void go(int n) 
{
    cout << n << " "; 
    int p; 
    if (n < 10) 
    {
        return; 
    }
    p = mnozi(n);
    go(p);
}

int main(int argc, char* argv[]) {
    int n; 
    cin >> n; 
    go(n);
    return 0;
}

Ja sad zavrsavam osmi razred, jel moze odmah na fax, vidite kako ja to znam DD xD salim se

[clzola]

@PeTkO, treci zadatak
Al' si ga zakomplikovao
Sta ce ti sortitanje ?

dovoljna ti je jedna for petlja da rijesis citav zadatak
Uzmes tri promenljive u koje ces da cuvas minimum, maximum i sumu svih elemata niza. Naziovimo ih 'min', 'max' i 'suma'. min, max i suma postavis da su jednaki prvom elementu niza, a[0].
Zatim ide for petlja od i=1 (drugog clana niza) do i<=n-1 (indeksiranje u C/C++ ide od nule!) i provjeravas da li je tekuci element niza manji od minimuma ili veci od maximuma i + racunas sumu.

Na kraju svega, oduzmes od sume 'min' i 'max' i podjelis sa n-2 i to je to

Kod ovakvih problema, nemoj da gledas to sad ucio si duze vremena web pa sad malo teze kapiras 'aplikativno' programiranje, vec problem pokusaj da rijesis matematicki.
Ovo je nista vise do matematika. Tako da ovakve probleme u stvari posmatraj kao matematicke probleme.

[Fantastic]

Evo zadatka sa ocenama

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
    int n; 
    cin >> n; 
    int k; 
    cin >> k; 
    n = n - 1; 
    int max = k; 
    int min = k; 
    int c = k;
    for (int i = 0; i<n; i++) 
    {
        cin >> k; 
        if (k>max) max = k;
        if (k<min) min = k; 
        c = c + k; 
    }
    int prosek = (c - max - min) / (n-1); 
    cout << prosek << "\n";
    return 0;
}

jel moze nekako iz osnovne direktno na fax da se ide ? posto vidim da su zadaci za malu decu

[PeTkO]

Zasto prosto kad moze komplikovano
Pa bunilo me je ovo da bude niz sortiran od najmanjeg ka najvecem broju, tj. oceni. Ali eto, nisam smislio prostije resenje od mog, ali kada sam video da moze prostije, onda sam bio u fazonu "Ti nisi normalan"

A sto se tice samog resavanja zadataka...Ja sve zadatke umem da resim u svojoj glavi, ali mi je problem kad to treba da prenesem na papir, u ovom slucaju u kod.

Evo jos jednog uradjenog zadatka:

Za datu Cezarovu šifru, kodirati string sastavljen od velikih slova engleske abecede. Kod ovog šifriranja, svako slovo
se menja odgovarajućim slovom iz drugog reda. Na primer, za reč*‘MATEMATIKA’ štampati ‘PDWHPDWLND’.
Original:**A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cezar:******D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Resenje:

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;

int main()
{
    char rec[120];
    char cezar[26]={'D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C'};
    cout << "Unesite rec (VELIKIM SLOVIMA): ";
    cin.getline(rec, 120);
    int duzina = strlen(rec);
    for(int i = 0; i < duzina; i++)
    {
       int index = rec[i] - 'A';
       char slovoZaZamenu = cezar[index];
       cout << slovoZaZamenu;
    }
    cin.get();
    system("pause");

}

[voodoo_]

Joj, ne koristi ovo system("pause"), time nepotrebno vezuješ program za Windows čiji shell podržava komandu pause, a na ostalim operativnim sistemima ne postoji komanda pause u shell-u.

Takođe, ako već koristiš C++, slobodno upotrebljavaj njegove mogućnosti umesto što pišeš C program sa char[] stringovima.

#include <iostream>
#include <string>

using std::cout;
using std::cin;
using std::string;

int main()
{
    string rec;
    string cezar = "DEFGHIJKLMNOPQRSTUVWXYZABC";

    cout << "Unesite rec (velikim slovima): ";
    cin >> rec;

    for(int i = 0; i < rec.length(); i++)
        cout << cezar[rec[i] - 'A'];

    cin.get();
    cin.ignore();

    return 0;
}

[PeTkO]

Kada ne koristim system("pause"), vec return 0, program mi se automatski zatvori, tako da ne mogu da vidim krajnji rezultat. Znaci radi sve dok ne dodje do poslednje naredbe.

Poslusacu tvoj savet za C++. Hvala