Fórum Ubuntu CZ/SK
Ubuntu pro osobní počítače => Software => Příkazový řádek a programování pro GNU/Linux => Téma založeno: SIGSEGV 31 Prosince 2010, 07:21:40
-
zdravim,
Myslim, ze komentar v kodu nepotrebuje dalsi vysvetleni ..
pripominam jen, ze se mi nechtelo delat bsearch(), proto to linearni vyhledavani stejne jako nedelani nejakeho map|table|hash ..
dale pripominam, ze pro L ocekavame korektni data, vzesla z predpokladaneho zpusobu inkrementu n .. (proto int a ne float|double)
pro matematiky ale neprogramatory: sqrt() == odmocnina, pow() == mocnina
otazka tedy zni: dokaze nekdo vyjadrit ciste aritmeticky n=?, pripadne ubastlit nejaky algoritmus pro bisection_method kterej to zefektivni ? (http://en.wikipedia.org/wiki/Bisection_method a http://en.wikipedia.org/wiki/Secant_method)
/* sample example: `gcc -o foo bar -lm`
* having inane equation n(n+sqrt(n))=L where:
* n increments as m=1; n=(++m)**2 .. so only integers are used
* the highest value of sqrt(n) is FF (255) so n could be up to 255**2
*
* you're getting L and need to determine n
* in example below we increment n and break() until we reach equality with L
*
* well, this code uses linear search which is NOT definitely very optimal
* foo() also requires that only correct L will be passed ..
*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
long foo(long long L)
{
long m, n, e;
m = n = 1;
e = pow(255, 2);
for(n = 1; n <= e; n = pow(++m, 2)) {
if(n * (n + sqrt(n)) == L)
break;
};
return(n);
}
int main(void)
{
printf("%ld\n", foo(2439853704)); /* L value is hardcoded here .. */
exit(0);
}
diky, 11
ps. overovat muzete napriklad takto:
# perl -Mbigint -e '$n=222**2; print $n*($n+sqrt($n)), " $n\n"'
2439853704 49284
pps. je to jenom priklad kodu, ktery resi opisem to, co by se melo resit aritmeticky .. samotny kod neni dulezity, stejne jako linearni|binarni vyhledavani ... to co je zajimave je bud prime vyjadreni n= a nebo bisection_metoda (a^4 + a^3 IMO)
-
mno, analyticky to sice resit jde, ale asi te to moc nepotesi... http://www.wolframalpha.com/input/?i=x^2%2Bx^%283%2F2%29%3Dn :)
jinak inkrementovat to n od 0 je pro vyssi cisla docela hloupe, mnohem lepsi mas zacit dekrementovat od odmocniny z L
a v pripade, ze chces pocitat jen pro n z intervalu <0,255>, tak naprosto nechapu co resis, kdyz si muzes predem vsechny vysledky vyplivnout do souboru, ktery muzes nasledne grepovat temi svymi zadanymi L...
P.S.:
tvrzeni v komentari, ze se pouzivaji jen itegery je naprosto mimo, protoze pouzivas funkce sqrt a pow... (klidne si to zkus dissassemblovat)
-
no, jestli nechces to analyticke reseni z wolframalpha, tak bude asi opravdu nejjednodussi pouzit to puleni intervalu, jako vychozi horni hranici muzes pouzit tu odmocninu z L a jako dolni hranici treba odmocninu z L/2 (to bude platne jen pro priblizne n>=1)
reseni napr tady - nezkousel jsem ani zkompilovat ale na pohled to vypada dobre... (pozor bude fungovat jen pro L>2 a z vrchu to bude omezeno vlastnostmi double)
double bisect(double L) {
double horni, dolni , stred;
horni = pow(L,0.5);
dolni = pow(L/2,0.5);
stred= dolni;
#define POZADOVANAPRESNOST 0.01
while ( (horni-dolni)> POZADOVANAPRESNOST )
stred = (horni-dolni)/2+dolni;
if ((pow(stred,2)+pow(stred,1.5))>L) {
horni=stred;
}
else {
dolni=stred;
}
}
return stred;
}
-
protože to tak není, jenom zaokrouhluješ na celý čísla
$ perl -Mbigint -E '$n=333**2; say $n*($n+sqrt($n))'
12333296358
$ , "sqrt(pow(12333296358,0.25)^2)"
333.2497189606259215505959496500707673843419867626453155931505670117
$ , 333^4
12296370321
$ , "sqrt(pow(12296370321,0.25)^2)"
332.9999999999999999999999999999999999999999999999999999999999999772
mám jednoduchou kalkulačku s bc
-
nechapu jak je to mozny ale mam to vyreseny:
prosim o vysvetleni proc u:
n(n+sqrt(n))=L === m4+m3=L
n=int(L**(1/4))
vcera jsem to tu necetl zrovna pozorne, takze k tomu, ze je to m^4+m^3=L (bral jsem to tak, ze n je obecne a tudiz je to celkove n^2+n^1.5=L )
vysvetleni proc oriznuti funguje je celkem jednoduche (ale na limity jsem si vcera ani nevzpomnel):
vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)
to oriznuti na cela cisla by melo fungovat pro vsechna takova m, ze m^4+m^3<(m+1)^4 (no, pro zaporna m je to samozrejme blbost (L^(1/4)>0) a to orezavani se podela i na casti intervalu (0,1) (pro m<1 a zaroven m^4+m^3>1), tzn zajimaji-li te jen kladna cela cisla, tak to funguje vsude
EDIT: vyse uvedene je z vetsiny hloupost, nechavam to tu pro ilustraci toho, jake hlouposti muze nekdy napsat i inteligentni clovek a take toho, ze zaobalime-li spravne jadro ( tzn fakt, ze m^4 =< m^4+m^3 < (m+1)^4 ) do hromady hloupych kecu, tak ostatni nemusi to jadro ani najit...)
-
vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)
IMO:
pri m jdoucim k nekonecnu se L limitne blizi nekonecnu taky, ne m^4 :)
take napr. jiz pro rovnici m^4+100*m^3+299=L neplati, ze m=int(L^(1/4)), pro libovolne cele kladne m, takze se to neda takto zobecnit (ty parametry 100 a 299 tam mam jen pro zjednoduseni vypoctu, urcite by sly najit i nejake mensi)
dale technicka poznamka: nejedna se o kvadratickou, ale kvartickou rovnici
nakonec otazka: kde na takovato zadani chodite? :)
-
vliv m^3 je ve srovnani s m^4 cim dal tim zanedbatelnejsi (pri m jdoucim k nekonecnu se L limitne blizi hodonote m^4), takze se da rict m^4~=L => |m|~=L^(1/4)
IMO:
pri m jdoucim k nekonecnu se L limitne blizi nekonecnu taky, ne m^4 :)
take napr. jiz pro rovnici m^4+100*m^3+299=L neplati, ze m=int(L^(1/4)), pro libovolne cele kladne m, takze se to neda takto zobecnit (ty parametry 100 a 299 tam mam jen pro zjednoduseni vypoctu, urcite by sly najit i nejake mensi)
1. ostavec:
to je to same
2. odstavec:
nevytrhavej to z kontextu, pro tebou uvedeny vyraz je jasne, ze to platit nebude, protoze neni pravda, ze m^4+100*m^3+299<(m+1)^4 (opet ma smysl bavit se jen o kladnych cislech)
EDIT: omlouvam se za lehce utocny ton, uznavam, ze citovany post byl napsan hloupe (viz jeho editace), takze proniknout k jadru pudla mohl byt nadlidsky vykon
-
Výraz (x4+x3)0,25 - (x4)0,25 (http://www.wolframalpha.com/input/?i=pow%28pow%28x%2C4%29%2Bpow%28x%2C3%29%2C0.25%29+-+pow%28pow%28x%2C4%29%2C0.25%29) nikdy nedosáhne vysokých hodnot, limitně se blíží 1/4. Něco o limitě v každý středoškolský učebnici matematiky :P
-
vzhledem k tomu, ze limity uz jsem prakticky zapomnel, tak jeste jednou (a lepe (a taky bez limit (a aby to pripadne pochopil i clovek s 3 promilemi v krvi* )))
m^4 = L <=> L^0.25 = m
(m+1)^4 = K <=> K^0.25 = m+1
kdyz budu predpokladat, ze m je cele cislo a misto 1 prictu cokoliv mensiho (napr. 0.99), tak
(m+0.99)^4 = K <=> K^0.25 = m+0.99
nic se samozrejme nezmenilo, ale vezmu-li rovnici
K^0.25 = m+0.99 a provedu pro obe strany oriznuti na celou cast, zjistim, ze
int(K^0.25) = m a tedy int( ((m+0.99)^4)^0.25 ) = m
--------------------------------------------------------------------------------------------
z vyse uvedeneho by kazdemu melo byt alespon intuitivne jasne (intuitivne celkem staci, protoze jak se rika, "matematiku nepochopis, na tu si zvyknes") ze plati:
int( ((m+z)^4)^0.25 ) = m (pro z z intervalu <0,1) a cele m )
a tedy, vzhledem k tomu, ze m^4+m^3 je mensi nez (m+1)^4 (na prvni pohled mozna neni videt, ale po roznasobeni :
(m+1)^4=m^4+4m^3+6m^2+4m+1
je to zrejme) plati, ze pro cele m bude vzdy platit int( ((m^4+m^3)^0.25 ) = m
---------------------------------------------------------------------------------------------
* budu vdecny za experimetalni vyzkouseni...
-
uff... rozhodne jednodussi nez ta limita... pacholika bych poprosil, jestli by mi mohl naznacit, jak tuto limitu obecne vyresit pouze pomoci znalosti stredoskolske matematiky ;)
mne z podminky (viz MacHala)
m4+m3 < (m+1)4
po uprave vychazi
3m3+6m2+4m+1 > 0, coz je trivialne splneno pro vsechna prirozena m (tim je dukaz ukoncen (za strizliva tedy) :) )
pro zajimavost jiz pro vyraz m4+5m3 tato podminka obecne neplati, neni tedy mozne psatpow(m, 4) + 5 * pow(m, 3) = L <=====> (int) pow(L, 0.25) = m