首页 > 试题广场 >

牛牛恨66

[编程题]牛牛恨66
  • 热度指数：1501 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
众所周知，牛牛不喜欢6这个数字（因为牛牛和66发音相近）
所以他想知道，不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）
输入只包含一个正整数n（1<=n<20）

示例1

输入

1

输出

"10"

说明

1，2,3,4,5,6,7,8,9,10 这十个数字中都满足条件
示例2

输入

2

输出

"99"

说明

因为66不可以
算法知识视频讲解
开通博客
头像 Miss.Zhou
发表于 2020-02-07 19:15:08
显而易见的动态规划先不看二重循环，先只考虑a[i]+=(a[i-1]+a[i-2])9这句话啥意思呢对于i位数的答案，是与i-1位和i-2位的答案有关系的假设a[i]表示i位数中满足条件的数，如果没有连续的6（1）第i位是0,1,2,3,4,5,7,8,9，第i-1位随便（2）第i位是6，第i-1位 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Maokt
发表于 2021-08-02 13:43:44
算法思想一：递归 解题思路： 由题知：对于 i 位数的答案，是与 i-1 位和 i-2 位的答案有关系的，首先想到采用递归的方式进行计算 1、递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。 2、递归如何推进：当前位（第i位） 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-02 23:42:16
题目描述众所周知，牛牛不喜欢6这个数字（因为牛牛和66发音相近）所以他想知道，不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）输入只包含一个正整数n（1<=n<20） 方法一：递归的思想 求解思路对于本题目所要求解的答案，因为要求出不连续的6，因此我们自然想到第i位数字是否 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-01 19:42:31
题意整理 输入正整数 。 在 到 之间，有多少个数字不包含连续的 ，则输出多少。 方法一（记忆化递归） 1.解题思路 递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。 递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客534170409号
发表于 2021-08-06 23:29:20
题目描述 要求输出不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）输入只包含一个正整数n（1<=n<20） 方法一 记忆化搜索 解题思路 定义DFS函数，搜索位十进制数字中符合要求数字的个数。在计数时，对于位数为的数字，如果第位为，那么第位必须不能为，所以第位有个数字可 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 未来0116
发表于 2021-08-04 21:23:18
一.题目描述NC517牛牛恨66求不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的），输入只包含一个正整数n（1<=n<20）二.算法(动态规划)状态定义：dp[i]表示输入为i时，有多少个数字不含有连续的6。状态初始化：当输入为0时，只有1不含66，赋值为1；当输入为1时， 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 数组
难度：
7条回答 3021浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号