C #, bez pętli
OK, przejrzałem kilka z tych linków, ale szczerze mówiąc, były trochę nudne. Nie jestem zainteresowany optymalizacją tego z tabelami skrótów i tak dalej. Dlaczego powinienem? Masz cholernego superkomputera!
Do diabła, nawet nie chcę zawracać sobie głowy pętlami! To rozwiązanie będzie zgodne z zasadą braku pętli .
Pamiętaj, że kod, który zamierzam napisać, nie jest dobrym kodem lub rodzajem kodu, który napisałbym w prawdziwym życiu (na wypadek, gdyby przyszli pracodawcy to przeczytali). Ten kod podkreśla zwięzłość i umiejętność pracy w narracji oraz deasfasuje właściwe konwencje, rytuały, pętle i tak dalej.
Aby zademonstrować, o czym mówię, zaczniemy od szokującej klasy z polami publicznymi do przechowywania argumentów równania:
class BealOperands
{
public BigInteger A, B, C, x, y, z;
}
OK, zaczniemy od tego, co jest prawdopodobnie najtrudniejszym wyzwaniem. Musimy znaleźć sposób na permutację poprzez każdą kombinację tych operandów. Istnieją niewątpliwie sposoby, aby to zrobić bardziej efektywnie niż sprawdzanie każdej permutacji, ale nie mogę się martwić, aby je rozgryźć. A dlaczego mam? Mamy cholernego superkomputera!
Oto algorytm, który wymyśliłem. Jest niewiarygodnie nieefektywny i ciągle przegląda te same operandy, ale kogo to obchodzi? Superkomputer!
- Traktuj sześć operandów jako liczbę podstawową 2 i przenikaj przez każdą kombinację.
- Traktuj sześć operandów jako liczbę podstawową 3 i przenikaj przez każdą kombinację.
- Traktuj sześć operandów jako liczbę podstawową 4 i przenikaj przez każdą kombinację.
- (...)
Jak to wszystko zrobić bez pętli? Łatwo! Wystarczy zaimplementować IEnumerablei powiązane, IEnumeratoraby wypompować permutacje. Później użyjemy LINQ do zapytania.
class BealOperandGenerator : IEnumerable<BealOperands>
{
// Implementation of IEnumerable<> and IEnumerable -- basically boilerplate to get to BealOperandGeneratorEnumerator.
public IEnumerator<BealOperands> GetEnumerator() { return new BealOperandGeneratorEnumerator(); }
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}
class BealOperandGeneratorEnumerator : IEnumerator<BealOperands>
{
public BealOperandGeneratorEnumerator() { Reset(); }
private BealOperands operands;
private BigInteger @base;
public void Reset()
{
// A is set to 0, which is "before" its minimum value, because IEnumerators are supposed to
// point to their first element *after* the first call to MoveNext().
// All other operands are set to their minimum values.
operands = new BealOperands { A = 0, B = 1, C = 1, x = 3, y = 3, z = 3 };
@base = 2;
}
public BealOperands Current
{
get
{
// We need to return a copy, since we'll be manipulating our internal one.
return new BealOperands {
A = operands.A, B = operands.B, C = operands.C,
x = operands.x, y = operands.y, z = operands.z };
}
}
public bool MoveNext()
{
// Increment the lowest "digit" and "carry" as necessary.
operands.A++;
if (operands.A - 1 >= @base)
{
operands.A = 1; operands.B++;
if (operands.B - 1 >= @base)
{
operands.B = 1; operands.C++;
if (operands.C - 1 >= @base)
{
operands.C = 1; operands.x++;
if (operands.x - 3 >= @base)
{
operands.x = 3; operands.y++;
if (operands.y - 3 >= @base)
{
operands.y = 3; operands.z++;
if (operands.z - 3 >= @base)
{
operands.z = 3; @base++;
}
}
}
}
}
}
// There will always be more elements in this sequence.
return true;
}
// More boilerplate
object System.Collections.IEnumerator.Current { get { return Current; } }
public void Dispose() { }
}
Teraz jesteśmy w biznesie! Wszystko, co musimy zrobić, to wymienić przykład BealOperandGeneratori znaleźć kontrprzykład Hipotezi Beala.
Naszym kolejnym dużym problemem jest to, że nie ma wbudowanego sposobu na podniesienie BigIntegerpotęgi do BigInteger. Istnieje BigInteger.Pow(BigInteger value, int exponent)i BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), ale nie ma metody na podniesienie BigIntegerdo potęgi innej BigIntegermodulo nieskończoności.
Co za błyszczący gwóźdź problemu! Wygląda na to, że został rozwiązany za pomocą naszego IEnumerable/ IEnumeratormłota!
class BigIntegerPowerEnumerable : IEnumerable<Tuple<BigInteger, BigInteger>>
{
public BigIntegerPowerEnumerable(BigInteger @base, BigInteger exponent) { this.@base = @base; this.exponent = exponent; }
BigInteger @base, exponent;
public IEnumerator<Tuple<BigInteger, BigInteger>> GetEnumerator() { return new BigIntegerPowerEnumerator(@base, exponent); }
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}
class BigIntegerPowerEnumerator : IEnumerator<Tuple<BigInteger, BigInteger>>
{
public BigIntegerPowerEnumerator(BigInteger @base, BigInteger exponent)
{
originalBase = @base;
originalExponent = exponent;
Reset();
}
BigInteger originalBase, currentBase, originalExponent, currentExponent;
bool finished;
public void Reset()
{
// IEnumerable.Reset() is a silly method. You're required to implement it when you implement IEnumerable,
// but it isn't used by foreach or LINQ or anything. If you want to re-enumerate the enumerable, just get
// a brand new enumerator.
// In this case it gets in the way. The only reason I'm storing the original values is so I can implement
// this useless method properly. I supposed I could just throw a NotImplementedException or something,
// but it's done now.
currentBase = originalBase;
currentExponent = originalExponent;
finished = false;
}
public bool MoveNext()
{
if (finished) return false;
if (currentExponent <= Int32.MaxValue)
{
currentBase = BigInteger.Pow(currentBase, (Int32)currentExponent);
currentExponent = 1;
finished = true;
}
else
{
currentBase = BigInteger.Pow(currentBase, Int32.MaxValue);
currentExponent -= Int32.MaxValue;
}
return true;
}
public Tuple<BigInteger, BigInteger> Current
{
get { return new Tuple<BigInteger, BigInteger>(currentBase, currentExponent); }
}
object System.Collections.IEnumerator.Current { get { return Current; } }
public void Dispose() { }
}
static class BigIntegerPowExtension
{
public static BigInteger Pow(this BigInteger @base, BigInteger exponent)
{
return new BigIntegerPowerEnumerable(@base, exponent).Last().Item1;
}
}
Teraz mamy metodę rozszerzenia Pow, którą można wywołać na a BigInteger, i przyjmuje BigIntegerwykładnik wykładniczy i brak modułu.
OK, cofnijmy się. Jak możemy stwierdzić, czy konkretny BealOperandsjest kontrprzykładem hipotezy Beala? Cóż, dwie rzeczy muszą być prawdą:
- Operandy, po podłączeniu do tej formuły u góry strony, muszą tworzyć prawdziwe równanie.
- A, B i C NIE mogą mieć wspólnego czynnika podstawowego (tzn. Ich GCD wynosi 1).
Mamy to, czego potrzebujemy, aby sprawdzić pierwszy warunek. I okazuje się, że drugi warunek jest o wiele łatwiejszy do sprawdzenia niż się wydaje. BigIntegerzapewnia cudowną GreatestCommonDivisormetodę, która pozwala nam wygodnie ominąć cały koszmar próbowania wdrożenia tego bez pętli.
Jesteśmy więc gotowi napisać metodę, aby sprawdzić, czy a BealOperandsjest kontrprzykładem. Tutaj idzie...
static class BealOperandsExtensions
{
public static bool IsBealsConjectureCounterExample(this BealOperands o)
{
// If the equation isn't even true, we don't have a counter example unfortunately
if (o.A.Pow(o.x) + o.B.Pow(o.y) != o.C.Pow(o.z))
{
return false;
}
// We have a counterexample if A, B and C are coprime
return BigInteger.GreatestCommonDivisor(o.A, o.B) == 1 &&
BigInteger.GreatestCommonDivisor(o.A, o.C) == 1 &&
BigInteger.GreatestCommonDivisor(o.B, o.C) == 1;
}
}
I wreszcie możemy połączyć to wszystko za pomocą tej dość sprytnej Mainmetody:
static class Program
{
static void Main()
{
var bealOperandGenerator = new BealOperandGenerator();
if (bealOperandGenerator.Any(o => o.IsBealsConjectureCounterExample()))
{
Console.WriteLine("IN YOUR FACE, BEAL!");
}
}
}
A, B, C, x, y i z są dodatnimi liczbami całkowitymi o x, y, z> 2, wówczas A, B i C mają wspólny czynnik pierwszy.