Tävlingsprogrammering/Uppgifter/Lagomvinklade trianglar

Mall:Proguppgift

Lösning

Vi loopar över sidorna a och b och för att slippa dubletter ser vi till att t.ex. a<=b, För varje par (a,b) räknar vi ut den tredje sidan c och kollar om den är ett heltal <=N, i så fall ökas en räknare. Eftersom det maximala N är så litet hinner man t.o.m. loopa över alla sidlängder c om man vill undvika flyttalsräkning.

Exempel i C:

#include <stdio.h>
#include <math.h>

int main() {
  int a,b,c,count,N;
  scanf("%d", &N);
  count=0;
  for(a=1;a<=N;a++) {
    for(b=a;b<=N;b++) {
      c=floor(sqrt(a*a+b*b-a*b));
      if(c<=N && c*c==a*a+b*b-a*b) count++;
      }
    }
  }
  printf("%d\n", count);
  return 0;
}

Som ovan, fast i Java. Observera att vi inte behöver kolla om c<=N, eftersom det garanterat kommer att vara det om a<=N och b<=N, ty a*b>=min(a*a,b*b) och således är c*c = a*a + b*b - a*b <= N*N.

import java.util.*;

public class Lagom
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Talet N ? ");
		final int N = scan.nextInt();

		int svar = 0; //Antalet lagom vinklade trianglar.

		//Vi testar alla möjliga kombinationer av a och b, och för varje
		// kombination kollar vi om det finns ett möjligt c värde som är ett heltal.
		// Att vi ställer kravet att a<=b gör att vi undviker dubletter.
		for(int a = 1; a<=N; a++)
		for(int b = a; b<=N; b++)
		{
			final int cSqr = a*a + b*b - a*b; //Vad c^2 måste vara.
			final int c = (int)Math.sqrt(cSqr); //Vad blir då c?
			//Man behöver inte oroa sig för avrundningsfel.
			//Math.sqrt garanterar att om input är en perfekt kvadrat,
			// så är output ett heltal. D.v.s. Math.sqrt(25) ger alltid
			// 5.0 som svar och aldrig 4.99999999999999 eller liknande.

			if(c*c==cSqr) ++svar; //Är c ett heltal?
		}

		System.out.println("Antal trianglar: " + svar);
	}
}

En Haskell lösning med samma idé:

getInt :: IO Int
getInt = fmap read getLine

main = do  
  putStrLn "Talet N ? "
  n <- getInt  
  putStrLn.("Antal trianglar: "++). show $ f n
  

f :: Int -> Int
f n = sum [1| a<-[1..n], b<-[a..n], c <- [floor(sqrt(fromIntegral (a*a+b*b-a*b)))] , c^2==a^2+b^2-a*b]

En lite coolare Haskell-lösning.

-- Lagomvinklade Trianglar
module Main where

main = putStr "Talet N ? " >> fmap read getLine >>= \n ->
	putStrLn.("Antal trianglar: "++).show $ sum [1 | a <- [1..n], b <- [a..n], isSqr (a*a + b*b - a*b)]

isSqr c2 = c*c==c2 where c = truncate $ sqrt $ fromIntegral c2