C# multiplikatív inverz?
Itt a programrészlet, aminek a maradékos multiplikatív inverzet kéne számolnia:
public int mod(int a, int b)
{
int i=0;
while (a % b != 1)
{
a = a + a;
++i;
}
return i;
}
Mi lehet a hiba benne?
maradékos multiplikatív inverz pl.:
7*x=1(mod 23)
7*10=1(mod 23) Tehát x-t keresem a programmal.
Megvan a megoldás, rosszat számoltam vele.
public int mod(int a, int b)
{
if (a == b + 1)
{
return 1;
}
else while (a % b != 1)
{
a = a + a;
}
return a/((b+1)+1);
}
Csak épphogy volt időm ránézni, de sztem az első najdnem jó, csakhogy mindig önmagával növeled a-t, és nem az eredetivel, ami nem lesz jó.
A példádnál maradva, először a értéke 7, majd 14 lesz, ezután viszont 21 helyett 14+14=28, stb.
Javítottam:
public int mod(int a, int b)
{
int i = 1;
int osszeg = a;
while (osszeg % b != 1)
{
osszeg += a;
++i;
}
return i;
}
Formailag nem mond legyen a neve hanem pl multiplikativInverz.
Legyen egy x változó ami 0-tól b-1-ig azaz for (int x = 0; x < b; b++), ami ellenőrzi hogy (a*x) % b == 1 igaz-e ...
Ez lenne a triviális megoldás, ennél sokkal hatékonyabban is le lehet programozni, de akkor egy lineáris kongruencia megoldót kellene leprogramozni.
Egyébként meg feltételezted hogy mindig lesz a számnak multiplikatív inverze, ami nem igaz.
Írkálok hülyeségeket
"Formailag nem mond legyen a neve"
Formailag ne mod legyen a neve
És
for (int x = 0; x < b; x++)
De ha x-t növelem, akkor azt kapom meg, hogy hányszor növeltem meg 23-t(maradjunk eredeti példánál), hogy 7-tel osztva 1 legyen a maradék.
Nem pedig azt, hogy 7 hányszor van benne. Pedig úgy tűnik logikusnak, hogy ha 23-t megnövelem annyiszor, hogy a 7-es maradéka egyet adjon vissza, akkor hozzáadok egyet és elosztom 7-tel és az lesz x. De nem ad jó eredményt.
@17:58
Többször is elolvastam nem értem miért lenne logikus, de nem igaz.
Amit @16:41-es írt az jó megoldást ad ha van megoldás, különben végtelen ciklusba esik vagy az is lehet hogy túlcsordul és valami rossz megoldást ad.
pl. a=12, b=14 esetébe nincs megoldás.
Már leírtam a gondolatmenetet, de akkor most leírom a kódot is:
public int multiplikativInverz(int a,int b){
for (int x=0;x<b;x++){
if ( (a*x) % b == 1 )
return x;
}
return -1;
}
Mj.: Ha nincs megoldás akkor -1-et ad. (pozitív szám legyen a és b)
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!