| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 742 人关注过本帖
标题:K好数--算法复杂度分析求指点
只看楼主 加入收藏
shell羊
Rank: 2
等 级:论坛游民
帖 子:11
专家分:10
注 册:2014-10-31
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:2 
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
样例输出
7
数据规模与约定
对于30%的数据,KL <= 106;

对于50%的数据,K <= 16, L <= 10;

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

这里k和L的数据规模都是100,那么我现在考虑的有两个解法。一种是回溯法,一位一位的遍历每一种情况。如果是K进制,L位的话,那么总共要遍历K的L次方种情况。毕竟每一位上都可以是0到
K-1,当然回溯到不合题意的情况。
第二种是动态规划。求L位K进制数中K好数的数目,可以先求出L-1位K好数,L-2位K好数......1位K好数。设F[i][j]表示i位以数字j结尾的K好数数目,1<=i<=L,0<=j<K,状态转移方程:
F[i][j] = F[i-1][p](p遍历0到k-1的情况)的总和。那么这个算法的复杂度也是K的L次方次加法。
那么问题来了~~动态规划的节约时间的优点体现在哪里呢?或者说我用回溯法会时间超时,动态规划却不会的原因在哪里呢?
不知道我有么有清楚的描述我的问题~~~~求指点
搜索更多相关主题的帖子: 自然数 正整数 规模 
2015-03-21 10:20
shell羊
Rank: 2
等 级:论坛游民
帖 子:11
专家分:10
注 册:2014-10-31
收藏
得分:0 
自顶~~~
2015-03-21 13:38
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:20 
一头雾水,还未领会题意。多举例或许能看懂。
2015-03-21 16:21
快速回复:K好数--算法复杂度分析求指点
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029180 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved