Wikibooks

Tävlingsprogrammering/Uppgifter/Fermats lek

< Tävlingsprogrammering | Uppgifter


Fermats lek

Skriv ett program, som givet ett heltal A, där 2 < A < 100, hittar det minsta antalet heltal B, C, D, ... , där 1 ≤ B,C,D,... < A, så att ekvationen ovan uppfylls. Enligt Fermats stora sats finns det aldrig någon lösning med enbart två termer. Om det finns flera lika korta lösningar ska programmet skriva ut vilken som helst av dem och ordningen på talen spelar ingen roll.

Körningsexempel 1: 

A ? 6
Tal: 3 4 5

Körningsexempel 2: 

A ? 8
Tal: 2 2 4 6 6

Fotnot: Satsen gäller alla exponenter större än 2 och bevisades av Andrew Wiles så sent som 1995. Specialfallet med exponent 3 bevisades dock av Euler redan 1770.

Lösning

redigera

Detta är ett specialfall av det så kallade Knapsack-problemet och kan lösas på samma sätt med dynamisk programmering. På grund av att de tillåtna talen (heltalskuberna) är så utspridda går det dock även att göra en smart brute-force-lösning.

Dynamisk programmering

redigera

Man gör en tabell (kallad t[i] nedan) som håller reda på det minsta antalet termer som behövs för att skriva talet i. Denna tabell fylls för i=1,2,3.... tills A^3 uppnås. För varje tal i går man igenom alla möjliga termer j^3 och kollar om 1+t[i-j^3] är mindre än den tidigare bästa lösningen. Här utnyttjar man alltså att man vet den bästa lösningen för alla tal mindre än i, t.ex. just talet i-j^3. Man måste också hålla reda på vilka tal som ska ingå i en given lösning, men här räcker det faktiskt att spara det "sista" talet, j, för sedan kan man i efterhand loopa bakåt och få fram alla talen. En lurighet är att undvika triviallösningen A^3=A^3. Det kan t.ex. göras genom att man gör lösningen i=i tillgänglig ett steg efteråt.

Lösningsförslag i C: 

#include <stdio.h>

int cube(int n) {return n*n*n;}

int main() {
  int i,j,t[1000001],p[1000001], k,n;
  printf("A ? ");
  scanf("%d", &k);
  n=cube(k); 
  k=1;   //Håller reda på den närmaste kuben som kommer hittas
  for(i=2;i<=n;i++) {  //Loopa över alla tal i upp till målet (n)
    if(cube(k)==i-1) {     //Om förra talet var en heltalskub så gör det tillgängligt nu.
      t[i-1]=1;    //Triviallösning med 1 term.
      p[i-1]=k;    //Markera k själv som förälder till talet k^3.
      k++;
    }
    t[i]=i+1;   //Irrelevant maxvärde för att vi säkert ska hitta någonting mindre
    for(j=1;cube(j)<i;j++)   //Loopa över alla tänkbara tal j
       if(1+t[i-cube(j)]<t[i]) {   //Kolla om en summa med j är bättre än tidigare lösningar
          t[i]=1+t[i-cube(j)];
          p[i]=j;                 //Markera j som förälder till talet i.
       }
    }
  }
  printf("Tal: ");
  for(j=n;j>0;j=j-cube(p[j])) printf("%d ", p[j]);  //Loopa bakåt i föräldralistan tills det återstår 0.
  printf("\n");
  return 0;
}

Förtydligande exempel i Java. 

import java.util.*;

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

		System.out.print("A ? ");
		int A = scan.nextInt();

		//Sparar i fermat[i] hur många heltalskuber som krävs för att
		//bilda talet i.
		int [] fermat = new int [A*A*A+1];

		//Lagrar i parent[i] senaste talet vars heltalskub användes för
		//att skapa summan i.
		int [] parent = new int [A*A*A+1];

		//Lagrar alla heltalskuber för 1-A.
		int [] cubes = new int [A+1];

		//Beräknar alla kuber från 1-A.
		for(int i = 1; i<=A; i++)
		{
			cubes[i] = i*i*i;
		}

		//Beräknar hur många heltalskuber som krävs för att bilda respektive
		//summa från 1-A^3. (Det kan tyckas dumt, då vi bara är intresserade av
		//summan för A^3, men det är i själva verket smart!)
		for(int i = 1; i<fermat.length; i++)
		{
			//Från början så vet vi inte hur många kuber som krävs för detta tal i.
			//Men man bör vara pessimistisk.
			fermat[i] = Integer.MAX_VALUE;

			//Går igenom alla relevanta kuber som kan hjälpa till och bygga upp talet i.
			// j!=A eftersom A^3 = A^3 inte var ett godkänt svar.
			for(int j = 1; cubes[j]<=i && j!=A; j++)
			{
				//Från ett visst tal prev kan man addera j^3 för att nå vårt tal i.
				int prev = i - cubes[j];

				//Hur många kuber krävdes för att bygga upp talet prev?
				//Jo fermat[prev] stycken. Då är antalet som krävs för att bygga
				//upp vårt tal i fermat[prev]+1 stycken, om vi vill att j^3 ska
				//ingå i summan. Vill vi det? Ja om det är den hittills bästa lösningen så...
				if(1+fermat[prev]<fermat[i])
				{
					fermat[i] = 1 + fermat[prev]; //Nu är detta vårt minsta antal.
					parent[i] = j; //Talet vars kub vi använde oss av för att nå vårt tal i.
				}
			}
		}

		//Vi har tagit reda på minsta antalet kuber som krävs för att bygga upp talet A^3.
		//Detta antal finns lagrat i fermat[A^3], men nu vill vi veta vilka tal som användes.
		String svar = "";

		//I parent[A^3] har vi lagrat det senaste talet vars kub användes för att bilda summan
		//A^3. OK då har vi kommit en liten bit på vägen. Men om parent[A^3]^3 användes i summan
		//för att bilda A^3, så hade vi ju summan A^3 - parent[A^3]^3 innan vi valde att använda
		//oss av kuben, men vilket tal vars kub använde vi oss av för att bilda den summan...
		for(int i = A*A*A; i>0; i -= cubes[parent[i]])
		{
			svar += " " + parent[i];
		}

		//Skriver ut svaret.
		System.out.println("Tal:" + svar);
	}
}

