Tävlingsprogrammering/Uppgifter/Lagomvinklade trianglar

Lagomvinklade trianglar

En lagomvinklad triangel är vad vi i denna uppgift kallar en triangel där minst en av vinklarna är exakt 60 grader. De lagomvinklade trianglarna känner sig ofta förbisedda jämfört med de mycket mer kända rätvinkliga trianglarna (så kallat mindervinkelkomplex), trots att de lagomvinklade också har en snygg formel för sina sidlängder:

$c^{2}=a^{2}+b^{2}-ab$

Skriv ett program som skipar lite rättvisa i detta triangeldrama genom att fråga efter ett tal N (mellan 1 och 100) och sedan skriva ut hur många lagomvinklade trianglar det finns vars sidor är heltal i intervallet 1 till N.

Ett exempel på en lagomvinklad triangel med sidlängderna a = 5, b = 8 och c = 7.

Körningsexempel 1

Talet N ? 25 
Antal trianglar: 35

Förklaring: Först finns det 25 liksidiga trianglar med sidlängder 1 till 25. De övriga är:

3 8 7
5 8 7
5 21 19
6 16 14
7 15 13
8 15 13
9 24 21
10 16 14
15 24 21
16 21 19

Körningsexempel 2

Talet N ? 70
Antal trianglar: 112

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