Diskuze: N-tá mocnina

Člen

Zobrazeno 14 zpráv z 14.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
Upraveno dne 07.01.2011 13:30:53 administrátorem.<br />Ahoj,
nejspíše na to bude nějaká fce ale určitě se podívej na následující
algoritmus třebas ti pomůže jsou tam fce +,-,*,/, mocniny a odmocniny.
http://itnetwork.cz/index.php?…
Dobrý den,
pokud myslíte n-tou mocninu (vzápětí zmiňujete i odmocninu, to mě trochu
mate) a myslíte ji s celočíselným a kladným exponentem (x5
třeba), je to přece velmi jednoduché.
V tomto případě se X = X * X * X * X * X (těch X tam je 5, protože X je
na pátou). Celé to můžeme ještě rozepsat do několika stejných kroků,
přičemž každý krok bude pracovat již z výsledkem kroku minulého:
X = X * X (na druhou)
X = X * X (na třetí)
X = X * X (na čtvrtou)
X = X * X (na pátou)
Nyní vidíme, že operací jsme provedli o jednu méně - pro X na pátou jen 4, čili pro X na n-tou provedeme n-1 operací (protože X na prvou je již rovnou X a proto musíme první krok vynechat). Na to je FOR cyklus jako stvořený.
Kód bude vypadat následovně:
// 2 na patou:
x:=2; // zaklad mocniny
n:=5; // exponent
for i:=1 to (n - 1) do
x:=x * x;
// Po provedeni cyklu je v promenne X hodnota 32
Podrobnější vysvětlení a řešení i pro jiné, než přirozené exponenty naleznete zde: http://itnetwork.cz/index.php?…
Zdravím,
postupné mocnění (například pomocí for-cyklu) je rozumné použít pro malá čísla (základy) a exponenty. Pro větší případy (například pokud byste chtěli implementovat aritmetiku nad celými čísly delšími než Int64, ale i u něj už by to asi stálo za zváženou) se už nevyplácí, protože vyžaduje velké množství násobení. Například pokud bych počítal 320, musel bych provést 20 násobení. Přitom by jich stačilo mnohem méně.
Fígl je právě v tom pamatovat si, co už jsme spočítali dříve. Můžeme si nejprve rozložit exponent (v našem případě 20) na součet mocnin dvojky (v našem případě 20 = 24 + 22 = 16 + 4). Výsledek je součinem základů umocněných na tyto exponenty (v našem případě 320 = 34 * 316).
Tedy při výpočtu N-té celočíselné mocniny můžeme postupovat takto:
Mocniny[0] := 0;
Mocniny[1] := a;
Tmp := a;
For i := 2 To 32 Do
begin
Tmp := Tmp * Tmp; // Tady je hlavní trik
Mocniny[i] = Tmp;
end;
(v poli Mocniny[i] se bude nacházev výsledek a^(2^i). Obsah tohoto pole stačí pak spolu pronásobit podle dvojkového rozkladu exponentu a máme výsledek. Pro náš příklad 320 to vychází jako asi 5 násobení (4 násobení pro výpočet 3^(22) a 3^(24) a jedno pro jejich součin).
Nezapomínejte, že třeba v asymetrické kryptografii se používají daleko větší čísla (třeba v řádu 21024, což je přibližně řád 10300, tedy 300ciferná čísla) by takové násobení for-cyklem bylo hrozně pomalé (obvykle se totiž nějaké veliké číslo může nacházet i v exponentu). Kdežto při použití myšlenky kodu výše to je časově zvládnutelné (provede se pouze přibližně logaritmický počet násobení k velikosti exponentu).
Mocnění neceločíselným exponentem, odmocňování:
Zde lze využít vlastností funkce logaritmu (třeba přirozeného, ale je to
jedno). Protože platí:
a^b = e^(b * ln a)
v Delphi pak lze funkci mocniny napsat nějak takto:
Function Mocnina(a:Double; e:Double):Double;
begin
Result := exp (e * ln ( a ) );
end;
Tím tedy můžeme mocnit "reálným" číslem a také dělat odmocniny. Protože N-tá odmocnina z čísla a = a^(1/N). Problém samozřejmě může být v rozsahu datového typu, kterým jsou simulována reálná čísla a možných zaokrouhlovacích chybách.
Naincluduj si knihovnu Math (Uses Math), potom můžeš normálně používat funkci Power(zaklad, exponent).
Využití logaritmu je dobrý nápad, koukal jsem do Delfín a mají to tak
také sami udělané
Nemate prosím nejaký link k stiahnutiu tej kniznice?
Knihovna Math je standardně v Delphi, kdyby tam nebyla, nepsal bych naincluduj si, ale stáhni si.
Řešil jsem to takto:
program mocniny;
var cislo,vysledek,pomocne,n:integer;
begin
writeln('Program na vypocet mocnin.');
write('Zadejte cislo: ');
readln(cislo);
write('Zadejte exponent: ');
readln(n);
vysledek := cislo;
for pomocne := 1 to n-1 do
begin
vysledek := vysledek * cislo;
end;
writeln('Vysledek je: ',vysledek);
readln();
end.
Zdá se ti na tom něco špatně? Jen jeden negativní ohlas na můj kód a tuším, že nejspíš od tebe. Proč?
Zobrazeno 14 zpráv z 14.