Hoppa till innehållet

Tävlingsprogrammering/Uppgifter/Uppställning

Lägg till länkar
Från Wikibooks

Uppställning


FIGUR 2. Raden med barn i exemplet sedda bakifrån.

En grupp med n barn, låt oss kalla dem A, B, C och så vidare, beslutar sig för att testa din tankeförmåga. Utan att du ser dem ställer de upp sig på en rad. Sen räknar vart och en av dem hur många av de barn som står till vänster om honom/henne som är längre än han/hon själv, och sedan likadant med dem som står till höger. Var och en skriver ner dessa antal på en lapp som de ger till dig efter att ha frångått uppställningen. Deras enkla uppmaning till dig är att tala om i vilken ordning de stod.

Ett exempel med fem barn visas i figur 2 ovan. A har ett längre barn (D) till vänster om sig och två (C och E) till höger. B har tre längre barn till vänster om sig och ett till höger. C har ett längre barn till vänster om sig men inget till höger och så vidare. Informationen på lapparna kan sammanfattas så här:

BarnVänsterHöger
A12
B31
C10
D00
E20

Tyvärr klarade du inte nöten utan måste i hemlighet smyga iväg och skriva ett datorprogram som löser uppgiften. För att underlätta för dig själv nästa gång barnen ansätter dig så vill du kunna variera både antalet barn (mellan 3 och 8, inklusive) och informationen på lapparna. Du kan förutsätta att alla barn är olika långa och att de inte har gjort något misstag när de skrev lapparna. Intressant nog finns det aldrig mer än en lösning. Körningsexempel: 

Antal barn ? 5
Barn A, vänster ? 1
Barn A, höger ? 2
Barn B, vänster ? 3
Barn B, höger ? 1
Barn C, vänster ? 1
Barn C, höger ? 0
Barn D, vänster ? 0
Barn D, höger ? 0
Barn E, vänster ? 2
Barn E, höger ? 0

Uppställningen: D A C B E

Lösning

[redigera]

Eftersom antalet barn är begränsat till 8, finns det endast 8! = 40320 möjliga uppställningar. Det är alltså ett utmärkt exempel på en uppgift där datorn lätt testar alla möjligheter på en bråkdel av den tid det skulle ta att komma på en smartare lösning. Att få fram alla permutationer (uppställningsordningar) kan antingen göras med en enkel rekursiv funktion: 

void MLX(int nr) {
  if(nr==n) {
    //Testa permutationen som nu är lagrad i barn[0..n-1]
  }
  for(barn[nr]=0;barn[nr]<n;barn[nr]++) if(!tagen[barn[nr]]) {
    tagen[barn[nr]]=1;
    MLX(nr+1)
    tagen[barn[nr]]=0;
  }
}

eller genom den inbyggda C++-funktionen next_permutation, vilket visas i lösningen nedan.

Det som gör uppgiften lite klurig är att man lätt blandar ihop de tre "ordningar" som förekommer: indataordningen, uppställningsordningen och längdordningen. Det gäller därför att förenkla programmet så mycket som möjligt. En sådan förenkling är att ge varje barn en påhittad, relativ längd redan när man läser in indata. Vi vet ju att precis ett barn (det längsta) kommer att ha 0 barn som är längre på såväl vänster och höger sida, precis ett barn (det näst längsta) kommer att ha sammanlagt 1 barn som är längre, o.s.v. Därför verkar n-nv-nh (där n är antalet barn, nv är antalet längre barn till vänster och nh är antalet längre barn till höger) vara en vettig relativ längd. 


#include <iostream>
#include <vector>

using namespace std;

vector<int> barn;
int n,v[100],h[100],langd[100];

int ok() {   //Kontrollerar om den permutation som för tillfället ligger i barn[0..n-1] stämmer med indatan
  int i,j,rv,rh;
  for(i=0;i<n;i++) {
    rv=rh=0;
    for(j=0;j<i;j++) if(langd[barn[j]] > langd[barn[i]]) rv++; //Räkna antalet längre barn till vänster om barn[i]
    for(j=i+1;j<n;j++) if(langd[barn[j]] > langd[barn[i]]) rh++;  //Räkna antalet längre barn till höger om barn[i]
    if(rv!=v[barn[i]] || rh!=h[barn[i]]) return 0; //Returnera 0 om det inte stämmer med indatan
  }
  return 1;
}

