C#: N pętli

Question

Jak przekonwertować ten kod, aby mieć n zagnieżdżone pętle:

  int num = 4; 

      for (int i = 0; i <= num; i++) 
      { 
       for (int j = 0; j + i <= num; j++) 
       { 
        for (int k = 0; i + j + k <= num; k++) 
        { 
         for (int l = 0; i + j + k + l <= num; l++) 
         { 
          Console.WriteLine(i + " " + j + " " + k + " " + l); 
         } 
        } 
       } 
      } 

Więc jeśli num jest 2 to nie będzie tylko 2 pętle; ja i j.

To nie jest praca domowa i miałem nadzieję, że zrobię to w sposób ciągły. Każda Console.WriteLine() musi być przechowywana jak element razem.

Dane wyjściowe tego programu tworzą n wymiarowe wykładniki hiperspozycji.

Answer 1

Ok, chcesz nierekurencyjnym rozwiązanie, które jest parametryzowane w num i ma stałą liczbę zagnieżdżonych pętli, tak?

Oto szkic metody, która to robi. Wypełnianie szczegółów pozostawia się jako ćwiczenie.

Po pierwsze, zakładam, że masz niezmienny typ "Vector", który może być krotką 0-t, 1-tką, 2-tką, 3-tką, ... n-krotką.

Metoda przyjmuje rozmiar wektora i zwraca sekwencję wektorów o tym rozmiarze.

IEnumerable<Vector> MakeVectors(int num) 
{ 
    Vector current = new Vector(num); // make an all-zero vector with num items. 
    while(true) 
    { 
     yield return current; 
     Vector next; 
     bool gotAnother = GetNextVector(current, out next); 
     if (!gotAnother) break; 
     current = next; 
    } 
} 

Tam. Problem został zredukowany do dwóch mniejszych problemów:

1) Czy wektor o numerze num jest ostatnim wektorem w sekwencji?

2) Jeśli nie, jaki jest następny wektor?

Powinno być całkiem proste, aby ustalić, jaki jest następny wektor: zwiększyć wartość ostatniego slotu. Jeśli to czyni go zbyt dużym, ustaw go na zero i zwiększ wartość poprzedniego gniazda. Powtarzaj, aż znajdziesz coś, co ma zostać zwiększone.

Sens?

Answer 2

Biorąc Ci na słowo, że nie jest to praca domowa, patrz poniżej:

public void LoopRecursively(Stack<int> valuesSoFar, int dimensions) 
    { 
     for (var i = 0; SumOf(valuesSoFar) + i <= dimensions; i++) 
     { 
      valuesSoFar.Push(i); 
      if (valuesSoFar.Count == dimensions) 
      { 
       Console.WriteLine(StringOf(valuesSoFar)); 
      } 
      else 
      { 
       LoopRecursively(valuesSoFar, dimensions); 
      } 
      valuesSoFar.Pop(); 
     } 
    } 

    private int SumOf(IEnumerable<int> values) 
    { 
     return values.Sum(x => x); 
    } 

    private string StringOf(IEnumerable<int> values) 
    { 
     return string.Join(" ", values.Reverse().Select(x => x.ToString()).ToArray()); 
    } 

Answer 3

Normalnie byłoby użyć rekurencji dla scenariuszy gdzie masz zagnieżdżone pętle, w których liczba zagnieżdżonych pętli nie jest znana w czasie kompilacji . Coś z ideą:

void func(const vector<int> &times, int depth) { 
    if (depth == times.size()) return; 
    for (int i = 0; i < times[depth]; ++i) { 
     cout << depth; 
     func(times, depth + 1); 
    } 
} 

Answer 4

Jako alternatywę dla manipulowania cyframi osobno, tak jak w przypadku rozwiązań rekursywnych i tych, które używają wektora <>, można polegać na reprezentacjach maszyn i arytmetyki. Nie jest to szybsze, jeśli za każdym razem musisz sprawdzać każdą cyfrę za każdym razem, ale jeśli implementujesz iterator, to zmniejszy to ilość miejsca w iteratorze, a jeśli nie korzystasz z każdej pojedynczej wartości, może również popraw swoją efektywność. W każdym razie jest to interesujące równoważne podejście. Tutaj idzie ...

Najpierw pomyśl o nieco bardziej ogólnym przypadku, w którym masz zagnieżdżone pętle n, z których każda liczy od 0 do num. W takim przypadku zasadniczo liczy się od 0 do num^n - 1 w bazie numer.Więc można zrobić coś takiego:

for(int x=0; x<(num^n); x++) 
{ 
    int digit_0 = x % num; 
    int digit_1 = (x/num) % num; 
    int digit_2 = (x/num^2) % num; 
    // etc. 
} 

zauważyć, że:

• Jeśli nie natywnego typu liczba całkowita jest wystarczająco duży dla danej aplikacji, a następnie trzeba będzie użyć jakiegoś dużej klasy całkowitej. Spowoduje to zmniejszenie wydajności części składowania i przyrostu, choć może nie aż tak, jak użycie wektora o długości num.
• Jeśli naprawdę za każdym razem przyglądasz się każdej cyfrze, potrzebujesz wektora cyfr i nic nie zyskujesz. Jest to bardzo przydatne, gdy za każdym razem nie patrzysz na wszystkie cyfry.
• Wszystkie dzielniki powinny być wstępnie obliczone, więc musisz zachować do tego wektor!

W każdym razie, dla konkretnego pytania, nie chcesz liczyć do num za każdym razem, gdy chcesz liczyć do num - (the sum of the already decided digits). Najprostszy sposób wyjaśnienia tego po prostu poprzez umieszczenie odpowiedniego warunku continue w twoich pętlach. Tutaj jest to z pewnymi wartościami podstawionych w Bo gdy n=2 i num=10:

for(x=0; x<100; x++) // i.e. x < num*num 
{ 
    int ones = x%10; // i.e. x % num 
    int tens = (x/10) % 10; // i.e. (x/num) % num 

    if(ones + tens < 10) 
    { 
    // actually do work 
    } 
} 

(W przypadku, gdy nie jest oczywiste, nie oznacza, że ​​powinieneś faktycznie korzysta 100 i 10 w kodzie, to jest tylko przykład ilustracyjny .)

Możesz zwiększyć wydajność, obliczając, o ile chcesz zwiększyć x, lub zmniejszając zakres x, a następnie odwzorowując bezpośrednio do swojej podprzestrzeni zamiast do całej przestrzeni. (Ale w 2-d i 3-d używasz dokładnie połowy możliwych wartości, więc dodatkowa praca przyniosłaby ci tylko przyspieszenie 2. Myślę, że to jest to samo, gdy n> 3, ale jestem zbyt leniwy, aby to sobie wyobrazić teraz, przepraszam!)