Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
4017 Forumaš(ica)
Pridružen/a: 11. 03. 2012. (20:55:09) Postovi: (17)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 11:13 ned, 25. 11. 2012 Naslov: |
|
|
Kad radis uzastopno dijeljenje prostim faktorom, nemoj brojati svaki korak, nego svaki faktor.
Dakle, imas nesto poput
[code:1]while (p > 1) {
if (n % p == 0) {
while (n % p == 0) {
n /= p;
}
}
p++;
}[/code:1]
Ako nesto radis (npr. dizanje brojaca) u unutrasnjoj petlji, onda ce se to nesto napraviti za sve proste faktore onoliko puta koliko se pojavljuju u rastavu (tj. racunajuci kratnost), jer unutrasnja petlja u svakom koraku uklanja jednu pojavu faktora [tt]p[/tt].
Ako to nesto premjestis izvan te petlje (ali unutar [tt]if[/tt]), onda ce se to raditi tocno jednom za svaki [tt]p[/tt] takav da je [tt]n % p == 0[/tt], sto znaci tocno jednom za svaki prosti faktor ([b]ne[/b] racunajuci kratnost).
Namjerno ne pisem gotovi kod. Imas ideju, isprobaj... korisnije je nego da samo c/p-as.
Kad radis uzastopno dijeljenje prostim faktorom, nemoj brojati svaki korak, nego svaki faktor.
Dakle, imas nesto poput
Kod: | while (p > 1) {
if (n % p == 0) {
while (n % p == 0) {
n /= p;
}
}
p++;
} |
Ako nesto radis (npr. dizanje brojaca) u unutrasnjoj petlji, onda ce se to nesto napraviti za sve proste faktore onoliko puta koliko se pojavljuju u rastavu (tj. racunajuci kratnost), jer unutrasnja petlja u svakom koraku uklanja jednu pojavu faktora p.
Ako to nesto premjestis izvan te petlje (ali unutar if), onda ce se to raditi tocno jednom za svaki p takav da je n % p == 0, sto znaci tocno jednom za svaki prosti faktor (ne racunajuci kratnost).
Namjerno ne pisem gotovi kod. Imas ideju, isprobaj... korisnije je nego da samo c/p-as.
_________________ 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] |
|
jaija Forumaš(ica)
Pridružen/a: 12. 11. 2012. (15:59:39) Postovi: (5)16
|
Postano: 11:32 ned, 25. 11. 2012 Naslov: |
|
|
profesore, ja sam u početku išao ovako :
broj=broj*baza+n%baza,
di mi je n učitani broj, a baza učitana baza.
ali mi se problem javlja kod broja 16 u bazi dva. po ovom kodu, on umjesto da ispisuje 00001 on ispisuje samo 1, što je logično jer sam mu dao da računa samo sumu sa nulama sve do 1. ali drugačije nisam znao nego da složim niz i ograničim ga ''bezveze'' recimo na 1000 jer mi nitko ne će zadatk 1000 znamenaka(valjda :D).
ali što ako me traži u zadatku da ispiše broj, a ne znamenke...složiti ovakav niz nije točno rješenje.
profesore, ja sam u početku išao ovako :
broj=broj*baza+n%baza,
di mi je n učitani broj, a baza učitana baza.
ali mi se problem javlja kod broja 16 u bazi dva. po ovom kodu, on umjesto da ispisuje 00001 on ispisuje samo 1, što je logično jer sam mu dao da računa samo sumu sa nulama sve do 1. ali drugačije nisam znao nego da složim niz i ograničim ga ''bezveze'' recimo na 1000 jer mi nitko ne će zadatk 1000 znamenaka(valjda ).
ali što ako me traži u zadatku da ispiše broj, a ne znamenke...složiti ovakav niz nije točno rješenje.
|
|
[Vrh] |
|
4017 Forumaš(ica)
Pridružen/a: 11. 03. 2012. (20:55:09) Postovi: (17)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 12:27 ned, 25. 11. 2012 Naslov: |
|
|
@jaija: To se lako rijesi tako da brojis pocetne nule (ili ukupni broj znamenaka), pa - kod konacnog ispisa - kad [tt]broj[/tt] padne na nulu, ispises jos onoliko nula koliko ti brojac kaze. :)
Moze se ispisivati slijeva na desno i bez invertiranja:
1. nadjes broj znamenaka broja [tt]n[/tt] zapisanog u bazi [tt]b[/tt] (zovimo ga [tt]cnt[/tt]),
2. izracunas odgovarajucu potenciju baze, najvecu koja je manja ili jednaka [tt]n[/tt], sto je [tex]\verb~pot~ = b^{\verb~cnt~-1}[/tex],
3. u svakom koraku:
3.1. racunas koliko je [tt]n / pot[/tt] (prva znamenka) i koliko je [tt]n % pot[/tt] (ostatak broja koji koristis u iducem koraku umjesto [tt]n[/tt])
3.2. okines potenciju: [tt]pot /= b[/tt].
Korak 1 je bitan, tj. [b]nemoj[/b] racunati
[code:1]pot = 1;
while (n <= pot) pot *= b;
pot /= b;[/code:1]
jer ti se to raspadne za velike brojeve ([tt]pot[/tt] u petlji nepotrebno postane neprikaziv).
@4017: Ne, naravno. Zamisli da ti Excel za neki racun ispise 5 rezultata, pa si ti biraj koji je ok. :)
Rjesenje je jednostavno: ako nesto treba ispisati na kraju, onda i stavi taj ispis na kraj (i.e., izbaci ga izvan svih petlji).
@jaija: To se lako rijesi tako da brojis pocetne nule (ili ukupni broj znamenaka), pa - kod konacnog ispisa - kad broj padne na nulu, ispises jos onoliko nula koliko ti brojac kaze.
Moze se ispisivati slijeva na desno i bez invertiranja:
1. nadjes broj znamenaka broja n zapisanog u bazi b (zovimo ga cnt),
2. izracunas odgovarajucu potenciju baze, najvecu koja je manja ili jednaka n, sto je [tex]\verb~pot~ = b^{\verb~cnt~-1}[/tex],
3. u svakom koraku:
3.1. racunas koliko je n / pot (prva znamenka) i koliko je n % pot (ostatak broja koji koristis u iducem koraku umjesto n)
3.2. okines potenciju: pot /= b.
Korak 1 je bitan, tj. nemoj racunati
Kod: | pot = 1;
while (n <= pot) pot *= b;
pot /= b; |
jer ti se to raspadne za velike brojeve (pot u petlji nepotrebno postane neprikaziv).
@4017: Ne, naravno. Zamisli da ti Excel za neki racun ispise 5 rezultata, pa si ti biraj koji je ok.
Rjesenje je jednostavno: ako nesto treba ispisati na kraju, onda i stavi taj ispis na kraj (i.e., izbaci ga izvan svih petlji).
_________________ 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] |
|
ena! Forumaš(ica)
Pridružen/a: 09. 11. 2012. (19:53:18) Postovi: (B)16
|
|
[Vrh] |
|
Shirohige Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56) Postovi: (ED)16
Spol:
|
Postano: 13:11 ned, 25. 11. 2012 Naslov: |
|
|
[quote="vsego"]...
Konkretno, u primjeru:
[table]n n![format]align:left[/format] racunas
1 1 1 mod 5 = [color=green]1[/color]
2 1 * 2 = 2 ([color=green]1[/color] * 2) mod 5 = [color=blue]2[/color]
3 2 * 3 = 6 ([color=blue]2[/color] * 3) mod 5 = [color=red]1[/color]
4 6 * 4 = 24 ([color=red]1[/color] * 4) mod 5 = [b]4[/b][/table]
Dakle, ostatak je 4 (isto kao i [tex]24 \mod 5[/tex]), sto je ekvivalentno ostatku -1 (jednostavno: 4+1 je djeljivo s 5).
Jasnije?[/quote]
Puno jasnije, tj. nisam shvaćao ove obojane ostatke odnosno da se sljedeći broj množi s tim ostatkom, ali imam problem s brojem 4.
[url]http://img35.imageshack.us/img35/157/25112012130651.png[/url]
"Ručno" sam provjerio što petlja radi za broj 4 i jasno mi je što se događa no je li taj broj 4 poseban slučaj ili mi je kod krivo napisan?
[url]http://paste2.org/p/2519982[/url]
vsego (napisa): | ...
Konkretno, u primjeru:
n | n! | racunas |
---|
1 | 1 | 1 mod 5 = 1 | 2 | 1 * 2 = 2 | (1 * 2) mod 5 = 2 | 3 | 2 * 3 = 6 | (2 * 3) mod 5 = 1 | 4 | 6 * 4 = 24 | (1 * 4) mod 5 = 4 |
Dakle, ostatak je 4 (isto kao i [tex]24 \mod 5[/tex]), sto je ekvivalentno ostatku -1 (jednostavno: 4+1 je djeljivo s 5).
Jasnije? |
Puno jasnije, tj. nisam shvaćao ove obojane ostatke odnosno da se sljedeći broj množi s tim ostatkom, ali imam problem s brojem 4.
http://img35.imageshack.us/img35/157/25112012130651.png
"Ručno" sam provjerio što petlja radi za broj 4 i jasno mi je što se događa no je li taj broj 4 poseban slučaj ili mi je kod krivo napisan?
http://paste2.org/p/2519982
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
Shirohige Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56) Postovi: (ED)16
Spol:
|
|
[Vrh] |
|
4017 Forumaš(ica)
Pridružen/a: 11. 03. 2012. (20:55:09) Postovi: (17)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
4017 Forumaš(ica)
Pridružen/a: 11. 03. 2012. (20:55:09) Postovi: (17)16
|
|
[Vrh] |
|
BlameGame Forumaš(ica)
Pridružen/a: 14. 09. 2011. (19:17:53) Postovi: (6C)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 4:13 pon, 26. 11. 2012 Naslov: |
|
|
[quote="BlameGame"]Zadatak 30, jel smije ispisati 9 1, samo je do poretka,[/quote]
Ako je "samo do poretka", cemu kompliciranje? Ispisi ispravnim redoslijedom i mir.
[quote="BlameGame"]32, sto ako je baza veca od 9?[/quote]
Pise da se ucitava baza strogo manja od 10, dakle baze strogo vece od 9 ne treba razmatrati.
BlameGame (napisa): | Zadatak 30, jel smije ispisati 9 1, samo je do poretka, |
Ako je "samo do poretka", cemu kompliciranje? Ispisi ispravnim redoslijedom i mir.
BlameGame (napisa): | 32, sto ako je baza veca od 9? |
Pise da se ucitava baza strogo manja od 10, dakle baze strogo vece od 9 ne treba razmatrati.
_________________ 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] |
|
Agnes Forumaš(ica)
Pridružen/a: 06. 11. 2012. (20:39:11) Postovi: (8)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
Shirohige Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56) Postovi: (ED)16
Spol:
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 14:33 pon, 26. 11. 2012 Naslov: |
|
|
Kao prvo, testiras za bazu 10, sto pise da nece biti. Razlog tome je overflow (probaj 9012345678 prikazati u racunalu).
Kao drugo, cemu sluzi prva petlja? Zbog nje dobijes i ovo:
[code:1]Unesite prirodni broj n: 4096
Unesite bazu b: 2
NE
broj = -727379968 [/code:1]
Procitaj [url=http://degiorgi.math.hr/forum/viewtopic.php?p=176464#176464]moj posljednji post na prvoj stranici ovog topica[/url] i vidi sto radis. Takodjer, isprobaj svoj program (na papiru, korak po korak!) za [tex]4096 = 2^{12}[/tex] i bazu [tex]2[/tex] i pazi s kakvim nebulozno velikim brojem u jednom trenu baratas, samo zato da bi iskrampao nesto reda velicine samo 4000.
Kao prvo, testiras za bazu 10, sto pise da nece biti. Razlog tome je overflow (probaj 9012345678 prikazati u racunalu).
Kao drugo, cemu sluzi prva petlja? Zbog nje dobijes i ovo:
Kod: | Unesite prirodni broj n: 4096
Unesite bazu b: 2
NE
broj = -727379968 |
Procitaj moj posljednji post na prvoj stranici ovog topica i vidi sto radis. Takodjer, isprobaj svoj program (na papiru, korak po korak!) za [tex]4096 = 2^{12}[/tex] i bazu [tex]2[/tex] i pazi s kakvim nebulozno velikim brojem u jednom trenu baratas, samo zato da bi iskrampao nesto reda velicine samo 4000.
_________________ 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] |
|
Agnes Forumaš(ica)
Pridružen/a: 06. 11. 2012. (20:39:11) Postovi: (8)16
|
Postano: 15:14 pon, 26. 11. 2012 Naslov: |
|
|
Hvala, jel je onda ovo dobro rješenje? (znam da nije baš najljepše) :)
#include <stdio.h>
int main (void)
{int n, x, k, sum, d, t, y, z, sqrtn;
scanf("%d", &n);
x=1;
k=0;
sum=0;
while(x<n)
{z=x;
if(x*x==n) {sqrtn=x; break;}
x++;
if(x*x>n){sqrtn=x; break;}}
y=sqrtn;
while(y<=n)
{t=1;
d=2;
while(d<y)
{if((y%d)==0) {t=0;break;}
d++;}
if(t) {sum+=y; k++;}
y++;}
printf(" suma prostih je %d, broj prostih je %d", sum, k);
return 0;
}
Hvala, jel je onda ovo dobro rješenje? (znam da nije baš najljepše)
#include <stdio.h>
int main (void)
{int n, x, k, sum, d, t, y, z, sqrtn;
scanf("%d", &n);
x=1;
k=0;
sum=0;
while(x<n)
{z=x;
if(x*x==n) {sqrtn=x; break;}
x++;
if(x*x>n){sqrtn=x; break;}}
y=sqrtn;
while(y<=n)
{t=1;
d=2;
while(d<y)
{if((y%d)==0) {t=0;break;}
d++;}
if(t) {sum+=y; k++;}
y++;}
printf(" suma prostih je %d, broj prostih je %d", sum, k);
return 0;
}
|
|
[Vrh] |
|
Shirohige Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56) Postovi: (ED)16
Spol:
|
Postano: 15:42 pon, 26. 11. 2012 Naslov: |
|
|
[quote="vsego"]Kao prvo, testiras za bazu 10, [b]sto pise da nece biti[/b].
...[/quote]
Zbog toga sam sve fulao. Ja sam program pisao s pretpostavkom da može za bilo koju bazu, pa mi je prva petlja (barem je trebala) pretvarala broj iz dekadskog u sustav navedene baze, pa sam u drugoj petlji "vadio" pojedine znamenke s ciljem da vidim jesu li sve prisutne u tom novom broju, ali s obzirom da sam u drugoj petlji to radio tako da dijelim sa 10, opet bi i 10 trebala biti max. baza no s obzirom na velike brojke, to ne ide baš tako...
Ovako sam ga prvobitno napisao:
[url]http://paste2.org/p/2525214[/url]
i testirao sam, 16 2, 4096 2, i 14722862 8 (broj je u oktalnom= 70123456) i za sve je ispisalo "DA". Pokušao sam unijeti i neke koje imaju sve znamenke, ali neke više puta i ispisalo je da, a za one brojeve koji ne odgovaraju, ne.
Jeli to sad dobro?
vsego (napisa): | Kao prvo, testiras za bazu 10, sto pise da nece biti.
... |
Zbog toga sam sve fulao. Ja sam program pisao s pretpostavkom da može za bilo koju bazu, pa mi je prva petlja (barem je trebala) pretvarala broj iz dekadskog u sustav navedene baze, pa sam u drugoj petlji "vadio" pojedine znamenke s ciljem da vidim jesu li sve prisutne u tom novom broju, ali s obzirom da sam u drugoj petlji to radio tako da dijelim sa 10, opet bi i 10 trebala biti max. baza no s obzirom na velike brojke, to ne ide baš tako...
Ovako sam ga prvobitno napisao:
http://paste2.org/p/2525214
i testirao sam, 16 2, 4096 2, i 14722862 8 (broj je u oktalnom= 70123456) i za sve je ispisalo "DA". Pokušao sam unijeti i neke koje imaju sve znamenke, ali neke više puta i ispisalo je da, a za one brojeve koji ne odgovaraju, ne.
Jeli to sad dobro?
|
|
[Vrh] |
|
|