Smart brute force

redigera

Problemet går också att lösa med en rekursiv funktion som testar alla möjliga termer och sedan anropar sig själv för att hitta nästa term. Men då gäller det att snabbt hitta en hyfsat bra lösning så att man kan skära av sökningen när man har fler termer än en lösning som redan är hittad. Om exempelvis A=100 ska man inte börja med lösningen 1+1+1.... (en miljon gånger) och sedan 1+1....+8 o.s.v. utan man bör tvärtom hela tiden börja att lägga till en så stor term som möjligt (d.v.s. 99^3+....). Observera att en girig (engelska: greedy) lösning som alltid väljer det största talet INTE alltid fungerar, utan man måste testa även mindre termer, men den giriga lösningen är en mycket bra förstagissning som begränsar sökningen enormt. Faktum är att för A<=100 ger den giriga lösningen max 13 termer (den bästa lösningen ger högst 5 termer om man bortser från de ganska ointressanta A<=5).

Lösningförslag i C: 

#include <stdio.h>

int cube(int n) {return n*n*n;}
int min,p[100],bra[100];   // faktiskt max 13 termer, det kan man undersöka först om man vill

void MLX(int nr, int left) {  //nr=antal termer hittills, left=kvarvarande mål
  int j,g;
  if(left==0) {
    min=nr;
    for(j=0;j<nr;j++) bra[j]=p[j];  //Spara lösningen.
  }
  else if(nr+1<min) {      //Fortsätt BARA om vi har chans att hitta en bättre lösning.
    j=(nr==0)?left-1:left;  //Tillåt inte en ensam term forsta gangen.
    for(g=0;cube(g+1)<=j;g++);      //Hitta greedy-förslaget g
    for(p[nr]=g;p[nr]>=1;p[nr]--) MLX(nr+1,left-cube(p[nr]));         //Loopa från g och nedåt.
   }
}

int main() {
  int n,i;
  printf("A ? ");
  scanf("%d", &n);
  min=cube(n)+1;
  MLX(0,cube(n));
  printf("Tal: ");
  for(i=0;i<min;i++) printf("%d ",bra[i]);
  return 0;
}

Möjligen en lite dummare brute force lösning i Java, men ändå en som klarar sig inom tidsgränsen (och som förhoppningsvis är lite lättare att förstå). 

import java.util.*;

public class FermatsLek
{
	//Talet A.
	static int A;

	//Alla kuber från 1-A.
	static int [] kuber;

	//Minsta antalet mindre heltal som krävs.
	static int min = 100;

	//Vilka talen är.
	static String svar = "";

	/*
	i: Talet som ska testas.
	summa: Summan man hittills kommit upp i.
	antal: Antalet termer som använts.
	val: Vilka termerna var.
	*/
	public static void rek(int i, int summa, int antal, String val)
	{
		//Ska vi avbryta?
		if(antal>=min) return;
		else if(i<1) return;
		else if(summa>kuber[A]) return;
		else if(summa==kuber[A])
		{
			//Vi har hittat ett svar.
			min = antal;
			svar = val;
		}

		//Vi testar med denna och samma tal/kub igen.
		rek(i, summa+kuber[i], antal+1, val+" "+i);

		//Vi testar med denna, men går sedan vidare på en mindre.
		rek(i-1, summa+kuber[i], antal+1, val+" "+i);

		//Vi skiter i denna kub.
		rek(i-1, summa, antal, val);
	}

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

		System.out.print("A: ");
		A = scan.nextInt();

		kuber = new int [A+1];

		//Beräknar alla kuber från 1-A.
		for(int i = 1; i<=A; i++)
		{
			kuber[i] = i*i*i;
		}

		//Vi börjar givetvis att testa med det största talet först.
		rek(A-1, 0, 0, "");

		//Skriver ut svaret.
		System.out.println("Tal: " + svar);
	}
}


Mindre läsbar lösning i Haskell. 

-- Fermats lek
module Main where
import IO
import Char

main = do {
	putStr "A ? ";
	atmp <- getLine;
	a <- return $ read atmp;
	
	putStrLn $ "Tal: " ++ (fermat (a^3) (a-1))
}

fermat :: Int -> Int -> String
fermat a tal = map replace [ x | x <- show $ snd (ferm a tal [] 100), x/='[', x/=']' ]
	where
	replace ',' = ' '
	replace x = x

ferm :: Int -> Int -> [Int] -> Int -> (Int, [Int])
ferm a tal acc mini	| a<0 || tal<1	= (100, [])
			| len >= mini	= (100, [])
			| poss > 0	= (100, [])
			| a==0		= (len, acc)
			| otherwise	= minimum [br1, br2, br3]
			where
			poss = a - (mini-len-1)*tal^3
			len = length acc
			br1 = ferm (a - tal^3) tal (tal:acc) mini
			br2 = ferm (a - tal^3) (tal-1) (tal:acc) (min mini (fst br1))
			br3 = ferm a (tal-1) acc (minimum [mini, fst br1, fst br2])
Hämtad från ”https://sv.wikibooks.org/w/index.php?title=Tävlingsprogrammering/Uppgifter/Fermats_lek&oldid=49495”