这里的问题是确定长度为N的字符串中包含的字符'0'到'9'的总数,提供一个整数N和一个字符串前缀数组pre[],使得这些字符串中没有任何一个包含提供的前缀。本文的目的是实现一个程序,找到不具有给定前缀的N位数的数量。
在C编程语言中,一组不同的字符串被称为数组,因为数组是一组具有相似类型的数据片段的线性组合。
As we already know, the string is a character-by-character, one-dimensional array that ends with an empty or a null character.
示例示例1
让我们假设输入N = 2,
The given prefix, pre = {“1”}
登录后复制
Output obtained: 90
登录后复制
解释
在这里,除了{"01","10",“11”, “12”, “13", “14”, “15”, “16”, “17”, “18”, “19”, "21", "31", "41", "51", "61", "71", "81", "91"}之外的所有2位数字符串都是有效的。
示例示例2
让我们将输入值 N = 3 作为例子。
The given prefix, pre = {“56”}
登录后复制
Output obtained: 990
登录后复制
解释
在这里,除了{"560", "561", “562”, “563", “564”, “565”, “566”, “567”, “568”, “569”}之外的所有3位数字字符串都是有效的。
示例示例3
让我们来看一个输入N = 1,
The given prefix, pre = {“6”}
登录后复制
Output obtained: 9
登录后复制
解释
除了{"6"}之外,这里的所有1位数字符串都是有效的。
问题陈述
实现一个程序来找到不具有给定前缀的N位数的数量。
方法
为了找到不带给定前缀的N位数的数量,我们使用以下方法。
解决这个问题并找到不具有给定前缀的N位数的方法
考虑到字符串中每个位置有10个字符选项,总共有(10N)个潜在字符串。不要计算所需字符串的总数,而是减去不需要的字符串的总数。在迭代前将具有相同初始字符的前缀合并为较长的前缀可能导致某些重复的删除。
算法
找到不具有以下给定前缀的N位数的计数算法
-
第一步 − 开始
-
第二步 - 定义函数来计算长度为N的字符串中不包含给定前缀的总数
-
第三步 - 计算总共存在的字符串
-
第四步 - 创建一个数组和计数器 a 和 aCount,并将这些前缀插入其中
-
步骤 5 − 创建一个新的前缀字符串数组
-
第6步 - 对于每个起始字符进行迭代
-
第7步 - 迭代数组以计算最小大小的前缀
-
第8步 - 现在将所有这些最小前缀放入新的前缀数组中
-
第9步 - 迭代新的前缀
-
第10步 - 扣除不需要的字符串
-
第11步 − 打印获得的结果
-
第12步 − 停止
示例:C程序
这是上述算法的C程序实现,用于查找不具有给定前缀的N位数的数量。
#include
#include
#include
#define MAX_LENGTH 10
// Function to calculate total strings of length N without the given prefixes
int totalStrings(int N, char pre[][MAX_LENGTH], int pre_Count){
// Calculate total strings present
int total = (int)(pow(10, N) + 0.5);
// Make an array and counter a and aCount respectively and insert these prefixes with same character in the array
char a[10][MAX_LENGTH];
int aCount[10] = {0};
for (int i = 0; i < pre_Count; i++) {
int index = pre[i][0] - '0';
strcpy(a[index] + aCount[index] * MAX_LENGTH, pre[i]);
aCount[index]++;
}
// Make a new array of prefixes strings
char new_pre[pre_Count][MAX_LENGTH];
int new_pre_count = 0;
// Iterating for each of the starting //character
for (int x = 0; x < 10; x++){
int m = N;
// Iterate over the array to calculate minimum size prefix
for (int j = 0; j < aCount[x]; j++){
int p_length = strlen(a[x] + j * MAX_LENGTH);
m = (m < p_length) ? m : p_length;
}
// now take all these minimum prefixes in the new array of prefixes
for (int j = 0; j < aCount[x]; j++){
int p_length = strlen(a[x] + j * MAX_LENGTH);
if (p_length