| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
 Postano: 1:02 sri, 28. 11. 2012 Naslov: |
    |
|
|
Ajmo vidjeti sto se zapravo dogadja kod invertiranja (MO je valjda nekakav matematicki odsjek).
Neka je zadano
[tex]a = (a_n a_{n-1} \dots a_3a_2a_1a_0)_b = \sum_{k=0}^n a_kb^k, \quad x = 0[/tex].
Jedan korak invertiranja broja radi:
[code:1]a /= b;
x = x * b + a % b;[/code:1]
Dakle, nakon prvog koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3a_2a_1)_b = \sum_{k=1}^n a_kb^{k-1}, \quad x = x \cdot b + a_0 = a_0[/tex].
Nakon drugog koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3a_2)_b = \sum_{k=2}^n a_kb^{k-2}, \quad x = x \cdot b + a_1 = a_0b + a_1[/tex].
Nakon treceg koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3)_b = \sum_{k=3}^n a_kb^{k-3}, \quad x = x \cdot b + a_2 = a_0b^2 + a_1b + a_2[/tex].
Nakon [tex]n[/tex]-tog koraka imamo:
[tex]a = (a_n)_b = \sum_{k=n}^n a_kb^{k-n} = a_n, \quad x = x \cdot b + a_{n-1} = a_0b^{n-1} + a_1b^{n-2} + \cdots + a_{n-1} = \sum_{k=0}^{n-1} a_kb^{n-1-k}[/tex].
Konacno, nakon [tex](n+1)[/tex]-og koraka imamo:
[tex]a = 0, \quad x = x \cdot b + a_n = a_0b^n + a_1b^{n-1} + \cdots + a_{n-1}b + a_n = \sum_{k=0}^{n} a_kb^{n-k} = (a_0 a_1 a_2 \dots a_n)_b[/tex].
Proces uopce ne ovisi o tome je li [tex]b < 10[/tex], [tex]b = 10[/tex] ili [tex]b > 10[/tex] i ne vidim kako bi mogao ovisiti. Jedini razlog zasto imate limit na bazu je sto vam za vece [tex]b[/tex]-ove ponestane slova, ali algoritam za invertiranje je uvijek isti.
Ajmo vidjeti sto se zapravo dogadja kod invertiranja (MO je valjda nekakav matematicki odsjek).
Neka je zadano
[tex]a = (a_n a_{n-1} \dots a_3a_2a_1a_0)_b = \sum_{k=0}^n a_kb^k, \quad x = 0[/tex].
Jedan korak invertiranja broja radi:
| Kod: | a /= b;
x = x * b + a % b; |
Dakle, nakon prvog koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3a_2a_1)_b = \sum_{k=1}^n a_kb^{k-1}, \quad x = x \cdot b + a_0 = a_0[/tex].
Nakon drugog koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3a_2)_b = \sum_{k=2}^n a_kb^{k-2}, \quad x = x \cdot b + a_1 = a_0b + a_1[/tex].
Nakon treceg koraka imamo:
[tex]a = (a_n a_{n-1} \dots a_3)_b = \sum_{k=3}^n a_kb^{k-3}, \quad x = x \cdot b + a_2 = a_0b^2 + a_1b + a_2[/tex].
Nakon [tex]n[/tex]-tog koraka imamo:
[tex]a = (a_n)_b = \sum_{k=n}^n a_kb^{k-n} = a_n, \quad x = x \cdot b + a_{n-1} = a_0b^{n-1} + a_1b^{n-2} + \cdots + a_{n-1} = \sum_{k=0}^{n-1} a_kb^{n-1-k}[/tex].
Konacno, nakon [tex](n+1)[/tex]-og koraka imamo:
[tex]a = 0, \quad x = x \cdot b + a_n = a_0b^n + a_1b^{n-1} + \cdots + a_{n-1}b + a_n = \sum_{k=0}^{n} a_kb^{n-k} = (a_0 a_1 a_2 \dots a_n)_b[/tex].
Proces uopce ne ovisi o tome je li [tex]b < 10[/tex], [tex]b = 10[/tex] ili [tex]b > 10[/tex] i ne vidim kako bi mogao ovisiti. Jedini razlog zasto imate limit na bazu je sto vam za vece [tex]b[/tex]-ove ponestane slova, ali algoritam za invertiranje je uvijek isti.
_________________ 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] |
|
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: 3:47 sri, 28. 11. 2012 Naslov: |
|
|
|
Djabe jedan sat vjezbi ako ne zelite niti citati. [url=http://degiorgi.math.hr/forum/viewtopic.php?t=18497]Lijepo sam objasnio[/url] da je pitanje "to je broj sa znamenkama od 0 do 9?" besmisleno i potjece iz toga da uporno mistificirate brojevne sustave. Ucitavanje i ispis uvijek idu dekadski (ako nije drugacije navedeno), a za sve ostalo je apsolutno svejedno pise li u varijabli [tt]b[/tt] broj 2, 3, 16, 1719 ili bilo sto prirodno (strogo vece od 1).
"Simetricni broj" je upravo izokretanje iz mog proslog posta, gdje je lijepo -- matematicki, jer ste "[url=http://degiorgi.math.hr/forum/viewtopic.php?p=176392#176392]fax upisali iz ljubavi prema matematici[/url]" -- opisano da nema nikakve veze koja je baza zadana.
P.S. Kome i dalje treba "jedan sat vjezbi o ovome", postoje demonstrature. Nastavnici su se jako potrudili da imate velik broj vrlo kvalitetnih demosa, pa onda i iskoristite to.
Djabe jedan sat vjezbi ako ne zelite niti citati. Lijepo sam objasnio da je pitanje "to je broj sa znamenkama od 0 do 9?" besmisleno i potjece iz toga da uporno mistificirate brojevne sustave. Ucitavanje i ispis uvijek idu dekadski (ako nije drugacije navedeno), a za sve ostalo je apsolutno svejedno pise li u varijabli b broj 2, 3, 16, 1719 ili bilo sto prirodno (strogo vece od 1).
"Simetricni broj" je upravo izokretanje iz mog proslog posta, gdje je lijepo – matematicki, jer ste "fax upisali iz ljubavi prema matematici" – opisano da nema nikakve veze koja je baza zadana.
P.S. Kome i dalje treba "jedan sat vjezbi o ovome", postoje demonstrature. Nastavnici su se jako potrudili da imate velik broj vrlo kvalitetnih demosa, pa onda i iskoristite to.
_________________ 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] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: 
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 4:52 sri, 28. 11. 2012 Naslov: |
|
|
|
[quote="Shirohige"][quote="mdoko"]Ma, jok! Rekurzivne funkcije nisu uopće potrebne za zadatke iz Programirana 1. Time se bavimo na početku Programiranja 2.[/quote]
A kako je moguće dobiti ispravan poredak znamenki bez rekurzije ili nizova? :?:[/quote]
Evo bez rekurzije, nizova i "izokretanja":
[code:1]#include <stdio.h>
#include <stdlib.h>
/* racuna broj znamenki */
int broj_znamenki(int broj, int baza){
int koliko = 0;
while(broj > 0){
koliko = koliko + 1;
broj = broj / baza;
}
return koliko;
}
/* vraca i-tu znamenku, brojeci zdesna, od nule */
int znamenka(int broj, int baza, int i){
while(i > 0){
broj = broj / baza;
i = i - 1;
}
return broj % baza;
}
int main(){
int n, b, i, bz;
printf("n = "); scanf("%d", &n);
printf("b = "); scanf("%d", &b);
printf("Znamenke broja %d u bazi %d, redom s lijeva na desno: ", n, b);
bz = broj_znamenki(n, b);
for(i = bz - 1; i >= 0; i = i - 1){
printf("%d ", znamenka(n, b, i));
}
return EXIT_SUCCESS;
}[/code:1]
| Shirohige (napisa): | | mdoko (napisa): | | Ma, jok! Rekurzivne funkcije nisu uopće potrebne za zadatke iz Programirana 1. Time se bavimo na početku Programiranja 2. |
A kako je moguće dobiti ispravan poredak znamenki bez rekurzije ili nizova?  |
Evo bez rekurzije, nizova i "izokretanja":
| Kod: | #include <stdio.h>
#include <stdlib.h>
/* racuna broj znamenki */
int broj_znamenki(int broj, int baza){
int koliko = 0;
while(broj > 0){
koliko = koliko + 1;
broj = broj / baza;
}
return koliko;
}
/* vraca i-tu znamenku, brojeci zdesna, od nule */
int znamenka(int broj, int baza, int i){
while(i > 0){
broj = broj / baza;
i = i - 1;
}
return broj % baza;
}
int main(){
int n, b, i, bz;
printf("n = "); scanf("%d", &n);
printf("b = "); scanf("%d", &b);
printf("Znamenke broja %d u bazi %d, redom s lijeva na desno: ", n, b);
bz = broj_znamenki(n, b);
for(i = bz - 1; i >= 0; i = i - 1){
printf("%d ", znamenka(n, b, i));
}
return EXIT_SUCCESS;
} |
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
BlameGame
Forumaš(ica)
Pridružen/a: 14. 09. 2011. (19:17:53)
Postovi: (6C)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
BlameGame
Forumaš(ica)
Pridružen/a: 14. 09. 2011. (19:17:53)
Postovi: (6C)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
4017
Forumaš(ica)
Pridružen/a: 11. 03. 2012. (20:55:09)
Postovi: (17)16
|
|
| [Vrh] |
|
Phoenix
Forumaš(ica)
Pridružen/a: 15. 05. 2010. (18:46:07)
Postovi: (164)16
Sarma: -
|
| Postano: 23:46 čet, 29. 11. 2012 Naslov: |
|
|
Ako je točka [t ex](x_1,y_1)[/t ex] na pravcu [t ex]y=ax+b[/t ex], mora vrijediti [t ex]y_1=ax_1+b[/t ex].
Ako je ista točka ispod navedenog pravca, tada, promatrajući pravac [t ex]x=x_1[/t ex] koji prolazi kroz točku [t ex](x_1,y_1)[/t ex] i siječe pravac [t ex]y=ax+b[/t ex] u točno jednoj točki, zaključujemo da je ordinata dane točke, odnosno [t ex]y_1[/t ex], manja od ordinate točke nastale presijecanjem dva gornje navedena pravca. To sjecište je, pak, točka [t ex](x_1,ax_1+b)[/t ex]. Dakle, mora vrijediti [t ex]y_1<ax_1+b[/t ex].
Konačno, ono što tebe u zadatku zanima jesu točke koje zadovoljavaju [t ex]y_1 \ leq ax_1+b[/t ex].
Ako je ista točka ispod navedenog pravca, tada, promatrajući pravac [tex]x=x_1[/tex] koji prolazi kroz točku [tex](x_1,y_1)[/tex] i siječe pravac [tex]y=ax+b[/tex] u točno jednoj točki, zaključujemo da je ordinata dane točke, odnosno [tex]y_1[/tex], manja od ordinate točke nastale presijecanjem dva gornje navedena pravca. To sjecište je, pak, točka [tex](x_1,ax_1+b)[/tex]. Dakle, mora vrijediti [tex]y_1<ax_1+b[/tex].
Konačno, ono što tebe u zadatku zanima jesu točke koje zadovoljavaju [tex]y_1 \leq ax_1+b[/tex].
|
|
| [Vrh] |
|
Shirohige
Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56)
Postovi: (ED)16
Spol: 
|
| Postano: 18:20 pet, 30. 11. 2012 Naslov: |
|
|
|
[quote="vsego"]Ajmo vidjeti sto se zapravo dogadja kod invertiranja (MO je valjda nekakav matematicki odsjek).
........
Proces uopce ne ovisi o tome je li [tex]b < 10[/tex], [tex]b = 10[/tex] ili [tex]b > 10[/tex] i ne vidim kako bi mogao ovisiti. Jedini razlog zasto imate limit na bazu je sto vam za vece [tex]b[/tex]-ove ponestane slova, ali algoritam za invertiranje je uvijek isti.[/quote]
:wall: :wall: :wall:
Upravo tu metodu sam i koristio za neke zadatke, a nisam ni skužio što zapravo radim, dok je ono što sam ja smatrao invertiranjem broja je zapravo bila zamjena znamenki tj. ono što sam pričao da "znam" samo do baze 10 je bilo iskorištavanje činjenice da do baze 10 svaka znamenka u brojevima zapisanih u bazama 2-10 zauzima jedno "mjesto" pa sam za sve baze do 10 koristio tu formulu, ali ne s varijablom b već uvijek broj odnosno bazu 10, no nije više ni bitno, gl. da su dvoumice razrješene, hvala!
[quote="mdoko"]
Evo bez rekurzije, nizova i "izokretanja":
...[/quote]
Ovo nije dovoljno komplicirano da bi se ja toga sjetio. :shock:
No odmah je i poslužilo za 47. i 48. zad. tako da hvala! :D
Nego, 48. zadatak, zar ne bi za vrijednosti n=54 i b=2 izlaz trebao biti 54, 5, 0, a ne 54, 6, 0 ?
| vsego (napisa): | Ajmo vidjeti sto se zapravo dogadja kod invertiranja (MO je valjda nekakav matematicki odsjek).
........
Proces uopce ne ovisi o tome je li [tex]b < 10[/tex], [tex]b = 10[/tex] ili [tex]b > 10[/tex] i ne vidim kako bi mogao ovisiti. Jedini razlog zasto imate limit na bazu je sto vam za vece [tex]b[/tex]-ove ponestane slova, ali algoritam za invertiranje je uvijek isti. |
Upravo tu metodu sam i koristio za neke zadatke, a nisam ni skužio što zapravo radim, dok je ono što sam ja smatrao invertiranjem broja je zapravo bila zamjena znamenki tj. ono što sam pričao da "znam" samo do baze 10 je bilo iskorištavanje činjenice da do baze 10 svaka znamenka u brojevima zapisanih u bazama 2-10 zauzima jedno "mjesto" pa sam za sve baze do 10 koristio tu formulu, ali ne s varijablom b već uvijek broj odnosno bazu 10, no nije više ni bitno, gl. da su dvoumice razrješene, hvala!
| mdoko (napisa): |
Evo bez rekurzije, nizova i "izokretanja":
... |
Ovo nije dovoljno komplicirano da bi se ja toga sjetio. 
No odmah je i poslužilo za 47. i 48. zad. tako da hvala! 
Nego, 48. zadatak, zar ne bi za vrijednosti n=54 i b=2 izlaz trebao biti 54, 5, 0, a ne 54, 6, 0 ?
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 18:57 pet, 30. 11. 2012 Naslov: |
|
|
|
[quote="Shirohige"]Nego, 48. zadatak, zar ne bi za vrijednosti n=54 i b=2 izlaz trebao biti 54, 5, 0, a ne 54, 6, 0 ?[/quote]
Ma, to je namjerno, da se vidi pratite li na nastavi. ;)
| Shirohige (napisa): | | Nego, 48. zadatak, zar ne bi za vrijednosti n=54 i b=2 izlaz trebao biti 54, 5, 0, a ne 54, 6, 0 ? |
Ma, to je namjerno, da se vidi pratite li na nastavi. 
_________________ 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] |
|
Shirohige
Forumaš(ica)
Pridružen/a: 16. 11. 2012. (20:19:56)
Postovi: (ED)16
Spol:
|
|
| [Vrh] |
|
Popara
Forumaš(ica)
Pridružen/a: 17. 08. 2012. (19:05:50)
Postovi: (3B)16
Spol:
Lokacija: Zadar/Zagreb
|
| Postano: 1:06 sub, 1. 12. 2012 Naslov: |
|
|
|
Koliko će nama za prolazak na kolokviju igrati ulogu brzina programa?Govorim za zadatak 12.Riješio sam ga na dva načina i moram priznati da je ''moj'' algoritam ali i ovaj algoritam:
[quote="vsego"]
[quote="BlameGame"]Moze netko pliz 12.??[/quote]
[tt]for[/tt]-petlja u kojoj neki [tt]k[/tt] ide od 1, pa dok je [tt]2 * k * k <= m[/tt]. Time osiguras da je prvi sumand ([tex]k^2[/tex]) kvadrat prirodnog broja i da je manji od drugog, cime sprijecis ponavljanje parova. Ostaje provjeriti da je [tex]m - k^2[/tex] potpuni kvadrat, sto mozes rastavom na proste faktore (umjesto ispisa faktora, brojis koliko se puta svaki pojavio; broj je potpuni kvadrat ako se svi pojave parno mnogo puta). Ako je [tex]m - k^2[/tex] potpuni kvadrat, povecas odgovarajuci brojac.
Na kraju petlje, vidis je li brojac veci ili jednak [tex]n[/tex]. Ako nije, resetiras brojac, povecas [tt]m[/tt] za jedan i ponovis pricu.[/quote]
dosta spor.Već ako upišem broj 7 mu treba više od minute da izvrti to sve.
Koliko će nama za prolazak na kolokviju igrati ulogu brzina programa?Govorim za zadatak 12.Riješio sam ga na dva načina i moram priznati da je ''moj'' algoritam ali i ovaj algoritam:
| vsego (napisa): |
| BlameGame (napisa): | | Moze netko pliz 12.?? |
for-petlja u kojoj neki k ide od 1, pa dok je 2 * k * k ⇐ m. Time osiguras da je prvi sumand ([tex]k^2[/tex]) kvadrat prirodnog broja i da je manji od drugog, cime sprijecis ponavljanje parova. Ostaje provjeriti da je [tex]m - k^2[/tex] potpuni kvadrat, sto mozes rastavom na proste faktore (umjesto ispisa faktora, brojis koliko se puta svaki pojavio; broj je potpuni kvadrat ako se svi pojave parno mnogo puta). Ako je [tex]m - k^2[/tex] potpuni kvadrat, povecas odgovarajuci brojac.
Na kraju petlje, vidis je li brojac veci ili jednak [tex]n[/tex]. Ako nije, resetiras brojac, povecas m za jedan i ponovis pricu. |
dosta spor.Već ako upišem broj 7 mu treba više od minute da izvrti to sve.
|
|
| [Vrh] |
|
kobila krsto
Forumaš(ica)
Pridružen/a: 02. 07. 2009. (16:55:08)
Postovi: (6A)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 1:47 sub, 1. 12. 2012 Naslov: |
|
|
|
[quote="Popara"]Koliko će nama za prolazak na kolokviju igrati ulogu brzina programa?Govorim za zadatak 12.Riješio sam ga na dva načina i moram priznati da je ''moj'' algoritam ali i ovaj algoritam:
[quote="vsego"][quote="BlameGame"]Moze netko pliz 12.??[/quote]
[tt]for[/tt]-petlja u kojoj neki [tt]k[/tt] ide od 1, pa dok je [tt]2 * k * k <= m[/tt]. Time osiguras da je prvi sumand ([tex]k^2[/tex]) kvadrat prirodnog broja i da je manji od drugog, cime sprijecis ponavljanje parova. Ostaje provjeriti da je [tex]m - k^2[/tex] potpuni kvadrat, sto mozes rastavom na proste faktore (umjesto ispisa faktora, brojis koliko se puta svaki pojavio; broj je potpuni kvadrat ako se svi pojave parno mnogo puta). Ako je [tex]m - k^2[/tex] potpuni kvadrat, povecas odgovarajuci brojac.
Na kraju petlje, vidis je li brojac veci ili jednak [tex]n[/tex]. Ako nije, resetiras brojac, povecas [tt]m[/tt] za jedan i ponovis pricu.[/quote]
dosta spor.Već ako upišem broj 7 mu treba više od minute da izvrti to sve.[/quote]
Nisam bas siguran da si dobro shvatio ideju, jer meni taj algoritam za [tt]n = 7[/tt] radi ispod sekunde. Za [tt]n = 11[/tt] mu treba cca pola minute da dodje do broja 160225:
[code:1]$ gcc t.c && time echo 11 | ./a.out
m = 160225
1. 160225 = 225 + 160000 = 15^2 + 400^2
2. 160225 = 1024 + 159201 = 32^2 + 399^2
3. 160225 = 5776 + 154449 = 76^2 + 393^2
4. 160225 = 6561 + 153664 = 81^2 + 392^2
5. 160225 = 12769 + 147456 = 113^2 + 384^2
6. 160225 = 19600 + 140625 = 140^2 + 375^2
7. 160225 = 30625 + 129600 = 175^2 + 360^2
8. 160225 = 33489 + 126736 = 183^2 + 356^2
9. 160225 = 46656 + 113569 = 216^2 + 337^2
10. 160225 = 51984 + 108241 = 228^2 + 329^2
11. 160225 = 63504 + 96721 = 252^2 + 311^2
real 0m32.588s
user 0m32.557s
sys 0m0.006s[/code:1]
Za znatizeljne, evo i koda, s dodanim ispisom svih trazenih suma (taj dio nije dio zadatka, ali je koristan za provjeru rjesenja):
[code:1]#include <stdio.h>
int main(void) {
unsigned n, i, cnt;
unsigned n1array[17], n2array[17];
unsigned long m, m2;
scanf("%d", &n);
if (n > 17) {
printf("E, pretjer'o si...\n");
return 1;
}
m = 2 * n * n;
while (1) {
unsigned long n1, n12, m2 = m / 2, n2 = m;
cnt = 0;
for (n1 = 1; (n12 = n1 * n1) < m2; n1++) {
unsigned long n22 = m - n12, tmp;
while ((tmp = n2 * n2) > n22) n2--;
if (tmp == n22) {
n1array[cnt] = n1;
n2array[cnt] = n2;
if (++cnt >= n) break;
}
}
if (cnt >= n) break;
m++;
}
printf("m = %lu\n", m);
for (i = 0; i < cnt; i++)
printf(" %2d. %lu = %lu + %lu = %lu^2 + %lu^2\n", i+1, m, n1array[i]*n1array[i], n2array[i]*n2array[i], n1array[i], n2array[i]);
return 0;
}[/code:1]
Istini za volju, ima ovdje jos optimizacija koje nisam prije spominjao. Sitnica su koristenje pomocnih varijabli, da izbjegnem vise puta racunanje istih kvadrata. Vjerojatno veci stos je resetiranje varijable [tt]n2[/tt] samo kad se [tt]m[/tt] mijenja. Logika je jednostavna: dok [tt]n1[/tt] raste, [tt]n2[/tt] moze samo padati, pa nema potrebe da ga resetiram za svaki [tt]n1[/tt]. IMO, ocito, ali svejedno naglasavam.
Takodjer, [tt]m[/tt] krece od [tt]2 * n * n[/tt], jer jednostavno ne moze biti manji. To je vrijednost koju bi dobili za
[tex]1^2+x_1^2, 2^2 + x_2^2, \dots, n^2+x_n^2[/tex],
dakle, kad bi svi [tex]n_1 \in \{1,2,\dots,n\}[/tex] dali rezultat (sto nece, ali [b]JE[/b] razumna donja ograda). Posto je [tex]n_1 \le n_2[/tex], to je [tex]x_n \ge n[/tex], pa je i [tex]m \ge n^2+x_n^2 \ge 2n^2[/tex].
Ljubitelji matematike su vjerojatno i sami primijetili ove detalje. ;)
Brzina se na prakticnim kolokvijima nije bas previse gledala dok sam ja bio na kolegiju, ali naravno da stvar mora zavrsiti u konacnom vremenu. Vjerujem da ce test-primjeri biti razumni i da se ne ocekuje da slazete bas kodove poput ovog mog.
P.S. Moje racunalo je cca 3 godine staro, tako da sigurno nije 60+ puta brze od onoga na cemu vi isprobavate, sto znaci da moja dobra vremena ne dolaze odavde. :D
| Popara (napisa): | Koliko će nama za prolazak na kolokviju igrati ulogu brzina programa?Govorim za zadatak 12.Riješio sam ga na dva načina i moram priznati da je ''moj'' algoritam ali i ovaj algoritam:
| vsego (napisa): | | BlameGame (napisa): | | Moze netko pliz 12.?? |
for-petlja u kojoj neki k ide od 1, pa dok je 2 * k * k ⇐ m. Time osiguras da je prvi sumand ([tex]k^2[/tex]) kvadrat prirodnog broja i da je manji od drugog, cime sprijecis ponavljanje parova. Ostaje provjeriti da je [tex]m - k^2[/tex] potpuni kvadrat, sto mozes rastavom na proste faktore (umjesto ispisa faktora, brojis koliko se puta svaki pojavio; broj je potpuni kvadrat ako se svi pojave parno mnogo puta). Ako je [tex]m - k^2[/tex] potpuni kvadrat, povecas odgovarajuci brojac.
Na kraju petlje, vidis je li brojac veci ili jednak [tex]n[/tex]. Ako nije, resetiras brojac, povecas m za jedan i ponovis pricu. |
dosta spor.Već ako upišem broj 7 mu treba više od minute da izvrti to sve. |
Nisam bas siguran da si dobro shvatio ideju, jer meni taj algoritam za n = 7 radi ispod sekunde. Za n = 11 mu treba cca pola minute da dodje do broja 160225:
| Kod: | $ gcc t.c && time echo 11 | ./a.out
m = 160225
1. 160225 = 225 + 160000 = 15^2 + 400^2
2. 160225 = 1024 + 159201 = 32^2 + 399^2
3. 160225 = 5776 + 154449 = 76^2 + 393^2
4. 160225 = 6561 + 153664 = 81^2 + 392^2
5. 160225 = 12769 + 147456 = 113^2 + 384^2
6. 160225 = 19600 + 140625 = 140^2 + 375^2
7. 160225 = 30625 + 129600 = 175^2 + 360^2
8. 160225 = 33489 + 126736 = 183^2 + 356^2
9. 160225 = 46656 + 113569 = 216^2 + 337^2
10. 160225 = 51984 + 108241 = 228^2 + 329^2
11. 160225 = 63504 + 96721 = 252^2 + 311^2
real 0m32.588s
user 0m32.557s
sys 0m0.006s |
Za znatizeljne, evo i koda, s dodanim ispisom svih trazenih suma (taj dio nije dio zadatka, ali je koristan za provjeru rjesenja):
| Kod: | #include <stdio.h>
int main(void) {
unsigned n, i, cnt;
unsigned n1array[17], n2array[17];
unsigned long m, m2;
scanf("%d", &n);
if (n > 17) {
printf("E, pretjer'o si...\n");
return 1;
}
m = 2 * n * n;
while (1) {
unsigned long n1, n12, m2 = m / 2, n2 = m;
cnt = 0;
for (n1 = 1; (n12 = n1 * n1) < m2; n1++) {
unsigned long n22 = m - n12, tmp;
while ((tmp = n2 * n2) > n22) n2--;
if (tmp == n22) {
n1array[cnt] = n1;
n2array[cnt] = n2;
if (++cnt >= n) break;
}
}
if (cnt >= n) break;
m++;
}
printf("m = %lu\n", m);
for (i = 0; i < cnt; i++)
printf(" %2d. %lu = %lu + %lu = %lu^2 + %lu^2\n", i+1, m, n1array[i]*n1array[i], n2array[i]*n2array[i], n1array[i], n2array[i]);
return 0;
} |
Istini za volju, ima ovdje jos optimizacija koje nisam prije spominjao. Sitnica su koristenje pomocnih varijabli, da izbjegnem vise puta racunanje istih kvadrata. Vjerojatno veci stos je resetiranje varijable n2 samo kad se m mijenja. Logika je jednostavna: dok n1 raste, n2 moze samo padati, pa nema potrebe da ga resetiram za svaki n1. IMO, ocito, ali svejedno naglasavam.
Takodjer, m krece od 2 * n * n, jer jednostavno ne moze biti manji. To je vrijednost koju bi dobili za
[tex]1^2+x_1^2, 2^2 + x_2^2, \dots, n^2+x_n^2[/tex],
dakle, kad bi svi [tex]n_1 \in \{1,2,\dots,n\}[/tex] dali rezultat (sto nece, ali JE razumna donja ograda). Posto je [tex]n_1 \le n_2[/tex], to je [tex]x_n \ge n[/tex], pa je i [tex]m \ge n^2+x_n^2 \ge 2n^2[/tex].
Ljubitelji matematike su vjerojatno i sami primijetili ove detalje.
Brzina se na prakticnim kolokvijima nije bas previse gledala dok sam ja bio na kolegiju, ali naravno da stvar mora zavrsiti u konacnom vremenu. Vjerujem da ce test-primjeri biti razumni i da se ne ocekuje da slazete bas kodove poput ovog mog.
P.S. Moje racunalo je cca 3 godine staro, tako da sigurno nije 60+ puta brze od onoga na cemu vi isprobavate, sto znaci da moja dobra vremena ne dolaze odavde.
_________________ 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] |
|
kikota
Forumaš(ica)
Pridružen/a: 25. 09. 2011. (17:09:30)
Postovi: (22)16
Spol:
Lokacija: Dalmacijaa <3
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
| [Vrh] |
|
briemann0
Forumaš(ica)
Pridružen/a: 12. 10. 2012. (18:45:05)
Postovi: (5)16
Spol:
|
| Postano: 22:31 sub, 1. 12. 2012 Naslov: |
|
|
|
[quote="vsego"]
[code:1]#include <stdio.h>
int main(void) {
unsigned n, i, cnt;
unsigned n1array[17], n2array[17];
unsigned long m, m2;
scanf("%d", &n);
if (n > 17) {
printf("E, pretjer'o si...\n");
return 1;
}
m = 2 * n * n;
while (1) {
unsigned long n1, n12, m2 = m / 2, n2 = m;
cnt = 0;
for (n1 = 1; (n12 = n1 * n1) < m2; n1++) {
unsigned long n22 = m - n12, tmp;
while ((tmp = n2 * n2) > n22) n2--;
if (tmp == n22) {
n1array[cnt] = n1;
n2array[cnt] = n2;
if (++cnt >= n) break;
}
}
if (cnt >= n) break;
m++;
}
printf("m = %lu\n", m);
for (i = 0; i < cnt; i++)
printf(" %2d. %lu = %lu + %lu = %lu^2 + %lu^2\n", i+1, m, n1array[i]*n1array[i], n2array[i]*n2array[i], n1array[i], n2array[i]);
return 0;
}[/code:1]
[/quote]
Vjerujem da za [tex]n=2[/tex] treba biti [tex]50=1^2+7^2=5^2+5^2[/tex], a ne [tex]65[/tex], jer je [tex]x_1 \leq x_2[/tex].
A evo i moga rješenja 12. zadatka (sa nepotrebnim ispisom) koje je, čak i dosta brzo. Pa ako kome pomogne, super.
[code:1]#include <stdio.h>
#include <math.h>
unsigned long n,l;
unsigned long g(unsigned long i){
unsigned long j, m=0; double s;
for(j=1;j*j<i;j++){
s=sqrt((double)(i-j*j));
if((unsigned long)s==s && s>=j) m++;
if(m==n) break;
} return m;
}
unsigned long f(unsigned long n){
unsigned long i;
for(i=2;;i++){
if(g(i)==n)break;
} return i;
}
void p(unsigned long l){
unsigned long i,k=0; double s;
for(i=1;i*i<l;i++){s=sqrt(l-i*i);
if((unsigned long)s==s && s>=i){k++;
printf("\t%lu. %lu = %lu + %lu = %lu^2 + %lu^2\n",k,l,i*i,(unsigned long)s*(unsigned long)s,i,(unsigned long)s);
if(k==n) break;
}
}
}
int main(void){
scanf("%lu", &n); l=f(n);
printf("m=%lu\n",l); p(l);
return 0;
}[/code:1]
Za [tex]n=11[/tex] dobijem:
[code:1]$ gcc 012.c -lm && time echo 11 | ./a.out
m=160225
1. 160225 = 225 + 160000 = 15^2 + 400^2
2. 160225 = 1024 + 159201 = 32^2 + 399^2
3. 160225 = 5776 + 154449 = 76^2 + 393^2
4. 160225 = 6561 + 153664 = 81^2 + 392^2
5. 160225 = 12769 + 147456 = 113^2 + 384^2
6. 160225 = 19600 + 140625 = 140^2 + 375^2
7. 160225 = 30625 + 129600 = 175^2 + 360^2
8. 160225 = 33489 + 126736 = 183^2 + 356^2
9. 160225 = 46656 + 113569 = 216^2 + 337^2
10. 160225 = 51984 + 108241 = 228^2 + 329^2
11. 160225 = 63504 + 96721 = 252^2 + 311^2
real 0m1.342s
user 0m1.340s
sys 0m0.000s
[/code:1]
| vsego (napisa): |
| Kod: | #include <stdio.h>
int main(void) {
unsigned n, i, cnt;
unsigned n1array[17], n2array[17];
unsigned long m, m2;
scanf("%d", &n);
if (n > 17) {
printf("E, pretjer'o si...\n");
return 1;
}
m = 2 * n * n;
while (1) {
unsigned long n1, n12, m2 = m / 2, n2 = m;
cnt = 0;
for (n1 = 1; (n12 = n1 * n1) < m2; n1++) {
unsigned long n22 = m - n12, tmp;
while ((tmp = n2 * n2) > n22) n2--;
if (tmp == n22) {
n1array[cnt] = n1;
n2array[cnt] = n2;
if (++cnt >= n) break;
}
}
if (cnt >= n) break;
m++;
}
printf("m = %lu\n", m);
for (i = 0; i < cnt; i++)
printf(" %2d. %lu = %lu + %lu = %lu^2 + %lu^2\n", i+1, m, n1array[i]*n1array[i], n2array[i]*n2array[i], n1array[i], n2array[i]);
return 0;
} |
|
Vjerujem da za [tex]n=2[/tex] treba biti [tex]50=1^2+7^2=5^2+5^2[/tex], a ne [tex]65[/tex], jer je [tex]x_1 \leq x_2[/tex].
A evo i moga rješenja 12. zadatka (sa nepotrebnim ispisom) koje je, čak i dosta brzo. Pa ako kome pomogne, super.
| Kod: | #include <stdio.h>
#include <math.h>
unsigned long n,l;
unsigned long g(unsigned long i){
unsigned long j, m=0; double s;
for(j=1;j*j<i;j++){
s=sqrt((double)(i-j*j));
if((unsigned long)s==s && s>=j) m++;
if(m==n) break;
} return m;
}
unsigned long f(unsigned long n){
unsigned long i;
for(i=2;;i++){
if(g(i)==n)break;
} return i;
}
void p(unsigned long l){
unsigned long i,k=0; double s;
for(i=1;i*i<l;i++){s=sqrt(l-i*i);
if((unsigned long)s==s && s>=i){k++;
printf("\t%lu. %lu = %lu + %lu = %lu^2 + %lu^2\n",k,l,i*i,(unsigned long)s*(unsigned long)s,i,(unsigned long)s);
if(k==n) break;
}
}
}
int main(void){
scanf("%lu", &n); l=f(n);
printf("m=%lu\n",l); p(l);
return 0;
} |
Za [tex]n=11[/tex] dobijem:
| Kod: | $ gcc 012.c -lm && time echo 11 | ./a.out
m=160225
1. 160225 = 225 + 160000 = 15^2 + 400^2
2. 160225 = 1024 + 159201 = 32^2 + 399^2
3. 160225 = 5776 + 154449 = 76^2 + 393^2
4. 160225 = 6561 + 153664 = 81^2 + 392^2
5. 160225 = 12769 + 147456 = 113^2 + 384^2
6. 160225 = 19600 + 140625 = 140^2 + 375^2
7. 160225 = 30625 + 129600 = 175^2 + 360^2
8. 160225 = 33489 + 126736 = 183^2 + 356^2
9. 160225 = 46656 + 113569 = 216^2 + 337^2
10. 160225 = 51984 + 108241 = 228^2 + 329^2
11. 160225 = 63504 + 96721 = 252^2 + 311^2
real 0m1.342s
user 0m1.340s
sys 0m0.000s
|
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 22:53 sub, 1. 12. 2012 Naslov: |
|
|
|
[quote="briemann0"]Vjerujem da za [tex]n=2[/tex] treba biti [tex]50=1^2+7^2=5^2+5^2[/tex], a ne [tex]65[/tex], jer je [tex]x_1 \leq x_2[/tex].[/quote]
U pravu si. Ja sam uzeo da je [tex]n_1 < n_2[/tex]. Ispravni kod treba imati [tt]<=[/tt] umjesto [tt]<[/tt] u ovoj liniji:
[code:1] for (n1 = 1; (n12 = n1 * n1) <= m2; n1++) {[/code:1]
Hvala na ispravci. :karma:
Usput, [tt]sqrt()[/tt] je los izbor jer se, zbog konacnosti aritmetike racunala, moze desiti da daje gresku. Nesto u stilu da [tt]sqrt(49)[/tt] vrati 6.99999. Nece se desiti na tako malim brojevima, ali ne znam ima li neku internu zastitu da se ne desi na vecim brojevima. Opcenito, cjelobrojne algoritme je zdravo drzati na cjelobrojnoj aritmetici.
| briemann0 (napisa): | | Vjerujem da za [tex]n=2[/tex] treba biti [tex]50=1^2+7^2=5^2+5^2[/tex], a ne [tex]65[/tex], jer je [tex]x_1 \leq x_2[/tex]. |
U pravu si. Ja sam uzeo da je [tex]n_1 < n_2[/tex]. Ispravni kod treba imati ⇐ umjesto < u ovoj liniji:
| Kod: | | for (n1 = 1; (n12 = n1 * n1) <= m2; n1++) { |
Hvala na ispravci. 
Usput, sqrt() je los izbor jer se, zbog konacnosti aritmetike racunala, moze desiti da daje gresku. Nesto u stilu da sqrt(49) vrati 6.99999. Nece se desiti na tako malim brojevima, ali ne znam ima li neku internu zastitu da se ne desi na vecim brojevima. Opcenito, cjelobrojne algoritme je zdravo drzati na cjelobrojnoj aritmetici.
_________________ 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] |
|
|
