Hej alle
Jeg lavede en brute force-løsning der skulle finde to talrækker
som følger en given regel, nemlig den at summen af to vilkårlige
elementer i en række ikke også må være i samme række.
Eksempler:
1 2 4
3 5
er okay.
1 2 3
4 5
er forkert
Til at tjekke en løsning bruger jeg følgende rutine. ROWS er 2 (foreløbig).
bool respect_rule () {
int h, p2, sum;
for (int row=0; row<ROWS; ++row) {
// De følgende to linjer kopierer én række over i et array, hold[]
// Antag blot at den række der skal undersøges, er hold[] og se bort fra denne kopiering.
h=0;
for (int nr=1; nr<=LIMIT; ++nr) if (number[nr]==row) hold[++h]=nr;
for (int p0=1; p0<=h-2; ++p0)
for (int p1=p0+1; p1<=h-1; ++p1) {
sum=hold[p0]+hold[p1];
// Test1:
p2=p1+1;
while (sum>=hold[p2]) if (hold[p2++]==sum) return 0;
// Test 2:
for (p2=p1+1; p2<=h; ++p2) if (hold[p2]==sum) return 0;
}
}
return 1;
}
Hvis jeg kobler Test1 ind, er der rigtige løsninger der forkastes.
(Det gælder i hvert fald 1 2 4 8 - 3 5 6 7)
Hvis jeg kobler Test2 ind (og Test2 fra), ser det ud til at virke.
Jeg er på herrens mark hvad forklaring angår. Jeg ville f.eks. umiddelbart
forvente at *Test2* var for hård.
Test1 er baseret på at tallene altid står sorteret. Hvis f.eks. summen er
5 og næste element er 11, behøver jeg ikke tjekke videre da summen
umuligt kan blive lig med de større og større tal.
Test2 tjekker i bund hver gang.
--
Bertel
http://bertel.lundhansen.dk/ FIDUSO:
http://fiduso.dk/