博文
求最大公约数的两种算法(2006-07-30 03:09:00)
摘要：求最大公约数的两种算法 ________________________________________辗转相除法和移位相减法（Euclid & stein 算法）给出Stein算法如下： 1. 如果A=0，B是最大公约数，算法结束 2. 如果B=0，A是最大公约数，算法结束 3. 设置A1 = A、B1=B和C1 = 1 4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 5. 如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 6. 如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 8. n++，转4 //greatest common divisor//by heaton//2005/03/11#include <iostream>using namespace std;//交换a ，b的值 void swap(int& a1,int &b1){ int temp; temp=a1; a1=b1; b1=temp; } //辗转相除法 int gcd(int a,int b){ if(a < b)sw......
6 （农历的算法，这个是最花费我心力的～～）(2006-07-30 03:08:00)
摘要：void Lunar(){int n;printf("1.Inquire the corresponding lunar day of the day you input\n");printf("2.Inquire the corresponding solar day of the day you input\n");printf("3.Exit\n");printf("Please input right number of the option which you want to inqiure:");scanf("%d",&n);switch (n){case 1: solar_lunar(); break;case 2: lunar_solar(); break;case 3: screen(); break;default: printf("Error!Please input the right character!!!\n"); Lunar(); break;}}void solar_lunar(){ int year,month,day,gan,zhi,animal;char yn; Date *date; input(solar_lunar); if((y<1900)||(y>2100)) { &......
一个比较臃肿的电子表程序（欢迎提加好的算法和语法）(2006-07-30 03:05:00)
摘要：#include<stdio.h>#include<graphics.h>#include<math.h>#include<time.h>#include<conio.h>#define BB 3.1415926/180/*弧度*/#define R 200#define X 320#define Y 240main(){int gdriver=9,gmode=2;void draw();void ddraw();double x1,y1,x2,y2;int i;initgraph(&gdriver,&gmode,"");draw();/*画界面*/ddraw();/*处理秒、分、时针的转动*/getch();}void draw(){double x1,y1,x2,y2;int i;setbkcolor(1);setcolor(11);setlinestyle(0,0,3);circle(X,Y,R);setcolor(5);circle(X,Y,8);setcolor(5);setlinestyle(0,0,1);for(i=0;i<360;i=i+6){x1=X+(R-1.5)*cos(i*BB);y1=Y+(R-1.5)*sin(i*BB);if(i%90==0) {x2=X+(R-20)*cos(i*BB); y2=Y+(R-20)*sin(i*BB);}else if(i%30==0) {x2=X+(R-13)*cos(i*BB); y2=Y+(R-13)*sin(i*BB);}else {x2=X+(R-8)*cos(i*BB); y2=Y+(R-8)*sin(i*BB);}line(x1,y1,x2,y2);}}void ddraw(){struct tm *local;time_t t;double x2,y2;float sec1,sec2,min,hour,n;t=time(NULL);local=localtime(&t);printf(ctime(&t));sec1=local-......
遗传算法(2006-07-30 03:04:00)
摘要：遗传算法介绍遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中"物竞天择、适者生存"进化过程。1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础。 用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(Genetic Algorithm in Continuous Space, GACS)，暂不讨论。 一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行： (1) 对待解决问题进行编码； (2) 随机初始化群体X(0):=(x1, x2, … xn)； (3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好坏； (4) 应用选择算子产生中间代Xr(t)； (5) 对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想； (6) t:=t+1；如果不满足终止条件继续(3)。 GA中最常用的算子有如下几种： (1) 选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulette wheel)模型。 (2) 交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3) 变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。 GA的程序设计应考虑到通用性，而且......
贪心算法::启发式搜索(2006-07-30 03:02:00)
摘要：蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。而更好的做法是运用“贪心策略”。【贪心算法】贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。C++代码：在（VC6上调试通过）#include "stdio.h"class horse{public: horse(int,int); ~horse(); void solve(int,int);protected: void dfs(int,int,int); int **data; int *head; &nbs......
QQ 加密算法(2006-07-30 03:01:00)
摘要：QQ 加密算法 QQ使用的加密算法来源于一种称为TEA（Tiny Encryption Algorithm）加密算法。它是在1994年由英国剑桥大学的David Wheeler和Roger Needham所发明的一种加密方法。大概来说，它是使用128bit密钥加密64bit数据产生64bit输出的一种算法。这种算法的可靠性是通过加密轮数而不是算法的复杂度来保证的。具体的算法可以参考：http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html。实现可以参考：http://abcn.net/crypto.htm。QQ使用16轮的加密（这是最低限，推荐应该是32轮）。QQ在使用这个算法的时候，由于需要加密不定长的数据，所以使用了一些常规的填充办法和交织算法（也就是说，把前一组的加密结果和后一组的进行运算，产生新的结果）。具体的填充算法是：原始字符串加上8个字节再加上填充字符数应该是8的倍数（至少填充2个字节）。填充后的字符串是这样组织的。第一个字节，为填充字符数减2 OR 上0xA8。后面是填充字节。然后是待加密的数据，最后是7个0。填充的字节一般是0xAD，但再0A1dD版本中，会使用随机的填充字符串。一般，我们会用解密后最后是否7个零来判断是否正确的解密。......
公历历法::星期算法(2006-07-30 02:57:00)
摘要：原创]【引】《创世纪》创世在宇宙天地尚未形成之前，黑暗笼罩着无边无际的空虚混饨，上帝那孕育着生命的灵运行其中，投入其中，施造化之工，展成就之初，使世界确立，使万物齐备。上帝用七天创造了天地万物。这创造的奇妙与神秘非形之笔墨所能写尽，非诉诸言语所能话透。第一日，上帝说：“要有光！”便有了光。上帝将光与暗分开，称光为昼，称暗为夜。于是有了晚上，有了早晨。第二日，上帝说：“诸水之向要有空气隔开。”上帝便造了空气，称它为天。……第七日，天地万物都造齐了，上帝完成了创世之功。在这一天里，他歇息了，并赐福给第七天，圣化那一天为特别的日子，因为他在那一天完成了创造，歇工休息。就这样星期日也成为人类休息的日子。“造化钟神秀，阴阳割分晓。”上帝就是这样开辟鸿蒙，创造宇宙万物的。以上来自《圣经》，现在还有一些基督教徒每个礼拜天去教堂朝拜，可见一个星期七天就源于此，这正是我讨论的中心，如何计算哪年哪月哪日是星期几。【公历历法】公历历法很简单，年有润年（LeapYear）和平年之分，平年每月天数恒为：月份 一 二 三 四 五 六 七 八 九 十 十一 十二天数 31 28 31 30 31 30 31 31 30 31 30 31共365天。润年366天，二月多一天，29天。【润年判断】如果年份数能被4整除但不能被100整除或者能被400整除者，为润年。【400年刚好一个轮回】很容易想到每400年内的润年数相等，即刚好一个轮回，400年有多少个润年？被4整除的有100个，被100整除的有4个，被400整除的只有1个，所以一共有100-4+1=97个润年，所以400年共有(365*400+97)天，即146097天，除7余0！也就是说2001年1月1日的星期数与1年1月1日的星期数相同，翻出日历一看，星期一，我不知道上帝什么时候造的人，或许是1年1月1日。这样一来，任何一个日期我们都可以把它折算到0~399年之内的日期来算，0年的说法不准确，或许没有，但不影响这个数学结论，我们只是借它来推一推而已。【起初的400年】如果每一年都是平年，即365天，除7余1，也就是说如果不遇上润年，每往下一年就会使星期数增一。同样的道理，如果遇上润年，则多增一。我们要算的也就是把润年数算出来就行了，很容易，如果是y年（0<=y<400），则遇......
阴阳历算法(2006-07-30 02:49:00)
摘要：阴阳历算法________________________________________程序为： /* 西历农历转换程式 黄晓鸣 1995,7,25 prototype: int calconv( struct convdate * ); struct convdate { int source; ==0 则输入日期为西历, !=0 则输入为农历 int solaryear; 输出或输入之西历年份 int solarmonth; 西历月 int solardate; 西历日 int lunaryear; 输出或输入之农历年份 int lunarmonth; 农历月 int lunardate; 农历日 int weekday; 该日为星期几 ( 0==星期日, 1==星期一, ... ) int kan; 该日天干 ( 0==甲, 1==乙, ..., 9==癸 ) int chih; 该日地支 ( 0==子, 1==丑, ..., 11==亥 ) }; 呼叫时须设定 souce 的值, 若为 0 则为西历转农历, 否则为农历转西历. 然後视 输入为西历或农历来设定西历或农历的年月日. 转换後的年月日会填入结构中( 农 历或西历 ), 以及该日为星期几, 天干地支. 若函式的返回值为 0 表示没有错误, 1 为输入之年份错误, 2 为输入之月份错误, 3 为输入之日期错误. 输入之西历年须在 1937 - 2031 间 输入之农历年须在 1936 - 2030 间 若须扩充, 则增加 lunarcal[] */ #define firstyear 1936 /* the first year in lunarcal[] */ struct convdate { int source; int solaryear; int solarmonth; int solardate; int lunaryear; int lunarmonth; int lunardate; int weekday; int kan; int chih; }; struct taglunarcal { int basedays; /* 到西历 1 月 1 日到农历正月初一的累积日数 */ int intercalation; /* 闰月月份. 0==此年没有闰月 */ int basewee......
求最大公约数的算法。(2006-07-30 02:48:00)
摘要：1、欧几里德算法和扩展欧几里德算法 欧几里德算法 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为： void swap(int & a, int & b) { int c = a; a = b; b = c; } int gcd(int a,int b) { if(0 == a ) { return b; } if( 0 == b) { return a; } &......
计算名次算法(2006-07-30 02:48:00)
摘要：看到一个模板函数,用来计算名次,真是奇妙!!template <class T>void Ran (T a[], int n, int r[]){// 计算a[0;n-1]中n个元素的名次 for (int i = 1; i<n; i++) r[i] = 0;//初使化 //逐对比较所有元素 for ( int i = 1; i < n; i++) for ( int j = 1; j < i; j++) if (a[i] <= a[i]) r[i]++; else r[j]++;}//计算后的名次放入r[]中......