博文
[TOJ]1011阶乘末尾非零数求和(2005-06-05 15:27:00)
摘要：阶乘末尾非零数求和
Time Limit:1s Memory Limit:1000k
Total Submit:4730 Accepted:1336
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
对于小于25000的自然数n,求阶乘n!,(n-1)!,(n-2)!...3!,2!,1!右边的非零数之和。
例如：
当n=5时，
5!=120,右边非零数为2;
4!=24,右边非零数为4;
3!=6,右边非零数为6;
2!=2,右边非零数为2;
1!=1,右边非零数为1。
其右边的非零数之和为15。
Input
本题有多组数据，每组数据包含一个正整数N(N不大于25000)占一行。
Output
对给定的每组输入数据，输出一个整数。每个结果占一行。不要输出额外的空行。
Sample Input
5
10
1
Sample Output
15
39
1
#include<iostream.h>
int deal(int n,int &bn)
/*n为待处理的数，处理的结果是先去除尾部所有0，然后去掉2或5的因子
*bn返回因子2的个数减因子5的个数
*函数返回去掉这些因子的n
*/
{
while(n%10==0)n/=10;
if(!(n&1))
do{n>>=1;++bn;}
......
[2005-5-30]程序员考完啦！(2005-05-30 14:28:00)
摘要：昨天刚考完，
感觉像回到高中时代的最后那几天，
开考前，考生们把考场大楼围得水泄不通，
考生们比较复杂，因为从程序员到系统分析师，有些考试不一定是学生能够完成的，
没有仔细打量这些形色考生，
拿到卷子后，也顾不得太多了，埋头做吧，
上午题很容易，考的跟编程关系不大，考的是计算机基础知识，也就是纯记忆的东西啦，一个字概括，考的是知识的广度，
下午题也很容易，考的就是编程啦，C语言为主，前三道相对容易，主要也就是考知识的深度啦，专门对应于《数据结构》、《算法与C语言》，
第一道是流程图填空，考的是奇偶校验的计算方法，不明白的也没关系，因为题目有详细的说明文档，
第二题是求最大公约数，采用辗转相减法，
第三题是一道二叉树的题，求二叉树的右子树的最左结点，前三道都很容易，十几分钟搞定，
第四~五题选一道，第四题是C，剧院定票的一小程序，第五题是VB，具体没看，我做的第四题，看懂了程序之后也很容易填出来，
最后三道题是考面向对象的程序设计，选考Java,VB或C++，我选了最后一个C++的，求一个Date类的某月有多少天的程序，相对来说极其容易，了解一下this指针和一点皮毛的C++知识就可以搞定了，
这样看来取消初级程序员后，中级程序员确实降低了难度，相信很多人都能通过考试。
下一站：高程。......
贪心算法::启发式搜索(2005-05-23 12:12:00)
摘要：蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。
而更好的做法是运用“贪心策略”。
【贪心算法】
贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。
以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。
对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。
C++代码：在（VC6上调试通过）
#include "stdio.h"
class horse
{
public:
horse(int,int);
~horse();
void solve(int,int);
protected:
&nbs......
穷举搜索::回溯与深搜(2005-05-23 11:43:00)
摘要：计算机常用算法大致有两大类，一类叫蛮干算法，一类叫贪心算法，前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。
【建立解空间】
问题的解应该如何描述，如何建立？借助图论的思想，我们可以用图来描述，图的定义为G<V,E>，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。描述了解，那如何建立解空间，即如何对图进行搜索？
【深度优先搜索】
(Depth First Search)是用栈的机制对图的顶点进行深度优先的搜索。简易流程如下：
DFS(V0（起始顶点）)
访问V0
for(v=V0的第一个子结点 到 最后一个子结点（边所对的顶点））
如果v未被访问，DFS(v);
搜索过程是先往结点深处搜索，一旦有子结点未访问就向下遍历。这样的方法类似回溯算法，先往下试探，如果不行出退回（回溯）。
【回溯】
回溯的经典例子是8皇后问题。
例：在国际象棋地图上（8×8）放上8个皇后，使任意两个皇后都不在同一行或同一列或同一斜行，找出所有解。
每一个皇后的位置可以认为是一个顶点，而皇后之间不在同一行或同一列或同一斜行的性质认为是顶点之间的关系，我们可以用回溯试探的方法考虑：先依次试探每一个皇后的位置，如果有不满足条件的情况则退回，直到完成所有解的计数和输出。
用数组存储：int pos[8];
pos[0]表示第一个皇后的位置（0,1,...7)依次类推。
流程：
dfs(c)//c从0开始
for(v=0;v<8;++v)
如果pos[c]:=v满足条件，dfs(......
排序由浅入深（二）::交换排序(2005-05-22 19:38:00)
摘要：【交换排序】
是一种主要以交换的方式对序列进行排序的方法。
其实排序的基本方法或手段主要就是比较和交换，像选择法等都借助了交换的手段，但都不是主要以交换为手段，在直接选择排序的时候，一轮比较就能确定最大元素的位置，然后再进行交换，也就是说这样的交换是“稳定”的。
【冒泡排序法】
也叫起泡排序法，过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较，如果逆序则交换，作用只能使一个元素到达最终位置，而其它的交换是多余的，如果只进行比较而不交换的话，就跟直接选择排序法一样，不同的是，它是不稳定的。
void bubblesort(int n,list r)
{
for (i=1;i=n-1,i++)
{
flag=1;//标记是否有交换
for (j=1;j=n-1;j++)
if (r[j].key>r[j+1].key)
{
flag=0;
swap(r[j],r[j+1]);//交换相邻元素
}
if(flag)return;//如果一轮比较没有元素交换则说明整体有序，直接退出
}
}
【快速排序法】
也是一种交换排序法，实际上它是冒泡法的改进。
【算法】
思想是：一次划分使整个元素部分有序，即从序列中任选一个元素，然后对其它元素进行这样的划分，使得所有比它小（大）的元素在左侧而所有比它大（小）的元素在右侧，然后用分治的思想对左右侧的序列同样的处理，直到只有一个元素为止......
排序由浅入深（一）::选择排序(2005-05-22 18:56:00)
摘要：【选择排序】
的思想是依次从待排序数列中选择最大（小）的、第二大（小）的等等，然后依次重新排列为有序数列。
以某个关键字（key）选一个最大（小）的元素出来，可以看成是一场比赛，就像拳击比赛，如果你能从第一局打到最后一局，那你就是最强者，我们选出这个最强者的过程就是选择的过程，选出来之后，将它标记，然后再从剩下的选手中以同样的方法（分治）选出第二强的，依次下去，直到只剩一个选手（边界）为止。这就是选择排序的全部思想方法。
①直接打擂的方式：（直接选择排序法）
直接选择排序法的算法是这样的，首先选出前n个元素中的最小（大）者，如果这个最小（大）者不是第1个元素，则与第1个元素交换，然后以同样的方法对付后n-1个元素（分治），直到处理的元素只剩一个，即得到有序序列。它和冒泡排序法很类似，不同的是冒泡排序法进行了更多次的交换，而有些交换是不必要的，这使得冒泡排序法是不稳定的，而直接选择排序法是稳定的排序法。
②锦标赛的方法：（树型选择法）
玩过拳皇游戏的人就知道这种比赛方法，实际中的比赛可以不必要打这么多次，我们可以把n个选手分成n/2组，假定n=8，先分成4组，每组两人，两个人打一局，这样可以产生4个胜者，再将这4个人分2组，每组同样两人，各自再打一局，这样可以产生2个胜者，同样再做一次就能产生冠军。这样做的好处是强者可以只打几场就能坐上冠军的宝座，不像前一种方法，冠军要跟其它的人都打一场才能确定（当然，这是最糟的情况）。但是树型选择法最大的缺点是需要的存储空间要大，要建一个败者树，对n很大的情况不太理想。
③堆排序：
将前一种方法进一步改进，使得在O(1)的空间复杂度上就能完成的选择排序法，就是大名鼎鼎的“堆排序法”。堆是一个线性表，下标从1开始取，且满足：nk>=max{n2k,n2k+1}或者nk<=min{n2k,n2k+1}，前者称为大顶堆，后者称为小顶堆。这样看似乎不太明白，我们把堆转换成完全二叉树，它的特点就相当显然了。
【完全二叉树】
是这样一棵二叉树，我们以堆中的元素，从头取，先取1个，做为根，再取2个，做为它的左右子结点，再取4个做为下一层的子结点，依次下去就构成完全二叉树。它的前n-1层（n是它的总层数，称为......
分治的实现::递归程序设计(2005-05-23 21:33:00)
摘要：【分治算法】
是一种思想，你拿到的问题往往不会是很简单的事情，而再复杂再难的问题都可以分解成一些有限的简单问题的和，这就是分治法的原理。
举个最简单的例子，计算阶乘之和n!+(n-1)!+...+1!：
n可以取大取小，问题的范围可以大可以小，如果小就比较容易，比如1！=1这是己知，如何将大问题化成小问题，找它们之间的联系：
如果n=k已经解决，那么n=k+1能否解决，如何解决？
很显然：n=k+1的情况就是将n=k的结果加上(k+1)!的值。
【递归程序设计】
是一种算法常用设计方法，在高级语言中，函数之间可以进行嵌套调用，用栈的机制实现，这样的做法可以使我们在算法设计的时候能够达到套调算法设计。
int facsum(int n)
{
if(n==1)return 1;
return fac(n)+facsum(n-1);
}
/*fac()为求阶乘函数，facsum()为阶乘求和函数*/
“if(n==1)return 1;”为小问题、简单问题解的直接描述，在递归中称为递归边界，没有设定边界的递归是只能‘递’不能‘归’的，即死循环。
“return fac(n)+facsum(n-1);”中将n的范围缩小：n-1，以此将大问题化为类似的小问题，类似很重要，如果不类似就不能调同一个函数，这很显然。——这样一个过程就是分治算法的实现。
[阶乘求和可以用更高效率的算法求解，以上只是做为一个简单例子]
再举一例，将数组的元素逆置：
void inverse(int a[],int n)
{
if(__①__)return;
swap(a[0],a[n-1]);/*swap(a,b)为交换a,b的值*/
inverse(__②__);
}
①处为小问题解描述，也是递归边界，怎样的小问题是很显然的呢？当数组的元素个数小于2时是不需要逆置的，所以填：......
[2005-5-21]开个头吧(2005-05-21 20:16:00)
摘要：上周思想课才刚开课，
老师进教室跟我们认识一番后，说我们学的是心理学，
之前的认识是，心理医生、心理学家或者催眠大师是一些不正常的人，
之后的认识是，这个老师的确有一手，因为它会抓住我们听课的心理，因为虽然戴着高高的眼镜，却猜得到我们在赶第二天的高代作业，
心里在想什么被人猜透是件很尴尬的事，
老师很得意的样子，要我们每人拿出一张纸来，
然后写二十个“我是……”，
我想了很久……我是？！
……我是一个为了全世界软件技术的发展而不懈努力的人！（呵呵~~说大了一点，其实就是，我喜欢编程：P）......