数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学不包含指定前缀的 N 位数的个数
本问题旨在确定长度为 N 的字符串的总数，这些字符串包含字符“0”到“9”，给定一个整数 N 和一个字符串前缀数组 pre[]，这样任何字符串都不能包含所提供的前缀。本文旨在实现一个程序来查找不包含给定前缀的 N 位数的个数。
在 C 语言中，各种字符串的集合被称为数组，因为数组是相似类型数据的线性分组。
众所周知，字符串是一个字符一个字符的，一维数组，以空字符或 null 字符结尾。
示例 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
让我们输入 N = 3，
The given prefix, pre = {“56”}
Output obtained: 990
解释
这里所有三位数字符串，除了 {"560", "561", “562”, “563", “564”, “565”, “566”, “567”, “568”, “569”} 都是有效的。
示例 3
让我们输入 N = 1，
The given prefix, pre = {“6”}
Output obtained: 9
解释
这里所有一位数字符串，除了 {"6"} 都是有效的。
问题陈述
实现一个程序来查找不包含给定前缀的 N 位数的个数。
方法
为了找到不包含给定前缀的 N 位数的个数，我们使用以下方法。
解决这个问题并找到不包含给定前缀的 N 位数个数的方法
鉴于字符串中每个位置都有 10 个字符选项，因此共有 (10N) 个潜在字符串。与其计算所需字符串的总数，不如减去不需要的字符串的总数。在遍历前缀之前，将初始字符相同的较长前缀合并，可能会消除某些重复。
算法
下面给出了查找不包含给定前缀的 N 位数个数的算法
步骤 1 − 开始
步骤 2 − 定义函数以计算长度为 N 的字符串总数，不包含给定前缀
步骤 3 − 计算存在的字符串总数
步骤 4 − 分别创建数组和计数器 a 和 aCount，并将这些具有相同的前缀插入其中
步骤 5 − 创建一个新的前缀字符串数组
步骤 6 − 迭代每个起始字符
步骤 7 − 迭代数组以计算最小大小的前缀
步骤 8 − 现在将所有这些最小前缀放入新的前缀数组中
步骤 9 − 迭代新的前缀
步骤 10 − 减去不需要的字符串
步骤 11 − 打印获得的结果
步骤 12 − 停止
示例：C 程序
这是上面编写的算法的 C 语言程序实现，用于查找不包含给定前缀的 N 位数的个数。
#include <stdio.h>
#include <math.h>
#include <string.h>
#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 <= m){
strcpy(new_pre[new_pre_count], a[x] + j * MAX_LENGTH);
new_pre_count++;
}
}
}
// Iterating through the new prefixes
for (int i = 0; i < new_pre_count; i++){
// Subtract the unwanted strings
total -= (int)(pow(10, N - strlen(new_pre[i])) + 0.5);
}
return total;
}
// The main function
int main(){
int N = 5;
char pre[][MAX_LENGTH] = {"1", "0", "2"};
int pre_Count = sizeof(pre) / sizeof(pre[0]);
printf("%d\n", totalStrings(N, pre, pre_Count));
return 0;
}
输出
70000
结论
同样，我们可以找到不包含给定前缀的 N 位数的个数。
本文解决了获取查找不包含给定前缀的 N 位数个数的程序的挑战。
这里提供了 C 语言代码以及查找不包含给定前缀的 N 位数个数的算法。
81 次查看
