Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Valaki mondja meg!

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]  

Szeretnél hozzászólni? Jelentkezz be.
[410] Róbert Gida2008-04-04 13:58:23

Van egyébként osztásmentes verziója is a négyzetgyök kiszámolásának (ott szorozni kell). Továbbá a legjobb programok természetesen nem teljes pontossággal számolnak, mint te például 14 jeggyel, hanem mindig kb. megduplázzák az értékes jegyek számát az ak-ban.

Előzmény: [409] Sirpi, 2008-04-04 12:42:14
[409] Sirpi2008-04-04 12:42:14

Ha már felmerült a téma, és azt állítottam, hogy a pontos jegyek száma iterációs lépésenként duplázódik, akkor kicsit pontosítanék, meg bizonyítanám is az állításomat. Tehát a rekurzió a_{k+1}= \frac{a_k+n/a_k}2

A számtani-mértani közepek közti egyenlőtlenség szerint ez mindig legalább \sqrt{n}, így tegyük fel, hogy x=\sqrt{n}+c (tehát x-nek c(\geq0) a hibája), és nézzük meg, hogy x-re alkalmazva az iterációt, mekkora lesz a következő tag, azaz \frac{x+n/x}2 hibája.

\frac{x+n/x}2 - \sqrt n = \frac{\sqrt n + c + \frac n{\sqrt n + c}}2 - \sqrt n = \frac{-\sqrt n + c + \frac n{n-c^2} \cdot (\sqrt n - c)}2=

=\frac{(\frac{n}{n-c^2}-1)\cdot (\sqrt n - c)}2=\frac{\frac{c^2}{n-c^2}\cdot (\sqrt n - c)}2=\frac{c^2}{2(\sqrt n + c)}

Ebből már pár dolog kiolvasható. Ha x nagy \sqrt n-hez viszonyítva, akkor a hiba nagyjából feleződik: x=tn, ekkor c is hasonló nagyságrendű, és \frac{c^2}{2(\sqrt n + c)} \approx \frac {t^2n^2}{2tn} = x/2

Viszont ha már c<1, akkor a következő hiba már kisebb, mint c2, vagyis valóban igaz a lépésenkénti duplázódó pontosság.

* * *

Ha gyorsítani akarunk az eljáráson, akkor annyit még érdemes megtenni, hogy a \sqrt n-re adunk egy körülbelüli becslést, hogy az algoritmusnak ne kelljen az n,n/2,n/4... lépéseken végigmennie. Ha d alapú számrendszert használunk, akkor keressük meg a legkisebb k-t, amire n\leqd2k, és ilyenkor indítsuk az algoritmust dk-ból, ezzel az első jó pár lépést megspóroljuk.

Egy példa a \sqrt 2 kiszámolására, a1=2 indulóértékkel:

2,00000000000000 --- 1,50000000000000 --- 1,41666666666667 --- 1,41421568627451 --- 1,41421356237469 --- 1,41421356237309 --- 1,41421356237309

Vagyis a 6. érték már 14 jegyre pontos.

Előzmény: [406] Sirpi, 2008-04-03 10:40:19
[408] Hajba Károly2008-04-04 00:18:51

Hallgass Sirpire, meglásd megéri!

Mivel a Sirpi javasolta rekurziós gyökvonás pontossága hatványozottan nő, így nagy számok esetén is gyors eredményt adhat. Talán nagyobb problémád lesz a nagy számok kezelésével, mint ezzel az eljárással.

Előzmény: [407] csewe, 2008-04-03 14:48:10
[407] csewe2008-04-03 14:48:10

