没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全算法训练3-51

算法训练3-51

需积分: 0 0 下载量 21 浏览量 2022-08-08 18:50:43 上传评论收藏 31KB DOCX 举报

温馨提示

试读

13页

满足条件的3位4进制数：111、113、130、131 、133、200、 202、 203、220、 222、300、 302、 303、311、 313、3

资源详情

资源评论

资源推荐

算法训练 3-5

3 算法训练 K 好数

问题描述

如果一个自然数 N 的 K 进制表示中任意的相邻的两位都不是相邻的数字，那么我们就

说这个数是 K 好数。求 L 位 K 进制数中 K 好数的数目。例如 K = 4，L = 2 的时候，所有 K

好数为 11、13、20、22、30、31、33 共 7 个。由于这个数目很大，请你输出它对

1000000007 取模后的值。

输入格式

输入包含两个正整数，K 和 L。

输出格式

输出一个整数，表示答案对 1000000007 取模后的值。

样例输入

4 2

样例输出

数据规模与约定

对于 30%的数据，K

<= 10

；

对于 50%的数据，K <= 16， L <= 10；

对于 100%的数据，1 <= K,L <= 100。

题目分析:

1 理解”L 位 K 进制数中的 K 好数的数目”

K 进制数，取值范围为[0，K-1]； “L 位 K 进制数”，如：“2 位 4 进制

数”、 “3 位 7 进制数”；要求是任意相邻的两位不是相邻的数字。

2 “由于数很大……输出取模后的值”这一条件？

在数据规范与约定中，我们知道 1 K 100，1 L 100。假设 K=100，

L=100，即 100 位 100 进制数中 100 好数的情况下，它的数目约就有 100

100

，肯

定超过了 int，long long。所以通过取模来减小运算量。

3 举例分析 “2 位 4 进制数”和“3 为 4 进制数”

满足条件的 2 位 4 进制数：11、13 、20 、22 、 30、 31、 33，共 7 个。

满足条件的 3 位 4 进制数：111、113、130、131 、133、200、 202、 203、

220、 222、300、 302、 303、311、 313、330、 331、 333，共 18 个。

解题思路 1:

1 使用动态规划，通过组合子问题的解来求解原问题。

2 用 F[i][j]表示长为 i，最后一位数字是 j 的 K 好数的个数，则

F[i][j]= F[i][j]+sum F[i-1][k]，其中|j-k|!=1。

当前位置的数总数=当前位置的数的数目+前一个位置的数的总数。

i j

…

100

1 0

…

100

解题思路 2:

在 F[i][j]中，i 代表所在的位数（i=0 代表个位，i=1 代表十

位，以此类推）。j 代表取 K 进制数的一个数(如果是 4 进制数，那

么 j 取[0,3]中的一个数)。F[i][j]表示当前位置的数 K 好数的个

数，则 F[i][j]= F[i][j]+sum F[i-1][k]，其中|j-k|!=1。

i j

…

100

…

100

参考代码:

#include <iostream>

using namespace std;

int main(int argc, char** argv) {

int k,l;

cin>>k>>l;

long long table[100][100];

for(int i=0;i<k;i++)

{ table[0][i]=1ll;

}

table[0][0]=0ll;

for(int i=1;i<l;i++)

{ for(int j=0;j<k;j++)

{

long long x=0;

for(int y=0;y<k;y++)

{

if(y!=j+1 && y!=j-1)

{

x+=table[i-1][y];

}

剩余12页未读，继续阅读

内容反馈

耄先森吖

粉丝: 59
资源: 293

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

算法训练3-51

评论0

最新资源

算法训练3-51

评论0

单片机MC-51应用

程序员考试刷题-algorithms:算法

基于ATmega2560设计的智能家居机器人管家AD设计硬件原理PCB+软件程序源码+文档资料.zip

DeepRL_PyTorch：用于研究的深度强化学习代码。 当前，仅存在算法代码：DQN，C51，QR-DQN，IQN和QUOTA

matlab体素法代码-3D-shape-retrieval:针对三维模型检索，并采用卷积神经网络，提出两个算法：1.采用体素化深层特征进行训

图像矩阵matlab代码-comparingGSalgorithms:比较GS算法

寂寞的数-Java（暴力破解）

单片机技术应用-课程标准.doc

基于51单片机YS-LDV7语音识别+配套资料-电路方案

NCP:通过传播网络代码来学习通用的神经体系结构

MinDS模型的matlab代码-FaceX:基于显式形状回归算法的高性能开源人脸标志物检测器

《单片机技术应用》课程标准.doc

C++进阶课程讲义_v1.0.4.pdf

解析深度学习：语音识别实践

Hadoop硬实战 [（美）霍姆斯著][电子工业出版社][2015.01]_PDF电子书下载 带书签目录 高清完整版.rar )

java安卓开发外卖订餐系统课程设计.doc

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

STM32F103C8T6核心板-电路原理图1.PDF

软件工程导论(第六版)课后习题答案1

OpenVAS离线资源

最新资源

DeepRL_PyTorch：用于研究的深度强化学习代码。当前，仅存在算法代码：DQN，C51，QR-DQN，IQN和QUOTA

Hadoop硬实战 [（美）霍姆斯著][电子工业出版社][2015.01]_PDF电子书下载带书签目录高清完整版.rar )