int main() {
  int i;
  cout << "Antal barn ? ";  
  cin >> n;
  for(i=0;i<n;i++){ 
    cout << "Barn " << (char)('A'+i) << ", vänster ? ";
    cin >> v[i]; 
    cout << "Barn " << (char)('A'+i) << ", höger ? ";
    cin >> h[i];
    langd[i]=n-v[i]-h[i]; //Ge barnet en relativ längd  
  }
  for(i=0;i<n;i++) barn.push_back(i); //Starta med permutationen [0,1,2,3...n-1]
  do {
    if(ok()) {
      cout << "Uppställningen: ";
      for(i=0;i<n;i++) cout << (char)(barn[i]+'A') << " ";
      cout << endl;
      return 0;
    }
  } while (next_permutation(barn.begin(),barn.end()));
  return 0; //Här skulle vi hamna om något barn givit en felaktig uppgift
}


Enklare lösning i c++, genom att placera ut barnen i tur och ordning från kortast till längst 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string namn;
vector<string>barn;

void placera_in(int plats, string fr, int grplats) //plats är hur många längre som ska stå till vänster om barnet, fr är barnets bokstav och grplats är först samma som plats från början
{
     int rakna=0; //Börja räkna platser från noll
     for (int i=0; i<plats; i++)
     {
         if (barn[i]=="kaka")//Räkna bara tomma platser (där inget barn ännu ätit upp kakan)
         {
            rakna++;
         }
     }

     if (barn[plats]=="kaka" && rakna==grplats){
        barn[plats]=fr;//Om platsen är tom och vi gått rätt antal steg placerar vi in barnet
     }
     
     else
        placera_in(plats+1, fr, grplats); //Annars anropar vi funktionen igen tills vi är klara
}

int main()
{
    int antal;
    cout << "Antal barn ? ";
    cin >> antal;
    
    for (int i=0; i<antal; i++)
    {
        barn.push_back("kaka"); //Lägg en kaka på varje plats, barn gillar kakor
    }
    
    for (int i=0; i<antal; i++)
    {
        namn+=65+i; //Ge barnen namn från A och framåt
    }
    
    int vanster[antal], hoger[antal];
    for (int i=0; i<antal; i++)
    {
        cout << "Barn " << namn[i] << ", vänster ? ";
        cin >> vanster[i];
        cout << "Barn " << namn[i] << ", höger   ? ";
        cin >> hoger[i];
    }

    for (int i=0; i<antal; i++)
    {
        for (int j=0; j<antal; j++)
        {
              if (vanster[j] + hoger[j] == antal-(i+1)) //Den kortaste som ännu inte är placerad ska placeras
              {
                  string slask;
                  slask+=namn[j];
                  placera_in(vanster[j], slask, vanster[j]);
              }
        }
    }
    
    cout << "\nUppställningen:";
    
    for (int i=0; i<antal; i++)
    {
        cout << " " << barn[i];
    }
    
    cout << endl;
    return 0;
}


Ytterligare en alternativ lösning, där standardbiblioteket används flitigt: 

#include <vector>
#include <algorithm>
#include <iostream>

struct Kid{
	size_t left,right;
	char id;
};
bool sortLength(const Kid& a,const Kid& b){
	return a.left+a.right<b.left+b.right;
}

void wrt(char a){std::cout << ' ' << a;}

