hur tänker man? förkorta ett bråk? (koden finns)

[tokfan]

förkorta ett bråk?

Kod: Markera allt

{
			
		int m = t;
		

		while( n % m != 0 ||t % m !=0)
		{
			m = m-1;
		}
    
		n =  n/m;
		t =  t/m;
	}

t= täljare n= nämnare (som ni kanske förstått)

När resten från nämnaren inte är noll eller resten från täljaren inte är noll?
båda måste ju vara noll om man ska få ut ett jämt tal. Jag fattar fel på nåt vis. hur ska jag tänka?

[Swech]

Koden testar väl tills dess att både n och t går att dela med m med rest = 0 för båda.
Så länge som det finns en rest så upprepas det med m-1

Swech

[sodjan]

> När resten från nämnaren inte är noll eller resten från täljaren inte är noll?

Snarare *Så länge som resten...*
Inte "När resten..."

[pbgp]

Du vill väl ha största gemensamma nämnaren? Den får man lätt med Euklides algoritm, varsågod:

Kod: Markera allt

int gcd_euclid(unsigned int a, unsigned int b)
{
  if( a < b ){
    a = a^b;
    b = a^b;
    a = a^b;
  }
  int c;

  while( b ) {
    c = a%b;
    a = b;
    b = c;
  }

  return a;
}

[thebolt]

För att förtydliga det hela lite

Kod: Markera allt

int m = t;

while( n % m != 0 ||t % m !=0) {
  m = m-1;
}

Detta hittar ju det största tal lika med eller mindre än täljaren som både täljare och nämnare är jämnt delbart med. Nu är det ju lite onödigt att börja med täljaren om den är större än nämnaren, så en första sätt att förbättra det vore att börja m på det minsta av t och n.. Men som pbgp säger så är detta m benämnt "största gemensamma delare" och kan beräknas med Euklides algoritm. pbgps kod är dock onödigt komplicerad, då den använder ett xor-trick för att få minsta delen.. skulle jag koda det hela skulle jag skriva enl. följande

Kod: Markera allt

unsigned int gcd(unsigned int a, unsigned int b)
{
  int c;
  if (a < b) {
    // Swap so a is larger
    c = a; a = b; b = c;
  }

  while (b != 0) {
    c = b;
    b = a % b;
    a = c;
  }

  return a;
}

...
int divider;

divider = gcd(t, n);
if (divider > 1) {
  t = t / divider;
  n = n / divider;
}

Om man är på en platform där modulo-operatorn är dyr går det också implementera Euklides algoritm med upprepad subtraktion enl

Kod: Markera allt

unsigned int gcd(unsigned int a, unsigned int b)
{
  int c;
  if (a < b) {
    // Swap so a is larger
    c = a; a = b; b = c;
  }

  while(b != 0) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}

[pbgp]

Asch, vad är väl lite hobbykodning utan små trix Men jag får erkänna att jag stoppade in xor-tricket mest för att se om någon skulle reagera (kalla mig troll om du vill )

[4kTRB]

Så här kan det se ut i Java:

Kod: Markera allt

 
public class GCD {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		GreatestCommonDivisor gcd = new GreatestCommonDivisor(22543,876);
		gcd.computeGCD();
		System.out.println(gcd.getGCD());
	}
}

public class GreatestCommonDivisor {

	private int gcd;
	private int[] g = new int[100];
	private int index;
	
	public GreatestCommonDivisor(int a, int n){
		g[0] = a;
		g[1] = n;
		index = 1;
	}
	
	public void computeGCD(){
		g[index+1] = g[index-1] % g[index];
		index++;
		while(g[index] > 0) {						
			g[index+1] = g[index-1] % g[index];
			index++;
		}
		gcd = g[index-1];
	}
	
	public int getGCD(){
		return gcd;
	}
}

[thebolt]

Asch, vad är väl lite hobbykodning utan små trix

Nu blir det lite OT, men iaf.. XOR-tricket finns ju till för att kunna swappa två variabler utan nått extra lagringsutrymme, men nu behöver du ju ändå en temporärvariabel i funktionen (om man inte använder min "successiva subtraktioner-version då";) så då är det ju onödigt, och ofta tom långsammare än ett par "move".

-M

[pbgp]

helt riktigt.