Dwie (2-cyfrowe) liczby są zapisywane razem, więc tworzą jeden 4-cyfrowy numer. Ten 4-cyfrowy numer można podzielić przez mnożenie tych dwóch liczb. Problem polega na tym, że muszę znaleźć te liczby.

Napisałem algorytm i otrzymałem 2 parę tych liczb.

1) 13 i 52, SO 1352 można podzielić przez 13 * 52.

2) 17 i 34, więc 1734 można podzielić przez 17 * 34.

Mój algorytm wygląda tak:

for (int i = 1010; i <= 9999; i++)
{
    int mult = (i / 100) * (i % 100);

    if ((i % 100) > 9 && i % mult == 0)
    {
        Console.WriteLine(i / 100 + " <--> " + i % 100);
    }
}

Edytuj: Za pomocą tego algorytmu (na podstawie odpowiedzi mentalurg) uważam, że te liczby są broczne szybsze

for (int i = 10; i < 99; i++)
{
    for (int j = 10; j < 99; j++)
    {
        int mult = i * j;
        int num = i * 100 + j;

        if (num % mult == 0)
        {
           Console.WriteLine(i + " <--> " + j);
        }
    }
}

Jestem zainteresowany tym, jak mogę wykonać ten algorytm bardziej wydajny.

2
user9035668 2 czerwiec 2018, 10:39

3 odpowiedzi

Najlepsza odpowiedź

Jest to bardzo wydajne:

var query =
    from x in Enumerable.Range(10, 90)
    from n in Enumerable.Range(1, 10).TakeWhile(w => w * x < 100)
    let v = x * (100 + n)
    where v % (n * x * x) == 0
    select new { x, y = n * x };

Oblicza wszystkie możliwe pierwsze cyfry. Następnie oblicza wszystkie możliwe drugie cyfry wielokrotności pierwszej cyfry, która są większa niż zero i mniej niż 100. Następnie wytwarza wartość kandydata w kontrolach, jeśli jest podzielna przez produkt obu cyfr.

Daje oba możliwe odpowiedzi.

Oto odpowiednik za pomocą pętli for:

for (int x = 10; x <= 99; x++)
{
    for (int n = 1; x * n < 100; n++)
    {
        var j = x * n;
        int v = x * 100 + j;
        int d = x * j;
        if (v % d == 0)
        {
            Console.WriteLine(x + " <--> " + j);
        }
    }
}
2
Enigmativity 2 czerwiec 2018, 08:22

Wynika, że jedna z par jest A i B, a więc czterocyfrowa liczba może być wyrażona jako 100a + b. Zrób trochę matematyki

100a + b = m * a * b

Podzielony przez po obu stronach, mamy

100 + b / a = m * b

Możemy stwierdzić, że

  1. B można podzielić przez A, powiedzmy (B == N * A);

  2. b musi być większy niż a, ponieważ 101 jest głównym. i nie może być 3/7/9 razy a, ponieważ 103/107/109 są również primes, ale zaniedbujmy to, aby ułatwia pętlę. Można to łatwo obsługiwać w wewnętrznej pętli następującego kodu.

Więc do pętli można tak napisać

for (int a = 10; a < 50; a++)
{
    for (int n = 2; n * a < 100; n++)
    {
        if ((100 + n) % (n * a) == 0)
            Console.WriteLine(a + " " + n * a);
    }
}

Liczba iteracji pętli zmniejsza się do kilku dziesiątki, od prawie 10 tys.

1
kennyzx 4 czerwiec 2018, 01:10

Użyj 2 zagnieżdżonych cykli od 1 do 99 i unikniesz dwóch operacji podziału na każdym kroku.

-1
mentallurg 2 czerwiec 2018, 07:52