Petando la pila. Problemas y retos usando recursividad.

[HackmanC]

Hola,

Iniciado por leosansan

En realidad no se trata de permutaciones sino de variaciones. ...

Entre que son peras y son manzanas me tire por las conjugatorias. Ya en serio, el concepto teórico de las permutaciones, variaciones y combinaciones, sin y con repetición, y sin y con orden lo tengo claro. El problema es que no encuentro la forma de generar la secuencia exacta de una forma optimizada, es decir, sin usar ciclos o mas recursiones/comparaciones de las necesarias.

Iniciado por Pantaláimon

... Dejo este código por si queréis hacer tests: ...

Gracias, me sirvió bastante para hacer algunas pruebas. Aunque ahora pude comprobar que la secuencia de permutaciones es correcta, y los números los comprueba bien, todavía me queda la duda que tenga algún error.


Bueno, entonces así que las permutaciones serán, con el problema que seguramente la mitad de las operaciones las va a realizar de nuevo al transponer los dígitos al otro bando, por ejemplo, 123x456 y 456x123. Al final se generan n! permutaciones, basado el algoritmo de Heap, aunque se generan mas del doble de recursiones.

Código C:

#include <stdio.h>
#include <stdlib.h>
 
int count(const int value, const int i) {
    return value == 0 ? i : count(value / 10, i + 1);
}
 
void split(const int value, int dst[], const int i) {
    if (value > 0 && i >= 0) {
        dst[i] = value % 10;
        split(value / 10, dst, i - 1);
    }
}
 
int join(int value, const int src[], const int end, const int begin, const int dec) {
    if (end >= begin) {
        value += src[end] * dec;
        return join(value, src, end - 1, begin, dec * 10);
    }
    return value;
}
 
void swap(int dst[], const int a, const int b) {
    int t = dst[b]; dst[b] = dst[a]; dst[a] = t;
}
 
int esvampiro3(const int value, int src[], const int digits) {
    int value1 = join(0, src, (digits / 2) - 1, 0, 1);
    int value2 = join(0, src, digits - 1, (digits / 2), 1);
 
    printf("%.4d x %.4d\n", value1, value2);
 
    if (value1 * value2 == value && !(value1 % 10 == 0 && value2 % 10 == 0)) {
        return 1;
    }
 
    return 0;
}
 
int esvampiro2(const int value, int src[], int c[], const int digits, int i) {
    if(i < digits) {
        if (c[i] < i) {
            swap(src, i, i % 2 ? c[i] : 0);
            if (esvampiro3(value, src, digits)) {
                return 1;
            }
            c[i]++;
            i = 1;
        } else {
            c[i] = 0;
            i++;
        }
        return esvampiro2(value, src, c, digits, i);
    }
    return 0;
}
 
int esvampiro(const int value, int src[], int c[], const int digits, int i) {
    if (esvampiro3(value, src, digits)) {
        return 1;
    }
    return esvampiro2(value, src, c, digits, i);
}
 
int esVampiro(int num) {
    int i;
    int digits = count(num, 0);
    int n[digits];
    int c[digits];
 
    split(num, n, digits - 1);
    for (i = 0; i < digits; i++) {
        c[i] = 0;
    }
 
    if (digits % 2 == 0) {
        return esvampiro(num, n, c, digits, 1);
    }
 
    return 0;
}
 
int main(int argc, char** argv) {
    printf("%d\n", esVampiro(939658));
    return (EXIT_SUCCESS);
}
 

Saludos,

ps:

Aparte de que, al parecer, me estoy quedando medio cegatón, anteriormente mencioné que la había comprobado contra la base de datos, lo volví a comprobar y el resultado era 120, no 720 como había indicado anteriormente. Por eso no se salían las cuentas. Ya mas despacio use el formato condicional de Excel para comprobar que los números no se repetían, en lugar de la base de datos.