145 = suma 1! + 4! + 5!. Muszę napisać program w C, który znajduje 5-cyfrowych liczb, które mają tę właściwość.

Skonuicznie napisałem kod na 3 cyfry. Użyłem tego samego kodu dla 5 cyfr, ale nie może znaleźć żadnego numeru.

Chciałbym mi pomóc z moim rozwiązaniem, aby zobaczyć, gdzie się mylę.

#include <stdio.h>

int factorial(int n);

main() {
    int pin[5];

    int q = 1;
    int w = 0;
    int e = 0;
    int r = 0;
    int t = 0;

    int result = 0;

    int sum = 0;

    for (q = 1; q <= 9; q++) {
        for (w = 0; w <= 9; w++) {
            for (e = 0; e <= 9; e++) {
                for (r = 0; r <= 9; r++) {
                    for (t = 0; t <= 9; t++) {
                        pin[0] = q;
                        pin[1] = w;
                        pin[2] = e;
                        pin[3] = r;
                        pin[4] = t;

                        int factq = factorial(q);
                        int factw = factorial(w);
                        int facte = factorial(e);
                        int factr = factorial(r);                                                                       
                        int factt = factorial(t);

                        sum = factq + factw + facte + factr + factt;                
                        result = 10000 * q + 1000 * w + 100 * e + 10 * r + t * 1;

                        if (sum == result)
                            printf("ok");
                    }
                }
            }
        }
    }
}

int factorial(int n) {
    int y;
    if (n == 1) {
        y = 1;
    } else if (n == 0)
        y = 0;
    else {
        y = n * factorial(n - 1);
        return y;
    }
}
2
user11011743 26 luty 2019, 00:00

2 odpowiedzi

Najlepsza odpowiedź

Twoja funkcja factorial nie zwraca wartości we wszystkich przypadkach:

int factorial (int n) {
    int y;
    if (n==1) {
        y = 1;
    }
    else 
        if (n==0)
            y = 0;
        else {
            y = n * factorial(n-1);
            return y;
        }
}

Zwraca tylko wartość, gdy wykonuje połączenie rekurencyjne. Przypadki bazowe nic nie zwracają. Nieprawidłowe zwrócenie wartości z funkcji, a następnie próbując użyć tej wartości wywołuje Udefiniowane zachowanie.

Przenieś oświadczenie return na dole funkcji, więc zostaje wywołany we wszystkich przypadkach. Również wartość 0! jest 1, a nie 0.

int factorial (int n) {
    int y;
    if (n<=1)
        y = 1;
    else 
        y = n * factorial(n-1);
    return y;
}

Ponadto, gdy znajdziesz wartość docelową, prawdopodobnie chcesz ją wydrukować:

printf("ok: %d\n", result);
4
dbush 25 luty 2019, 21:09

Odpowiedź DBUSH jest dokładna w wskazaniu, dlaczego Twój kod nie działa. Jest to alternatywne rozwiązanie, aby zmniejszyć ilość obliczeń wykonanych przez program, nie ponownym obliczeniem czynnika każdego cyfry na każdym etapie drogi. Sposób, w jaki twój program działa, jest ona wiąże się z około 500 000 połączeń do funkcji czynnościowej z zagnieżdżonej pętli, a następnie z kolei rekurencyjnie wywołuje funkcję średnio 4-liskie czasy dla każdego połączenia od zagnieżdżonej pętli, więc jest około 2 miliony połączeń factorial. Im bardziej cyfry, tym szybciej ten numer rośnie i droższy jest. Aby uniknąć wszystkich tych przeliczeń, możesz utworzyć Look-up table, który przechowuje faktoryzację cyfr [0-9] i po prostu wygląda je w razie potrzeby.

Możesz obliczyć te wartości z wyprzedzeniem i zainicjować lut z tymi wartościami, ale jeśli hipotetycznie chciałeś, aby były obliczane przez program, ponieważ jest to przypisanie programowania, w którym nie można wyciąć takim krokiem, nadal jest dość trywialny wypełnić lut.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

void populate_lut(uint32_t *lut);

int main(void) {
   // lut is an array holding the factorials of numerals 0-9
   uint32_t lut[10];
   populate_lut(lut);
    for (uint8_t q = 1; q <= 9; q++) {
        for (uint8_t w = 0; w <= 9; w++) {
            for (uint8_t e = 0; e <= 9; e++) {
                for (uint8_t r = 0; r <= 9; r++) {
                    for (uint8_t t = 0; t <= 9; t++) {
                        // now instead of calculating these factorials, just look them up in the look-up table
                        uint32_t sum = lut[q] + lut[w] + lut[e] + lut[r] + lut[t];                
                        uint32_t result = 10000 * q + 1000 * w + 100 * e + 10 * r + t * 1;

                        if (sum == result) {
                            printf("Solution: %" PRIu32 "\n", result);
                        }
                    }
                }
            }
        }
    }
}

// populate your lookup table with the factorials of digits 0-9
void populate_lut(uint32_t *lut) {
   lut[0] = 1;
   lut[1] = 1;
   for(uint8_t i = 2; i < 10; ++i) {
      lut[i] = lut[i-1] * i;
   }
}
1
Christian Gibbons 25 luty 2019, 23:37