int main(){
	std::cout << "Antal barn ? ";
	size_t sz;
	std::cin >> sz;
	std::vector<Kid> kids(sz);
	for(size_t i=0;i<sz;++i){
		char c=kids[i].id=char('A'+i);
		std::cout << "Barn " << c << ", vänster ? ";
		kids[i].left=input();
		std::cout << "Barn " << c << ", höger   ? ";
		kids[i].right=input();
	}
	//Här börjar den egentliga beräkningen
	std::sort(kids.begin(),kids.end(),sortLength); //Sortera barnen efter deras längder
	std::vector<char> result;
	for(std::vector<Kid>::const_iterator iter=kids.begin();iter!=kids.end();++iter)
		result.insert(result.begin()+(iter->left),iter->id); //Och lägg in dem på rätt ställe
	//Skriv ut resultatet
	std::cout << "\nUppställningen:";
	std::for_each(result.begin(),result.end(),wrt);
	std::cout << std::endl;
}


Alternativ lösning i Ruby 

 #!/usr/bin/env ruby
 @n = gets.to_i #Antal barn
 @bl = Array.new
 @length = Array.new
 for n in 0 ... @n #Indata
   @bl[n] = gets.to_i
   @length[n] = @n - @bl[n] - gets.to_i - 1 #Beräknar "längden"
 end
 @answer = Array.new(@n)
 @taken = Array.new(@n)
 for n in 0 ... @n #Här löses uppgiften
   @left = @bl[@length.index(n)] #left är antal barn till vänster om barnet med längd n
   for p in 0 ... @n
     if @left == 0 and !@taken[p]
       @answer[p] = @length.index(n)
       @taken[p] = true
       break
     end
     @left -= 1 unless @taken[p]
   end
 end
 puts "Uppställningen:" #Här börjar utdatan
 for n in 0 ... @answer.length
   print (65+n).chr," "
   end
 end

Som programmerare i Java vill man ju självklart göra en klass av barnet, eftersom den har en hel del attribut. Följaktligen använder sig lösningsexemplet nedan av en hjälpklass Unge. Lösningen tilldelar varje barn en relativ längd och testar sedan alla möjligheter. 

import java.util.*;

public class Barn
{
	//Slutgiltigt svar.
	static String answer = "";

	//Array för att ställa upp barnen.
	static Unge [] order;

	//Vår rekursiva metod som testar alla möjligheter och kollar
	// vilken som blir rätt.
	/*
	barn: Bara en referens till arrayen där vi lagrar barnen.
	sequence: Barnen vi har placerat ut i ordning,
	i: Positionen vi nu ska testa att placera ett barn på.
	*/
	public static void rek(Unge [] barn, String sequence, int i)
	{
		//Om vi funnit ett svar så behöver vi inte leta längre.
		if(answer.length()!=0) return;

		//Om vi har placerat alla barn så ska vi kontrollera
		// att de står rätt-
		if(barn.length == i)
		{
			//Om de står rätt, så lagrar vi ordningen.
			if(checkOrder())
			{
				answer = sequence;
				return;
			}
		}

		//Går igenom arrayen med barn och testar att placera
		// varje unge på denna plats.
		for(int j = 0; j<barn.length; j++)
		{
			//Om vi redan använt barnet i kombinationen vi
			//håller på med, så skiter vi i den.
			if(!barn[j].used)
			{
				//Placerar barnet på positionen.
				order[i] = barn[j];

				//Markerar nu att barnet är använt.
				barn[j].used = true;

				//Går vidare och testar på nästa position.
				rek(barn, sequence + barn[j].name + " ", i+1);

				//Avmarkerar att barnet har använts.
				// Han/hon kanske ska stå på en annan position.
				barn[j].used = false;
			}
		}
	}

	//Metod som kontrollerar om vi placerat ungarna rätt.
	public static boolean checkOrder()
	{
		//Den som står längst till vänster har givetvis
		// inga personer till vänster om sig.
		if(order[0].left!=0) return false;

		//Den som står längst till höger har givetvis
		// inga personer till höger om sig.
		if(order[order.length-1].right!=0) return false;

		//Går igenom arrayen och kollar att alla har
		// rätt antal till höger om sig.
		for(int i = 0; i<order.length-1; i++)
		{
			//Hur många vi ska ha.
			int check = order[i].right;

			//Räknar hur många vi har.
			int antal = 0;

			for(int j = i+1; j<order.length; j++)
			{
				if(order[j].length>order[i].length) antal++;
			}

			//Om det inte stämmer så stämmer inte ordningen.
			if(antal!=check) return false;
		}

		//Går igenom arrayen och kollar att alla har
		// rätt antal till vänster om sig.
		for(int i = 1; i<order.length; i++)
		{
			//Hur många vi ska ha.
			int check = order[i].left;

			//Räknar hur många vi har.
			int antal = 0;

			for(int j = i-1; j>=0; j--)
			{
				if(order[j].length>order[i].length) antal++;
			}

			if(antal!=check) return false;
		}

		//Om vi klarat oss igenom alla tester har vi funnit lösningen.
		return true;
	}

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

