| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Shaman
Forumaš(ica)
Pridružen/a: 24. 09. 2011. (22:21:43)
Postovi: (76)16
Spol: 
|
|
| [Vrh] |
|
Jurinho
Forumaš(ica)
Pridružen/a: 01. 11. 2011. (23:39:13)
Postovi: (26)16
Spol:
|
|
| [Vrh] |
|
sasha.f
Forumaš(ica)
Pridružen/a: 25. 10. 2011. (20:04:19)
Postovi: (3D)16
|
 Postano: 0:56 pet, 6. 1. 2012 Naslov: |
    |
|
|
što se tiče 4. zadaće, zapela sam na ovom zadatku pa ako je netko voljan pogledati? :)
Napišite program koji učitava prirodni broj n<131, te niz od n cijelih brojeva. Program treba pronaći najveći element niza djeljiv s 5, te u originalnom poretku ispisati indekse onih elementa niza kojima je prva znamenka jedna od znamenki pronađenog maksimuma.
Ako traženi maksimum ne postoji, program ne smije ništa ispisati. Ispisane brojeve odvojite razmacima.
[code:1]int main(void)
{
int x[131];
int n, i, max, znam, p;
do
{
scanf("%d", &n);
}
while(n<0 || n>=131);
for(i=0; i<n; i++)
{
scanf("%d", &x[i]);
}
for(i=0; i<n; i++)
{
if(x[i]%5==0)
{
max=x[i];
break;
}
}
for(i=0; i<n; i++)
{
if(x[i]%5==0)
{
if(x[i]>max)
max=x[i];
}
}
for(i=0; i<n; i++)
{
if(x[i]<0)
x[1]=-x[1];
while(x[i]>0)
{
p=x[i]%10;
x[i]=x[i]/10;
}
while(max>0)
{
znam=max%10;
if(znam==x[i])
{
printf("%d", i);
}
max=max/10;
}
}
return 0;
}
[/code:1]
što se tiče 4. zadaće, zapela sam na ovom zadatku pa ako je netko voljan pogledati? 
Napišite program koji učitava prirodni broj n<131, te niz od n cijelih brojeva. Program treba pronaći najveći element niza djeljiv s 5, te u originalnom poretku ispisati indekse onih elementa niza kojima je prva znamenka jedna od znamenki pronađenog maksimuma.
Ako traženi maksimum ne postoji, program ne smije ništa ispisati. Ispisane brojeve odvojite razmacima.
| Kod: | int main(void)
{
int x[131];
int n, i, max, znam, p;
do
{
scanf("%d", &n);
}
while(n<0 || n>=131);
for(i=0; i<n; i++)
{
scanf("%d", &x[i]);
}
for(i=0; i<n; i++)
{
if(x[i]%5==0)
{
max=x[i];
break;
}
}
for(i=0; i<n; i++)
{
if(x[i]%5==0)
{
if(x[i]>max)
max=x[i];
}
}
for(i=0; i<n; i++)
{
if(x[i]<0)
x[1]=-x[1];
while(x[i]>0)
{
p=x[i]%10;
x[i]=x[i]/10;
}
while(max>0)
{
znam=max%10;
if(znam==x[i])
{
printf("%d", i);
}
max=max/10;
}
}
return 0;
}
|
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 2:27 pet, 6. 1. 2012 Naslov: |
|
|
|
Bilo bi zgodno da si navela i za koje brojeve ne radi.
Ovo mi je sumnjivo: [tt]x[[color=red]1[/color]]=-x[[color=red]1[/color]];[/tt]
Koliki je [tt]max[/tt] ako niti jedan broj nije djeljiv s 5?
Sto se desi u zadnjoj while-petlji ako su svi manji od nule?
Sto se desi s [tt]max[/tt] nakon prvog izvodjenja zadnje for-petlje?
I, za kraj, ako neki [tt]x[/tt] ima vise znamenki koje odgovaraju uvjetu, program ce ga vise puta ispisati (umjesto samo jednom).
Bilo bi zgodno da si navela i za koje brojeve ne radi.
Ovo mi je sumnjivo: x[1]=-x[1];
Koliki je max ako niti jedan broj nije djeljiv s 5?
Sto se desi u zadnjoj while-petlji ako su svi manji od nule?
Sto se desi s max nakon prvog izvodjenja zadnje for-petlje?
I, za kraj, ako neki x ima vise znamenki koje odgovaraju uvjetu, program ce ga vise puta ispisati (umjesto samo jednom).
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
sasha.f
Forumaš(ica)
Pridružen/a: 25. 10. 2011. (20:04:19)
Postovi: (3D)16
|
| Postano: 11:16 pet, 6. 1. 2012 Naslov: |
|
|
|
nisam ni poslala taj zadatak jer vidim da ne valja a nikako odgonetnut što trebam promjeniti, pogledat ću sad.. hvala! :) evo, poslala sam treći i netočno je za brojeve: 1 i 3664. ne razumijem zašto. meni ispada rezultat: 1. zar ne bi tako trebalo biti? isto tako i za četvrti zadatak (gotovo su jednaki samo što se u njemu traži suma indeksa parnih elemenata, a indeksi počinju od nule zar ne? i onda ako je prvi element paran njegov indeks je 0?).
zad 3:
Napišite program koji učitava prirodni broj n≤17, te niz od n cijelih brojeva. Program treba ispisati sumu zadnjih 9 neparnih elemenata niza.
Ako neparnih brojeva ima manje od 9, ispišite sumu svih neparnih. Ako neparnih brojeva uopće nema u nizu, ispišite 0.
[code:1]int main(void)
{
int x[17];
int n, i, b, suma;
do
{
scanf("%d", &n);
}
while(n<0 || n>17);
for(i=0; i<n; i++)
{
scanf("%d", &x[i]);
}
b=0;
suma=0;
for(i=n-1; i>=0; --i)
{
if(x[i]%2!=0)
{
b++;
suma=suma+x[i];
}
if(b==9)
break;
}
if(b==9)
printf("%d", suma);
if(b<9)
printf("%d", suma);
if(b==0)
printf("0");
return 0;
}[/code:1]
nisam ni poslala taj zadatak jer vidim da ne valja a nikako odgonetnut što trebam promjeniti, pogledat ću sad.. hvala! evo, poslala sam treći i netočno je za brojeve: 1 i 3664. ne razumijem zašto. meni ispada rezultat: 1. zar ne bi tako trebalo biti? isto tako i za četvrti zadatak (gotovo su jednaki samo što se u njemu traži suma indeksa parnih elemenata, a indeksi počinju od nule zar ne? i onda ako je prvi element paran njegov indeks je 0?).
zad 3:
Napišite program koji učitava prirodni broj n≤17, te niz od n cijelih brojeva. Program treba ispisati sumu zadnjih 9 neparnih elemenata niza.
Ako neparnih brojeva ima manje od 9, ispišite sumu svih neparnih. Ako neparnih brojeva uopće nema u nizu, ispišite 0.
| Kod: | int main(void)
{
int x[17];
int n, i, b, suma;
do
{
scanf("%d", &n);
}
while(n<0 || n>17);
for(i=0; i<n; i++)
{
scanf("%d", &x[i]);
}
b=0;
suma=0;
for(i=n-1; i>=0; --i)
{
if(x[i]%2!=0)
{
b++;
suma=suma+x[i];
}
if(b==9)
break;
}
if(b==9)
printf("%d", suma);
if(b<9)
printf("%d", suma);
if(b==0)
printf("0");
return 0;
} |
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
|
| [Vrh] |
|
sasha.f
Forumaš(ica)
Pridružen/a: 25. 10. 2011. (20:04:19)
Postovi: (3D)16
|
|
| [Vrh] |
|
eikosan
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (01:26:25)
Postovi: (5)16
|
| Postano: 20:48 pet, 6. 1. 2012 Naslov: |
|
|
|
Može li mi itko reći što ne valja u ovom programu jer nikako ne uspijevam naći grešku..?
Zadatak:
Napišite program koji učitava cijeli broj n, te ispisuje sumu svih prostih djelitelja (uvažavajući kratnost) svih cijelih brojeva različitih od nule koji se nalaze između n i 40 (uključivo).
[code:1]#include <stdio.h>
int main (void)
{
int n,i,j,k,prost=1,suma2=0,suma=0,suma3=0;
scanf("%d", &n);
for (i=n; i<=40; ++i)
{
suma3+=suma2;
suma2=0;
for (j=2; j<=i; ++j)
{
suma2+=suma;
suma=0;
if (i%j==0)
{
prost=1;
if ((j!=2) && (j!=3))
{
for (k=2; k<=j/2; ++k)
{
if(j%k==0)
{
prost=0;
}
}
}
if (prost==1)
suma+=j;
}
}
}
suma3+=suma2;
printf("%d", suma3);
return 0;
}
[/code:1]
Molim pomoć. :(
Može li mi itko reći što ne valja u ovom programu jer nikako ne uspijevam naći grešku..?
Zadatak:
Napišite program koji učitava cijeli broj n, te ispisuje sumu svih prostih djelitelja (uvažavajući kratnost) svih cijelih brojeva različitih od nule koji se nalaze između n i 40 (uključivo).
| Kod: | #include <stdio.h>
int main (void)
{
int n,i,j,k,prost=1,suma2=0,suma=0,suma3=0;
scanf("%d", &n);
for (i=n; i<=40; ++i)
{
suma3+=suma2;
suma2=0;
for (j=2; j<=i; ++j)
{
suma2+=suma;
suma=0;
if (i%j==0)
{
prost=1;
if ((j!=2) && (j!=3))
{
for (k=2; k<=j/2; ++k)
{
if(j%k==0)
{
prost=0;
}
}
}
if (prost==1)
suma+=j;
}
}
}
suma3+=suma2;
printf("%d", suma3);
return 0;
}
|
Molim pomoć. 
|
|
| [Vrh] |
|
gflegar
Forumaš(ica)
Pridružen/a: 12. 10. 2011. (15:03:41)
Postovi: (10D)16
Spol:
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 23:33 pet, 6. 1. 2012 Naslov: |
|
|
|
A sto ako je [tt]n[/tt] > 40? Pise "izmedju", dakle bez prejudiciranja koji od ta dva broja je veci.
Ovja prethodni algoritam, molim ne tako. Umjesto "za svaki [tt]i[/tt] od 2 do [tt]sqrt(t)[/tt]", bolje je "dok je [tt]t[/tt] > 1" i na kraju bez onog "[tt]t[/tt] je prosti faktor od [tt]p[/tt]".
A sto ako je n > 40? Pise "izmedju", dakle bez prejudiciranja koji od ta dva broja je veci.
Ovja prethodni algoritam, molim ne tako. Umjesto "za svaki i od 2 do sqrt(t)", bolje je "dok je t > 1" i na kraju bez onog "t je prosti faktor od p".
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
gflegar
Forumaš(ica)
Pridružen/a: 12. 10. 2011. (15:03:41)
Postovi: (10D)16
Spol:
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 12:45 sub, 7. 1. 2012 Naslov: |
|
|
|
[quote="gflegar"]Zasto? Moje je brze :P[/quote]
1. Manje je intuitivno, pa riskiras da se student koji to koristi pogubi.
2. Treba pazljivo implementirati. I.e., ako ostavis ovako, racunas korijen u svakom koraku, sto uvodi poprilicnu sumnju u to da je brze. Dakle, mozes:
2.1. Umjesto korijena prijeci na [tt]i * i <= t[/tt], pa imas dodatno mnozenje u svakom koraku (i problem s overflowom) ili
2.2. Cacheirati vrijednost korijena (u nadi da sam korijen, sto je realna aritmetika u rjesavanju cjelobrojnog problema) nece nista zbrljati.
Primijeti da taj korijen moras racunati barem za svaki prosti faktor broja. Tom sporom operacijom se pokusavas rijesiti inkrementa za 1, sto je implementirano direktno u procesoru (kao procesorska naredba).
2.3. Hibrid 2.1 i 2.2, no ostaje ti problem overflowa, a i gubi se potencijalno ubrzanje za brojeve kojima je [tex]p_{k-1}[/tex] puno manji od [tex]p_k[/tex].
3. Sigurno nece biti brze za brojeve oblika [tex]x = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_n^{k_n}[/tex], [tex]p_1 < p_2 < \dots < p_n[/tex], [tex]p_i[/tex] prosti, [tex]k_n \in \mathbb{N} \setminus \{1\}[/tex]. Dapace, za takve brojeve ce biti sporije, zbog dodatnog racunanja oko uvjeta petlje.
To znaci da ostaje usporediti potencijalni dobitak za brojeve kojima je [tex]k_n = 1[/tex] s gubitkom koji imas na svim brojevima.
Da zakljucim: ne tvrdim da nisi u pravu, no imam ozbiljne sumnje oko toga. Znas li dokazati da je prosjecno brze i tako opravdati solidno kompliciranje koda?
| gflegar (napisa): | Zasto? Moje je brze  |
1. Manje je intuitivno, pa riskiras da se student koji to koristi pogubi.
2. Treba pazljivo implementirati. I.e., ako ostavis ovako, racunas korijen u svakom koraku, sto uvodi poprilicnu sumnju u to da je brze. Dakle, mozes:
2.1. Umjesto korijena prijeci na i * i ⇐ t, pa imas dodatno mnozenje u svakom koraku (i problem s overflowom) ili
2.2. Cacheirati vrijednost korijena (u nadi da sam korijen, sto je realna aritmetika u rjesavanju cjelobrojnog problema) nece nista zbrljati.
Primijeti da taj korijen moras racunati barem za svaki prosti faktor broja. Tom sporom operacijom se pokusavas rijesiti inkrementa za 1, sto je implementirano direktno u procesoru (kao procesorska naredba).
2.3. Hibrid 2.1 i 2.2, no ostaje ti problem overflowa, a i gubi se potencijalno ubrzanje za brojeve kojima je [tex]p_{k-1}[/tex] puno manji od [tex]p_k[/tex].
3. Sigurno nece biti brze za brojeve oblika [tex]x = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_n^{k_n}[/tex], [tex]p_1 < p_2 < \dots < p_n[/tex], [tex]p_i[/tex] prosti, [tex]k_n \in \mathbb{N} \setminus \{1\}[/tex]. Dapace, za takve brojeve ce biti sporije, zbog dodatnog racunanja oko uvjeta petlje.
To znaci da ostaje usporediti potencijalni dobitak za brojeve kojima je [tex]k_n = 1[/tex] s gubitkom koji imas na svim brojevima.
Da zakljucim: ne tvrdim da nisi u pravu, no imam ozbiljne sumnje oko toga. Znas li dokazati da je prosjecno brze i tako opravdati solidno kompliciranje koda?
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
gflegar
Forumaš(ica)
Pridružen/a: 12. 10. 2011. (15:03:41)
Postovi: (10D)16
Spol:
|
| Postano: 13:55 sub, 7. 1. 2012 Naslov: |
|
|
|
[quote="vsego"]1. Manje je intuitivno, pa riskiras da se student koji to koristi pogubi.
[/quote]
Zato sam i to napisao "u slucaju da te zanima taj algoritam", ne kao algoritam koji bi se trebao koristiti nego vise kao "za one koji zele znati vise".
[quote="vsego"]
2. Treba pazljivo implementirati. I.e., ako ostavis ovako, racunas korijen u svakom koraku, sto uvodi poprilicnu sumnju u to da je brze. Dakle, mozes:
2.1. Umjesto korijena prijeci na [tt]i * i <= t[/tt], pa imas dodatno mnozenje u svakom koraku (i problem s overflowom) ili
2.2. Cacheirati vrijednost korijena (u nadi da sam korijen, sto je realna aritmetika u rjesavanju cjelobrojnog problema) nece nista zbrljati.
Primijeti da taj korijen moras racunati barem za svaki prosti faktor broja. Tom sporom operacijom se pokusavas rijesiti inkrementa za 1, sto je implementirano direktno u procesoru (kao procesorska naredba).
2.3. Hibrid 2.1 i 2.2, no ostaje ti problem overflowa, a i gubi se potencijalno ubrzanje za brojeve kojima je [tex]p_{k-1}[/tex] puno manji od [tex]p_k[/tex].
[/quote]
Ovo gore je [b]pseudokod[/b], tj. napisao sam tako da bude razumljivije. U ovom zadatku se najbolje odluciti za varijantu 2.1. Dodatno mnozenje nije neki veliki problem jer samo malo poveca konstantu kod slozenosti, a u zivotnom vijeku osobe koja pokrene program nece doci do owerflowa.
[quote="vsego"]
3. Sigurno nece biti brze za brojeve oblika [tex]x = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_n^{k_n}[/tex], [tex]p_1 < p_2 < \dots < p_n[/tex], [tex]p_i[/tex] prosti, [tex]k_n \in \mathbb{N} \setminus \{1\}[/tex]. Dapace, za takve brojeve ce biti sporije, zbog dodatnog racunanja oko uvjeta petlje.
To znaci da ostaje usporediti potencijalni dobitak za brojeve kojima je [tex]k_n = 1[/tex] s gubitkom koji imas na svim brojevima.
[/quote]
Gubitak kod brojeva takvog tipa je zanemariv. Neznam tocno izracunati slozenost svojeg algoritma, ali dobra gornja medja je [tex]\sqrt n[/tex], dok vas algoritam radi u [tex]n[/tex] u najgorem slucaju. Stovise, moj algoritam je u nekim slucajevima sporiji ali samo zbog te konstante, sto se, citiram "rjesava kupnjom brzeg racunala".
[quote="vsego"]Da zakljucim: ne tvrdim da nisi u pravu, no imam ozbiljne sumnje oko toga. Znas li dokazati da je prosjecno brze i tako opravdati solidno kompliciranje koda?[/quote]
Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze jer mozemo jednostavno provjeriti :D
Ovo su 2 koda koja racunaju sumu svih prostih djlitelja (uvazavajuci kratnost) svih prostih brojeva do [b]N[/b].
ovaj koristi moj algoritam:
[code:1]#include <stdio.h>
long suma_prostih(int n){
long sol = 0;
int i;
for (i = 2; i * i <= n; ++i) {
while (n % i == 0) {
sol += i;
n /= i;
}
}
if (n == 1) n = 0;
return sol + n;
}
int main(void){
int n;
scanf("%d", &n);
long sol = 0;
int i;
for (i = 2; i <= n; ++i) {
sol += suma_prostih(i);
}
printf("%ld\n", sol);
return 0;
}[/code:1]
a ovaj vas:
[code:1]#include <stdio.h>
long suma_prostih(int n){
long sol = 0;
int i = 2;
while (n > 1) {
while (n % i == 0) {
sol += i;
n /= i;
}
++i;
}
return sol;
}
int main(void){
int n;
scanf("%d", &n);
long sol = 0;
int i;
for (i = 2; i <= n; ++i) {
sol += suma_prostih(i);
}
printf("%ld\n", sol);
return 0;
}[/code:1]
a ovo su rezultati testiranja na nekoliko brojeva:
[code:1]goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.1
1000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.2
10000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.3
100000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.4
1000000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.1
142707
real 0m0.003s
user 0m0.000s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.1
142707
real 0m0.005s
user 0m0.008s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.2
10243046
real 0m0.009s
user 0m0.004s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.2
10243046
real 0m0.061s
user 0m0.060s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.3
795571828
real 0m0.048s
user 0m0.044s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.3
795571828
real 0m3.895s
user 0m3.884s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.4
64989338772
real 0m0.955s
user 0m0.952s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.4
64989338772
real 5m18.612s
user 5m18.164s
sys 0m0.000s
[/code:1]
[b]Testirano na 64-bitnom Ubuntu 11.10,
Procesor: Intel® Core™ i7-2630QM CPU @ 2.00GHz × 8[/b]
Meni se ovo ponasa "ocekivano", vas algoritam ima slozenost (nemojte me loviti za rijec, to je slozenost "otprilike") [tex]n^2[/tex] a moj [tex]n \sqrt n[/tex],
| vsego (napisa): | 1. Manje je intuitivno, pa riskiras da se student koji to koristi pogubi.
|
Zato sam i to napisao "u slucaju da te zanima taj algoritam", ne kao algoritam koji bi se trebao koristiti nego vise kao "za one koji zele znati vise".
| vsego (napisa): |
2. Treba pazljivo implementirati. I.e., ako ostavis ovako, racunas korijen u svakom koraku, sto uvodi poprilicnu sumnju u to da je brze. Dakle, mozes:
2.1. Umjesto korijena prijeci na i * i ⇐ t, pa imas dodatno mnozenje u svakom koraku (i problem s overflowom) ili
2.2. Cacheirati vrijednost korijena (u nadi da sam korijen, sto je realna aritmetika u rjesavanju cjelobrojnog problema) nece nista zbrljati.
Primijeti da taj korijen moras racunati barem za svaki prosti faktor broja. Tom sporom operacijom se pokusavas rijesiti inkrementa za 1, sto je implementirano direktno u procesoru (kao procesorska naredba).
2.3. Hibrid 2.1 i 2.2, no ostaje ti problem overflowa, a i gubi se potencijalno ubrzanje za brojeve kojima je [tex]p_{k-1}[/tex] puno manji od [tex]p_k[/tex].
|
Ovo gore je pseudokod, tj. napisao sam tako da bude razumljivije. U ovom zadatku se najbolje odluciti za varijantu 2.1. Dodatno mnozenje nije neki veliki problem jer samo malo poveca konstantu kod slozenosti, a u zivotnom vijeku osobe koja pokrene program nece doci do owerflowa.
| vsego (napisa): |
3. Sigurno nece biti brze za brojeve oblika [tex]x = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_n^{k_n}[/tex], [tex]p_1 < p_2 < \dots < p_n[/tex], [tex]p_i[/tex] prosti, [tex]k_n \in \mathbb{N} \setminus \{1\}[/tex]. Dapace, za takve brojeve ce biti sporije, zbog dodatnog racunanja oko uvjeta petlje.
To znaci da ostaje usporediti potencijalni dobitak za brojeve kojima je [tex]k_n = 1[/tex] s gubitkom koji imas na svim brojevima.
|
Gubitak kod brojeva takvog tipa je zanemariv. Neznam tocno izracunati slozenost svojeg algoritma, ali dobra gornja medja je [tex]\sqrt n[/tex], dok vas algoritam radi u [tex]n[/tex] u najgorem slucaju. Stovise, moj algoritam je u nekim slucajevima sporiji ali samo zbog te konstante, sto se, citiram "rjesava kupnjom brzeg racunala".
| vsego (napisa): | | Da zakljucim: ne tvrdim da nisi u pravu, no imam ozbiljne sumnje oko toga. Znas li dokazati da je prosjecno brze i tako opravdati solidno kompliciranje koda? |
Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze jer mozemo jednostavno provjeriti 
Ovo su 2 koda koja racunaju sumu svih prostih djlitelja (uvazavajuci kratnost) svih prostih brojeva do N.
ovaj koristi moj algoritam:
| Kod: | #include <stdio.h>
long suma_prostih(int n){
long sol = 0;
int i;
for (i = 2; i * i <= n; ++i) {
while (n % i == 0) {
sol += i;
n /= i;
}
}
if (n == 1) n = 0;
return sol + n;
}
int main(void){
int n;
scanf("%d", &n);
long sol = 0;
int i;
for (i = 2; i <= n; ++i) {
sol += suma_prostih(i);
}
printf("%ld\n", sol);
return 0;
} |
a ovaj vas:
| Kod: | #include <stdio.h>
long suma_prostih(int n){
long sol = 0;
int i = 2;
while (n > 1) {
while (n % i == 0) {
sol += i;
n /= i;
}
++i;
}
return sol;
}
int main(void){
int n;
scanf("%d", &n);
long sol = 0;
int i;
for (i = 2; i <= n; ++i) {
sol += suma_prostih(i);
}
printf("%ld\n", sol);
return 0;
} |
a ovo su rezultati testiranja na nekoliko brojeva:
| Kod: | goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.1
1000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.2
10000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.3
100000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ cat > tp.in.4
1000000
^C
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.1
142707
real 0m0.003s
user 0m0.000s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.1
142707
real 0m0.005s
user 0m0.008s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.2
10243046
real 0m0.009s
user 0m0.004s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.2
10243046
real 0m0.061s
user 0m0.060s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.3
795571828
real 0m0.048s
user 0m0.044s
sys 0m0.000s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.3
795571828
real 0m3.895s
user 0m3.884s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_ja < tp.in.4
64989338772
real 0m0.955s
user 0m0.952s
sys 0m0.004s
goran@goran-Dell-System-Inspiron-N7110:~/Programming$ time ./test_sego < tp.in.4
64989338772
real 5m18.612s
user 5m18.164s
sys 0m0.000s
|
Testirano na 64-bitnom Ubuntu 11.10,
Procesor: Intel® Core™ i7-2630QM CPU @ 2.00GHz × 8
Meni se ovo ponasa "ocekivano", vas algoritam ima slozenost (nemojte me loviti za rijec, to je slozenost "otprilike") [tex]n^2[/tex] a moj [tex]n \sqrt n[/tex],
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 15:15 sub, 7. 1. 2012 Naslov: |
|
|
|
Sve 5 i slozio bih se da si u pravu da je brze na danim primjerima. Ipak, mislim da treba reci par sitnica.
1. I dalje ti kod ima problem overflowa. Vjerujem da bi znao sloziti naci [tt]n[/tt] za koji je [tt]i * i < n[/tt]. Za dovoljno veliki prosti broj (veci od najveceg prikazivog punog kvadrata), program ce ti zavrsiti u beskonacnoj petlji.
Rjesenje: [tt]sqrt()[/tt] (cacheiran u neku varijablu, naravno), no tu vec treba puno pedanterije da se provjeri da ce realna aritmetika bas uvijek dati korektan rezultat. Ovako napamet, rekao bih da hoce, no ne bih dao (svoju) ruku u vatru. ;)
Alternativno rjesenje: dodatno ogranicenje na [tt]i[/tt], u ovisnosti o [tt]MAX_INT[/tt] (ili [tt]MAX_LONG[/tt] ili sto vec) ili, jos prljavije, majmuniranje s overflowom (pratis kad [tt]i * i[/tt] padne, pa zakljucujes sto vec treba).
Ostalo su sporednoce:
2. Dokazivanje korektnosti algoritama i racunanje slozenosti su itekako ozbiljne znanosti. Mjerenje je ok za nasu raspravu ovdje, ali "Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze" generalno ne stoji.
3. Preporuka za testiranje programa pod Linuxom, da si smanjis kuckanje tijekom testiranja programa:
[tt]gcc ime_fajla.c && echo ulazni parametri za scanf | ./a.out[/tt]
Za tvoje primjere (pretpostavljam da koristis bash):
[tt]for n in 1000 10000 100000; do time echo $n | ./a.out; done[/tt]
Sve 5 i slozio bih se da si u pravu da je brze na danim primjerima. Ipak, mislim da treba reci par sitnica.
1. I dalje ti kod ima problem overflowa. Vjerujem da bi znao sloziti naci n za koji je i * i < n. Za dovoljno veliki prosti broj (veci od najveceg prikazivog punog kvadrata), program ce ti zavrsiti u beskonacnoj petlji.
Rjesenje: sqrt() (cacheiran u neku varijablu, naravno), no tu vec treba puno pedanterije da se provjeri da ce realna aritmetika bas uvijek dati korektan rezultat. Ovako napamet, rekao bih da hoce, no ne bih dao (svoju) ruku u vatru. 
Alternativno rjesenje: dodatno ogranicenje na i, u ovisnosti o MAX_INT (ili MAX_LONG ili sto vec) ili, jos prljavije, majmuniranje s overflowom (pratis kad i * i padne, pa zakljucujes sto vec treba).
Ostalo su sporednoce:
2. Dokazivanje korektnosti algoritama i racunanje slozenosti su itekako ozbiljne znanosti. Mjerenje je ok za nasu raspravu ovdje, ali "Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze" generalno ne stoji.
3. Preporuka za testiranje programa pod Linuxom, da si smanjis kuckanje tijekom testiranja programa:
gcc ime_fajla.c && echo ulazni parametri za scanf | ./a.out
Za tvoje primjere (pretpostavljam da koristis bash):
for n in 1000 10000 100000; do time echo $n | ./a.out; done
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
gflegar
Forumaš(ica)
Pridružen/a: 12. 10. 2011. (15:03:41)
Postovi: (10D)16
Spol:
|
| Postano: 15:37 sub, 7. 1. 2012 Naslov: |
|
|
|
[quote="vsego"]
1. I dalje ti kod ima problem overflowa. Vjerujem da bi znao sloziti naci [tt]n[/tt] za koji je [tt]i * i < n[/tt] (svaki prikazivi broj veci od korijena najveceg [tt]int[/tt]-a, [tt]long[/tt]-a ili sto vec oslucis koristiti za [tt]n[/tt]). Ovisno o primjeni, to moze biti ozbiljan problem i toga treba biti svjestan, jer poprilicno limitiras upotrebljivost algoritma (korijen iz gornje medje nikako nije malo ogranicenje).
Rjesenje: [tt]sqrt()[/tt] (cacheiran u neku varijablu, naravno), no tu vec treba puno pedanterije da se provjeri da ce realna aritmetika bas uvijek dati korektan rezultat. Ovako napamet, rekao bih da hoce, no ne bih dao (svoju) ruku u vatru. ;)
[/quote]
Ovo se lako rijesi. Recimo da doticni tip podataka koristi [tex]2n[/tex] bitova za prikaz broja (i zbog jednostavnosti uzmimo da nema bita za predznak). Tada je najmanji broj koji nije prikaziv [tex]2^{2n}[/tex], pa su prikazivi kvadrati svih brojeva do [tex]2^n-1[/tex], pa gledamo samo [tt]i[/tt]-jeve do tog broja (znam da to dodaje 2 operacije svakom koraku, ali ne utjece ozbiljnije na slozenost).
[quote="vsego"]
2. Dokazivanje korektnosti algoritama i racunanje slozenosti su itekako ozbiljne znanosti. Mjerenje je ok za nasu raspravu ovdje, ali "Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze" generalno ne stoji.
[/quote]
Bez brige, ne omalovazavam niti jednu od navedenih znanosti. Primjetite "ne mora [b]uvijek[/b]", tj. postoje slucajevi kad se ne mora (npr. ovaj).
[quote="vsego"]
3. Preporuka za testiranje programa pod Linuxom, da si smanjis kuckanje tijekom testiranja programa:
[tt]gcc ime_fajla.c && echo ulazni parametri za scanf | ./a.out[/tt]
Za tvoje primjere (pretpostavljam da koristis bash):
[tt]for n in 1000 10000 100000; do time echo $n | ./a.out; done[/tt][/quote]
Jos sam uvijek dosta nov sto se tice linuxa, uzet cu si jednom truda pa malo bolje prouciti bash :)
| vsego (napisa): |
1. I dalje ti kod ima problem overflowa. Vjerujem da bi znao sloziti naci n za koji je i * i < n (svaki prikazivi broj veci od korijena najveceg int-a, long-a ili sto vec oslucis koristiti za n). Ovisno o primjeni, to moze biti ozbiljan problem i toga treba biti svjestan, jer poprilicno limitiras upotrebljivost algoritma (korijen iz gornje medje nikako nije malo ogranicenje).
Rjesenje: sqrt() (cacheiran u neku varijablu, naravno), no tu vec treba puno pedanterije da se provjeri da ce realna aritmetika bas uvijek dati korektan rezultat. Ovako napamet, rekao bih da hoce, no ne bih dao (svoju) ruku u vatru.
|
Ovo se lako rijesi. Recimo da doticni tip podataka koristi [tex]2n[/tex] bitova za prikaz broja (i zbog jednostavnosti uzmimo da nema bita za predznak). Tada je najmanji broj koji nije prikaziv [tex]2^{2n}[/tex], pa su prikazivi kvadrati svih brojeva do [tex]2^n-1[/tex], pa gledamo samo i-jeve do tog broja (znam da to dodaje 2 operacije svakom koraku, ali ne utjece ozbiljnije na slozenost).
| vsego (napisa): |
2. Dokazivanje korektnosti algoritama i racunanje slozenosti su itekako ozbiljne znanosti. Mjerenje je ok za nasu raspravu ovdje, ali "Lijepa stvar kod programiranja je ta da se ne mora uvijek matematicki dokazati sto je prosjcno brze" generalno ne stoji.
|
Bez brige, ne omalovazavam niti jednu od navedenih znanosti. Primjetite "ne mora uvijek", tj. postoje slucajevi kad se ne mora (npr. ovaj).
| vsego (napisa): |
3. Preporuka za testiranje programa pod Linuxom, da si smanjis kuckanje tijekom testiranja programa:
gcc ime_fajla.c && echo ulazni parametri za scanf | ./a.out
Za tvoje primjere (pretpostavljam da koristis bash):
for n in 1000 10000 100000; do time echo $n | ./a.out; done |
Jos sam uvijek dosta nov sto se tice linuxa, uzet cu si jednom truda pa malo bolje prouciti bash
|
|
| [Vrh] |
|
Darija.x
Forumaš(ica)
Pridružen/a: 10. 07. 2008. (18:31:47)
Postovi: (34)16
Lokacija: Velika Gorica
|
| Postano: 17:34 sub, 7. 1. 2012 Naslov: |
|
|
Pomagajte :)
[u]Zadatak glasi: [/u]Napišite program koji učitava cijeli broj n, te ispisuje sumu svih prostih djelitelja (ignorirajući kratnost) svih cijelih brojeva različitih od nule koji se nalaze između n i 7 (uključivo).
[code:1]#include<stdio.h>
int main()
{
int suma=0, n, i, p, an, suma1=0, suma2=0;
scanf("%d", &n);
if(n<7)
{
if(n<0)
{
an=-n;
for(p=2;p<an;p++)
{
for(i=1;i<=an;i++)
{
while(i>0)
{ if((i%p)==0)
suma1=suma1+p;
while((i%p)==0)
i=i/p;}
}
}
for(p=2;p<=7;p++)
{
for(i=1;i<=7;i++)
{ while(i>0){
if((i%p)==0)
suma2=suma2+p;
while((i%p)==0)
i=i/p;}
}
}
suma=suma1 + suma2;
printf("%d", suma);
}
if(n>0)
{
for(p=2;p<=7;p++)
{
for(i=n;i<=7;i++)
{ while(i>0){
if((i%p)==0)
suma=suma+p;
while((i%p)==0)
i=i/p;
}}
}
printf("%d", suma);
}
}
if(n>=7)
{
for(p=2;p<=n;p++)
{
for(i=7;i<=n;i++)
{ while(i>0){
if((i%p)==0)
suma=suma+p;
while((i%p)==0)
i=i/p;
}}
}
printf("%d", suma);
}
return 0;
}
[/code:1]
Zadatak glasi: Napišite program koji učitava cijeli broj n, te ispisuje sumu svih prostih djelitelja (ignorirajući kratnost) svih cijelih brojeva različitih od nule koji se nalaze između n i 7 (uključivo).
| Kod: | #include<stdio.h>
int main()
{
int suma=0, n, i, p, an, suma1=0, suma2=0;
scanf("%d", &n);
if(n<7)
{
if(n<0)
{
an=-n;
for(p=2;p<an;p++)
{
for(i=1;i<=an;i++)
{
while(i>0)
{ if((i%p)==0)
suma1=suma1+p;
while((i%p)==0)
i=i/p;}
}
}
for(p=2;p<=7;p++)
{
for(i=1;i<=7;i++)
{ while(i>0){
if((i%p)==0)
suma2=suma2+p;
while((i%p)==0)
i=i/p;}
}
}
suma=suma1 + suma2;
printf("%d", suma);
}
if(n>0)
{
for(p=2;p<=7;p++)
{
for(i=n;i<=7;i++)
{ while(i>0){
if((i%p)==0)
suma=suma+p;
while((i%p)==0)
i=i/p;
}}
}
printf("%d", suma);
}
}
if(n>=7)
{
for(p=2;p<=n;p++)
{
for(i=7;i<=n;i++)
{ while(i>0){
if((i%p)==0)
suma=suma+p;
while((i%p)==0)
i=i/p;
}}
}
printf("%d", suma);
}
return 0;
}
|
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 17:57 sub, 7. 1. 2012 Naslov: |
|
|
|
Prvo, ne trebaju ti toliki slucajevi:
[code:1]if (n < 7) {
from = n;
to = 7;
} else {
from = 7;
to = n;
}
for (p = from; p <= to; ++p) {
int ap = (p < 0 ? -p : p);
...
}[/code:1]
Drugo, imas brojac for-petlje koji se zove [tt]i[/tt], ali ga onda u while-petlji "sazvaces" (dijelis dok ne padne na 1). Sto bi trebala biti njegova vrijednost u iducem koraku for-petlje?
Trece, cini mi se da ti [tt]p[/tt] ima dvostruku ulogu. Malo zelis da je to broj cije proste fatkore pregledavas (u for-petljama ima tu ulogu), a malo da je to sam prosti faktor (u while-petljama).
Preporucam da prvo slozis program koji ce racunati sumu prostih faktora za neki ucitani [tt]temp[/tt], a onda da to upetljas u petlju koja ce racunati sumu faktora za sve brojeve izmedju [tt]n[/tt] i 7. Varijablu u toj petlji nazovi [tt]t[/tt], da se ne pokolje s [tt]p[/tt]-om iz algoritma za proste faktore i njenu vrijednost kopiraj u prije spomenuti [tt]temp[/tt] (tako da dijeljenje ne unisti vrijednost od [tt]t[/tt]).
Prvo, ne trebaju ti toliki slucajevi:
| Kod: | if (n < 7) {
from = n;
to = 7;
} else {
from = 7;
to = n;
}
for (p = from; p <= to; ++p) {
int ap = (p < 0 ? -p : p);
...
} |
Drugo, imas brojac for-petlje koji se zove i, ali ga onda u while-petlji "sazvaces" (dijelis dok ne padne na 1). Sto bi trebala biti njegova vrijednost u iducem koraku for-petlje?
Trece, cini mi se da ti p ima dvostruku ulogu. Malo zelis da je to broj cije proste fatkore pregledavas (u for-petljama ima tu ulogu), a malo da je to sam prosti faktor (u while-petljama).
Preporucam da prvo slozis program koji ce racunati sumu prostih faktora za neki ucitani temp, a onda da to upetljas u petlju koja ce racunati sumu faktora za sve brojeve izmedju n i 7. Varijablu u toj petlji nazovi t, da se ne pokolje s p-om iz algoritma za proste faktore i njenu vrijednost kopiraj u prije spomenuti temp (tako da dijeljenje ne unisti vrijednost od t).
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
homoviator
Forumaš(ica)
Pridružen/a: 31. 01. 2011. (18:42:32)
Postovi: (3A)16
|
| Postano: 23:15 sub, 7. 1. 2012 Naslov: |
|
|
|
Može pomoć, prog ne radi za negativne brojeve. Gdje je greska?
-Napišite program koji učitava prirodni broj n<31, te niz od n cijelih brojeva. Program treba učitane brojeve ispisati padajuće sortirano prema sumi znamenaka u bazi 13; ako neka dva različita broja imaju jednaku sumu znamenaka u bazi 13, onda ih uspoređujete na uobičajeni način. Ispisane brojeve odvojite razmacima.-
[code:1]
#include <stdio.h>
int sumaZnam(int niz)
{
int suma=0;
if(niz<0) niz=-niz;
while(niz>0)
{
suma=+(niz%13);
niz/=13;
}
return suma;
}
int main(void)
{
int n,niz[31],suma,i,j,temp;
scanf("%d",&n);
if(n<31 && n>0)
{
for(i=0;i<n;i++)
{
scanf("%d",&niz[i]);
}
}
for(i=0;i<n-1;i++)
{
suma=sumaZnam(niz[i]);
for(j=i+1;j<n;j++)
{
if(suma<sumaZnam(niz[j]))
{
temp=niz[i];
niz[i]=niz[j];
niz[j]=temp;
}
else if(suma==sumaZnam(niz[j]) && niz[i]<niz[j])
{
temp=niz[i];
niz[i]=niz[j];
niz[j]=temp;
}
suma=sumaZnam(niz[i]);
}
}
for(i=0;i<n-1;i++) printf("%d,",niz[i]);
printf("%d",niz[n-1]);
return 0;
}
[/code:1]
Može pomoć, prog ne radi za negativne brojeve. Gdje je greska?
-Napišite program koji učitava prirodni broj n<31, te niz od n cijelih brojeva. Program treba učitane brojeve ispisati padajuće sortirano prema sumi znamenaka u bazi 13; ako neka dva različita broja imaju jednaku sumu znamenaka u bazi 13, onda ih uspoređujete na uobičajeni način. Ispisane brojeve odvojite razmacima.-
| Kod: |
#include <stdio.h>
int sumaZnam(int niz)
{
int suma=0;
if(niz<0) niz=-niz;
while(niz>0)
{
suma=+(niz%13);
niz/=13;
}
return suma;
}
int main(void)
{
int n,niz[31],suma,i,j,temp;
scanf("%d",&n);
if(n<31 && n>0)
{
for(i=0;i<n;i++)
{
scanf("%d",&niz[i]);
}
}
for(i=0;i<n-1;i++)
{
suma=sumaZnam(niz[i]);
for(j=i+1;j<n;j++)
{
if(suma<sumaZnam(niz[j]))
{
temp=niz[i];
niz[i]=niz[j];
niz[j]=temp;
}
else if(suma==sumaZnam(niz[j]) && niz[i]<niz[j])
{
temp=niz[i];
niz[i]=niz[j];
niz[j]=temp;
}
suma=sumaZnam(niz[i]);
}
}
for(i=0;i<n-1;i++) printf("%d,",niz[i]);
printf("%d",niz[n-1]);
return 0;
}
|
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 0:23 ned, 8. 1. 2012 Naslov: |
|
|
|
Ovako nabrzinu ne vidim gresku u kodu, no ajde prvo ispravi ocito, pa ako i dalje ne radi, potrazit cemo dalje.
[quote="homoviator"]Ispisane brojeve odvojite [color=red]razmacima[/color].[/quote]
Ovako nabrzinu ne vidim gresku u kodu, no ajde prvo ispravi ocito, pa ako i dalje ne radi, potrazit cemo dalje.
| homoviator (napisa): | | Ispisane brojeve odvojite razmacima. |
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
homoviator
Forumaš(ica)
Pridružen/a: 31. 01. 2011. (18:42:32)
Postovi: (3A)16
|
|
| [Vrh] |
|
|