tulajdonképpen a szummát (remélem jól fogalmazok" szeretném visszafejteni n = (1 + 2 + 3 + 4 + ...végtelen) az egyenlettel megkapom ,hogy hányadik lépésnél éri el az n -et az összedás.

ehhez tudnotok kell hogy az eredeti képletem n = x * (x + 1 ) / 2 volt ezzel a képlettel megkaptam hogy hány számot kell összeadnom ,hony n -hez jussak.

reményeim szerint egy prímszitához tudom majd felhasználni a képletet , amivel néhányszáz esetleg néhányezer digites számokrol mondanám meg hogy prím e

a gyökvonás hosszú időtrabló folyamat, és nekem gyors algoritmus kellene

de sajnos nem ez az egyetlen probléma , hanem a nagy számok programozása is úgyhogy egyenlőre csak akkora számokra írom meg a rutint amekkorát a programnyelv alapból kezelni tud ,és ha sikeres akkor rátérek a nagyobb feladatra

ez nekem csak kedvtelés , de nagyon megköszönném, ha segitenétek.

Előzmény: [406] Sirpi, 2008-04-03 10:40:19
[406] Sirpi2008-04-03 10:40:19

Igazából mire és milyen környezetben kell Neked erre megoldást adni? Mert amit írtam (a másodfokú egyenlet megoldóképlete szerinti megoldást), az a megoldás, és más nincs, szóval nem lehet gyökjel nélkül felírni. Programmal akarod esetleg csinálni? (Mert ott elvileg van gyökvonás.) Meg milyen nagyságrendű az n? Ha ezekre választ adsz, akkor jobban segíteni tudunk talán abban, amire szükséged van.

* * *

A gyökvonást mi magunk is implementálhatjuk, alapműveletekkel, ha épp nem akarunk beépítettet használni. Legyen mondjuk a1=1 (vagy a \sqrt{n} bármilyen közelítése, ha tudunk jobbat), majd a_{k+1}= \frac{a_k + n / a_k}2. Ez a rekurzió nagyon gyorsan tart a \sqrt{n}-hez, ak+1-nek kétszer annyi jegye pontos, mint ak-nak. Csak be kell állítani valami leállási paramétert, hogy a program ne fusson a végtelenségig (pl. \left|a_{k+1}-a_k\right| < 10^{-10}, vagy amilyen pontosság nekünk kell).

Előzmény: [405] csewe, 2008-04-03 08:42:26
[405] csewe2008-04-03 08:42:26

nem kell az x-nek egésznek lenni

Előzmény: [404] BohnerGéza, 2008-04-02 19:31:13
[404] BohnerGéza2008-04-02 19:31:13

Az x-nek is egésznek kell lennie?

Előzmény: [400] csewe, 2008-04-02 17:02:09
[403] csewe2008-04-02 17:50:26

köszi a megoldást

még azt kérdezném,hogy nem menne ez gyökvonás nélkül

mert nagy számoknál ez elég problémás

[401] Sirpi2008-04-02 17:33:12

Ez x-ben egy másodfokú egyenlet (x2+x-n=0).

x_{1,2}=\frac {-1 \pm \sqrt{4n+1}}{2}

Előzmény: [400] csewe, 2008-04-02 17:02:09
[400] csewe2008-04-02 17:02:09

sziasztok

meg kellene oldanom ezt az egyenletet

n = x*(x + 1)

n pozitív egész pl:30 , 42 , 50 stb

szeretném megkapni x - et

persze nem ezeknél a kis számoknál okoz gondot a dolog

ha valaki tudja legyenszives vezesse le nekem a megoldást

köszi

[399] BohnerGéza2008-03-26 19:07:39

Így összeállt a helyes út az elsőfokú kétismeretlenes diofantoszi egyenlet megoldásához!

Előzmény: [398] Sirpi, 2008-03-26 16:31:32
[398] Sirpi2008-03-26 16:31:32

A 3.-at annyival egészíteném én ki, hogy mivel a 45 és a 102 lnko-ja 3, ezért azzal rögtön le lehet osztani:

34x+15y=53/3

Vagyis nincs egész megoldás, mert a bal oldal biztos egész, a jobb meg nem.

Előzmény: [396] BohnerGéza, 2008-03-26 10:32:40
[397] Korrob2008-03-26 16:21:59

Köszönöm szépen mindkettőtöknek.

Előzmény: [395] Sirpi, 2008-03-25 17:46:59
[396] BohnerGéza2008-03-26 10:32:40

Sipri hozzászólását kiegészítve:

Előzmény: [394] Korrob, 2008-03-25 17:26:39
[395] Sirpi2008-03-25 17:46:59

A 2. és a harmadik ugyanolyan típusú, a 2-esen mutatom meg, hogy megy a dolog. Kell találnod egy megoldást, ilyen pl. az x=4, y=1. Ezt pl. meg lehet úgy tenni, hogy a 19-ből 7-esével lépkedsz lefelé (felfelé), és figyeled, mikor jutsz 3-mal osztható számhoz.

Ha megvan egy megoldás, fel kell használni, hogy ha x és y megoldás, akkor x+7 és y-3 is az, vagyis a megoldások: 4+7k, 1-3k. Behelyettesítve: 3(4+7k)+7(1-3k)=12+21k+7-21k=19, tehát tényleg megoldások.

Az első pedig elég közismert:

xy=x+y

xy-x-y+1=1

(x-1)(y-1)=1

Innen rögtön kijön, hogy tetszőleges x esetén y=1+\frac 1{x-1}, valósokra ezzel meg is oldottuk a feladatot. Ha azt is feltesszük, hogy mindkettő egész, akkor is könnyű dolgunk van, ugyanis az 1 csak 1.1 és (-1).(-1) alakban bomlik két egész szám szorzatára, innen a megoldások: x=y=0 és x=y=2.

Előzmény: [394] Korrob, 2008-03-25 17:26:39
[394] Korrob2008-03-25 17:26:39

Szervusztok! Nem vagyok valami jó matekból Elsőfokú diofantoszi egyenletekre kéne általános megoldás. ilyenekre pl.: xy=x+y 3x+7y=19 102x+45y=53 stb.

Előre is köszi.

[393] epsilon2008-03-24 12:10:04

OK, köszi!Így már minden tiszta, a fölös zárójelt láttam, de sejtettem, hogy elpötyögés volt csak, amúgy meg nem ártott semmit :-) Üdv: epsilon

Előzmény: [392] Róbert Gida, 2008-03-24 11:55:23
[392] Róbert Gida2008-03-24 11:55:23