		System.out.print("Antal barn: ");
		int antal = scan.nextInt();

		//Namn till barnen.
		String [] namn = {"A","B","C","D","E","F","G","H"};

		//Array för att spara barnen.
		Unge [] barn = new Unge [antal];

		//Skapar arrayen för positionerna att placera barnen på.
		order = new Unge [antal];

		//Läser in ungarna.
		for(int i = 0; i<antal; i++)
		{
			System.out.print("Barn " + namn[i] + ", vänster: ");
			int left = scan.nextInt();

			System.out.print("Barn " + namn[i] + ", höger: ");
			int right = scan.nextInt();

			//Skapar barnet. antal-(left+right) är barnets relativa längd.
			//Om man t.ex. har 0 längre personer till höger och vänster
			// om sig, så är man ju längst i gruppen.
			barn[i] = new Unge(namn[i], antal-(left+right), left, right);
		}

		//Nu finner vi svaret. Vi skickar med en referens till vår array med
		// barn, vi har inte placerat några barn och vi ska börja testa att
		// placera barnen på den första positionen med index 0.
		rek(barn, "", 0);

		//Skriver ut svaret.
		System.out.println("Uppställningen: " + answer);
	}
}

class Unge
{
	//Hur många längre man har till vänster om sig.
	int left;

	//Hur många längre man har till höger om sig.
	int right;

	//Barnets relativa längd.
	int length;

	//Barnets namn.
	String name;

	//Om vi har placerat ut barnet.
	boolean used = false;

	public Unge(String name, int length, int left, int right)
	{
		this.name = name;
		this.length = length;
		this.left = left;
		this.right = right;
	}
}


Lösnings-monster i Haskell. 

-- Uppställning
module Main where
import IO
import Data.List

type Barn = ((Char,Int),(Int,Int))

main = do {
	putStr "Antal barn ? ";
	n <- getLine;
	
	barn <- readBarn 0 (read n) (read n);
	
	putStrLn $ "Uppstallningen: " ++ (svar $ permutations barn)
}

bkstvr = "ABCDEFGH"

readBarn :: Int -> Int -> Int -> IO [Barn]
readBarn _ 0 _ = return []
readBarn n to tot = do {
		barn <- return $ bkstvr !! n;
		putStr ("Barn " ++ [barn] ++ ", vanster ? ");
		lf <- getLine;
		left <- return $ read lf;
		putStr ("Barn " ++ [barn] ++ ", hoger ? ");
		rg <- getLine;
		right <- return $ read rg;
		
		rest <- readBarn (n+1) (to-1) tot;
		
		return $ ((barn,tot-left-right),(left,right)):rest
}

svar :: [[Barn]] -> String
svar perms = foldr (\((c,_),(_,_)) xs -> (c:' ':xs)) [] (verify perms)

verify :: [[Barn]] -> [Barn]
verify (h:t) = if (ver h []) then h else (verify t)
	where
	ver :: [Barn] -> [Barn] -> Bool
	ver [] _ = True
	ver (h@((_,ln),(lf,rg)):t) used = (a==lf) && (b==rg) && (ver t (h:used))
		where
		a = length [x | x <- used, (snd (fst x))>ln]
		b = length [x | x <- t, (snd (fst x))>ln]
Hämtad från ”https://sv.wikibooks.org/w/index.php?title=Tävlingsprogrammering/Uppgifter/Uppställning&oldid=49416”