Toer-logaritmer i Java

[William_S]

Hei!

Driver med en oppgave hvor jeg skal lage en metode som returnerer toerlogartimer til et heltall n. Jeg har en metode som alltid fungerer greit, men i oppgaven skal jeg ikke bruke metoden på den formen. Metoden jeg ikke får lov til å bruke er:

public static int glog(int n)
{
	if(n<1)throw new IllegalArgumentException("Illegale verdier"); 
	 int k = 2; 
	int svar = (int) Math.floor(Math.log(n)/Math.log(k)); 
	return svar; 

  }

 

Den fungerer alltid greit da jeg bruker logaritmeregler fra matematikken.

Men det er en metode på denne formen her jeg skal bruke:

public static int glog2(int n)
{
	if (n<1) throw new IllegalArgumentException("Illegale verdier");
	int svar =0; 
	for (int i = 1;i<n;i*=2)
	{

	 svar++; 


	}

return svar; 
}

 

Denne metoden teller opp antall ganger for-løkken blir utført og den fungerer alltid greit for tall som går opp i 2^n altså 2,4,8,16, 32 osv. Men problemet er at operasjonen utføres en gang for mye når jeg har tall i mellom 2^n og 2^(n+1) feks 5 da. Da vil svaret bli 3, men jeg vil at svaret skal bli 2. Metoden skal som sagt ikke gi det nøyaktige desimaltallet log2 av et tall, men heller runde ned til nærmeste heltall. Altså hvis vi putter inn 5 skal den gi 2 som er log2 av 4. Håper noen har noen fine løsninger på den siste metoden for hvordan fikse problemet. Det er sikkert noe så banalt enkelt som en if test jeg ikke har kommet på.

Endret 4. september 2010 av William_S

[sindrebn]

Hei!

 

Problemet ligger i for-løkka di.

For det første blir det feil å sammenligne i med n. Svar vil da, som du sier, bli én for mye fordi den vil øke både når i = 1, 2 og 4 dersom n = 5. Hvis du sammenligner i*2 med n, vil du få svar = 2 (svar øker når i = 2 og i = 4).

Da blir det i tillegg viktig å teste på at i*2 er mindre enn eller lik n.

Eks: n = 4. Første iterasjon - i = 2, andre - i = 4 => svar = 2.

 

Følgende metode gir rett resultat:

public static int glog2(int n) {
if (n < 1) throw new IllegalArgumentException("Illegale verdier");
int svar = 0, i = 1; 
for (;(i*=2) <= n;) // Alternativt while ((i*=2) <= n)
	svar++;
return svar; 
}

Endret 7. september 2010 av sindrebn