二分法的应用问题枚举三位数

Question

一个六位数，每一位上数字都是非零自然数，任何 3 个连续排列的数字都构成能被4 和 7 整除的三位数，那么这个六位数是?

01 #include<bits/stdc++.h>

02 using namespace std;

03 const int MOD=4*7;

04 int f[10],g[10];

05 int main(){

06 int left,right,mid,sum,n=0;

07 for(int i=1;i<10;i++){

08 left=1,right=9;

09 // 二分法找到一个 mid，使其满足题目要求

10 while(left<=right){

11 mid=(left+right)>>1;

12 sum=(20i)%MOD-mid; //这里看不懂,请大神帮忙*****

13 if(!sum){

14 f[n]=i;

15 g[n++]=mid;

16 break;

17 }

18 else if(sum<0)

19 right=mid-1;//如果和太小，就减小右边界

20 else

21 left=mid+1;//如果和太大，就增加左边界

22 }

23 }

24 for(int i=0;i<n;i++)

25 for(int j=0;j<n;j++)

26 for(int k=0;k<n;k++)

27 if(!((3f[i]+f[j]-2f[k])%MOD)) //这里也看不懂**********。

28 cout<<f[i]<<f[j]<<f[k]<<g[i]<<g[j]<<g[k]<<endl;

29 return 0;

30 }

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

这段代码试图解决的问题是找出一个六位数，这个数的每一位都是非零自然数，且任何三个连续排列的数字组成的三位数都能被4和7整除。代码使用了二分查找法来寻找符合条件的数字。下面我将解释你提到的两个问题：

代码段10-22中二分法的应用：

二分查找法通常用于在有序数组中查找特定元素。在这个问题中，二分查找被用来找到一个数字mid，这个数字与给定的数字i组合，能够构成一个能被4和7整除的三位数。

代码段12中的sum=(20*i)%MOD-mid;：

这行代码的目的是构造一个三位数，其中i是百位数字，mid是十位数字。20*i表示将i放在百位，然后对4和7的乘积（即MOD）取模，确保结果仍然是一个三位数。然后从这个结果中减去mid，得到的结果sum就是三位数的个位数字。如果sum为0，说明找到了一个符合条件的三位数。

代码段27中的if(!((3*f[i]+f[j]-2*f[k])%MOD))：

这行代码是在检查由三个数字f[i]、f[j]和f[k]构成的三位数是否满足条件。这个三位数的构造方式是：百位是f[i]，十位是f[j]，个位是通过特定的线性组合3*f[i] + f[j] - 2*f[k]得到的。这个线性组合确保了无论f[k]如何变化，三位数都能被4和7整除。

解释代码逻辑：

1. 初始化：f数组和g数组用于存储找到的符合条件的数字对。
2. 外层循环：遍历每一位可能的百位数字（从1到9）。
3. 二分查找：对于每一位百位数字，使用二分查找找到与之对应的十位数字，使得构成的三位数能被4和7整除。
4. 存储结果：找到的符合条件的数字对存储在f和g数组中。
5. 内层循环：三重循环遍历所有可能的数字对组合，检查由三个数字对构成的六位数是否满足条件。

代码实现：

这段代码实际上并没有完全实现题目要求的功能，因为它没有考虑到所有连续的三位数都必须满足条件。它只是简单地找到了一些符合条件的数字对，并没有确保这些数字对组合成的六位数满足题目的所有条件。

参考资料：

• 二分查找算法
• C++编程基础

如果你需要一个完整的解决方案，可能需要重新设计算法，确保所有连续的三位数都满足能被4和7整除的条件。这可能需要更复杂的逻辑，而不是简单的二分查找和线性组合。