Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
aska Forumaš(ica)
Pridružen/a: 02. 11. 2005. (20:01:50) Postovi: (5B)16
|
Postano: 18:10 pet, 30. 3. 2007 Naslov: Zadatak 2.8. (vjezbe) |
|
|
Zadatak koji sam ostala duzna na demonstraturama danas:
[quote]Zadatak 2.8 (pismeni ispit, 27.6.2005). Napisite rekurzivnu funk-
ciju koja uzima barem jedan argument x iz N. Funkcija treba vratiti
broj na koliko razlicitih nacina se x moze prikazati kao umnozak pri-
rodnih brojeva vecih od 1. Na primjer, za x = 12, funkcija treba vratiti
4 (2 · 2 · 3, 2 · 6, 3 · 4 i 12), za x = 30 treba vratiti 5 (2 · 3 · 5, 2 · 15,
3 · 10, 5 · 6, 30), a za x = 24 treba vratiti 7 (2 · 2 · 2 · 3, 2 · 2 · 6, 2 · 12,
2 · 3 · 4, 3 · 8, 4 · 6, 24).
Napisite i program kojim se testira funkcija (treba samo ucitati broj,
pozvati funkciju i ispisati rezultat).
Napomena: Uz argument x, funkcija smije primati dodatne po-
mocne argumente, ali nije dozvoljeno koristenje polja, lista, te globalnih
i static varijabli![/quote]
Rjesenje:
[code:1]
int f(int x,int max){
int i,rez=0;
if(x==1)return 1;
for(i=max;i<=x;i++) if((x%i)==0)rez+=f(x/i,i);
return rez; }
[/code:1]
Ok, problematican je dio bio izvesti da ne brojimo vise puta iste nacine (npr. za 12 su 223, 232 i 322 isti nacin).
Ideja je da gledamo samo uzlazno sortirane nizove( :arrow: 223).
Niz dobimo tako da dijelimo x s nekim prirodnim brojevima dok ne dobijemo 1 (u gornjem primjeru, 12 podijelimo s 2, pa ono sto dobijemo (6) dijelimo opet s 2 pa rezultat (3) dijelimo s 3).
Caka je u tome da svaki put nas broj dijelimo samo s brojevima jednakim ili vecim od onog s kojim smo zadnji put dijelili (i.e. kad jednom podijelimo 6 sa 2, iduci put ono sto dobijemo (3) mozemo dijeliti samo opet s 2 ili s 3 (jer nema smisla dijeliti 3 s brojevima vecim od 3)).
To izvedemo tako da uvedemo ekstra parametar max koji pamti koji je najveci broj s kojim smo dosad dijelili.
Prvi broj s kojim ima smisla dijeliti x je broj 2 ( nacin 1*x gleda se posljednji; u zadnjem koraku for petlje x dijelimo s x) pa se funkcija u mainu poziva sa f(x,2).
Btw, demonstratura ce iduci tjedan biti, samo ne u petak. :)
Bit ce neka obavijest na oglasnoj/forumu.
8)
Zadatak koji sam ostala duzna na demonstraturama danas:
Citat: | Zadatak 2.8 (pismeni ispit, 27.6.2005). Napisite rekurzivnu funk-
ciju koja uzima barem jedan argument x iz N. Funkcija treba vratiti
broj na koliko razlicitih nacina se x moze prikazati kao umnozak pri-
rodnih brojeva vecih od 1. Na primjer, za x = 12, funkcija treba vratiti
4 (2 · 2 · 3, 2 · 6, 3 · 4 i 12), za x = 30 treba vratiti 5 (2 · 3 · 5, 2 · 15,
3 · 10, 5 · 6, 30), a za x = 24 treba vratiti 7 (2 · 2 · 2 · 3, 2 · 2 · 6, 2 · 12,
2 · 3 · 4, 3 · 8, 4 · 6, 24).
Napisite i program kojim se testira funkcija (treba samo ucitati broj,
pozvati funkciju i ispisati rezultat).
Napomena: Uz argument x, funkcija smije primati dodatne po-
mocne argumente, ali nije dozvoljeno koristenje polja, lista, te globalnih
i static varijabli! |
Rjesenje:
Kod: |
int f(int x,int max){
int i,rez=0;
if(x==1)return 1;
for(i=max;i<=x;i++) if((x%i)==0)rez+=f(x/i,i);
return rez; }
|
Ok, problematican je dio bio izvesti da ne brojimo vise puta iste nacine (npr. za 12 su 223, 232 i 322 isti nacin).
Ideja je da gledamo samo uzlazno sortirane nizove( 223).
Niz dobimo tako da dijelimo x s nekim prirodnim brojevima dok ne dobijemo 1 (u gornjem primjeru, 12 podijelimo s 2, pa ono sto dobijemo (6) dijelimo opet s 2 pa rezultat (3) dijelimo s 3).
Caka je u tome da svaki put nas broj dijelimo samo s brojevima jednakim ili vecim od onog s kojim smo zadnji put dijelili (i.e. kad jednom podijelimo 6 sa 2, iduci put ono sto dobijemo (3) mozemo dijeliti samo opet s 2 ili s 3 (jer nema smisla dijeliti 3 s brojevima vecim od 3)).
To izvedemo tako da uvedemo ekstra parametar max koji pamti koji je najveci broj s kojim smo dosad dijelili.
Prvi broj s kojim ima smisla dijeliti x je broj 2 ( nacin 1*x gleda se posljednji; u zadnjem koraku for petlje x dijelimo s x) pa se funkcija u mainu poziva sa f(x,2).
Btw, demonstratura ce iduci tjedan biti, samo ne u petak.
Bit ce neka obavijest na oglasnoj/forumu.
_________________
|
|
[Vrh] |
|
lela Forumaš(ica)
Pridružen/a: 10. 02. 2007. (13:57:40) Postovi: (8)16
|
|
[Vrh] |
|
MKova Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38) Postovi: (187)16
Spol:
|
Postano: 18:24 sub, 7. 4. 2007 Naslov: |
|
|
ok, pitanje o materijalu s [url=http://degiorgi.math.hr/c/predavanja/predavanje_1.pdf]predavanja prof. Nogo, stranica 17[/url]
[code:1]
int x=3,a=5;
printf("%d\n",x);
printf("%p\n",&x); /* 0012FED4 */
printf("%p\n",&a); /* 0012FEC8 */
[b](int*)x=&a;[/b]
printf("%d\n",*(int*)x);
printf("%p\n",(int*)x);
printf("%p\n",&(int*)x);
printf("%p\n",x);
[/code:1]
što je [b][i](int*)x=&a[/i][/b]; ?? .... castanje x-a u pointer na integer pa spremanje u njega memorijske adrese od varijable a? U DevC++u stvar ne prolazi... Zar se integer može castat u pointer na integer?
ok, pitanje o materijalu s predavanja prof. Nogo, stranica 17
Kod: |
int x=3,a=5;
printf("%d\n",x);
printf("%p\n",&x); /* 0012FED4 */
printf("%p\n",&a); /* 0012FEC8 */
[b](int*)x=&a;[/b]
printf("%d\n",*(int*)x);
printf("%p\n",(int*)x);
printf("%p\n",&(int*)x);
printf("%p\n",x);
|
što je (int*)x=&a; ?? .... castanje x-a u pointer na integer pa spremanje u njega memorijske adrese od varijable a? U DevC++u stvar ne prolazi... Zar se integer može castat u pointer na integer?
_________________ suradnici za razvoj igre traženi!! vidi ovo
|
|
[Vrh] |
|
pecina Forumaš(ica)
Pridružen/a: 19. 01. 2005. (14:15:23) Postovi: (157)16
Spol:
Lokacija: Happily traveling through space since 1986!
|
|
[Vrh] |
|
MKova Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38) Postovi: (187)16
Spol:
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
MKova Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38) Postovi: (187)16
Spol:
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
MKova Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38) Postovi: (187)16
Spol:
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
|