首页 > 代码库 > 【编程之美】2.8 找符合条件的整数
【编程之美】2.8 找符合条件的整数
给定一个正整数N，求一个最小的正整数M（M > 1），使得N * M的十进制表示中只有0和1。
我的思路：
从最低位到最高位找M，每次使得乘积的最后面多一位符合0、1的条件。
那么先找能够让末尾数字变成0的备选项 举例若N的个位数是9 考虑从后面来的进位 c 让 x * 9 + c 的末尾是0或1
设个位数字为9 则eligibleNum中存储的数字
eligibleNum[0][0] = 0 因为9 * 0 + 0 = 0 末尾符合0或1
eligibleNum[0][0] = 9 因为9 * 9 + 0 = 81 末尾符合0或1
eligibleNum[1][0] = 0 因为9 * 1 + 1 = 10 末尾符合0或1
eligibleNum[1][1] = 1 因为9 * 0 + 1 = 1 末尾符合0或1
...
这样，对每一位判断时 只要知道了进位c N的个位数字 就可以直接查找得到符合条件的备选项
然后利用广度优先搜索，查找最小的M
代码中的问题：这个代码无法判断无解的情况 而且 在答案的位数过多的时候会报错 判断进位由于跟已有的低位都有牵扯 导致必须使用这个数字的乘法 导致大数会溢出
总之，是个烂代码。唯一欣慰的是练习了一下广度优先搜索
#include <iostream>#include <vector>#include <queue>using namespace std;//判断n里面是否只有0和1bool IsAll01(int n){ while(n) { if((n % 10 == 0) || (n % 10 == 1)) { n = n / 10; } else { return false; } } return true;}/*设个位数字为9 则eligibleNum中存储的数字eligibleNum[0][0] = 0 因为9 * 0 + 0 = 0 末尾符合0或1 eligibleNum[0][0] = 9 因为9 * 9 + 0 = 81 末尾符合0或1 eligibleNum[1][0] = 0 因为9 * 1 + 1 = 10 末尾符合0或1 eligibleNum[1][1] = 1 因为9 * 0 + 1 = 1 末尾符合0或1 ...*/void getEligibleNum(int single, vector<vector<int>> * eligibleNum){ for(int i = 0; i < 10; i++) //对每一个被加数 { vector<int> tmp; for(int j = 0; j < 2; j++) //对每一个允许的和的末尾数0、1 { for(int k = 0; k < 10; k++) { int multi = k * 10 + j - i; if((multi >= 0) && (multi % single == 0) && (multi/single < 10)) { tmp.push_back(multi/single); //把符合条件的数存入 } else { continue; } } } eligibleNum->push_back(tmp); }}////获得所有符合条件的答案 广度优先搜索void getAllAllowedAns(int N, vector<vector<int>> * eligibleNum,vector<vector<int>> * allAllowedAns, queue<vector<int>> Q){ bool isHaveAns = false; //当前循环下是否已经找到答案 int currentLength = Q.front().size(); while(Q.front().size() == currentLength) { int addNum; int alreadyNum = 0; int pow = 1; int currentMulti = 0; if(currentLength == 0) { addNum = 0; } else { for(int i = currentLength - 1; i >= 0; i--) { alreadyNum = alreadyNum * 10 + Q.front()[i]; pow *= 10; } currentMulti = alreadyNum * N; addNum = (currentMulti / pow ) % 10; } vector<int>::iterator it; for(it = (*eligibleNum)[addNum].begin(); it < (*eligibleNum)[addNum].end(); it++) //遍历所有备选项 { vector<int> currentAns = Q.front(); currentAns.push_back(*it); if(IsAll01((*it) * N + currentMulti / pow)) //符合条件的答案 { allAllowedAns->push_back(currentAns); isHaveAns = true; } else { Q.push(currentAns); } currentAns.pop_back(); } Q.pop(); } if(isHaveAns == true && currentLength != 0) { return; } else { getAllAllowedAns(N, eligibleNum, allAllowedAns, Q); }}char * getSmallestM(int N){ vector<vector<int>> eligibleNum; //符合条件的数字 vector<vector<int>> allAllowedAns; vector<int> tmpAns; queue<vector<int>> Q; Q.push(tmpAns); int single; //数字N的个位上的数 while(N % 10 == 0) //N末尾的0对结果没有影响去掉 N = N / 10; single = N % 10; getEligibleNum(single, &eligibleNum); getAllAllowedAns(N, &eligibleNum, &allAllowedAns, Q); return NULL;}int main(){ getSmallestM(35); return 0;}
下面上高大上的答案：
答案没有考虑M，而是从找M*N入手。因为M*N只有0和1 表示更为简便。
用一个向量存储X % N = i 的每一种 i 情况下最小的X
对与10^k + Y 的情况
先计算 j = 10^k % N
然后用 （j + 已有的余数）% N 若出现了新的余数则存起来
且 100 % N = (10 % N) * 10 % N 利用这种规律可以避免10^k的大数表示
这种情况下 只要维护一个N个空间的余数向量 每个元素是个不定长的数组，存储M*N的第几位是1 也避免了大数的表达
且遍历时间很少 如果最后答案有K位 每一位只需遍历N次 最终只需遍历(K-1)*N步 非常快
代码：BigInt[0] 就是最小的M * N的值
#include <iostream>#include <vector>using namespace std;typedef unsigned char uchar;//BigInt中存储M * N的结果中 1的位置void GetSmallestM(int N, vector<vector<uchar>> * BigInt){ int i , j; vector<uchar> init; init.clear(); //初始化 每一个都存个空的 for(i = 0; i < N; i++) { BigInt->push_back(init); } (*BigInt)[1].push_back(0); //余数为1的最小的数肯定是1 第0位是1 int NoUpdate = 0; //i 表示当前最高位是 10^i 次方 j表示 10^i % N的值 100 % N = ((10 % N) * 10) % N 注意 j避免表示大数的方法 for(i = 1, j = 10 % N; ; i++, j = (j * 10) % N) { bool flag = false; //出现新的余数 存储 if((*BigInt)[j].size() == 0) { flag = true; (*BigInt)[j].clear(); (*BigInt)[j].push_back(i); } //对当前已有的余数遍历 判断 (j + k) % N是否出现新余数 for(int k = 1; k < N; k++) { if((*BigInt)[j].size() > 0 && ((*BigInt)[k].size() > 0 && i > (*BigInt)[k][(*BigInt)[k].size() - 1]) //这个条件表示当前的余数非空 且 当前的余数不是因为当前i下 早些的k循环处理中产生的 BigInt的每一项中不能有相同的数字 && (*BigInt)[(k + j) % N].size() == 0) { flag = true; (*BigInt)[(k + j) % N] = (*BigInt)[k]; (*BigInt)[(k + j) % N].push_back(i); } } if(flag == false) NoUpdate++; else NoUpdate = 0; //如果经过一个循环节没有更新 则无解 跳出 因为循环N次都没有出现新的余数 而N的余数一共最多就N种 //找到答案了也跳出 if(NoUpdate == N || (*BigInt)[0].size() > 0) break; } if((*BigInt)[0].size() == 0) { cout << "M not exist" << endl; } else { return; }}int main(){ vector<vector<uchar>> BigInt; GetSmallestM(99, &BigInt); return 0;}
【编程之美】2.8 找符合条件的整数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。