博文
求最大公约数的算法。(2006-07-30 02:28: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:27:00)
摘要：template <typename T> void SelectionSort(T arr[],int n) { int smallIndex; //表中最小元素的下标 int pass,j; //用来扫描子表的下标 T temp; //用来交换表元素的临时变量 //pass的范围是0~n-2 for (pass=0;pass<n-1;pass++) { //从下标pass开始扫描子表 smallIndex=pass; //j遍历整个子表arr[pass+1]到arr[n-1] for(j=pass+1;j<n;j++) //如果找到更小的元素,则将该位置赋值给smallIndex if(arr[j]<arr[smallIndex]) smallIndex=j; //如果smallIndex和pass不在相同的位置 //则将子表中的最小项与arr[pass]交换 if(smallIndex!=pass) { temp=arr[pass]; arr[pass]=arr[smallIndex]; arr[smallIndex]=temp; } } } ......
小数转化成分数的两个算法(2006-07-30 02:26:00)
摘要：我自己的：#include <stdio.h>#define M 10000int main(){ int n,m,r; float f; printf("f="); scanf("%f",&f); n=(int)(f*M); //分子； m=M; //分母； printf("%f=%d/%d\n",f,n,M); r=m%n; //计算分子分母的最大公约数； while(r) { m=n; n=r; r=m%n; } r=n; n=(int)(f*M),n/=r; //分数化简； m=M/r; printf("%f=%d/%d\n\n",f,n,m); system("PAUSE"); return 0......
洗牌的一个算法 (2006-07-30 02:22:00)
摘要：#include<iostream>using namespace std;struct pukepai{ char d; //点 char s; //花色 }; char dian(int i) { switch(i) { case 0: return 'K'; case 1: return 'A'; case 11: return 'J'; case 12: return 'Q'; default: return i+48; }}void display(){ pukepai p[54]; int temp[54],tem,i,j; for(i=0;i<54;i++)temp[i]=i+1; srand(time(0)); for(i=0;i<54;i++) //洗牌 1---54的随机数 ......
一个圆周率的算法(2006-07-30 02:21:00)
摘要：#include <stdio.h> int a=10000, b, c=2800, d, e, f[2801], g; main() { for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b); return 0;} ......
旋转算法(2006-07-30 02:21:00)
摘要：1 2 3 412 13 14 511 16 15 610 9 8 7以上图形如何实现，算法？===========================================================================#include<iostream>#include<stdlib.h>using namespace std;int mask=4,m=1,i,j;void check(int mask){ switch (mask) { case 4:j++;break; //表示行,向右 case 3:i++;break; //列向下 case 2:j--;break; //行,向左 case 1:i--;break; //列向上 }}int main(int argc,char *argv[]){ int n; co......
把字符串转换为二进制再输出的算法(2006-07-30 02:20:00)
摘要：#include<iostream>using namespace std;string Str2Bin (char* str){int change,k=0,mask=8;char bit;char stack[100]={0};for (short i = 0; i <strlen(str); i++){ for(int j=0;j<4;j++) { stack[k++]=(mask&(str[i]-48))?49:48; mask>>=1; } mask=8; }return(stack);}int main(int argc,char *argv[]){ char str[8]="0123456"; cout<<"你输入的是:"<<str<<endl; cout<<"转换后是:"<<Str2Bin(str)<<endl; system("PAUSE"); return 0;} ......
通配符的一个算法.(2006-07-30 02:19:00)
摘要：#include <iostream>#include <cstdlib>#include <string>using namespace std;char dp_match( const char *str1, const char *str2){ int slen1 = strlen(str1); int slen2 = strlen(str2); char match[100][100]; memset(match, 0, 100*100); match[0][0] = 1; int i, j, k, m; for(i=1; i<=slen1; ++i) { for(j=1; j<=slen2; ++j) if(match[i-1][j-1]) if(str1[i-1]==str2[j-1] || str2[j-1]=='?') match[i][j]=1; ......
骑士周游算法(2006-07-30 02:19:00)
摘要：/*===================骑士周游算法--用链栈实现===================*/#include<stdio.h>#include <malloc.h>#define LEN sizeof(struct stack)struct stack{int row;int col;int dir;struct stack *next;struct stack *prior;};struct stack*head = (struct stack*)malloc(LEN);struct stack*q=head;void push(int i,int j,int v){struct stack *p=(struct stack*)malloc(LEN);p->row=i;p->col=j;p->dir=v;p->next=q;q=p;}void pop(){struct stack *temp;temp=q->prior;free(q);q=temp;}void start(){ int y,z,v=0;int i,j;int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};int c[6][6];for(i=0;i<6;i++){for(j=0;j<6;j++)c[j]=0;}printf("input y:");scanf("%d",&y);printf("input z:");scanf("%d",&z);int account=0;while(account<35){while(v<8){i=y+move[v][0];j=z+move[v][1];if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0){ push(y,z,v+1);account++;c[y][z]=account;y=i;z=j;v=0;}else v++;}if(v==8&&account>0&&account!=35){y=q->row;z=q->col;v=q-&g......
排列的生成算法之一：字典序法(2006-07-30 02:13:00)
摘要： 排列的生成算法之一：字典序法发信站: BBS 水木清华站 (Fri Apr 27 16:39:27 2001)有这么一道数学题： * * * ---- + ---- + ---- =1 ** ** ** *为1~9的数字，每个数字必须用且只能用一次。分母为两位数。 可以用排列的生成算法枚举所有的情况（当然，还有其他方法，但最好要优化）double a[10];int i=345126789,ii;//1,2显然不能是分子，设a[1]，a[2]，a[3]为分子且a[1]<a[2]<a[3]while(i<=789654321) { ii=i; for(int j=9;j>0;j--) { a[j]=ii%10; ii=ii/10; } if(a[1]<a[2]&&a[2]<a[3]) { if(fabs((a[1]/(a[4]*10+a[5])+a[2]/(a[6]*10+a[7])+a[3]/(a[8]*10+a[9]))-1)< 1e-6) cout<<a[1]<<"/"<<(a[4]*10+a[5])<<"+" <<a......