nieprawidłowa odpowiedź do zadania

0

Witam! rozwiązuje zadanie: http://projecteuler.net/problem=43 , w wyniku działania mojego kodu otrzymuje 2 liczby spełniające te warunki: 1490357286 i 4190357286, jednak ich suma (5680714572) jest nieprawidłowym wynikiem do zadania. Oto kod:

  long suma = 0;
            for (int d1 = 1; d1 < 10; d1++)
            {
                for (int d2 = 0; d2 < 10; d2++)
                {
                    if (d2 == d1) continue;
                    for (int d3 = 0; d3 < 10; d3++)
                    {
                        if (d3 == d2 || d3 == d1) continue;
                        for (int d4 = 0; d4 < 10; d4=d4+2)
                        {
                            if (d4 == d3 || d4 == d2 || d4 == d1) continue;
                            for (int d5 = 0; d5 < 10; d5++)
                            {
                                if (d5 == d4 || d5 == d3 || d5 == d2 || d5 == d1) continue;
                                if (Int32.Parse(d3.ToString() + d4.ToString() + d5.ToString()) % 3 != 0) continue;
                                for (int d6 = 0; d6 < 6; d6=d6+5)
                                {
                                    if (d6 == d5 || d6 == d4 || d6 == d3 || d6 == d2 || d6 == d1) continue;
                                    for (int d7 = 0; d7 < 10; d7++)
                                    {
                                        if (d7 == d6 || d7 == d5 || d7 == d4 || d7 == d3 || d7 == d2 || d7 == d1) continue;
                                        if ((Math.Pow(d5, 2) + d6 + d7) % 7 != 0) continue;
                                        for (int d8 = 0; d8 < 10; d8++)
                                        {
                                            if (d8 == d7 || d8 == d6 || d8 == d5 || d8 == d4 || d8 == d3 || d8 == d2 || d8 == d1) continue;
                                            if ((d6 + d8 - d7) % 11 != 0) continue;
                                            for (int d9 = 0; d9 < 10; d9++)
                                            {
                                                if (d9 == d8 || d9 == d7 || d9 == d6 || d9 == d5 || d9 == d4 || d9 == d3 || d9 == d2 || d9 == d1) continue;
                                                if (Int32.Parse(d7.ToString() + d8.ToString() + d9.ToString()) % 13 != 0) continue;
                                                for (int d10 = 0; d10 < 10; d10++)
                                                {
                                                    if (d10 == d9 || d10 == d8 || d10 == d7 || d10 == d6 || d10 == d5 || d10 == d4 || d10 == d3 || d10 == d2 || d10 == d1) continue;
                                                    if (Int32.Parse(d8.ToString() + d9.ToString() + d10.ToString()) % 13 != 0) continue;
                                                    Console.WriteLine(Int64.Parse(d1.ToString() + d2.ToString() + d3.ToString() + d4.ToString() + d5.ToString() + d6.ToString() + d7.ToString() + d8.ToString() + d9.ToString() + d10.ToString()));
                                                    suma += Int64.Parse(d1.ToString() + d2.ToString() + d3.ToString() + d4.ToString() + d5.ToString() + d6.ToString() + d7.ToString() + d8.ToString() + d9.ToString() + d10.ToString());
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

Wiem że pewnie nie jest on zbyt dobrze napisany, wykonuje się dość szybko i nie zwraca żadnych błędów. Czy ktoś widzi w czym tkwi problem? Czy może źle zrozumiałem treść zadania?

1

Nie wiem komu się będzie chciało analizować 10 czy 11 zagnieżdżonych pętli. Z tego co widzę to głównym zadaniem tego kodu jest wyświetlenie wszystkich możliwych permutacji tablicy [0,1,2,3,4,5,6,7,8,9]. Są na to prostsze sposoby, uwierz mi, złożoność O(n^{10}) to nie jest dobry wynik, a dodatkowo tego się nie da czytać i utrzymać.

0

jest jakiś algorytm wyszukujący wszystkie możliwe permutacje tablicy (bez powtórzeń) przy jak najmniejszej złożonosci obliczeniowej?

0

Jak wspomniał kolega wyżej kod jest straszny i ciężko w nim szukać błędu. Ta linia wygląda cokolwiek podejrzanie:
[code]
if ((Math.Pow(d5, 2) + d6 + d7) % 7 != 0) continue;
[code]

BTW nie wydaje mi się, że można mówić o złożoności o(n^10) - złożoność się rozpatruje względem rozmiaru wejścia, więc jest tu takie samo o(n) jak przy użyciu jednej pętli która idzie od 123456789 do 9876543210.

Edit.
Po namyślę, chyba najlepiej złożoność liczyć od ilości cyfr, wtedy jest n^n dla naiwnego algorytmu i n! dla sprawdzania kolejnych permutacji.

0

masz racje, źle zapisałem prawo podzielności, jednak poprawiłem i dalej nic. No nic szukam dalej ;)

0

Musisz zrefaktoryzować swój kod, bo inaczej to będziesz jeszcze długo tego błędu szukał.

0

proste wnioski prowadzą do 9*8!*2 = 725 760 bo d1 !=0, d6 == 0 albo 5

1 użytkowników online, w tym zalogowanych: 0, gości: 1