C++中计算区间内能被m整除且偶数位包含数字d的数字个数

给定一个整数区间、一个用作除数的变量m和一个用于检查数字'd'是否位于偶数位的变量d，任务是计算区间内能被变量m整除且偶数位包含数字d的数字个数。

例如

输入 - int start = 20, end = 50, d = 8, m = 4

输出 - 区间内能被m整除且偶数位包含数字d的数字个数为：2

解释 - 区间从20到50。因此，包含数字d（即8）的可能数字是28、38和48，其中8位于偶数位（即第2位），数字24和48能被m（即4）整除，因此个数为2。

输入 - int start = 10, end = 100, d = 6, m = 2

输出 - 区间内能被m整除且偶数位包含数字d的数字个数为：8

解释 - 区间从10到100。因此，包含数字d（即6）的可能数字是16、26、36、46、56、66、76、86和96，其中6位于偶数位，除了6和66（6位于奇数位），我们不包含这些数字。现在，我们将检查列表中能被2整除的数字，因此所有数字（即16、26、36、46、56、76、86和96）都能被2整除，因此个数为8。

下面程序中使用的算法如下

  • 创建一个从变量start到变量end的整数数字范围，并声明变量d和m并输入值。将数据传递给函数以进行进一步处理。
  • 创建一个向量类型的变量，例如vec。
  • 启动while循环，直到值为变量start中的值。现在，在while循环内部，将值val % 10压入向量中，并将val设置为val / 10。
  • 通过传递vec.begin()和vec.end()作为参数，调用STL中的reverse函数。
  • 使用memset将数组中的值设置为-1。
  • 返回set_total(0, 0, 0, vec)，这是一个将检查数字的偶数位是否为d且能被m整除的函数。
  • 在set_total函数内部 -
    • 检查IF place等于向量的size，然后检查IF temp = 0，则返回1或返回0。
    • 检查IF arr[place][temp][val]不等于-1，则返回arr[place][temp][val]的值。
    • 检查IF place % 2 = 1，则检查IF val = 0，则检查IF d大于vec[place]，则返回0
    • 声明变量temp_2并将其设置为0。
    • 检查IF d小于vec[place]，则将temp_2设置为1。
    • 声明变量temp_3并递归调用set_total()，并返回arr[place][temp][val] = temp_3
    • 声明一个变量count来存储结果。
    • 声明一个变量set_limit，如果val等于1，则将其设置为9，否则将其设置为vec[place]。
    • 从i = 0开始循环到set_limit，并检查IF i等于d，则继续。
    • 声明一个变量temp_2并将其设置为val
    • 检查IF i小于vec[place]，则将temp_2设置为1
    • 使用对set_total函数的递归调用设置count
    • 返回arr[place][temp][val] = count。

示例

在线演示

#include <bits/stdc++.h>
using namespace std;

int arr[20][20][2];
int d, m;

int set_total(int place, int temp, int val, vector < int > vec) {
   if (place == vec.size()) {
      if (temp == 0) {
         return 1;
      }
      return 0;
   }
   if (arr[place][temp][val] != -1) {
      return arr[place][temp][val];
   }
   if (place % 2) {
      if (val == 0) {
         if (d > vec[place]) {
            return 0;
         }
      }
      int temp_2 = val;
      if (d < vec[place]) {
         temp_2 = 1;
      }
      int temp_3 = set_total(place + 1, (10 * temp + d) % m, temp_2, vec);
      return arr[place][temp][val] = temp_3;
   }
   int count = 0;
   int set_limit = (val ? 9 : vec[place]);
   for (int i = 0; i <= set_limit; i++) {
      if (i == d) {
         continue;
      }
      int temp_2 = val;
      if (i < vec[place]) {
         temp_2 = 1;
      }
      count += set_total(place + 1, (10 * temp + i) % m, temp_2, vec);
   }
   return arr[place][temp][val] = count;
}

int divisible(int val) {
   vector < int > vec;
   while (val) {
      vec.push_back(val % 10);
      val = val / 10;
   }
   reverse(vec.begin(), vec.end());
   memset(arr, -1, sizeof(arr));
   return set_total(0, 0, 0, vec);
}
int main() {
   int start = 20, end = 50;
   d = 8, m = 4;
   int count = divisible(end) - divisible(start);
   cout << "Count of Numbers in a Range divisible by m and having digit d in even positions are: " << count;
   return 0;
}

如果我们运行上述代码，它将生成以下输出：

输出

Count of Numbers in a Range divisible by m and having digit d in even positions are: 2

更新于：2021年1月29日

浏览量 154

开启你的职业生涯

完成课程获得认证

开始学习
广告