首页 > 其他 > 详细

带分数 - DFS + 全排列

时间:2021-03-29 18:14:00      阅读:48      评论:0      收藏:0      [点我收藏+]

带分数:

 

可以表示为带分数的形式:100=3+69258 / 714 ;

还可以表示为:100=82+3546 / 197 ;

注意特征:带分数中,数字 191~9 分别出现且只出现一次(不包含 00)。

类似这样的带分数,100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 19 不重复不遗漏地组成带分数表示的全部种数。

数据范围

≤ 1000000

输入样例1:

100

输出样例1:

11
#include <stdio.h>
int n, ans = 0;
int a[10];

int niubi(int l, int r) {
    int i, sum = 0;
    for(i = l; i < r; i++) {
        sum = sum * 10 + a[i];
    }
    return sum;
}
void dfs(int x) {
    int i, j, k;
    if(x == 9) {
        /*
        for(k = 0; k < 9; k++) {
            printf("%d  ",a[k]);
        }
        printf("\nans = %d\n",ans);
        */
        for(i = 1; i < 9; i++) {
            for(j = i + 1; j < 9; j++) {
                int q = niubi(0, i);
                int w = niubi(i, j);
                int e = niubi(j, 9);
                if(e == 0)continue;

                if(q + w / e == n && w % e == 0) {
                    ans++;
                }
            }
        }
        return;
    }
    for(i = 1; i <= 9; i++) {
        if(book[i] == 0) {
            book[i] = 1;

            a[x] = i;
            dfs(x + 1);

            book[i] = 0;
        }

    }
}

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

 

带分数 - DFS + 全排列

原文:https://www.cnblogs.com/rongrongrong/p/14592830.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!