Программа на C, работает с 3 цифрами, но не работает с 5 цифрами

Question

145 = сумма 1! + 4! + 5!.Мне нужно написать программу на C, которая находит 5-значные числа с этим свойством.

Я успешно написал код для 3-х цифр.Я использовал тот же код для 5 цифр, но он не может найти любое число.

Я хотел бы помочь мне с моим решением, чтобы я мог видеть, где я ошибаюсь.

#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;
    }
}

Answer 1

Ответ dbush точен: он указывает, почему ваш код не работает.Это альтернативное решение, позволяющее сократить объем вычислений, выполняемых вашей программой, не пересчитывая факториал каждой цифры на каждом этапе пути.В настоящее время ваша программа работает примерно на 500 000 вызовов факторной функции из вашего вложенного цикла, а затем, в свою очередь, рекурсивно вызывает функцию в среднем 4 раза для каждого вызова из вложенного цикла, то есть около 2 миллионов вызововfactorial.Чем больше цифр вы добавите, тем быстрее будет расти это число и тем дороже оно становится.Чтобы избежать всех этих перерасчетов, вы можете создать Look-up table, в котором будет храниться факториал чисел [0-9] и просто искать их по мере необходимости.

Вы можете рассчитать эти значения заранее и инициализировать LUT с помощьюэти значения, но если гипотетически вы хотели, чтобы они были рассчитаны программой, потому что это программное задание, при котором вы не можете вырезать такой шаг, заполнение 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;
   }
}

Answer 2

Ваша функция factorial не возвращает значение во всех случаях:

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;
        }
}

Возвращает значение только тогда, когда она выполняет рекурсивный вызов.Базовые случаи ничего не возвращают.Если не вернуть значение из функции, а затем попытаться использовать это значение, вызовет неопределенное поведение .

Переместите оператор return в нижнюю часть функции, чтобы он вызывался во всех случаях,Также значение 0! равно 1, а не 0.

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

Кроме того, когда вы найдете целевое значение, вы, вероятно, захотите его напечатать:

printf("ok: %d\n", result);