Mit gondoltok a programozási gondolkodásomról?
Még viszonylag kezdő C++ programozó vagyok, és sokszor gyakorlok: nézegetek interneten feladatokat és azokat oldom meg. Sokszor találtam már magam olyan helyzetben életem során (nem feltétlenül a programozásban), hogy túlbonyolítok dolgokat, mikor azt sokkal egyszerűbben meg lehetett volna oldani. Ezért egy olyan kérdéssel fordulok hozzátok, hogy szerintetek mennyire sikerült jól ennek a feladatnak a megoldása:
Írj egy programot, amely kér a felhasználótól egy pozitív egész számot, és utána kiírja az összes, ennél a számnál kisebb olyan pozitív egész számot, amely nem prím!
Megoldásom:
#include <iostream>
using namespace std;
int Prim(int szam)
{
int oszto = 0;
for (int i=1; i<szam; i++)
{
if (szam%i == 0) oszto++;
}
if (oszto > 2) return 0;
else return 1;
}
int main()
{
int a = -1;
while (a < 0)
{
cout << "Szam: ";
cin >> a;
}
for (int i = a; i > 0; i--)
{
if (Prim(i) == 0) cout << i << endl;
}
return 0;
}
válasza:"A Fermat-prímteszt minden prímszámról helyesen eldönti hogy prím, viszont vannak számok melyekre prímet ad pedig nem azok, ezek az ún. Fermat-álprímek. Vagyis ha azt adja vissza hogy nem prím akkor tényleg nem az."
""..cserébe viszont beáldozzák a teljes bizonyosságot"
Ez nem igaz."
Nem tűnik fel, mennyire ellentmondasz magadnak? :D
Először azt állítod, hogy vannak olyan nem prím számok, melyeket prímként azonosít. Ebben igazad is van.(Hogy mennyire ritkák az ilyen számok, abba ne menjünk bele, mert nem ez a lényeg)
Aztán pedig kijelented, hogy nem igaz, hogy feladom a teljes bizonyosságot, ha így tesztelek.
Most gondolj bele, ha 1től Nig végigmész a számokon, és akár csak egy is van, amit a Fermat teszt prímként azonosít, holott nem az, akkor már nem jó eredményt kapsz, ugyanis a feladat az, hogy az összes nem prímszámot kiírasd.
Érteni is kéne, amiről beszélsz, nem csak bemagolni, +legalább önmagadnak nem kéne ellentmondani.
Röhej, hogy már jó 5 éve diplomáztam, de még mindig jobban emlékszek a dolgokra, mint a nagymellényű egyetemisták.. :D
válasza: válasza:"Nem tűnik fel, mennyire ellentmondasz magadnak? :D"
Nincs ellentmondás, (a Fermat teszt erőssége a nagyon nagy számoknál mutatkozik meg.) A Fermat teszt gyorsan kiszűr egy csomó számot melyeken mindegyiket végig ellenőrizni sokkal több idő lenne, mint Fermat tesztelni, nem áldozzák be a teljes bizonyosságot,mert elég csak azokat a számokat ellenőrizni melyekre prímet adott a Fermat-prímteszt, írtam hogy használják a Miller–Rabin-teszt-et.
Ezt különböző alapokra lefuttatják az adott számon, ha mondjuk 100 különböző alapra lefuttatják és prímet ad mindre akkor a tévedés valószínűsége 1:2^100 (vagy még kisebb), ami elfogadható, kisebb az esélye mint annak hogy elektorfizikai okból, a gép tévedjen vagyis hogy egy bit invertálódjon. Hozzáteszem hogy van determinisztikus polinomidejű prímtesztelő algoritmus is, de gyorsabb ha előtte a Fermat tesztel kiszűrünk egy csomó számot.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!