当前位置：网站首页>找数字（DFS）

找数字（DFS）

2022-04-23 01:21:00 【OldLeft】

给一个数 n，让你找出一个只由 0,1 组成的十进制数 m，要求这个正整数 m 可以被 n 整除。

输入格式
输入一个整数 n (1≤n<200)。

输出格式
对于输入整数 n 的每一个值，输出 m 的相应值，保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解，其中任何一个都是可以接受的。

本题答案不唯一，符合要求的答案均正确

样例输入

2

样例输出

10

思路：
在这里我们可以直接想到的就是枚举出所有的字符串，然后查看哪一个字符串是满足条件的。
比如 1 10 11 …
首先可以肯定的是，第一个字符是1。因为第一位为0是不符合数学定义的。
然后我们有两个选择，给这个字符串添加1或者添加0。（这里为了计算方便，我们使用一个整数代表这个字符串）
接下来我们要注意递归出口，和最优性剪枝就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
bool f;
void dfs(int cnt,ll num){
    
    if(f){
    // 递归出口1 找到了一种可行性答案。
        return;
    }
    if(cnt>=19){
    // 递归出口2 字符串的长度超多 19。
        return;
    }
    if(num%n==0){
    // 最优性剪枝 当已经找到了一种可行性解的时候，就没有必要继续搜索了
        f=true;
        cout<<num<<endl;
        return;
    }
    dfs(cnt+1,num*10);// num* 10+0 这个意思是在一个数字后面添加一个0 例如:12 -> 120
    dfs(cnt+1,num*10+1);// 这里和上面的思想一样，这个时候想必你应该学会了扩展吧 ^ _ ^ 。比如把一个字符串变成一个整数
}
int main(){
    
    cin>>n;
    dfs(1,1);
    return 0;
}

版权声明
本文为[OldLeft]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43833610/article/details/115771914

边栏推荐

猜你喜欢

随机推荐