[Számlálóban a legkülső zárójel persze felesleges]

n egész, d osztója, akkor d társosztója n/d, azaz d és e osztó-társosztó, ha d*e=n teljesül, ekkor persze e társosztója d, így az osztók párokba rendezhetőek (előfordulhat, hogy önmaga lesz a társosztó, ha n négyzetszám. Például n=36 osztó-társosztó listája:

(1,36),(2,18),(3,12),(4,9),(6,6)

Ha ezt egy négyzetszámra végzed el: k2=d*e, akkor minden párban pontosan az egyik lesz legfeljebb k, kivéve, ha k=d=e, ez triviális, így a k-nál nem nagyobb osztók száma=k2 osztópárjainak a száma=\frac {numdiv(k^2)+1}{2}, ha k=p^{\alpha}*q^{\beta}, akkor ebben az esetben ez \frac {(2*\alpha +1)*(2*\beta +1)+1}{2}

Előzmény: [391] epsilon, 2008-03-24 11:42:42
[391] epsilon2008-03-24 11:42:42

Köszi Róbert Gida! Profi munka, és mégis elemi. A társosztóról röviden a lényeget hol olvashatom el pl. a neten, vagy elmondod-e egy pár szóban, mert a következő képlet nem jön be :-( Üdv: epsilon

Előzmény: [390] Róbert Gida, 2008-03-24 11:30:35
[390] Róbert Gida2008-03-24 11:30:35

p,q-val szinte mindig prímeket jelölünk, pozitív egészeket máskor ne jelölj így.

Először nézzük azt az esetet, amikor p és q prímek, n=p^{\alpha}*q^{\beta} ekkor n2-nek (2*\alpha+1)*(2*\beta+1) pozitiv osztója van. Osztó társosztó fogalmát használva ezek közül \frac {((2*\alpha +1)*(2*\beta +1)+1)}{2} lesz n-nél nem nagyobb, ezek közül (\alpha+1)*(\beta+1) osztja n-et (hiszen ennyi az n osztóinak a száma), így ennyit le kell vonni, azaz az eredmény:

\frac {((2*\alpha +1)*(2*\beta +1)+1)}{2}-(\alpha +1)*(\beta +1)=\alpha * \beta

Ha p és q nem prím, akkor ugyanezzel a gondolatmenettel:

\frac {numdiv(n^2)+1}{2}-numdiv(n)

(Ez persze prímekre is ugyanazt adja.) ahol numdiv(x):=x pozitiv osztóinak a száma.

Előzmény: [386] epsilon, 2008-03-24 09:56:10
[389] epsilon2008-03-24 11:16:52

Köszi, nem lehetne-e kapcsolatba hozni az n és az n×n osztóinak képleteivel?

Előzmény: [388] S.Ákos, 2008-03-24 10:11:23
[388] S.Ákos2008-03-24 10:11:23

Helyesen:

\sum_{i=1}^{[log_p q^\beta]} \bigg[log_q \bigg[\frac{q^\beta}{p^i}\bigg]\bigg]+\sum_{j=1}^{[log_q p^\alpha]} \bigg[log_p \bigg[\frac{p^\alpha}{q^j}\bigg]\bigg]

Előzmény: [387] S.Ákos, 2008-03-24 10:09:31
[387] S.Ákos2008-03-24 10:09:31

Ha nem számoltam el valamit, valami ilyesmi lenne: \sum_{i=1}^{log_p q^\beta} \bigg[log_q \bigg[\frac{q^\beta}{p^i}\bigg]\bigg]+\sum_{j=1}^{log_q p^\alpha} \bigg[log_p \bigg[\frac{p^\alpha}{q^j}\bigg]\bigg]. Zárt alakot sajnos nem tudok mondani.

Előzmény: [386] epsilon, 2008-03-24 09:56:10
[386] epsilon2008-03-24 09:56:10

Helló! Megint van egy feladatom, valakinek van-e valami jó ötlete? Kösz, üdv: epsilon

[385] epsilon2008-03-18 11:28:18

Helló nadorp!Noha gyakran elpötyögök dolgokat :-( szerencsére, a lényeget nem írtam el, és fordításól van a feladat, átnéztem, és most is egyértelműen azt írja, hogy milyen n-re van pozutív egész gyöke, a válasz 4p+3, de ez szerintem nem jelenti azt, hogy MINDEN ILYEN n értékre, azért kérdeztem Tőúletek, hogy nem-e azt szeretnék tudni, hogy n milyen alakú kell legyen (szükséges feltétel) mert esetleg nem mondhatnak többet??? (pl. oszthatósági szempontból) az n-ről. Szóval valahogy meg szeretném tudni, hogy egyáltalán van-e ilyen n, ha van hány, azok meg valóan szükségszerűen 4p+3 alakúak kell legyenek? Talán így megmenthető a feladat, mert másképpen ....nem látom mit is lehetne izonyítani? Üdv: epsilon

Előzmény: [383] epsilon, 2008-03-18 06:41:43

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]