C++ 中计算数字个数（小于或等于 N 且数字和为给定值）

给定一个包含数字的字符串 str 和一个总和 total 作为输入。目标是找到小于等于 str 的数字，其各位数字之和等于 total。

让我们通过例子来理解。

例如

输入 - N=”110”  sum=5

输出 - 小于或等于 N 且数字和为给定值的数字个数为：7

解释 - 小于或等于 110 且数字和等于 5 的数字为：

5、14、23、32、41、50 和 104。

输入 - N=”1000”  sum=3

输出 - 小于或等于 N 且数字和为给定值的数字个数为：10

解释 - 小于或等于 1000 且数字和等于 3 的数字为：

3、12、21、30、102、111、120、201、210 和 300。

下面程序中使用的方案如下

在这种方案中，我们将使用动态规划将数字及其数字的和存储在数组 arr[18][2][162] 中。这里 18 表示最多 18 位数字，2 表示值 0 和 1。而 162 表示如果所有 18 位数字都是 9，则可能的最大和 (18*9=162)。

元素 arr[i][j][k] 的值表示考虑前 i 位数字的数字个数，其中 j 为 0 或 1，具体取决于当前构造的数字的第 i 位是否小于或大于 N 中的前 i 位数字。（如果 N 为 123 且 i 为 2，则我们将检查 2 位数字是否等于或大于 12。如果等于 12，则 j 在 arr[i][j][k] 中将为 1，否则 j 将为 0）。索引 k 将是 arr[i][j][k] 中前 i 位数字的和。

如果 i=N 的位数且 k=输入的和，则结果为 1，否则为 0。

为了填充下一位数字（第 i+1 位），我们将检查 j。如果 j 为 1，则前 i-1 位数字等于 N 的前 i-1 位数字，因此下一位数字只能取 0 到第 i+1 位数字之间的值，以使其 <= N。

如果 j 为 0，则前 i-1 位数字小于 N 中的前 i-1 位数字。因此，我们可以将 0 到 9 之间的任何值放在下一位数字（第 i+1 位）的位置，它仍然小于 N。

最后将结果作为最终计数返回。

  • 获取表示数字 N 的字符串 str 和 total 作为数字之和。
  • 获取数组 arr[18][2][162] 并使用 memset 将其初始化为 -1。
  • 函数 count_digits(int i, bool check, int temp, int total, string str, int size) 递归地填充 arr[][][]，并在最后返回小于或等于 N 且数字和为给定值的数字个数。
  • 如果当前数字位数 i 等于 N 的位数，且当前和 temp 等于输入的和 total，则返回 1，否则返回 0。
  • 获取计数 count = arr[i][check][temp]。如果它不等于 -1，则返回 count 作为结果。
  • 获取临时变量 check_2（布尔值）和 temp_2。（整数）。
  • 使用 for 循环遍历数字 0 到 9，并比较 check 是否为 1 或 0。如果为 1，则将当前数字 ch 与 str[i] 比较。如果它更大，则中断循环（不做任何事）。
  • 设置 check_2 = check || ch < str[i]。
  • 设置 temp_2 = temp + (ch - '0') 作为当前和。
  • 将 count_digits(i + 1, check_2, temp_2, total, str, size) 添加到 count 中，以递归计算数字之和。
  • 最后返回 count 作为结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
   if (i == size) {
      if (temp == total) {
         return 1;
      } else {
         return 0;
      }
   }
   int count = arr[i][check][temp];
   if (count != -1) {
      return count;
   }
   count = 0;
   bool check_2;
   int temp_2;
   for (char ch = '0'; ch <= '9'; ch++) {
      if (!check) {
         if (ch > str[i]) {
            break;
         }
      }
      check_2 = check || ch < str[i];
      temp_2 = temp + (ch - '0');
      count += count_digits(i + 1, check_2, temp_2, total, str, size);
   }
   return count;
}
int main() {
   string str = "1101";
   int size = str.size();
   int total = 5;
   memset(arr, -1, sizeof(arr));
   cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
   return 0;
}

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

输出

Count of numbers smaller than or equal to N with given digit sum are: 26

更新于: 2021年1月29日

2K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告