C语言穷举法 abcde/fghij=n,其中a~j为数字0~9的不同排列.n的值从2到79。统计这样的组合一共有多少个。

C语言穷举法 abcde/fghij=n,其中a~j为数字0~9的不同排列.n的值从2到79。统计这样的组合一共有多少个。

#include

int ans = 0;
int a[10];
bool used[10];

void dfs(int k) {
if (k == 10) {
int v0 = 0, v1 = 0;
for (int i = 0; i < 5; ++i) {
v0 = v0*10+a[i];
v1 = v1*10+a[i+5];
}
if (v0 >= 2*v1 && v0 <= 79*v1) {
ans++;
}
}

for (int i = 0; i < 10; ++i) {
if (!used[i]) {
a[k] = i;
used[i] = 1;
dfs(k+1);
used[i] = 0;
}
}
}

int main() {
dfs(0);
printf("%d\n", ans);
return 0;
}追问运行结果就不正确啊追答#include

int ans = 0;
int a[10];
bool used[10];
int v0, v1;

void dfs(int k) {
if (k == 10) {
v0 = 0, v1 = 0;
for (int i = 0; i < 5; ++i) {
v0 = v0*10+a[i];
v1 = v1*10+a[i+5];
}
if (v0%v1 == 0 && v0/v1 >= 2 && v0/v1 <= 97) {
ans++;
}
}

for (int i = 0; i < 10; ++i) {
if (!used[i]) {
a[k] = i;
used[i] = 1;
dfs(k+1);
used[i] = 0;
}
}
}

int main() {
dfs(0);
printf("%d\n", ans);
return 0;
}

//这样跟楼下的答案一下了，281，他的方法比这个方法优追问嗯额，谢啦！还想问一下程序执行速度啊？怎样可以更快？追答现在的算法复杂度是 O（10！） 而且系数还不小
splashchaos给出的方法就不错，复杂度是O(80*10^5)
也就是你枚举一半，比如枚举fghij，然后挨着乘以2到n看看得到的abcde是否是满足条件的，条件就是fghij abcde是不是0~9

这样子就ok了

根据题意，abcde最大的可能值为98765；而fghij最小的可能值是01234， 因此结合n=2~79, 作两个循环判断所有的取值； 判断的标准就是：把abcde和fghij按字符串合并，排序后和字符串0123456789比较即可。代码如下：#include 
#include 
#include 
int isunique(const size_t abcde, const size_t fghij);
int compare(const void * a, const void * b);
int main(int argc, char** argv) 
{
    size_t count = 0;
    int abcde, fghij, n;
    size_t n_min, n_max;
    size_t abcde_max;
    size_t fghij_min;
    
    n_min = 2;
    n_max = 79;
    fghij_min = 1234; 
    abcde_max = 98765; 
    
    for (n = n_min; n <= n_max; n++)
    {
        fghij = fghij_min;
        do {
            abcde = n * fghij;
               
            if (isunique(abcde, fghij) == 0)
            {            
               printf(" %05d = %05d * %d ", abcde, fghij, n);
               count ++;
            }
            
            fghij ++;   
        } while (abcde < abcde_max);
        
    }
    
    printf("Total found: %d ", count);
    
    return 0;
}
int isunique(const size_t a, const size_t b)
{
    char buffer[10];
    int c1, c2;
       
    if ((a > 99999) || (b > 99999))
       return -2;
       
    c1 = snprintf(buffer, 5, "%05d", a);       
    c2 = snprintf(buffer+c1, 5, "%05d", b);
       
    qsort(buffer, sizeof(buffer)/sizeof(buffer[0]), sizeof(char), compare);
    
    return strncmp(buffer, "0123456789", 10);    
}
int compare(const void * a, const void * b)
{
    return ( *(char*)a - *(char*)b );    
}
输出： 13458 = 06729 * 2
...
 98736 = 01452 * 68
Total found: 281