|
Serwis Edukacyjny w I-LO w Tarnowie 
Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek
|
|
Serwis Edukacyjny w I-LO w Tarnowie
Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek
|
ProblemZnaleźć kwadratowy pierwiastek całkowity nieujemnej liczby rzeczywistej x. Całkowity pierwiastek kwadratowy (ang. integer square root) jest największą liczbą całkowitą p, która spełnia nierówność: p2 ≤ x |
Problem możemy rozwiązać następująco.
Tworzymy ciąg kwadratów kolejnych liczb całkowitych począwszy
02 12 22 32 … i2
do momentu, gdy dla pewnego i otrzymamy spełnioną
nierówność
Pozostaje do rozwiązania efektywny sposób tworzenia kwadratów kolejnych liczb całkowitych. Wypiszmy kilkanaście początkowych wyrazów tego ciągu:
i
|
i2 |
0 |
0 |
1 |
1 |
2 |
4 |
3 |
9 |
4 |
16 |
5 |
25 |
6 |
36 |
7 |
49 |
8 |
64 |
9 |
81 |
10 |
100 |
11 |
121 |
12 |
144 |
… |
… |
Teraz policzmy ciąg różnic pierwszego rzędu:
r1i = i2-(i-1)2, dla i > 0.
Różnica pierwszego rzędu powstaje przez odjęcie od wyrazu
i-tego jego
poprzednika w ciągu, czyli wyrazu
i
|
i2
|
r1 |
0 |
0 |
– |
1 |
1 |
1 |
2 |
4 |
3 |
3 |
9 |
5 |
4 |
16 |
7 |
5 |
25 |
9 |
6 |
36 |
11 |
7 |
49 |
13 |
8 |
64 |
15 |
9 |
81 |
17 |
10 |
100 |
19 |
11 |
121 |
21 |
12 |
144 |
23 |
… |
… |
… |
Ciekawa rzecz – różnice pierwszego rzędu dla naszego ciągu tworzą ciąg kolejnych liczb nieparzystych. Teraz analogicznie utwórzmy ciąg różnic drugiego rzędu:
r2i = r1i-r1i(i-1), dla i > 1
Różnice drugiego rzędu powstają w analogiczny sposób z różnic pierwszego
rzędu, jak różnice pierwszego rzędu powstają z wyrazów ciągu
i
|
i2
|
r1 |
r2
|
0 |
0 |
– |
– |
1 |
1 |
1 |
– |
2 |
4 |
3 |
2 |
3 |
9 |
5 |
2 |
4 |
16 |
7 |
2 |
5 |
25 |
9 |
2 |
6 |
36 |
11 |
2 |
7 |
49 |
13 |
2 |
8 |
64 |
15 |
2 |
9 |
81 |
17 |
2 |
10 |
100 |
19 |
2 |
11 |
121 |
21 |
2 |
12 |
144 |
23 |
2 |
… |
… |
… |
… |
Różnice rzędu drugiego tworzą już ciąg stały o wyrazach równych 2. Nie ma sensu liczyć różnic wyższych rzędów, ponieważ otrzymamy tylko wyrazy równe 0. W tabelce na czerwono zaznaczyliśmy pierwsze wyrazy odpowiednio:
Mając te trzy wartości możemy rekurencyjnie konstruować ciąg kolejnych kwadratów:
a 0 = 0,r 1 = 1,r 2 = 2, gdziea 0 – pierwszy wyraz ciągu kwadratów
Dla
r 1i =r 1(i-1)+r 2 – kolejna różnica pierwszego rzędu powstaje z poprzedniej przez dodanie różnicy drugiego rzędu
a i =a i-1+r 1i – kolejny kwadrat powstaje z poprzedniego przez dodanie wyliczonej różnicy pierwszego rzędu
Zwróć uwagę, iż wykorzystujemy tylko dodawanie, dzięki czemu nasz algorytm jest szybki (dla małych liczb). Jednakże podany algorytm nie jest stosowany w praktyce do wyznaczania wartości pierwiastka kwadratowego. Podajemy go tutaj tylko ze względów dydaktycznych.
K01: a ← 0 ; pierwszy kwadrat 02 K02: r1 ← 1 ; początkowa wartość różnicy pierwszego rzędu K03: r2 ← 2 ; wartość różnic drugiego rzędu K04: i ← 0 ; numer pierwszego wyrazu K05: Dopóki a ≤ x, ; szukamy pierwszego wyrazu a większego od x wykonuj K06…K08 K06: a ← a+r1 ; następny kwadrat K07: r1 ← r1+r2 ; wyliczamy nową różnicę pierwszego rzędu K08: i ← i+1 ; następny numer K09: Zakończ z wynikiem i-1 ; obliczony pierwiastek całkowity
|
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
| W pierwszym wierszu program odczytuje liczbę x. Następnie wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim. Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka kwadratowego dla celów porównawczych. |
Pascal// Całkowity pierwiastek
// Data: 10.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------
program prg;
var
x : double;
i, a, r1, r2 : longword;
begin
readln(x);
a := 0;
r1 := 1;
r2 := 2;
i := 0;
while a <= x do
begin
inc(a, r1);
inc(r1, r2);
inc(i);
end;
dec(i);
writeln(i);
writeln(i*i);
writeln;
end. |
// Całkowity pierwiastek
// Data: 10.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------
#include <iostream>
using namespace std;
int main()
{
double x;
unsigned int i, a, r1, r2;
cin >> x;
a = 0;
r1 = 1;
r2 = 2;
for(i = 0; a <= x; i++)
{
a += r1;
r1 += r2;
}
i--;
cout << i << endl
<< i * i << endl
<< endl;
return 0;
} |
Basic' Całkowity pierwiastek ' Data: 10.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Dim As Double x Dim As Uinteger i, a, r1, r2 Input x a = 0 r1 = 1 r2 = 2 i = 0 While a <= x a += r1 r1 += r2 i += 1 Wend i -= 1 Print i Print i*i Print End |
Python
(dodatek)# Całkowity pierwiastek
# Data: 19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
x = float(input())
a, r1, r2, i = 0, 1, 2, 0
while a <= x:
a += r1
r1 += r2
i += 1
i -= 1
print(i)
print(i*i)
print()
|
| Wynik: |
135 11 121 |
Druga metoda znajdowania całkowitego pierwiastka kwadratowego pochodzi od Izaaka Newtona (chociaż podobną metodę stosowali już starożytni Babilończycy). Jeśli mamy pewne przybliżenie p pierwiastka liczby x, to lepsze przybliżenie otrzymamy stosując wzór:
p = (p+x/p)/2
Dlaczego to działa? Rozważmy dwa przypadki:
p < √x
Wtedy iloraz x/p jest większy od √x i po dodaniu go do p i podzieleniu sumy przez 2 otrzymamy liczbę większą od poprzedniego p, która przybliża się od dołu do rzeczywistego pierwiastka.
p > √x
Wtedy iloraz x/p jest mniejszy od √x i po dodaniu go do p i podzieleniu sumy przez 2 otrzymamy liczbę mniejszą od poprzedniego p, która przybliża się od góry do rzeczywistego pierwiastka.
Wynika z tego, iż w każdej iteracji otrzymujemy liczbę coraz bliższą wartości pierwiastka. Iterujemy dotąd, aż różnica pomiędzy dwoma kolejnymi przybliżeniami będzie mniejsza lub równa założonej dokładności ε – w przypadku pierwiastków całkowitych jest to 1.
K01: Jeśli x > 1, ; pierwiastki > 1 liczymy to idź do kroku K04 K02: p2 ← x ; inne nie K03: Idź do kroku K09 K04: p1 ← 0 ; zapewniamy |p1-p2| > 1 K05: p2 ← x shr 1 ; pierwsze przybliżenie pierwiastka K06: Dopóki |p1-p2| > 1: ; w pętli wyliczamy kolejne przybliżenia wykonuj kroki K07…K08 K07: p1 ← p2 ; zapamiętujemy bieżące przybliżenie K08: p2 ← (p2+x div p1) shr 1 ; wyliczamy nowe przybliżenie K09: Dopóki p2×p2 > x: ; jeśli przybliżenie było od góry, wykonuj p2 ← p2-1 ; zmniejszamy je K09: Zakończ z wynikiem p2
|
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
| W pierwszym wierszu program odczytuje liczbę x. Następnie wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim. Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka kwadratowego dla celów porównawczych. |
Pascal// Całkowity pierwiastek kwadratowy
// Data: 11.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------
program prg;
var
x, p1, p2 : longint;
begin
readln(x);
if x <= 1 then p2 := x
else
begin
p1 := 0;
p2 := x shr 1;
while abs(p1-p2) > 1 do
begin
p1 := p2;
p2 := (p2+x div p2) shr 1;
end;
while p2*p2 > x do dec(p2);
end;
writeln(p2);
writeln(p2*p2);
writeln;
end. |
// Całkowity pierwiastek kwadratowy
// Data: 11.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------
#include <iostream>
using namespace std;
int main()
{
int x, p1, p2;
cin >> x;
if(x <= 1) p2 = x;
else
{
p1 = 0; p2 = x >> 1;
while(abs(p1-p2) > 1)
{
p1 = p2;
p2 = (p2+x/p2) >> 1;
}
while(p2*p2 > x) --p2;
}
cout << p2 << endl
<< (p2*p2) << endl
<< endl;
return 0;
} |
Basic' Całkowity pierwiastek kwadratowy
' Data: 11.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------
Dim As Integer x, p1, p2
Input x
If x <= 1 Then
p2 = x
Else
p1 = 0: p2 = x Shr 1
While Abs (p1-p2) > 1
p1 = p2
p2 = (p2+x\p2) Shr 1
Wend
While p2*p2 > x: p2 -= 1: Wend
End If
Print p2
Print p2*p2
Print
End |
Python
(dodatek)# Całkowity pierwiastek kwadratowy
# Data: 19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
x = int(input())
if x <= 1:
p2 = x
else:
p1 = 0
p2 = x >> 1
while abs(p1-p2) > 1:
p1 = p2
p2 = (p2+x//p2) >> 1
while p2*p2 > x: p2 -= 1
print(p2)
print(p2*p2)
print()
|
Istnieje bardzo szybki algorytm wyznaczania wartości całkowitego pierwiastka kwadratowego, który wykorzystuje binarną reprezentację liczb – czyli idealnie nadaje się do zastosowania dla danych komputerowych, które przecież są liczbami binarnymi. Algorytm wywodzi się z chińskiego abakusa i nie wymaga skomplikowanych działań arytmetycznych – jedynie dodawania oraz przesuwania bitów. Dzięki tym zaletom może być z powodzeniem stosowany w prostych systemach mikrokontrolerów jednoukładowych.
K01: px ← 0 ; początkowa wartość pierwiastka K02: mb ← 1 shl 62 ; maska z ustawionym drugim najstarszym bitem K03: Dopóki mb > x: ; szukamy najstarszej potęgi 4, mniejszej od x wykonuj mb ← mb shr 2 K04: Dopóki mb ≠ 0: ; wyznaczamy kolejne bity pierwiastka wykonuj kroki K05…K09 K05: t ← px+mb ; łączymy bit maski z przybliżeniem pierwiastka K06: Jeśli x < t, ; sprawdzamy, czy dany bit ma być ustawiony. idź do kroku K09 K07: x ← x-t ; usuwamy bity z x K08: px ← t+mb ; dodajemy bit maski do px K09: px ← px shr 1 ; przesuwamy bity pierwiastka o 1 w prawo K09: mb ← mb shr 2 ; bity maski przesuwamy o 2 w prawo K10: Zakończ z wynikiem px
|
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
| W pierwszym wierszu program odczytuje liczbę x. Następnie wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim. Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka kwadratowego dla celów porównawczych. |
Pascal// Całkowity pierwiastek kwadratowy
// Data: 11.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------
program prg;
var
x, px, mb, t : qword;
begin
readln(x);
px := 0; mb := 1 shl 62;
while mb > x do
mb := mb shr 2;
while mb <> 0 do
begin
t := px+mb;
if x >= t then
begin
dec(x, t); px := t+mb;
end;
px := px shr 1;
mb := mb shr 2;
end;
writeln(px);
writeln(px*px);
writeln;
end. |
// Całkowity pierwiastek kwadratowy
// Data: 11.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------
#include <iostream>
using namespace std;
int main()
{
unsigned long long x, px, mb, t;
cin >> x;
px = 0; mb = 1; mb <<= 62;
while(mb > x) mb >>= 2;
while(mb)
{
t = px+mb;
if(x >= t)
{
x -= t; px = t+mb;
}
px >>= 1; mb >>= 2;
}
cout << px << endl
<< (px*px)
<< endl << endl;
return 0;
} |
Basic' Całkowity pierwiastek kwadratowy
' Data: 11.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------
Dim As Ulongint x, px, mb, t
Input x
px = 0: mb = 1 Shl 62
While mb > x: mb = mb Shr 2: Wend
While mb
t = px+mb
If x >= t Then
x -= t: px = t+mb
End If
px = px Shr 1
mb = mb Shr 2
Wend
Print px
Print px*px
Print
End |
Python
(dodatek)# Całkowity pierwiastek kwadratowy
# Data: 19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
x = int(input())
px = 0
mb = 1 << 62
while mb > x: mb >>= 2
while mb:
t = px+mb
if x >= t:
x -= t
px = t+mb
px >>= 1
mb >>= 2
print(px)
print(px*px)
print()
|
 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.
