※ 来源:・水木社区 http://newsmth.net・[FROM: 218.247.129.*]
发信人: nwn (Lie), 信区: DOS
标 题: Re: 如何用DOS命令，获取一个目录下的文件数目？
发信站: 水木社区 (Fri Mar 9 09:54:55 2007), 站内
dir /b | find /v /c "$$$$" > 1.log
该结果统计当前目录下的文件和目录数。
如果只需要文件，使用 dir /b /a-d | find /v /c "$$$$" >1.log
--
※ 来源:・水木社区 newsmth.net・[FROM: 125.46.17.*]
今天去水木看到的.果然强.我来解释一下意思
dir /b 使用空格式(没有标题信息或摘要)。
dir /a-d /a是显示具有指定属性的文件。d是目录,-d就是去掉目录
| 通道符,把dir /b的输出当中后面find的输入
find
/v 显示所有未包含指定字符串的行。
/c 仅显示包含字符串的行数
"$$$$" 特殊字符,一般文件中都没这个字符,不过可以用$$$$来命名文件夹,所以我建议用冒号,这个不能当作文件夹或者文件的名字.
> 输出到
1.log 文件
这个比较好:dir /b | find /v /c ":" > 1.log
# 4 figures arranged in 2 rows and 2 columns
attach(mtcars)
par(mfrow=c(2,2))
plot(wt,mpg, main="Scatterplot of wt vs. mpg")
plot(wt,disp, main="Scatterplot of wt vs disp")
hist(wt, main="Histogram of wt")
boxplot(wt, main="Boxplot of wt")
click to view在用Latex写文章，特别是长篇的论文，是非常方便的，虽然没有word那么傻瓜，生成文档需要编译，而且还要学习一些简单的命令，不过对于其节省的时间，它太划算了，想到word里面编写多个图片的文章是，稍微改动一下文章内容或者图像大小，图就不知道飘到哪里去了，每次都搞得人很恼火，用Latex就不存在这种问题，可以精确定位图片， 不过有件让我觉得麻烦的事情就是latex的源文件只支持eps格式的图形格式，需要将其他图片格式转化为eps，我以前用的方法是安装一个打印到文件的ps打印机，然后将图片打印为ps文件，然后用ghostview的ps->eps功能去转换，也可以使用软件如 jpg2ps，abs等等，不过这又会出现一个问题，有的时候生成的eps图像有多余的白边，需要裁除它。我以前基本上是在用ghost view的ps to eps功能时，不选择自动计算boundaryBox，自己手动裁剪，不过这种方法的问题是裁剪出的图片大小不精确。今天在Ctex论坛看到一个帖子，使用acrobat的裁剪功能，感觉非常实用，就收藏了：
用Adobe PDF打印机生成PDF图形，然后用Acrobat打开，执行菜单项
【文档（Document）】
【裁剪页面（Crop Pages）】选择【删除白边距（Remove White Margins）】
【文件（File）】
【另存为(Save As…)】，保存为EPS格式，结束。
| 用Latex打论文，通过\centering命定可以将图片居中。 但是一般做出来的图片可能会有空白的边缘，使得看到的实际的图片无法居中。 发现用Gsview居然可以简单的裁掉空白的边缘： 在file中选择ps\eps转换那一个，然后将自动裁边打钩，导出就OK了 |
start→Control Pannel→Hardware and Sound →Sound→Recording→点选Microphone 点下面的 Properties→Levels→ 将下面 Microphone Boost 调整到最大 一路OK 返回就可以了。
以上对应中文，大概为：开始按钮→控制面板→硬件和声音→声音→录制→选择相应麦克风并按右下的属性→级别→麦克风加强 →确定。
标签： libsvm回归预测软件使用方法教育 | 分类： 科研-支持向量机(SVM)预测 |
）！再次感谢你们的关注，希望在交流中一起进步!修改和增加部分已经用红色字体区分了，还有就是第五章图，估计以前做错的人不少，不要怪我！
先前的一些步骤可以参照我《科研-支持向量机(SVM)预测》中的几篇，包括文件格式等。标签： libsvmgridregressioneasygrid回归支持向量机教育 | 分类： 科研-支持向量机(SVM)预测 |
Although the linear regression model is simple and used frequently it's not adequate for some purposes. For example, imagine the response variable y to be a probability that takes on values between 0 and 1. A linear model has no bounds on what values the response variable can take, and hence y can take on arbitrary large or small values. However, it is desirable to bound the response to values between 0 and 1. For this we would need something more powerful than linear regression.
Another problem with the linear regression model is the assumption that the response y has a constant variance. This can not be the case if y follows for example a binomial distribution (y ~ Bin(p,n)). If y also is normalized so that it takes values between 0 and 1, hence y = Bin(p,n)/n, then the variance would then be Var(y) = p*(1-p), which takes on values between 0 and 0.25. To then make an assumption that y would have a constant variance is not feasible.
In situations like this, when our response variable follows a binomial distribution, we need to use general linear regression. A special case of general linear regression is logistic regression, which assumes that the response variable follows the logit-function shown in Figure 4.
Figure 4 The logit function
Note that it's only defined for values between 0 and 1. The logit function goes from minus infinity to plus infinity. The logit function has the nice property that logit(p) = -logit(1-p) and its inverse is defined for values from minus infinity to plus infinity, and it only takes on values between 0 and 1.
However, to get a better understanding for what the logit-function is we will now introduce the notation of odds. The odds of an event that occurs with probability P is defined as
odds = P / (1-P).
Figure 5 shows how the odds-function looks like. As we can see, the odds for an event is not bounded and goes from 0 to infinity when the probability for that event goes from 0 to 1.
However, it's not always very intuitive to think about odds. Even worse, odds are quite unappealing to work with due to its asymmetry. When we work with probability we have that if the probability for yes is p, then the probability for no is 1-p. However, for odds, there exists no such nice relationship.
To take an example: If a Boolean variable is true with probability 0.9 and false with probability 0.1, we have that the odds for the variable to be true is 0.9/0.1 = 9 while the odds for being false is 0.1/0.9 = 1/9 = 0.1111… . This is a quite unappealing relationship. However, if we take the logarithm of the odds, when we would have log(9) for true and log(1/9) = -log(9) for false.
Hence, we have a very nice symmetry for log(odds(p)). This function is called the logit-function.
logit(p) = log(odds(p)) = log(p/(1-p))
As we can see, it is true in general that logit(1-p)=-logit(p).
logit(1-p) = log((1-p)/p) = – log(p/(1-p)) = -logit(p)
Figure 5 The odds function
The odds function maps probabilities (between 0 and 1) to values between 0 and infinity.
The logit-function has all the properties we wanted but did not have when we previously tried to use linear regression for a problem where the response variable followed a binomial distribution. If we instead use the logit-function we will have p bounded to values between 0 and 1 and we will still have a linear expression for our input variable x
logit(p) = a + 
* x.
If we would like to rewrite this expression to get a function for the probability p it would look like
决策树这种算法有着很多良好的特性，比如说训练时间复杂度较低，预测的过程比较快速，模型容易展示（容易将得到的决策树做成图片展示出来）等。但是同时， 单决策树又有一些不好的地方，比如说容易over-fitting，虽然有一些方法，如剪枝可以减少这种情况，但是还是不够的。
模型组合（比如说有Boosting，Bagging等）与决策树相关的算法比较多，这些算法最终的结果是生成N(可能会有几百棵以上）棵树，这样可以大 大的减少单决策树带来的毛病，有点类似于三个臭皮匠等于一个诸葛亮的做法，虽然这几百棵决策树中的每一棵都很简单（相对于C4.5这种单决策树来说），但 是他们组合起来确是很强大。
在最近几年的paper上，如iccv这种重量级的会议，iccv 09年 的里面有不少的文章都是与Boosting与随机森林相关的。模型组合+决策树相关的算法有两种比较基本的形式 – 随机森林与GBDT((Gradient Boost Decision Tree)，其他的比较新的模型组合+决策树的算法都是来自这两种算法的延伸。本文主要侧重于GBDT，对于随机森林只是大概提提，因为它相对比较简单。
在看本文之前，建议先看看机器学习与数学(3)与其中引用的论文，本文中的GBDT主要基于此，而随机森林相对比较独立。
基础内容：
这里只是准备简单谈谈基础的内容，主要参考一下别人的文章，对于随机森林与GBDT，有两个地方比较重要，首先是information gain，其次是决策树。这里特别推荐Andrew Moore大牛的Decision Trees Tutorial，与Information Gain Tutorial。Moore的Data Mining Tutorial系列非常赞，看懂了上面说的两个内容之后的文章才能继续读下去。
决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树：
就是将空间划分成下面的样子：
这样使得每一个叶子节点都是在空间中的一个不相交的区域，在进行决策的时候，会根据输入样本每一维feature的值，一步一步往下，最后使得样本落入N个区域中的一个（假设有N个叶子节点）
随机森林(Random Forest):
随机森林是一个最近比较火的算法，它有很多的优点：
随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输 入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本 为那一类。
在建立每一棵决策树的过程中，有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那 么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M 个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一 个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。
按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域 的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数 据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。
随机森林的过程请参考Mahout的random forest 。这个页面上写的比较清楚了，其中可能不明白的就是Information Gain，可以看看之前推荐过的Moore的页面。
Gradient Boost Decision Tree:
GBDT是一个应用很广泛的算法，可以用来做分类、回归。在很多的数据上都有不错的效果。GBDT这个算法还有一些其他的名字，比如说MART(Multiple Additive Regression Tree)，GBRT(Gradient Boost Regression Tree)，Tree Net等，其实它们都是一个东西（参考自wikipedia – Gradient Boosting)，发明者是Friedman
Gradient Boost其实是一个框架，里面可以套入很多不同的算法，可以参考一下机器学习与数学(3)中的讲解。Boost是”提升”的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果。
原始的Boost算法是在算法开始的时候，为每一个样本赋上一个权重值，初始的时候，大家都是一样重要的。在每一步训练中得到的模型，会使得数据点的估计 有对有错，我们就在每一步结束后，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高 的权重。然后等进行了N次迭代（由用户指定），将会得到N个简单的分类器（basic learner），然后我们将它们组合起来（比如说可以对它们进行加权、或者让它们进行投票等），得到一个最终的模型。
而Gradient Boost与传统的Boost的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boost中，每个新的模型的简历是为了使得之前模型的残差往梯度方向减少，与传统Boost对正确、错误的样本进行加权有着很大的区别。
在分类问题中，有一个很重要的内容叫做Multi-Class Logistic，也就是多分类的Logistic问题，它适用于那些类别数>2的问题，并且在分类结果中，样本x不是一定只属于某一个类可以得到 样本x分别属于多个类的概率（也可以说样本x的估计y符合某一个几何分布），这实际上是属于Generalized Linear Model中讨论的内容，这里就先不谈了，以后有机会再用一个专门的章节去做吧。这里就用一个结论：如果一个分类问题符合几何分布，那么就可以用Logistic变换来进行之后的运算。
假设对于一个样本x，它可能属于K个分类，其估计值分别为F1(x)…FK(x)，Logistic变换如下，logistic变换是一个平滑且将数据规范化（使得向量的长度为1）的过程，结果为属于类别k的概率pk(x)，
对于Logistic变换后的结果，损失函数为：
其中，yk为输入的样本数据的估计值，当一个样本x属于类别k时，yk = 1，否则yk = 0。
将Logistic变换的式子带入损失函数，并且对其求导，可以得到损失函数的梯度：
上面说的比较抽象，下面举个例子：
假设输入数据x可能属于5个分类（分别为1,2,3,4,5），训练数据中，x属于类别3，则y = (0, 0, 1, 0, 0)，假设模型估计得到的F(x) = (0, 0.3, 0.6, 0, 0)，则经过Logistic变换后的数据p(x) = (0.16,0.21,0.29,0.16,0.16)，y – p得到梯度g：(-0.16, -0.21, 0.71, -0.16, -0.16)。观察这里可以得到一个比较有意思的结论：
假设gk为样本当某一维（某一个分类）上的梯度:
gk>0时，越大表示其在这一维上的概率p(x)越应该提高，比如说上面的第三维的概率为0.29，就应该提高，属于应该往“正确的方向”前进
越小表示这个估计越“准确”
gk<0时，越小，负得越多表示在这一维上的概率应该降低，比如说第二维0.21就应该得到降低。属于应该朝着“错误的反方向”前进
越大，负得越少表示这个估计越“不错误 ”
总的来说，对于一个样本，最理想的梯度是越接近0的梯度。所以，我们要能够让函数的估计值能够使得梯度往反方向移动（>0的维度上，往负方向移动，<0的维度上，往正方向移动）最终使得梯度尽量=0），并且该算法在会严重关注那些梯度比较大的样本，跟Boost的意思类似。
得到梯度之后，就是如何让梯度减少了。这里是用的一个迭代+决策树的方法，当初始化的时候，随便给出一个估计函数F(x)（可以让F(x)是一个随机的值，也可以让F(x)=0），然后之后每迭代一步就根据当前每一个样本的梯度的情况，建立一棵决策树。就让函数往梯度的反方向前进，最终使得迭代N步后，梯度越小。
这里建立的决策树和普通的决策树不太一样，首先，这个决策树是一个叶子节点数J固定的，当生成了J个节点后，就不再生成新的节点了。
算法的流程如下:（参考自treeBoost论文）
0. 表示给定一个初始值
1. 表示建立M棵决策树（迭代M次）
2. 表示对函数估计值F(x)进行Logistic变换
3. 表示对于K个分类进行下面的操作（其实这个for循环也可以理解为向量的操作，每一个样本点xi都对应了K种可能的分类yi，所以yi, F(xi), p(xi)都是一个K维的向量，这样或许容易理解一点）
4. 表示求得残差减少的梯度方向
5. 表示根据每一个样本点x，与其残差减少的梯度方向，得到一棵由J个叶子节点组成的决策树
6. 为当决策树建立完成后，通过这个公式，可以得到每一个叶子节点的增益（这个增益在预测的时候用的）
每个增益的组成其实也是一个K维的向量，表示如果在决策树预测的过程中，如果某一个样本点掉入了这个叶子节点，则其对应的K个分类的值是多少。比如 说，GBDT得到了三棵决策树，一个样本点在预测的时候，也会掉入3个叶子节点上，其增益分别为（假设为3分类的问题）：
(0.5, 0.8, 0.1), (0.2, 0.6, 0.3), (0.4, 0.3, 0.3)，那么这样最终得到的分类为第二个，因为选择分类2的决策树是最多的。
7. 的意思为，将当前得到的决策树与之前的那些决策树合并起来，作为新的一个模型(跟6中所举的例子差不多)
GBDT的算法大概就讲到这里了，希望能够弥补一下上一篇文章中没有说清楚的部分：）
实现：
看明白了算法，就需要去实现一下，或者看看别人实现的代码，这里推荐一下wikipedia中的gradient boosting页面，下面就有一些开源软件中的一些实现，比如说下面这个：http://elf-project.sourceforge.net/
参考资料：
除了文章中的引用的内容（已经给出了链接）外，主要还是参考Friedman大牛的文章：Greedy function approximation : A Gradient Boosting Machine
本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@gmail.com
Blogger一个突出的特点就是简洁但功能强大，没有多余而花哨的功能，必要的功能一个都不差。Bloger自由性最大的地方在于其模板可以自定义，也就是说你可以修改模板里的任何内容，包括Google的广告，这给那些懂Html和CSS的Blogger提供了很大的自由度。Blogger默认把用户的网志发布到免费提供的Blogspot.com主机上。可惜的是Blogspot.com从中国是无法访问。好在Blogger.com提供了一种很独特的服务，可以将博客的静态页面通过FTP发布到用户选择的服务器上。
通过FTP发布到其他主机
用户在Blogger.com上的默认Blog地址显然无法从国内访问，但是如果你有一个虚拟主机空间，或者其他支持FTP的空间，那么Blogger.com可以将这个地址上的日志文件全部发布到你的虚拟主机空间上去。
具体的方法是：登陆你的Blogger帐号，进入控制面板，更改设置，在"发布"选项卡中点击FTP的超级链接，然后录入FTP服务器地址，FTP用户名和密码。点保存设置后，就可以发布了，这时Blogger.com会将你的整个站发布到你指定的主机上。
至于这个FTP服务器，我推荐一个国内GFans提供的免费Blogger Spaces空间，支持FTP发布，最重要的是支持域名绑定，其服务器在广州，速度很快，希望大家不要滥用其服务。
通过电子邮件发布日志
在Blogger中写日志麻烦？告诉你一个技巧，你可以不登录Blogger网站，只要发送一封电子邮件就可以发表文章了。
具体的方法是：登陆你的Blogger帐号，进入控制面板，更改设置，在"电子邮件"中，在Mail-to-Blogger地址中可以自定义一个邮件地址，发送到此地址的邮件会自动张贴，BlogSend地址是另外一个电子邮件地址，只要一发布文章，系统会将其邮寄文章到此地址。
这里再介绍一个小技巧，就是在更新Blogger的同时也更新MSN Space。因为MSN Space也是支持邮件发布的，因此将Blogger发布后发送邮件的BlogSend地址修改为MSN Space的发布邮件地址，这样在Blogger上发布一篇文章后，系统就会自动将文章内容发送到Msn Spaces里，这样就同时更新了两个博客。
有一点值得注意的是，Blogger默认的编码是UTF-8编码，因此发送邮件的时候要将邮件编码设置为UTF-8的格式，建议登陆GMail发送邮件。一来GMail默认就是UTF-8格式的，编码全兼容，二来GMail支持自动保存功能，不怕电脑死机后丢失文章，三来GMail还可以自动备份发出去的文章，以免文章丢失。
使用第三方软件发布文章
Zoundry是一个第三方的日志发布软件，可以做到不用登陆Blogger即可发布日志，使用它来编辑和发布，速度和效率都非常理想。
添加Google Adsense广告
Google Blogger用户可以很快捷方便地申请加入Google Adsense广告服务。Google本身也推荐博客们使用Blogger的广告来为自己和Google赚钱。
Google工具栏的应用
Google工具栏有一个按钮是"发送到Blogger"，可以快速将当前网页发送到自己的Blogger空间上。
Google Picasa的应用
Picasa是Google的图像管理软件，在Picasa中点图片，再点"Blog This"，可以将选定图片发送到自己的Blogger空间上。
Blogger的申请地址是： http://www.blogger.com
In machine learning, understanding how one's model succeeds or fails for a particular dataset or sample is important to building better models. For Naive Bayes classifiers, a list of frequency counts and a confusion matrix is generally informative enough to understand what went wrong. For traditional decision trees, understanding how a sample traverses the tree is highly informative about which features caused a sample to be classified a particular way.
For GBDT models, since there are hundreds of decisions trees, we can not realistically expect a researcher to be able to look at all the decision trees and the individual path the sample traverses each tree. Our proposal is to work on visualizations of ensembles of GBDT for error analysis. Of particular focus will be generating a single representative tree from the ensemble and visualizations of the paths that a particular sample traverses and what features impacted the final results the most.
From:http://vis.berkeley.edu/courses/cs294-10-fa07/wiki/index.php/FP-Jerry_Ye_and_Jimmy_Chen
* Given Name: 名
* Surname: 姓
* Address1: 地址1
Address2: 地址2
Address3: 地址3（如果一行写不开，就在三行中分别写）
* City: 城市
State (US Only): 地区（不在美国就不用选）
Postal Code: 邮编
Province: 省
* Country: 国家
* Country to represent: 代表国家（不知道啥意思，中国人两个都填China就行）
* Timezone: 时区（选Asia/Chongqing）
Phone Number: 电话号码
* Email Address: 电子邮件
* Confirm Email Address: 确认电子邮件地址（就是把电子邮件地址重新打一遍）
Email Notifications: 邮件提醒（就是它给你发邮件提醒什么东西）
- Algorithm Competitions 算法比赛，就是SRM和TCOpen
- Software Development Opportunities 貌似就是有软件开发的项目就告诉你
- Employment Opportunities 工作机会
- TopCoder News & Events 新闻
* Enable Member Contact: 允许成员联系（似乎就是说是不是让别人在TC上能找到你）
* Show / hide earnings: 显示/隐藏收入（大概是说别人是不是能看到你赚了多少钱，TC的比赛可是有钱赚的）
* User Name: 用户名（下面的话提醒你一定不要填错，因为注册多个用户是不符合规定的。据说有人因为别人在TC客户端和他打招呼说“怎么你拿小号上了”，那个人的号就被封了）
* Password: 密码
* Confirm Password: 确认密码
* Secret Question: 密码找回问题（找回密码时需要回答这个问题，注意至少要8个字符长，而一个中文字似乎算一个字符，所以最后可能要打几个问号补齐长度）
* Secret Question Response: 密码找回问题答案
Quote: 座右铭，就是个签名档之类的东西
* Student/Professional: 学生/职业程序员
* = required 带*的项目必填
* Age : 年龄
* Gender : 性别（Male男，Female女）
* Ethnic Background : 民族背景（似乎选Asian or Pacific Islander就行吧……）
* Primary Interest in TopCoder : 在TC的主要兴趣，看不懂的就选第一个吧，那个是说你的兴趣在奖金……
* Shirt Size : T-Shirt大小（有的比赛会给排名前N的选手发T-Shirt，这里你需要选择适合自己的大小，如果选最后一个说明你不想要T-Shirt，人家也不发你了。TC的T-Shirt还是挺好看的，比AStar的好）
* College Major : 大学的专业
* College Major Description : 这个不知道啥意思，随便填点东西就行……
* Degree Program : 学位（从上到下分别为：准学士，学士，硕士，博士，中学生）
* Graduation Year : 毕业年份
* Graduation Month : 毕业月份
* Clubs / Organizations : 组织（一般选None，可以按住Ctrl点鼠标多选）
Other Clubs / Organizations : 其它组织
* School: 学校（点Choose School选择学校，可以搜索，不过为啥shanghaijiaotong university才2个人注册？！）
* Show / hide my school: 显示/隐藏我的学校
GPA: 不懂的自己百度去……
GPA Scale: 同上
Resume: 简历
* How did you hear about TopCoder?: 你怎么知道的TC，如果选了“Member Referral”的话，需要填写那个人在TC的用户名（欢迎填写sqybi~）
* = required
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
Let’s consider an infinite sequence A defined as follows:
A0 = 1;
Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)
You will be given n, p and q. Return the n-th element of A (index is 0-based).
Definition
Class:
InfiniteSequence
Method:
calc
Parameters:
long long, int, int
Returns:
long long
Method signature:
long long calc(long long n, int p, int q)
(be sure your method is public)
Notes
- [x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.
Constraints
- n will be between 0 and 10^12, inclusive.
- p and q will both be between 2 and 10^9, inclusive.
Examples
0)
0
2
3
Returns: 1
A[0] = 1.
1)
7
2
3
Returns: 7
A[0] = 1; A[1] = A[0] + A[0] = 2; A[2] = A[1] + A[0] = 2 + 1 = 3; A[3] = A[2] + A[1] = 3 + 2 = 5; A[7] = A[3] + A[2] = 5 + 3 = 8.
2)
10000000
3
3
Returns: 32768
3)
256
2
4
Returns: 89
4)
1
1000000
1000000
Returns: 2
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
#include <string>转自：http://sqybi.com/blog/archives/25
#include <vector>
class InfiniteSequence {
public:
long long calc(long long n, int p, int q) {
if (n == 0)
return 1;
else
return calc(n/p, p, q) + calc(n/q, p, q);
}
};
