博文
统计数字问题(2009-09-20 19:35:00)
摘要：/*****************************************************************************算法实现题1-1 统计数字问题问题描述： 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。编程任务： 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。参考网页：http://blog.csdn.net/jcwKyl/archive/2008/10/02/3009244.aspx********************************************************************************/#include <iostream>#include <vector>#include <cmath>#include <iterator>using namespace std;int pow(unsigned int idx);int main(){ int n; //从1开始编码到n,1<<n<<pow(10,9) int m; //m是个几位数,1<<m<<10 std::vector<int> stat_res(10,0);&......
动态规划0-1背包问题(2009-08-01 17:41:00)
摘要：#include<iostream>using namespace std;
//显然定义为全局变量不好
const int item=3;//物品数量const int max_wgt=10;//背包最大容量int c[item+1][max_wgt+1];//从1…i…item物品中,背包剩余空间为0<=j<=max_wgt的最大价值
int w[item+1]={0,3,4,5};//物品质量 int vl[item+1]={0,4,5,6}; //物品价值
int knapbag(){ for (int i=0;i<=item;i++)//初始化 { for (int j=0;j<=max_wgt;j++) { c[i][j]=0; } } //c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)} for (int i=1;i<=item;i++) { for (int j=1;j<=max_wgt;j++) { if (w[i]<=j) { if (vl[i]+c[i-1][j-w[i]]>c[i-1][j]) ......
回溯法N皇后(2009-07-24 15:37:00)
摘要：#include <iostream.h>#include <math.h>//x[i] represent to Queen i place in row i group x[i]void backtrack(int t);int const n=4;//the number of queenint x[n+1]; // the solutionint sum=0; //teh number of the solution
int nQueen(){ for(int i=0;i<=n;i++) x[i]=0; backtrack(1); return sum;}
bool placesafe(int k){ for(int j=1;j<k;j++) if( abs(k-j)==abs(x[j]-x[k]) || (x[j]==x[k]) )//the slope is 1 or -1,or in the same group return false; return true;}
void backtrack(int t){ if(t>n) { sum++; for(int j=1;j<=n;j++) { cout<<j<<","<<x[j]<<"#"; } cout<<endl; } else for( int i=1;i<=n;i++) { x[t]=i; if( placesafe(t) ) backtrack(t+1); }}
int main(){&......
main参数(2008-11-05 09:24:00)
摘要：main参数
C语言中的main函数,一般会带有2个参数,例如int main ( int argc, char* argv[]),这是一个典型的main函数的声明。这是为了在执行程序时需要向程序传递参数,参数argc代表了输入参数的个数,char *argv[]表示传入的参数的字符串,是一个字符串数组。例如在Unix平台下编写一个小程序:int main(int argc, char* argv[]){ int i; printf("test main parameter\n"); printf("argc:%d\n", argc); for(i=0;i<argc;i++) { printf("argv[%d]:%s\n", i, argv[i]); } exit(0);}
用cc编译后形成一个a.out*的可执行的文件,运行a.out,其结果是argc=1,argv[0]="a.out",运行的程序的文件名,也占用一个参数位置,也就是说argv数组中的第一个单元指向的字符串总是可执行程序的名字,以后的单元指向的字符串依次是程序调用时的参数。这个赋值过程时操作系统完成的,我们只需要拿来用就可以了。
main()主函数 每一C 程序都必须有一main()函数, 可以根据自己的爱好把它放在程序的某 个地方。有些程序员把它放在最前面, 而另一些程序员把它放在最后面, 无论放 在哪个地方, 以下几点说明都是适合的。 1. main() 参数 在Turbo C2.0启动过程中, 传递main()函数三个参数: argc, argv和env。 * argc: 整数, 为传给main()的命令行参数个数。 * argv: 字符串数组。 在DOS 3.X 版本中, argv[0] 为程序运行的全路径名; 对DOS 3.0 &......
堆排序和选择排序的效率对比的程序(2006-10-24 12:26:00)
摘要：#include <stdlib.h>#include <stdio.h>#include <dos.h>const int MAXSIZE = 20000;const int N = 5;int Data[MAXSIZE];void Print(){ int i; for (i = 0; i < MAXSIZE; i++) printf ("%d ", Data[i]);}void Create(){ int i; randomize(); for (i = 0; i < MAXSIZE; i++) Data[i] = random(1000); printf("\n");}void Swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;}void PushDown_MinHeap(int first, int last){ long i, j, x; i = first; j = i * 2; x = Data[i]......
2进制的高精度加,减和乘法的C++程序(2006-10-24 12:24:00)
摘要：#include <iostream.h>#include <mem.h>const int MAXSIZE = 20; //max length of the numberconst int K = 2; //baniry system 在这里可以修改K进制的高精度class hp{ int len; //length of number int s[MAXSIZE]; //store high precistion number public: hp(); hp hp::operator = (hp C);};hp::hp(){ len = 0; memset(s, 0, MAXSIZE*sizeof(int));}istream &operator >> (istream &in, hp &HP){ char s[MAXSIZE]; int i; ......
二路插入排序 (2006-08-20 12:05:00)
摘要：#include <stdio.h>#include <stddef.h>#define ARR_SIZE 10/* 函数原型 */void bidir_insert( int keys[], int temp[], const size_t i );int main(void){ size_t i; int keys[ARR_SIZE] = { 1050, 100, 150, 20, 9000, 5110, 3008, 1450, 5220, 500 }; int temp[ARR_SIZE]; /* 辅助数组 */ /* 进行二路插入排序 */ bidir_insert(keys, temp, ARR_SIZE); /* 输出排序结果 */ for ( i = 0; i < ARR_SIZE; ++i ) { printf("%d ", keys[i]); } printf("\......
高斯分布随机数源代码(2006-08-20 12:03:00)
摘要：#include <stdlib.h>#include <math.h>double gaussrand(){ static double V1, V2, S; static int phase = 0; double X; if ( phase == 0 ) { do { double U1 = (double)rand() / RAND_MAX; double U2 = (double)rand() / RAND_MAX; V1 = 2 * U1 - 1; V2 = 2 * U2 - 1; &nb......
残缺棋盘（defective chessboard）(2006-08-16 08:58:00)
摘要：残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图1 4 - 4所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为( 22k -1 ) / 3。可以验证( 22k -1 ) / 3是一个整数。k 为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k= 1时，正好存在3个非残缺的方格，并且这三个方格可用图1 4 - 4中的某一方向的三格板来覆盖。用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k 残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k×2k 棋盘一个很自然的划分方法就是将它划分为如图1 4 - 5 a所示的4个2k - 1×2k - 1 棋盘。注意到当完成这种划分后， 4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k 棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k - 1×2k - 1 残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图14-5b 所示，其中原2k×2k 棋盘中的残缺方格落入左上角的2k - 1×2k - 1&nb......
1000以内的阶乘(2006-08-14 17:16:00)
摘要：#include<stdio.h> # include <stdlib.h> // 计算 # define N 1000 int cal(unsigned int *s,int n) { unsigned long p; // p是对每一位乘法中的值加上进位，如34*5,4*5是20,3*5的加上进位2是17 unsigned long k=0; // k是一次乘法中的进位，如10进制乘法中，34*5,4*5的进位是2,3*5的进位是1 int i; static int m=1; // m是位数，表示s有总共有多少位数字，注意：是1000进制 static int b=0; /* b用来记录后面的0，比如213,000,000,000，则b=3,后面的3个000不必再参与计算了 */ // for(i=b;i<m;i++) { p=(long)s[i]*(long)n+k; k=p/N; s[i]=p-k*N; } // b是低位乘出来的000的数目,增加后加1 while(!s[b]) b++; // 最高位的进位处理 for(k=p/N;k;) { p=k; k=p/N; s[i++]=p-k*N; m++; // 进一次m加一次 } return m; } int main(int argc,char**argv) { /* s是用来存计算结果的，以N为进位，这里N=1000，如s[0]=1,s[1]=21,s[2]=213,s[3]以上都为0，&nb......